數(shù)據(jù)結(jié)構(gòu)自考題-7

1、數(shù)據(jù)結(jié)構(gòu)自考題 -7( 總分： 115.00 ，做題時間： 90 分鐘 )一、單項選擇題 ( 總題數(shù)： 15，分數(shù)： 30.00)1. 已知一采用開放地址法解決 Hash 表沖突，要從此 Hash 表中刪除一個記錄，正確的做法是( )A. 將該元素所在的存儲單元清空B. 將該元素用一個特殊的元素替代C. 將與該元素有相同 Hash地址的后繼元素順次前移一個位置D. 用與該無素有相同 Hash地址的最后插入表中的元素替代(分數(shù)： 2.00 )A.B. VC.D.解析：2. 在任意一棵二叉樹的前序序列和后序序列中，各葉子之間的相對次序關(guān)系( )A. 不一定相同B 都相同C 都不相同D 互為逆序分數(shù)

2、： 2.00 )A.B. VC.D.解析：3. 對于一棵具有三個結(jié)點的二叉樹，共有 ( ) 種不同的樹的形態(tài)。A. 4 B. 5 C. 6 D. 7分數(shù)： 2.00 )A.B. VC.D.解析：4. 棧一般情況下常采用以下兩種存儲方式 ( )A. 順序結(jié)構(gòu)和散列結(jié)構(gòu)B 散列結(jié)構(gòu)和鏈式結(jié)構(gòu)C.線性結(jié)構(gòu)和非線性結(jié)構(gòu)D 順序存儲結(jié)構(gòu)和鏈式結(jié)構(gòu)(分數(shù)： 2.00 )A.B.C.D. V解析：5. 考慮下列四種排序方法，在排序過程中，關(guān)鍵碼比較的次數(shù)與記錄的初始排列順序無關(guān)的是( )A. 直接插入排序和快速排序B 快速排序和歸并排序C.直接選擇排序和歸并排序D 直接插入排序和歸并排序(分數(shù)： 2.00

3、)A.B.C. VD.解析：6. 通常要求同一邏輯結(jié)構(gòu)中的所有數(shù)據(jù)元素具有相同的特性，這意味著 ( )A. 數(shù)據(jù)元素具有同一特點B. 不僅數(shù)據(jù)元素所包含的數(shù)據(jù)項的個數(shù)要相同，而且對應(yīng)數(shù)據(jù)項的類型要一致C. 每個數(shù)據(jù)元素都一樣D. 數(shù)據(jù)元素所包含的數(shù)據(jù)項的個數(shù)要相等(分數(shù)： 2.00 )A.B. VC.D.解析：7. 下列說法中正確的是 ( )A. 任何一棵二叉樹中至少有一個結(jié)點的度為2B. 任何一棵二叉樹中的每個結(jié)點的度為2C. 任何一棵二叉樹中的度肯定等于2D. 任何一棵二叉樹中的度可以小于2（分數(shù)： 2.00 ）A.B.C.D. V解析：8. 若進棧序列為 1,2,3,4,5,6 ，且進棧

4、和出?？梢源┎暹M行，則可能出現(xiàn)的出棧序列為 （ ）A. 3,2,6,1,4,5 B . 3,4,2,1,6,5 C . 1,2,5,3,4,6 D . 5,6,4,2,3,1（分數(shù)： 2.00 ）A.B. VC.D.解析：9. 設(shè)串 s1="Data Structures 、with Java" ， s2="it" ，則子串定位函數(shù) index（s1 ， s2） 的值為 （ ）A. 15 B . 16 C . 17 D . 18（分數(shù)： 2.00 ）A.B.B. VD.解析：10. 在一個具有N個頂點的無向完全圖中，包含的邊的總數(shù)是（）AN（N-1）/2

5、 B N（N-1） C N（N+1） DN（N+1）/2（分數(shù)： 2.00 ）A. VB.C.D.解析：11. 二維數(shù)組 Mi,j 的元素是 4個字符（每個字符占一個存儲單元 ）組成的串， 行下標 i 的范圍從 0到4，列 下標j的范圍從0到5。M按行存儲時元素 M3,5的起始地址與 M按列存儲時元素（）的起始地址相同。AM2,4 B M3,4 C M3,5 D M4,4（分數(shù)： 2.00 ）A.B. VC.D.解析：12. 按值可否分解，數(shù)據(jù)類型通常可分為兩類，它們是 （ ）A.靜態(tài)類型和動態(tài)類型 B 原子類型和表類型C.原子類型和結(jié)構(gòu)類型 D 數(shù)組類型和指針類型（分數(shù)： 2.00 ）A.B

