大學(xué)計算機《數(shù)據(jù)結(jié)構(gòu)》試卷及答案一、 選擇題(24分)下面關(guān)于線性表的敘述錯誤的是（ 。線性表采用順序存儲必須占用一片連續(xù)的存儲空間線性表采用鏈?zhǔn)酱鎯Σ槐卣加靡黄B續(xù)的存儲空間線性表采用鏈?zhǔn)酱鎯Ρ阌诓迦牒蛣h除操作的實現(xiàn)線性表采用順序存儲便于插入和刪除操作的實現(xiàn)m曼樹中總共有（）個空指針域。(A)2m-1 (B)2m (C)2m+1 (D)4mQ[0：M-1]FRF總是指向隊頭元素的前一位置，尾指針R環(huán)隊列中的元素個數(shù)為（。(A)R-F (B)F-R (C)(R-F+M)％M (D)(F-R+M)％M4ABCDCABD歷該二叉樹得到序列為（ 。BADC (B)BCDA (C)CDAB (D)CBDAn個頂點，則該完全無向圖中有（）條邊。(A)n(n-1)/2 (B)n2-12000個結(jié)點，則該二叉樹的最小高度為（。(A)9 (B)10 (C)11 (D)12n（個表頭結(jié)點。(A)n-1 (B)n (C)n+1 (D)2n-1(5，2，6，3，8)5進行一趟快速排序的結(jié)果為（。(A)2，3，5，8，6(C)3，2，5，6，8

(B)3，2，5，8，6(D)2，3，6，5，8二、填空題(24分)為了能有效地應(yīng)用HASH查找技術(shù)必須解決的兩個問題是 和 。x進棧，要求在下劃線處填上正確的語句。typedefstruct{ints[100];inttop;}sqstack;voidpush(sqstack&stack,intx){if(stack.top==m-1)printf(“overflow”);else{ ; ;}}中序遍歷二叉排序樹所得到的序列是 序列（填有序或無序?？焖倥判虻淖顗臅r間復(fù)雜度為 ，平均時間復(fù)雜度為 。設(shè)某棵二叉樹中度數(shù)為0的結(jié)點數(shù)為度數(shù)為1的結(jié)點數(shù)為則二叉樹中度數(shù)為2的結(jié)點數(shù)為 ；若采用二叉鏈表作為該二叉樹的存結(jié)構(gòu)，則該二叉樹中共有 個空指針域。設(shè)某無向圖中頂點數(shù)和邊數(shù)分別為n和e，所有頂點的度數(shù)之和為d，e= 。7.設(shè)一組初始記錄關(guān)鍵字序列為則利用選法建立的初始堆為 。8. 設(shè)某無向圖G

v3241v132v423v134

開始的深度優(yōu)先遍歷序列為 ；廣度優(yōu)先遍歷序列為 。三、應(yīng)用題(36分)1．設(shè)一組初始記錄關(guān)鍵字序列為(45，80，48，40，22，78)，則分別給出第4趟簡單選擇排序和第4趟直接插入排序后的結(jié)果。2．設(shè)指針變量pAqBAB的操作序列（llinkrlink。62時的比較次數(shù)并計算出查找成功時的平均查找長度。4T中邊的集合為62時的比較次數(shù)并計算出查找成功時的平均查找長度。4T中邊的集合為（鏈表）表示出該樹的存儲結(jié)構(gòu)并將該樹轉(zhuǎn)化成對應(yīng)的二叉樹。（如右圖所示過的邊的集合。設(shè)有一組初始記錄關(guān)鍵字為排序樹并給出構(gòu)造過程。四、算法設(shè)計題(16分)設(shè)有一組初始記錄關(guān)鍵字序列（1，K2，…，n夠在O(n)的時間復(fù)雜度內(nèi)將線性表劃分成兩部分，其中左半部分的每個關(guān)鍵字KiKi。ABC=A∩B的算法，其中集合A、B和C用鏈?zhǔn)酱鎯Y(jié)構(gòu)表示。數(shù)據(jù)結(jié)構(gòu)試卷（二）參考答案一、選擇題1.D 2.B 3.C 4.A 5.A 6.C 7.B 8.C二、填空題HASH函數(shù)，確定解決沖突的方法stack.top++，stack.s[stack.top]=x有序O(n2)，O(nlog2n)5. N0-1，2N0+N16. d/27. (31，38，54，56，75，80，55，63)8. (1，3，4，2)，(1，3，2，4)三、應(yīng)用題1. (22，40，45，48，80，78)，(40，45，48，80，22，78)2. q->llink=p;q->rlink=p->rlink;p->rlink->llink=q;p->rlink=q;3. 2,ASL=91*1+2*2+3*4+4*2)=25/94. 樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)略，二叉樹略5. E={(1，3)，(1，2)，(3，5)，(5，6)，(6，4)}6. 略四、算法設(shè)計題設(shè)有一組初始記錄關(guān)鍵字序列12…nO(n)的時間復(fù)雜度內(nèi)將線性表劃分成兩部分，其中左半部分的每個關(guān)鍵KiKi。voidquickpass(intr[],ints,intt){inti=s,j=t,x=r[s];while(i<j){while(i<j&&r[j]>x)j=j-1;if(i<j){r[i]=r[j];i=i+1;}while(i<j&&r[i]<x)i=i+1;if(i<j){r[j]=r[i];j=j-1;}}r[i]=x;}AC=A∩BA、BC用鏈?zhǔn)酱鎯Y(jié)構(gòu)表示。typedefstructnode{intdata;structnode*next;}lklist;voidintersection(lklist*ha,lklist*hb,lklist*&hc){lklist*p,*q,*t;for(p=ha,hc=0;p!=0;p=p->next){ for(q=hb;q!=0;q=q->