【正文】 _____________________________。5. 5. 設無向圖G中有n個頂點和e條邊，則其對應的鄰接表中有_________個表頭結點和_________個表結點。6. 6. 設無向圖G中有n個頂點e條邊，所有頂點的度數(shù)之和為m，則e和m有______關系。7. 7. 設一棵二叉樹的前序遍歷序列和中序遍歷序列均為ABC，則該二叉樹的后序遍歷序列為__________。8. 8. 設一棵完全二叉樹中有21個結點，如果按照從上到下、從左到右的順序從1開始順序編號，則編號為8的雙親結點的編號是___________，編號為8的左孩子結點的編號是_____________。9. 9. 下列程序段的功能實現(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. 設一個連通圖G中有n個頂點e條邊，則其最小生成樹上有________條邊。三、應用題（30分）1．設完全二叉樹的順序存儲結構中存儲數(shù)據(jù)ABCDE，要求給出該二叉樹的鏈式存儲結構并給出該二叉樹的前序、中序和后序遍歷序列。2．設給定一個權值集合W=(3，5，7，9，11)，要求根據(jù)給定的權值集合構造一棵哈夫曼樹并計算哈夫曼樹的帶權路徑長度WPL。3．設一組初始記錄關鍵字序列為(19，21，16，5，18，23)，要求給出以19為基準的一趟快速排序結果以及第2趟直接選擇排序后的結果。4．設一組初始記錄關鍵字集合為(25，10，8，27，32，68)，散列表的長度為8，散列函數(shù)H(k)=k mod 7，要求分別用線性探測和鏈地址法作為解決沖突的方法設計哈希表。5．設無向圖G（所右圖所示），要求給出該圖的深度優(yōu)先和廣度優(yōu)先遍歷的序列并給出該圖的最小生成樹。四、算法設計題(20分) 1. 1. 設計判斷單鏈表中結點是否關于中心對稱算法。2. 2. 設計在鏈式存儲結構上建立一棵二叉樹的算法。3. 3. 設計判斷一棵二叉樹是否是二叉排序樹的算法。數(shù)據(jù)結構試卷（五）參考答案一、選擇題 二、填空題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三、應用題1. 1. 鏈式存儲結構略，前序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)}四、算法設計題1. 1. 設計判斷單鏈表中結點是否關于中心對稱算法。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. 設計在鏈式存儲結構上建立一棵二叉樹的算法。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. 設計判斷一棵二叉樹是否是二叉排序樹的算法。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)。}}（六）一、選擇題(24分)1．下面關于線性表的敘述錯誤的是（ ）。 (A) 線性表采用順序存儲必須占用一片連續(xù)的存儲空間 (B) 線性表采用鏈式存儲不必占用一片連續(xù)的存儲空間(C) 線性表采用鏈式存儲便于插入和刪除操作的實現(xiàn)(D) 線性表采用順序存儲便于插入和刪除操作的實現(xiàn)2．設哈夫曼樹中的葉子結點總數(shù)為m，若用二叉鏈表作為存儲結構，則該哈夫曼樹中總共有（ ）個空指針域。 (A) 2m1 (B) 2m (C) 2m+1 (D) 4m3．設順序循環(huán)隊列Q[0：M1]的頭指針和尾指針分別為F和R，頭指針F總是指向隊頭元素的前一位置，尾指針R總是指向隊尾元素的當前位置，則該循環(huán)隊列中的元素個數(shù)為（ ）。 (A) RF (B) FR (C) (RF+M)％M (D) (FR+M)％M4．設某棵二叉樹的中序遍歷序列為ABCD，前序遍歷序列為CABD，則后序遍歷該二叉樹得到序列為（ ）。 (A) BADC (B) BCDA (C) CDAB (D) CBDA5．設某完全無向圖中有n個頂點，則該完全無向圖中有（ ）條邊。 (A) n(n1)/2 (B) n(n1) (C) n2 (D) n216．設某棵二叉樹中有2000個結點，則該二叉樹的最小高度為（ ）。 (A) 9 (B) 10 (C) 11 (D) 127．設某有向圖中有n個頂點，則該有向圖對應的鄰接表中有（ ）個表頭結點。 (A) n1 (B) n (C) n+1 (D) 2n18．設一組初始記錄關鍵字序列(5，2，6，3，8)，以第一個記錄關鍵字5為基準進行一趟快速排序的結果為（ ）。 (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. 為了能有效地應用HASH查找技術，必須解決的兩個問題是____________________和__________________________。2. 2. 下面程序段的功能實現(xiàn)數(shù)據(jù)x進棧，要求在下劃線處填上正確的語句。typedef struct {int s[100]。 int top。} sqstack。void push(sqstack amp。stack,int x){if (==m1) printf(“overflow”)。else {____________________。_________________。}}3. 3. 中序遍歷二叉排序樹所得到的序列是___________序列（填有序或無序）。4. 4. 快速排序的最壞時間復雜度為___________，平均時間復雜度為__________。5. 5. 設某棵二叉樹中度數(shù)為0的結點數(shù)為N0，度數(shù)為1的結點數(shù)為N1，則該二叉樹中度數(shù)為2的結點數(shù)為_________；若采用二叉鏈表作為該二叉樹的存儲結構，則該二叉樹中共有_______個空指針域。6. 6. 設某無向圖中頂點數(shù)和邊數(shù)分別為n和e，所有頂點的度數(shù)之和為d，則e=_______。7. 7. 設一組初始記錄關鍵字序列為(55，63，44，38，75，80，31，56)，則利用篩選法建立的初始堆為___________________________。8. 8. 設某無向圖G的鄰接表為，則從頂點V1開始的深度優(yōu)先遍歷序列為___________；廣度優(yōu)先遍歷序列為____________。三、應用題(36分)1． 1． 設一組初始記錄關鍵字序列為(45，80，48，40，22，78)，則分別給出第4趟簡單選擇排序和第4趟直接插入排序后的結果。2． 2． 設指針變量p指向雙向鏈表中結點A，指針變量q指向被插入結點B，要求給出在結點A的后面插入結點B的操作序列（設雙向鏈表中結點的兩個指針域分別為llink和rlink）。3． 3． 設一組有序的記錄關鍵字序列為(13，18，24，35，47，50，62，83，90)，查找方法用二分查找，要求計算出查找關鍵字62時的比較次數(shù)并計算出查找成功時的平均查找長度。4． 4． 設一棵樹T中邊的集合為{(A，B)，(A，C)，(A，D)，(B，E)，(C，F(xiàn))，(C，G)}，要求用孩子兄弟表示法（二叉鏈表）表示出該樹的存儲結構并將該樹轉化成對應的二叉樹。5． 5． 設有無向圖G（如右圖所示），要求給出用普里姆算法構造最小生成樹所走過的邊的集合。6． 6． 設有一組初始記錄關鍵字為(45，80，48，40，22，78)，要求構造一棵二叉排序樹并給出構造過程。四、算法設計題(16分) 1． 1． 設有一組初始記錄關鍵字序列（K1，K2，…，Kn），要求設計一個算法能夠在O(n)的時間復雜度內將線性表劃分成兩部分，其中左半部分的每個關鍵字均小于Ki，右半部分的每個關鍵字均大于等于Ki。2． 2． 設有兩個集合A和集合B，要求設計生成集合C=A∩B的算法，其中集合A、B和C用鏈式存儲結構表示。參考答案一、選擇題 二、填空題1. 1. 構造一個好的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)三、應用題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. 樹的鏈式存儲結構略，二叉樹略5. 5. E={(1，3)，(1，2)，(3，5)，(5，6)，(6，4)}6. 6. 略四、算法設計題1. 1. 設有一組初始記錄關鍵字序列（K1，K2，…，Kn），要求設計一個算法能夠在O(n)的時間復雜度內將線性表劃分成兩部分，其中左半部分的每個關鍵字均小于Ki，右半部分的每個關鍵字均大于等于Ki。void quickpass(int r[], int s, int t){ int i=s, j=t, x=r[s]。 while(ij){while (ij amp。amp。 r[j]x) j=j1。 if (ij) {r[i]=r[j]。i=i+1。} while (ij amp。amp。 r[i]x) i=i+1。 if (ij) {r[j]=r[i]。j=j1。} } r[i]=x。}2. 2. 設有兩個集合A和集合B，要求設計生成集合C=A∩B的算法，其中集合A、B和C用鏈式存儲結構表示。typedef struct node {int data。 struct node *ne