6、.C. VD.解析： 解析 按“值”是否可分解，可將數(shù)據(jù)類型劃分為兩類：原子類型，其值不可分解；結(jié)構(gòu)類型，其 值可分解為若干個成分。13. 如果我們采用二分查找法查找一個長度為n的有序表，則查找每個元素的平均比較次數(shù)（）對應(yīng)的判定樹的高度（假設(shè)樹高h>2）。A.大于B .小于C 等于D .無法確定分數(shù)： 2.00 ）A.B. VC.D.解析：14. 若采用孩子兄弟鏈表作為樹的存儲結(jié)構(gòu)，則樹的后序遍歷應(yīng)采用二叉樹的（ ）A.層次遍歷算法 B 前序遍歷算法 C 中序遍歷算法D 后序遍歷算法分數(shù)： 2.00 )A.B.C. VD.解析：15.指針p、q和r依次指向某循環(huán)鏈表中三個相鄰的結(jié)點，交

7、換結(jié)點*q和結(jié)點*r在表中次序的程序段是（）A.p> next=r; q> next=r > next; r > next=q;B.p> next=r; r> next=q; q> next=r> next;C.r> next=q; q> next=r > next; p > next=r;D.r> next=q; p> next=r; q> next=r> next;（分數(shù)： 2.00 ）A. VB.C.D.解析：二、填空題 （總題數(shù)： 10，分數(shù)： 20.00）。按外設(shè)的觀點所確定的基本存儲單元

8、稱16. 就文件而言， 按用戶的觀點所確定的基本存儲單元稱為 為。（分數(shù)： 2.00 ）填空項 1: （正確答案：邏輯記錄 物理記錄）解析：17. 在一般情況下用直接插入排序、選擇排序和冒泡排序的過程中，所需記錄交換次數(shù)最少的是1（分數(shù)： 2.00 ）填空項 1: （正確答案：選擇排序）解析：18. 多維數(shù)組和廣義表是一種非常復(fù)雜的非線性結(jié)構(gòu)，它們的邏輯特點是 1（分數(shù)： 2.00 ）填空項 1: （正確答案：一個數(shù)據(jù)元素可能有多個直接前趨和多個直接后繼）解析：19. 設(shè)s="l AM A ATHLETE" , t="GOOD",則執(zhí)行下列串操作序列之后

9、得到的suhl為。substr（sub1,s,5,2）;substr（sub2,s,6,8）;strcpy（t1,t）;strcat,（t1,sub2）;strcat（sub1,t1）;（分數(shù):2.00 ）填空項1: （正確答案："A GOOD ATHLETE）解析：20. 從一個順序存儲的循環(huán)隊列中刪除一個元素時，應(yīng)該1。（分數(shù):2.00）填空項1： （正確答案：先移動隊首指針，后取岀元素）解析：21. 設(shè)二維數(shù)組A10 20,5 10按行優(yōu)先存儲，每個元素占4個存儲單元，A10,5的存儲地址是1000，則A15,10的存儲地址是 1。（分數(shù)：2.00 ）填空項1: （正確答案：1

10、700）解析：22. 從樹的根結(jié)點到樹中的其余結(jié)點之間的路徑1惟一的（分數(shù)：2.00 ）填空項1： （正確答案：是）解析：23. 如圖所示的有向圖中含有 個強連通分量（分數(shù)：2.00 ）填空項1： （正確答案：2）解析：24. 假設(shè)以列優(yōu)先順序存儲二維數(shù)組A58，其中元素A00的存儲地址為LOC®），且每個元素占4個存儲單元，則數(shù)組元素Aij的存儲地址為1。（分數(shù)：2.00 ）填空項 1: （正確答案：LOC（st0）+4（5j+i）解析：25. 存儲在直接存儲器上的順序文件可以用順序查找法存取，也可以用 和進行查找（分數(shù)：2.00 ）填空項1: （正確答案：二分查找法分塊查找）解析

11、：三、解答題（總題數(shù)：3,分數(shù)：20.00）26. 某廣義表的表頭和表尾均為（a,（b,c），畫出該廣義表的圖形表示（分數(shù)：5.00 ）正確答案：（解析: 已知有向圖G的定義如下:G=(V,E)V=a,b,c,d,eE=< a,b >,< a,c >,< b,c >,< b,d >,< c,d >,< e,c >,< e,d >)(1) 畫出G的圖形；(2) 寫岀G的全部拓撲序列。(分數(shù)：10.00 )解析: 正確答案：（a,b,e,c,da,e,b,c,de,a,b,c,d）解析：，如果我們采用直接選擇排序方

