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