【正文】 ，則出隊列的語句為F =____________。2. 2. 設(shè)線性表中有n個數(shù)據(jù)元素，則在順序存儲結(jié)構(gòu)上實(shí)現(xiàn)順序查找的平均時間復(fù)雜度為___________，在鏈?zhǔn)酱鎯Y(jié)構(gòu)上實(shí)現(xiàn)順序查找的平均時間復(fù)雜度為___________。3. 3. 設(shè)一棵二叉樹中有n個結(jié)點(diǎn)，則當(dāng)用二叉鏈表作為其存儲結(jié)構(gòu)時，該二叉鏈表中共有________個指針域，__________個空指針域。4. 4. 設(shè)指針變量p指向單鏈表中結(jié)點(diǎn)A，指針變量s指向被插入的結(jié)點(diǎn)B，則在結(jié)點(diǎn)A的后面插入結(jié)點(diǎn)B的操作序列為______________________________________。5. 5. 設(shè)無向圖G中有n個頂點(diǎn)和e條邊，則其對應(yīng)的鄰接表中有_________個表頭結(jié)點(diǎn)和_________個表結(jié)點(diǎn)。6. 6. 設(shè)無向圖G中有n個頂點(diǎn)e條邊，所有頂點(diǎn)的度數(shù)之和為m，則e和m有______關(guān)系。7. 7. 設(shè)一棵二叉樹的前序遍歷序列和中序遍歷序列均為ABC，則該二叉樹的后序遍歷序列為__________。8. 8. 設(shè)一棵完全二叉樹中有21個結(jié)點(diǎn)，如果按照從上到下、從左到右的順序從1開始順序編號，則編號為8的雙親結(jié)點(diǎn)的編號是___________，編號為8的左孩子結(jié)點(diǎn)的編號是_____________。9. 9. 下列程序段的功能實(shí)現(xiàn)子串t在主串s中位置的算法，要求在下劃線處填上正確語句。int index(char s[ ], char t[ ]){i=j=0。while(istrlen(s) amp。amp。 jstrlen(t)) if(s[i]==t[j]){i=i+l。 j=j+l。}else{i=_______。 j=______。}if (j==strlen(t))return(istrlen(t))。else return (1)。}10. 10. 設(shè)一個連通圖G中有n個頂點(diǎn)e條邊，則其最小生成樹上有________條邊。三、應(yīng)用題（30分）1．設(shè)完全二叉樹的順序存儲結(jié)構(gòu)中存儲數(shù)據(jù)ABCDE，要求給出該二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)并給出該二叉樹的前序、中序和后序遍歷序列。2．設(shè)給定一個權(quán)值集合W=(3，5，7，9，11)，要求根據(jù)給定的權(quán)值集合構(gòu)造一棵哈夫曼樹并計算哈夫曼樹的帶權(quán)路徑長度WPL。3．設(shè)一組初始記錄關(guān)鍵字序列為(19，21，16，5，18，23)，要求給出以19為基準(zhǔn)的一趟快速排序結(jié)果以及第2趟直接選擇排序后的結(jié)果。4．設(shè)一組初始記錄關(guān)鍵字集合為(25，10，8，27，32，68)，散列表的長度為8，散列函數(shù)H(k)=k mod 7，要求分別用線性探測和鏈地址法作為解決沖突的方法設(shè)計哈希表。5．設(shè)無向圖G（所右圖所示），要求給出該圖的深度優(yōu)先和廣度優(yōu)先遍歷的序列并給出該圖的最小生成樹。四、算法設(shè)計題(20分) 1. 1. 設(shè)計判斷單鏈表中結(jié)點(diǎn)是否關(guān)于中心對稱算法。2. 2. 設(shè)計在鏈?zhǔn)酱鎯Y(jié)構(gòu)上建立一棵二叉樹的算法。3. 3. 設(shè)計判斷一棵二叉樹是否是二叉排序樹的算法。數(shù)據(jù)結(jié)構(gòu)試卷參考答案一、選擇題 二、填空題1. 1. (F+1) % m2. 2. O(n)，O(n)3. 3. 2n，n+14. 4. snext=pnext。 snext=s5. 5. n, 2e6. 6. m=2e7. 7. CBA8. 8. 4，169. 9. ij+1，010. 10. n1三、應(yīng)用題1. 1. 鏈?zhǔn)酱鎯Y(jié)構(gòu)略，前序ABDEC，中序DBEAC，后序DEBCA。2. 2. 哈夫曼樹略，WPL=783. 3. (18,5,16,19,21,23)，(5，16，21，19，18，23)4. 4. 線性探測： 鏈地址法：5. 5. 深度：125364，廣度：123456，最小生成樹T的邊集為E={(1，4)，(1，3)，(3，5)，(5，6)，(5,6)}四、算法設(shè)計題1. 1. 設(shè)計判斷單鏈表中結(jié)點(diǎn)是否關(guān)于中心對稱算法。typedef struct {int s[100]。 int top。} sqstack。int lklistsymmetry(lklist *head){ sqstack stack。 = 1。 lklist *p。 for(p=head。p!=0。p=pnext) {++。 []=pdata。} for(p=head。p!=0。p=pnext) if (pdata==[]) =。 else return(0)。 return(1)。}2. 2. 設(shè)計在鏈?zhǔn)酱鎯Y(jié)構(gòu)上建立一棵二叉樹的算法。typedef char datatype。typedef struct node {datatype data。 struct node *lchild,*rchild。} bitree。void createbitree(bitree *amp。bt){ char ch。 scanf(%c,amp。ch)。 if(ch==39。39。) {bt=0。 return。}bt=(bitree*)malloc(sizeof(bitree))。 btdata=ch。createbitree(btlchild)。 createbitree(btrchild)。}3. 3. 設(shè)計判斷一棵二叉樹是否是二叉排序樹的算法。int minnum=32768,flag=1。typedef struct node{int key。 struct node *lchild,*rchild。}bitree。void inorder(bitree *bt){ if (bt!=0) {inorder(btlchild)。 if(minnumbtkey)flag=0。 minnum=btkey。 inorder(btrchild)。}}數(shù)據(jù)結(jié)構(gòu)試卷（二）一、選擇題(24分)1．下面關(guān)于線性表的敘述錯誤的是（ ）。 (A) 線性表采用順序存儲必須占用一片連續(xù)的存儲空間 (B) 線性表采用鏈?zhǔn)酱鎯Σ槐卣加靡黄B續(xù)的存儲空間(C) 線性表采用鏈?zhǔn)酱鎯Ρ阌诓迦牒蛣h除操作的實(shí)現(xiàn)(D) 線性表采用順序存儲便于插入和刪除操作的實(shí)現(xiàn)2．設(shè)哈夫曼樹中的葉子結(jié)點(diǎn)總數(shù)為m，若用二叉鏈表作為存儲結(jié)構(gòu)，則該哈夫曼樹中總共有（ ）個空指針域。 (A) 2m1 (B) 2m (C) 2m+1 (D) 4m3．設(shè)順序循環(huán)隊列Q[0：M1]的頭指針和尾指針分別為F和R，頭指針F總是指向隊頭元素的前一位置，尾指針R總是指向隊尾元素的當(dāng)前位置，則該循環(huán)隊列中的元素個數(shù)為（ ）。 (A) RF (B) FR (C) (RF+M)％M (D) (FR+M)％M4．設(shè)某棵二叉樹的中序遍歷序列為ABCD，前序遍歷序列為CABD，則后序遍歷該二叉樹得到序列為（ ）。 (A) BADC (B) BCDA (C) CDAB (D) CBDA5．設(shè)某完全無向圖中有n個頂點(diǎn)，則該完全無向圖中有（ ）條邊。 (A) n(n1)/2 (B) n(n1) (C) n2 (D) n216．設(shè)某棵二叉樹中有2000個結(jié)點(diǎn)，則該二叉樹的最小高度為（ ）。 (A) 9 (B) 10 (C) 11 (D) 127．設(shè)某有向圖中有n個頂點(diǎn)，則該有向圖對應(yīng)的鄰接表中有（ ）個表頭結(jié)點(diǎn)。 (A) n1 (B) n (C) n+1 (D) 2n18．設(shè)一組初始記錄關(guān)鍵字序列(5，2，6，3，8)，以第一個記錄關(guān)鍵字5為基準(zhǔn)進(jìn)行一趟快速排序的結(jié)果為（ ）。 (A) 2，3，5，8，6 (B) 3，2，5，8，6 (C) 3，2，5，6，8 (D) 2，3，6，5，8二、填空題(24分)1. 1. 為了能有效地應(yīng)用HASH查找技術(shù)，必須解決的兩個問題是____________________和__________________________。2. 2. 下面程序段的功能實(shí)現(xiàn)數(shù)據(jù)x進(jìn)棧，要求在下劃線處填上正確的語句。typedef struct {int s[100]。 int top。} sqstack。void push(sqstack amp。stack,int x){if (==m1) printf(“overflow”)。else {____________________。_________________。}}3. 3. 中序遍歷二叉排序樹所得到的序列是___________序列（填有序或無序）。4. 4. 快速排序的最壞時間復(fù)雜度為___________，平均時間復(fù)雜度為__________。5. 5. 設(shè)某棵二叉樹中度數(shù)為0的結(jié)點(diǎn)數(shù)為N0，度數(shù)為1的結(jié)點(diǎn)數(shù)為N1，則該二叉樹中度數(shù)為2的結(jié)點(diǎn)數(shù)為_________；若采用二叉鏈表作為該二叉樹的存儲結(jié)構(gòu)，則該二叉樹中共有_______個空指針域。6. 6. 設(shè)某無向圖中頂點(diǎn)數(shù)和邊數(shù)分別為n和e，所有頂點(diǎn)的度數(shù)之和為d，則e=_______。7. 7. 設(shè)一組初始記錄關(guān)鍵字序列為(55，63，44，38，75，80，31，56)，則利用篩選法建立的初始堆為___________________________。8. 8. 設(shè)某無向圖G的鄰接表為，則從頂點(diǎn)V1開始的深度優(yōu)先遍歷序列為___________；廣度優(yōu)先遍歷序列為____________。三、應(yīng)用題(36分)1． 1． 設(shè)一組初始記錄關(guān)鍵字序列為(45，80，48，40，22，78)，則分別給出第4趟簡單選擇排序和第4趟直接插入排序后的結(jié)果。2． 2． 設(shè)指針變量p指向雙向鏈表中結(jié)點(diǎn)A，指針變量q指向被插入結(jié)點(diǎn)B，要求給出在結(jié)點(diǎn)A的后面插入結(jié)點(diǎn)B的操作序列（設(shè)雙向鏈表中結(jié)點(diǎn)的兩個指針域分別為llink和rlink）。3． 3． 設(shè)一組有序的記錄關(guān)鍵字序列為(13，18，24，35，47，50，62，83，90)，查找方法用二分查找，要求計算出查找關(guān)鍵字62時的比較次數(shù)并計算出查找成功時的平均查找長度。4． 4． 設(shè)一棵樹T中邊的集合為{(A，B)，(A，C)，(A，D)，(B，E)，(C，F(xiàn))，(C，G)}，要求用孩子兄弟表示法（二叉鏈表）表示出該樹的存儲結(jié)構(gòu)并將該樹轉(zhuǎn)化成對應(yīng)的二叉樹。5． 5． 設(shè)有無向圖G（如右圖所示），要求給出用普里姆算法構(gòu)造最小生成樹所走過的邊的集合。6． 6． 設(shè)有一組初始記錄關(guān)鍵字為(45，80，48，40，22，78)，要求構(gòu)造一棵二叉排序樹并給出構(gòu)造過程。四、算法設(shè)計題(16分) 1． 1． 設(shè)有一組初始記錄關(guān)鍵字序列（K1，K2，…，Kn），要求設(shè)計一個算法能夠在O(n)的時間復(fù)雜度內(nèi)將線性表劃分成兩部分，其中左半部分的每個關(guān)鍵字均小于Ki，右半部分的每個關(guān)鍵字均大于等于Ki。2． 2． 設(shè)有兩個集合A和集合B，要求設(shè)計生成集合C=A∩B的算法，其中集合A、B和C用鏈?zhǔn)酱鎯Y(jié)構(gòu)表示。數(shù)據(jù)結(jié)構(gòu)試卷（二）參考答案一、選擇題 二、填空題1. 1. 構(gòu)造一個好的HASH函數(shù)，確定解決沖突的方法2. 2. ++，[]=x3. 3. 有序4. 4. O(n2)，O(nlog2n)5. 5. N01，2N0+N16. 6. d/27. 7. (31，38，54，56，75，80，55，63)8. 8. (1，3，4，2)，(1，3，2，4)三、應(yīng)用題1. 1. (22，40，45，48，80，78)，(40，45，48，80，22，78)2. 2. qllink=p。 qrlink=prlink。 prlinkllink=q。 prlink=q。3. 3. 2,ASL=91*1+2*2+3*4+4*2)=25/94. 4. 樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)略，二叉樹略5. 5. E={(1，3)，(1，2)，(3，5)，(5，6)，(6，4)}6. 6. 略四、算法設(shè)計題1. 1. 設(shè)有一組初始記錄關(guān)鍵字序列（K1，K2，…，Kn），要求設(shè)計一個算法能夠在O(n)的時間復(fù)雜度內(nèi)將線性表劃分成兩部分，其中左半部分的每個關(guān)鍵字均小于Ki，右半部分的每個關(guān)鍵字均大于等于Ki。void quickpass(int r[], int s, int t){ int i=s, j