12、法對此序27. 已知有一關(guān)鍵字序列為97,86,53,108,72,34,215,146,11,68列進行排序（按照升序排列），請給岀每一趟的排序結(jié)果。（分數(shù)：5.00 ）正確答案：（直接選擇排序的過程為：從第i趟開始時，當(dāng)前的有序區(qū)和無序區(qū)分別為R1i和R1n（1 < -1<n-1），則在該趟排序是從當(dāng)前無序區(qū)中選出關(guān)鍵字最小的記錄RK，將它與無序區(qū)中的第1個記錄Ri交換，使R1i和Ri+1n分別變成新的有序區(qū)和新的無序區(qū)，每次排序都使有序區(qū) 增加一個記錄，無序區(qū)減少一個記錄，按照以上規(guī)則，我們得到各趟結(jié)果如下：初始：97,86,53,108,72,34,215,232,11,6

13、8第 1 趟：1186,53,108,72,34,215,232,97,68第 2 趟：11,3453,108,72,86,215,232,97,68第 3 趟：11,34,531108,72,86,215,232,97,68第 4 趟：11,34,53,6872,86,215,232,97,108第 5 趟：11,34,53,68,7286,215,232,97,108第 6 趟：11,34,53,68,72,86215,232,97,108第 7 趟：11,34,53,68,72,86,97232,215,108第 8 趟：11,34,53,68,72,86,97,108215,232第

14、9 趟：11,34,53,68,72,86,97,108,215,232）解析：四、算法閱讀題（總題數(shù)：3,分數(shù)：25.00）28. 求下面算法中變量count的值：（假設(shè)n為2的乘冪，并且n >2）int Timeint ncount=0;x=2;while(x < n/2) x*=2;count+;return(count)（分數(shù)：5.00 ） 正確答案：(count=log 2n)解析：29. 簡述一下算法的功能：status A (1inkedlist L)/L是無表頭結(jié)點的單鏈表if (L&&L > next) Q=L;L=L> next;P=

15、L;while(P > next)P=P > next; P> next=Q;Q > next=NULL;return ok;)/A（分數(shù)：5.00 ）正確答案：（本程序?qū)崿F(xiàn)的功能就是：如果L的長度不小于2,則將首元結(jié)點刪去并插入到表尾。）解析：二叉排序樹的存儲結(jié)構(gòu)定義為以下類型：typedef int KeyType;typedef struct nodeKeyType key; /*關(guān)鍵字項 */InfoType otherinfo; /*其它數(shù)據(jù)項 */struet node*lchild,*rchild; /*左、右孩子指針 */BSTNode,*BSTree;

16、閱讀算法f33，并回答問題：(1)對如圖所示的二叉排序樹T,寫出f33(T,8)返回的指針所指結(jié)點的關(guān)鍵字;在哪些情況下算法f33返回空指針？簡述算法f33的功能。BSTNode*f33(BSTree T,KeyType x)BSTNode*P; if(T=NULL)return NULL;p=f33(T > lehild,x);if(p!=NULL)return p;if(T > key > x)return T;return f33(T> rchild,x);(分數(shù)：15.00 )正確答案： （10）解析： 正確答案：仃是空樹或T中所有結(jié)點的關(guān)鍵字均不大于給定值 X

17、時，返回空指針。） 解析：正確答案：（如果二叉排序樹T中存在含有關(guān)鍵字大于給定值X的結(jié)點，則返回指針指向它們中關(guān)鍵字最小的結(jié)點，否則返回空指針。 ）解析：五、算法設(shè)計題 （ 總題數(shù)： 1，分數(shù)： 20.00） 假設(shè)以帶雙親指針的二叉鏈表作為 - 二叉樹的存儲結(jié)構(gòu)，其結(jié)點結(jié)構(gòu)的類型說明如下所示： typedef char DataType;typedef struct nodeDataType data;struct node*lchild,*rchild; /左右孩子指針struct node*parent; / 指向雙親的指針BinTNode;typedef BinTNode*BinTree;若px為指向非空二叉樹中某個結(jié)點的指針，可借助該結(jié)構(gòu)求得px所指結(jié)點在二叉樹的中序序列中的后繼。（分數(shù)： 20.00 ）（1）. 就后繼的不同情況，簡要敘述實現(xiàn)求后繼操作的方法；（分數(shù)：10.00 ） 正確答案： （ 分兩種情況討論 當(dāng)*px的右子樹不為空時，則從*px的右孩子開始，沿其左孩子往下查找，直至找到一個沒有左孩子的結(jié) 點為止，則該結(jié)點為 *pX 在中序序列中的后繼； 當(dāng) *px 的右子樹為空時，則沿 *px 的雙親指針鏈向上查找，直至找到其左子樹中包含 *px 的最年輕祖先， 則該祖先結(jié)點為 *px 在中序序列中的后繼。 ）解析：（2）. 編寫算法求 px 所指結(jié)點的中序序列