【正文】 . (A) A[1]，A[2]，A[3]，A[4] (B) A[1]，A[14]，A[7]，A[4] (C) A[7]，A[3]，A[5]，A[4] (D) A[7]，A[5] ，A[3]，A[4]7. 7. (A) 8 (B) 7 (C) 6 (D) 58. 8. (A) 5 (B) 6 (C) 7 (D) 89. 9. (A) aedfcb (B) acfebd (C) aebcfd (D) aedfbc10. 10. 隊列是一種（ ）的線性表。二、判斷題(20分)1. 1. 如果兩個關(guān)鍵字的值不等但哈希函數(shù)值相等，則稱這兩個關(guān)鍵字為同義詞。（ ）3. 3. 分塊查找的基本思想是首先在索引表中進行查找，以便確定給定的關(guān)鍵字可能存在的塊號，然后再在相應(yīng)的塊內(nèi)進行順序查找。（ ）5. 5. 向二叉排序樹中插入一個結(jié)點需要比較的次數(shù)可能大于該二叉樹的高度。（ ）7. 7. 非空的雙向循環(huán)鏈表中任何結(jié)點的前驅(qū)指針均不為空。（ ）9. 9. 圖的深度優(yōu)先遍歷算法中需要設(shè)置一個標(biāo)志數(shù)組，以便區(qū)分圖中的每個頂點是否被訪問過。（ ）2． 2． 下面程序段的功能是實現(xiàn)在二叉排序樹中插入一個新結(jié)點，請在下劃線處填上正確的內(nèi)容。struct node *lchild。}bitree。t,int k){if (t==0 ) {____________________________。tlchild=trchild=0。else__________________________。 _________________。5． 5． 設(shè)某棵二叉樹的中序遍歷序列為ABCD，后序遍歷序列為BADC，則其前序遍歷序列為__________。7． 7． 設(shè)有向圖中不存在有向邊Vi,Vj，則其對應(yīng)的鄰接矩陣A中的數(shù)組元素A[i][j]的值等于____________。9． 9． 設(shè)連通圖G中有n個頂點e條邊，則對應(yīng)的最小生成樹上有___________條邊。 設(shè)有一組初始記錄關(guān)鍵字序列為(50，16，23，68，94，70，73)，則將它們調(diào)整成初始堆只需把16與___________相互交換即可。四、算法設(shè)計題(20分)1. 1.2. 2.一、選擇題1．C 2．C 3．C 4．B 5．B6．C 7．B 8．C 9．A 10．A三、填空題1. 1. t=(bitree *)malloc(sizeof(bitree))，bstinsert(trchild,k)3. 3. headrlink，pllink5. 5. 1，167. 7. (13，27，38，50，76，49，65，97)9. 9.四、算法設(shè)計題1. 1. 設(shè)計一個在鏈?zhǔn)酱鎯Y(jié)構(gòu)上統(tǒng)計二叉樹中結(jié)點個數(shù)的算法。count){ if(bt!=0) {count++。 countnode(btrchild,count)。typedef struct {int vertex[m]。}gadjmatrix。int adjvertex。}glinklistnode。glinklistnode *firstarc。void adjmatrixtoadjlist(gadjmatrix g1[ ],glinkheadnode g2[ ]){int i,j。for(i=0。i++) g2[i].firstarc=0。i=n1。j=n1。padjvertex=j。 g[i].firstarc=p。padjvertex=i。 g[j].firstarc=p。一、選擇題(30分)1．下列程序段的時間復(fù)雜度為（ ）。 (A) ni (B) n+l i (C) n1i (D) i3．設(shè)F是由TT2和T3三棵樹組成的森林，與F對應(yīng)的二叉樹為B，TT2和T3的結(jié)點數(shù)分別為NN2和N3，則二叉樹B的根結(jié)點的左子樹的結(jié)點數(shù)為（ ）。 (A) O(n) (B) O(nlog2n) (C) O(n2) (D) O(1og2n)5．設(shè)指針變量p指向雙向鏈表中結(jié)點A，指針變量s指向被插入的結(jié)點X，則在結(jié)點A的后面插入結(jié)點X的操作序列為（ ）。 (A) 快速排序 (B) 堆排序 (C) 歸并排序 (D) 冒泡排序7．設(shè)輸入序列…、n經(jīng)過棧作用后，輸出序列中的第一個元素是n，則輸出序列中的第i個輸出元素是（ ）。 (A) 小于等于m的最大奇數(shù) (B) 小于等于m的最大素數(shù) (C) 小于等于m的最大偶數(shù) (D) 小于等于m的最大合數(shù)9．設(shè)在一棵度數(shù)為3的樹中，度數(shù)為3的結(jié)點數(shù)有2個，度數(shù)為2的結(jié)點數(shù)有1個，度數(shù)為1的結(jié)點數(shù)有2個，那么度數(shù)為0的結(jié)點數(shù)有（ ）個。 (A) n(n1)/2 (B) n(n1) (C) n(n+1)/2 (D) (n1)/2，則順序查找的平均比較次數(shù)為（ ）。 (A) 1 (B) 2 (C) 3 (D) 4，分成5塊，每塊6個元素，如果采用分塊查找，則其平均查找長度為（ ）。 (A) 1，2，3，4 (B) 2，3，4，1 (C) 1，4，2，3 (D) 1，2，4，3(34，76，45，18，26，54，92)，則由這組記錄關(guān)鍵字生成的二叉排序樹的深度為（ ）。3． 3． 設(shè)某順序循環(huán)隊列中有m個元素，且規(guī)定隊頭指針F指向隊頭元素的前一個位置，隊尾指針R指向隊尾元素的當(dāng)前位置，則該循環(huán)隊列中最多存儲_______隊列元素。5． 5． 在堆排序和快速排序中，如果從平均情況下排序的速度最快的角度來考慮應(yīng)最好選擇_________排序，如果從節(jié)省存儲空間的角度來考慮則最好選擇________排序。7． 7． 設(shè)一棵二叉樹的中序遍歷序列為BDCA，后序遍歷序列為DBAC，則這棵二叉樹的前序序列為____________________。9． 9． 設(shè)一組記錄關(guān)鍵字序列為(80，70，33，65，24，56，48)，則用篩選法建成的初始堆為_______________________。 有向圖的鄰接表和逆鄰接表中表結(jié)點的個數(shù)不一定相等。 對鏈表進行插入和刪除操作時不必移動鏈表中結(jié)點。 子串“ABC”在主串“AABCABCD”中的位置為2。 若一個葉子結(jié)點是某二叉樹的中序遍歷序列的最后一個結(jié)點，則它必是該二叉樹的先序遍歷序列中的最后一個結(jié)點。 希爾排序算法的時間復(fù)雜度為O(n2)。 用鄰接矩陣作為圖的存儲結(jié)構(gòu)時，則其所占用的存儲空間與圖中頂點數(shù)無關(guān)而與圖中邊數(shù)有關(guān)。 中序遍歷一棵二叉排序樹可以得到一個有序的序列。 入棧操作和入隊列操作在鏈?zhǔn)酱鎯Y(jié)構(gòu)上實現(xiàn)時不需要考慮棧溢出的情況。 順序表查找指的是在順序存儲結(jié)構(gòu)上進行查找。（ ） 設(shè)計計算二叉樹中所有結(jié)點值之和的算法。 設(shè)計將所有奇數(shù)移到所有偶數(shù)之前的算法。 設(shè)計判斷單鏈表中元素是否是遞增的算法。數(shù)據(jù)結(jié)構(gòu)試卷（13）參考答案二、填空題1. 1. pnext，sdata2. 2. 503. 3. m14. 4. 6，85. 5. 快速，堆6. 6. 19/77. 7. CBDA8. 8. 69. 9. (24，65，33，80，70，56，48)10. 10. 8void sum(bitree *bt,int amp。 sum(btlchild,s)。} }2． 2． 設(shè)計將所有奇數(shù)移到所有偶數(shù)之前的算法。 while(ij){ while (ij amp。 r[j]%2==0) j=j1。i=i+1。amp。 if (ij) {r[j]=r[i]。} } r[i]=x。int isriselk(lklist *head){if(head==0||headnext==0) return(1)。 p!=0。return(1)。一、選擇題(24分)1．下列程序段的時間復(fù)雜度為（ ）。 (A) 單向鏈表 (B) 單向循環(huán)鏈表(C) 雙向鏈表 (D) 雙向循環(huán)鏈表3．設(shè)指針q指向單鏈表中結(jié)點A，指針p指向單鏈表中結(jié)點A的后繼結(jié)點B，指針s指向被插入的結(jié)點X，則在結(jié)點A和結(jié)點B插入結(jié)點X的操作序列為（ ）。(A) 5，3，4，6，1，2 (B) 3，2，5，6，4，1(C) 3，1，2，5，4，6 (D) 1，5，4，6，2，35．設(shè)有一個10階的下三角矩陣A（包括對角線），按照從上到下、從左到右的順序存儲到連續(xù)的55個存儲單元中，每個數(shù)組元素占1個字節(jié)的存儲空間，則A[5][4]地址與A[0][0]的地址之差為（ ）。 (A) (B) (C) (D) 7. 二叉排序樹中左子樹上所有結(jié)點的值均（ ）根結(jié)點的值。 (A) 129 (B) 219 (C) 189 (D) 2299. 設(shè)有n個關(guān)鍵字具有相同的Hash函數(shù)值，則用線性探測法把這n個關(guān)鍵字映射到HASH表中需要做（ ）次線性探測。 (A) 2n (B) n+l (C) 2n1 (D) 2n+l ，則最多經(jīng)過（ ）趟插入排序可以得到有序序列。(A) F，H，C，D，P，A，M，Q，R，S，Y，X(B) P，A，C，S，Q，D，F(xiàn)，X，R，H，M，Y(C) A，D，C，R，F(xiàn)，Q，M，S，Y，P，H，X(D) H，C，Q，P，A，M，S，R，D，F(xiàn)，X，Y二、填空題(48分，其中最后兩小題各6分)1. 1. 設(shè)需要對5個不同的記錄關(guān)鍵字進行排序，則至少需要比較_____________次，至多需要比較_____________次。3. 3. 設(shè)二叉排序樹的高度為h，則在該樹中查找關(guān)鍵字key最多需要比較_________次。5. 5. 設(shè)一棵m叉樹脂的結(jié)點數(shù)為n，用多重鏈表表示其存儲結(jié)構(gòu)，則該樹中有_________個空指針域。8. 8. 設(shè)無向圖G中有n個頂點e條邊，則用鄰接矩陣作為圖的存儲結(jié)構(gòu)進行深度優(yōu)先或廣度優(yōu)先遍歷時的時間復(fù)雜度為_________；用鄰接表作為圖的存儲結(jié)構(gòu)進行深度優(yōu)先或廣度優(yōu)先遍歷的時間復(fù)雜度為_________。10. 10. 設(shè)一組初始關(guān)鍵字序列為(38，65，97，76，13，27，10)，則第3趟冒泡排序結(jié)束后的結(jié)果為_____________________。12. 12. 設(shè)有向圖G中的有向邊的集合E={1，2，2，3，1，4，4，5，5，3，4，6，6，5}，則該圖的一個拓?fù)湫蛄袨開________________________。typedef struct node{int data。________________。void createbitree(bitree *amp。ch)。39。else{ bt=(bitree*)malloc(sizeof(bitree))。 ________。}}14. 14. 下面程序段的功能是利用從尾部插入的方法建立單鏈表的算法，請在下劃線處填上正確的內(nèi)容。 struct node *next。 void lklistcreate(_____________ *amp。i=n。scanf(“%d”,amp。pnext=0。else {qnext=p。}} } 設(shè)計在鏈?zhǔn)酱鎯Y(jié)構(gòu)上合并排序的算法。 設(shè)計在二叉排序樹上查找結(jié)點X的算法。 設(shè)關(guān)鍵字序列(k1，k2，…，kn1)是堆，設(shè)計算法將關(guān)鍵字序列(k1，k2，…，kn1，x)調(diào)整為堆。數(shù)據(jù)結(jié)構(gòu)試卷（14）參考答案二、填空題1. 1. 4，102. 2. O(nlog2n)，O(n2)3. 3. n4. 4. 1，25. 5. n(m1)+16. 6. qnext7. 7. 線性結(jié)構(gòu)，樹型結(jié)構(gòu)，圖型結(jié)構(gòu)8. 8. O(n2)， O(n+e)9. 9. 8/310. 10. (38，13，27，10，65，76，97)11. 11. (10，13，27，76，65，97，38)12. 12. 12465313. 13. struct node *rchild，bt=0，createbitree(btlchild)14. 14. lklist，q=pvoid mergelklist(lklist *ha,lklist *hb,lklist *amp。 while(ha!=0 amp。 hb!=0) if(hadatahbdata){if(s==0) hc=s=ha。 s=ha。ha=hanext。 else {snext=hb。}。} if(ha==0) snext=hb。}2. 2. 設(shè)計在二叉排序樹上查找結(jié)點X的算法。 while(p!=0) if (pkey==key) return(p)。 else p=prchild。}3. 3. 設(shè)關(guān)鍵字序列