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

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

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

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

4、和出?？梢源┎暹M(jìn)行，則可能出現(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（分?jǐn)?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（分?jǐn)?shù)： 2.00 ）A.B.B. VD.解析：10. 在一個(gè)具有N個(gè)頂點(diǎn)的無(wú)向完全圖中，包含的邊的總數(shù)是（）AN（N-1）/2

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

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

7、換結(jié)點(diǎn)*q和結(jié)點(diǎn)*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;（分?jǐn)?shù)： 2.00 ）A. VB.C.D.解析：二、填空題 （總題數(shù)： 10，分?jǐn)?shù)： 20.00）。按外設(shè)的觀(guān)點(diǎn)所確定的基本存儲(chǔ)單元

8、稱(chēng)16. 就文件而言， 按用戶(hù)的觀(guān)點(diǎn)所確定的基本存儲(chǔ)單元稱(chēng)為 為。（分?jǐn)?shù)： 2.00 ）填空項(xiàng) 1: （正確答案：邏輯記錄 物理記錄）解析：17. 在一般情況下用直接插入排序、選擇排序和冒泡排序的過(guò)程中，所需記錄交換次數(shù)最少的是1（分?jǐn)?shù)： 2.00 ）填空項(xiàng) 1: （正確答案：選擇排序）解析：18. 多維數(shù)組和廣義表是一種非常復(fù)雜的非線(xiàn)性結(jié)構(gòu)，它們的邏輯特點(diǎn)是 1（分?jǐn)?shù)： 2.00 ）填空項(xiàng) 1: （正確答案：一個(gè)數(shù)據(jù)元素可能有多個(gè)直接前趨和多個(gè)直接后繼）解析：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）;（分?jǐn)?shù):2.00 ）填空項(xiàng)1: （正確答案："A GOOD ATHLETE）解析：20. 從一個(gè)順序存儲(chǔ)的循環(huán)隊(duì)列中刪除一個(gè)元素時(shí)，應(yīng)該1。（分?jǐn)?shù):2.00）填空項(xiàng)1： （正確答案：先移動(dòng)隊(duì)首指針，后取岀元素）解析：21. 設(shè)二維數(shù)組A10 20,5 10按行優(yōu)先存儲(chǔ)，每個(gè)元素占4個(gè)存儲(chǔ)單元，A10,5的存儲(chǔ)地址是1000，則A15,10的存儲(chǔ)地址是 1。（分?jǐn)?shù)：2.00 ）填空項(xiàng)1: （正確答案：1

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

11、：三、解答題（總題數(shù)：3,分?jǐn)?shù)：20.00）26. 某廣義表的表頭和表尾均為（a,（b,c），畫(huà)出該廣義表的圖形表示（分?jǐn)?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) 畫(huà)出G的圖形；(2) 寫(xiě)岀G的全部拓?fù)湫蛄小?分?jǐn)?shù)：10.00 )解析: 正確答案：（a,b,e,c,da,e,b,c,de,a,b,c,d）解析：，如果我們采用直接選擇排序方

12、法對(duì)此序27. 已知有一關(guān)鍵字序列為97,86,53,108,72,34,215,146,11,68列進(jìn)行排序（按照升序排列），請(qǐng)給岀每一趟的排序結(jié)果。（分?jǐn)?shù)：5.00 ）正確答案：（直接選擇排序的過(guò)程為：從第i趟開(kāi)始時(shí)，當(dāng)前的有序區(qū)和無(wú)序區(qū)分別為R1i和R1n（1 < -1<n-1），則在該趟排序是從當(dāng)前無(wú)序區(qū)中選出關(guān)鍵字最小的記錄RK，將它與無(wú)序區(qū)中的第1個(gè)記錄Ri交換，使R1i和Ri+1n分別變成新的有序區(qū)和新的無(wú)序區(qū)，每次排序都使有序區(qū) 增加一個(gè)記錄，無(wú)序區(qū)減少一個(gè)記錄，按照以上規(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,分?jǐn)?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)（分?jǐn)?shù)：5.00 ） 正確答案：(count=log 2n)解析：29. 簡(jiǎn)述一下算法的功能：status A (1inkedlist L)/L是無(wú)表頭結(jié)點(diǎn)的單鏈表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（分?jǐn)?shù)：5.00 ）正確答案：（本程序?qū)崿F(xiàn)的功能就是：如果L的長(zhǎng)度不小于2,則將首元結(jié)點(diǎn)刪去并插入到表尾。）解析：二叉排序樹(shù)的存儲(chǔ)結(jié)構(gòu)定義為以下類(lèi)型：typedef int KeyType;typedef struct nodeKeyType key; /*關(guān)鍵字項(xiàng) */InfoType otherinfo; /*其它數(shù)據(jù)項(xiàng) */struet node*lchild,*rchild; /*左、右孩子指針 */BSTNode,*BSTree;

16、閱讀算法f33，并回答問(wèn)題：(1)對(duì)如圖所示的二叉排序樹(shù)T,寫(xiě)出f33(T,8)返回的指針?biāo)附Y(jié)點(diǎn)的關(guān)鍵字;在哪些情況下算法f33返回空指針？簡(jiǎn)述算法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);(分?jǐn)?shù)：15.00 )正確答案： （10）解析： 正確答案：仃是空樹(shù)或T中所有結(jié)點(diǎn)的關(guān)鍵字均不大于給定值 X

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