本文格式為Word版，下載可任意編輯——數(shù)據(jù)結(jié)構(gòu)試題

問(wèn)題說(shuō)明

部分題目或答案有問(wèn)題，現(xiàn)將已經(jīng)發(fā)現(xiàn)的公布如下，同學(xué)在作這些模擬題的時(shí)候應(yīng)著重做題方法的理解，遇到問(wèn)題以教材或課件為準(zhǔn)，不確定的地方可找同學(xué)商榷或問(wèn)我

（1）試卷1第一套填空題第1題，試卷1第2套選擇題第3題關(guān)于循環(huán)隊(duì)列隊(duì)頭指針和隊(duì)尾指針的約定與教材不一致，以教材或課件為準(zhǔn)，實(shí)際上front指向的是隊(duì)頭元素，rear指向當(dāng)前尚未被占用的第一個(gè)隊(duì)列空間，隊(duì)慢或隊(duì)空的判定條件及入隊(duì)/出隊(duì)等操作具體可參考課件或教材

（2）試卷1第一套應(yīng)用題第5題，不聲明鄰接點(diǎn)順序時(shí)默認(rèn)編號(hào)最小的鄰接點(diǎn)為第一鄰接點(diǎn)，該圖的深度優(yōu)先遍歷序列為123465,答案錯(cuò)。此外，當(dāng)給定鄰接表時(shí)則鄰接點(diǎn)順序依照鄰接表中的前后順序確定，如試卷1其次套填空題第8題

（3）試卷1第五套應(yīng)用題第4題，兩種方法處理沖突的方法下所求ASL值相等都為7/6

（4）試卷1第五套填空題第8題答案給出的是小頂堆需滿足的條件，大頂堆滿足ki=k2iki=k2i+1（5）試卷1第一套填空題第9題模式匹配的BF算法以書中答案為準(zhǔn)，兩者區(qū)別在于，教材中存儲(chǔ)字符串的數(shù)組的0號(hào)單元不存放有效字符，而試卷答案認(rèn)為0號(hào)單元也放數(shù)組

（6）試卷1其次套填空題第7題給定初始序列建堆未聲明建大頂堆還是小頂堆，答案中給出的是小頂堆，大頂堆也要會(huì)建

（7）試卷1其次套應(yīng)用題第1題第4趟直接插入排序的結(jié)果應(yīng)為(22，40，45，48，80，78)；答案中給出的實(shí)際為第三趟，關(guān)鍵在于首元素自身有序不算一趟

（8）試卷1其次套填空題第2題入棧操作以教材為準(zhǔn)，教材中top是指向的棧頂(第一個(gè)空位置)的指針，與該套試卷中棧頂結(jié)構(gòu)不一樣，以教材為準(zhǔn)

（9）試卷1第三套填空題第12題答案中給出的不是拓?fù)湫蛄?，正確的是1423（10）試卷1中多處遇到空指針NULL時(shí)寫的是0而非NULL，實(shí)際兩者皆可

（11）試卷1第4套填空題第2題雙向鏈表的刪除答案錯(cuò)，應(yīng)為p—llink-rlink=p-rlink;p-rlink-llink=p-llink;此外，注意課堂中講的指針名和操作方法（12）第4套填空題第6題答案錯(cuò)，設(shè)哈夫曼樹(shù)中共有99個(gè)結(jié)點(diǎn)，則該樹(shù)中有____50_____個(gè)葉子結(jié)點(diǎn)；若采用二叉鏈表作為存儲(chǔ)結(jié)構(gòu)，則該樹(shù)中有__100___個(gè)空指針域。

（13）第5套選擇第8題答案應(yīng)為A:設(shè)連通圖G中的邊集E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，則從頂點(diǎn)a出發(fā)可以得到一種深度優(yōu)先遍歷的頂點(diǎn)序列為

(A)abedfc

(14)第5套應(yīng)用題第3題題目未指明查找方法，沒(méi)法作

（15）第6套選擇第5題應(yīng)選B，實(shí)際是任意結(jié)點(diǎn)至多只有一個(gè)孩子：設(shè)二叉樹(shù)的先序遍歷序列和后序遍歷序列正好相反，則該二叉樹(shù)滿足的條件是(B)高度等于其結(jié)點(diǎn)數(shù)

（16）第7套填空1題問(wèn)題本身錯(cuò)，設(shè)指針變量p指向雙向鏈表中的結(jié)點(diǎn)A，指針變量s指向被插入的結(jié)點(diǎn)X，則在結(jié)點(diǎn)A的后面插入結(jié)點(diǎn)X的操作序列為_(kāi)___s-left_____=p；s-right=p-right；___p-right_______=s；s-right-left=s；（設(shè)結(jié)點(diǎn)中的兩個(gè)指針域分別為left和right）。（17）第8套填空題第8題答案錯(cuò)

（18）第7套選擇第3題題目錯(cuò)，應(yīng)以60為基準(zhǔn)關(guān)鍵字，答案為C．設(shè)一組初始記錄關(guān)鍵字序列為(60，80，55，40，42，85)，則以第一個(gè)關(guān)鍵字60為基準(zhǔn)而得到的一趟快速排序結(jié)果是（）。(C)42，40，55，60，80，85

（17）第6套填空9題．快速排序算法的空間繁雜度平均狀況下為_(kāi)O(logn)_，最壞的狀況下為_(kāi)O(n)_。(18)第9套填空第3題，題目說(shuō)循環(huán)隊(duì)列有m個(gè)元素實(shí)際指循環(huán)隊(duì)列總長(zhǎng)為m，此外，該題關(guān)于隊(duì)頭和隊(duì)尾指針的約定不同于教材

（19）第9套填空第4題答案錯(cuò)，9個(gè)元素冒泡排序，第一趟比較次數(shù)為8，最多8趟

數(shù)據(jù)結(jié)構(gòu)試卷（一）

1．組成數(shù)據(jù)的基本單位是（C）。(A)數(shù)據(jù)項(xiàng)(B)數(shù)據(jù)類型(C)數(shù)據(jù)元素(D)數(shù)據(jù)變量

2．設(shè)數(shù)據(jù)結(jié)構(gòu)A=(D，R)，其中D={1，2，3，4}，R={r}，r={1，2，2，3，3，4，4，1}，則數(shù)據(jù)結(jié)構(gòu)A是（C）。(A)線性結(jié)構(gòu)(B)樹(shù)型結(jié)構(gòu)(C)圖型結(jié)構(gòu)(D)集合3．?dāng)?shù)組的規(guī)律結(jié)構(gòu)不同于以下（D）的規(guī)律結(jié)構(gòu)。(A)線性表(B)棧(C)隊(duì)列(D)樹(shù)4．二叉樹(shù)中第i(i≥1)層上的結(jié)點(diǎn)數(shù)最多有（B）個(gè)。

(A)2i(B)2i(C)2i-1(D)2i-1

5．設(shè)指針變量p指向單鏈表結(jié)點(diǎn)A，則刪除結(jié)點(diǎn)A的后繼結(jié)點(diǎn)B需要的操作為（C）。

(A)p-next=p-next-next(B)p=p-next(C)p=p-next-next(D)p-next=p

6．設(shè)棧S和隊(duì)列Q的初始狀態(tài)為空，元素E1、E2、E3、E4、E5和E6依次通過(guò)棧S，一個(gè)元素出棧后即進(jìn)入隊(duì)列Q，若6個(gè)元素出列的順序?yàn)镋2、E4、E3、E6、E5和E1，則棧S的容量至少應(yīng)當(dāng)是（B）。(A)6(B)4(C)3(D)2

7．將10階對(duì)稱矩陣壓縮存儲(chǔ)到一維數(shù)組A中，則數(shù)組A的長(zhǎng)度最少為（A）。(A)100(B)40(C)55(D)80

8．設(shè)結(jié)點(diǎn)A有3個(gè)兄弟結(jié)點(diǎn)且結(jié)點(diǎn)B為結(jié)點(diǎn)A的雙親結(jié)點(diǎn)，則結(jié)點(diǎn)B的度數(shù)數(shù)為（A）。(A)3(B)4(C)5(D)1

9．根據(jù)二叉樹(shù)的定義可知二叉樹(shù)共有（B）種不同的形態(tài)。(A)4(B)5(C)6(D)7

10.設(shè)有以下四種排序方法，則（A）的空間繁雜度最大。

(A)冒泡排序(B)快速排序(C)堆排序(D)希爾排序

二、填空題(30分)

1.設(shè)順序循環(huán)隊(duì)列Q[0：m-1]的隊(duì)頭指針和隊(duì)尾指針?lè)謩e為F和R，其中隊(duì)頭指針F指向當(dāng)前隊(duì)頭元素的前一個(gè)位置，隊(duì)尾指針R指向當(dāng)前隊(duì)尾元素所在的位置，則出隊(duì)列的語(yǔ)句為F=M-1__________;。2.設(shè)線性表中有n個(gè)數(shù)據(jù)元素，則在順序存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)順序查找的平均時(shí)間繁雜度為_(kāi)_O(N)___，在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上實(shí)現(xiàn)順序查找的平均時(shí)間繁雜度為_(kāi)_O(N)_______。

3.設(shè)一棵二叉樹(shù)中有n個(gè)結(jié)點(diǎn)，則當(dāng)用二叉鏈表作為其存儲(chǔ)結(jié)構(gòu)時(shí)，該二叉鏈表中共有________個(gè)指針域，__________個(gè)空指針域。

4.設(shè)指針變量p指向單鏈表中結(jié)點(diǎn)A，指針變量s指向被插入的結(jié)點(diǎn)B，則在結(jié)點(diǎn)A的后面插入結(jié)點(diǎn)B的操作序列為_(kāi)_____________________________________。

5.設(shè)無(wú)向圖G中有n個(gè)頂點(diǎn)和e條邊，則其對(duì)應(yīng)的鄰接表中有__1____個(gè)表頭結(jié)點(diǎn)和____N____個(gè)表結(jié)點(diǎn)。

6.設(shè)無(wú)向圖G中有n個(gè)頂點(diǎn)e條邊，所有頂點(diǎn)的度數(shù)之和為m，則e和m有______關(guān)系。7.設(shè)一棵二叉樹(shù)的前序遍歷序列和中序遍歷序列均為ABC，則該二叉樹(shù)的后序遍歷序列為_(kāi)_BCA___。8.設(shè)一棵完全二叉樹(shù)中有21個(gè)結(jié)點(diǎn)，假使依照從上到下、從左到右的順序從1開(kāi)始順序編號(hào)，則編號(hào)為8的雙親結(jié)點(diǎn)的編號(hào)是___4_____，編號(hào)為8的左孩子結(jié)點(diǎn)的編號(hào)是____16_______。9.以下程序段的功能實(shí)現(xiàn)子串t在主串s中位置的算法，要求在下劃線處填上正確語(yǔ)句。intindex(chars[],chart[]){

i=j=0;

while(istrlen(s)jstrlen(t))if(s[i]==t[j]){i=i+l;j=j+l;}else{i=_i_;j=__j__;}if(j==strlen(t))return(i-strlen(t));elsereturn(-1);}

三、應(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)=kmod7，要求分別用線性探測(cè)和鏈地址法作為解決沖突的方法設(shè)計(jì)哈希表。

5．設(shè)無(wú)向圖G（所右圖所示），要求給出該圖的深度優(yōu)先和廣度優(yōu)先遍歷的序列并給出該圖的最小生成樹(shù)。

四、算法設(shè)計(jì)題(20分)

1.設(shè)計(jì)判斷單鏈表中結(jié)點(diǎn)是否關(guān)于中心對(duì)稱算法。2.設(shè)計(jì)在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上建立一棵二叉樹(shù)的算法。3.設(shè)計(jì)判斷一棵二叉樹(shù)是否是二叉排序樹(shù)的算法。

數(shù)據(jù)結(jié)構(gòu)試卷（一）參考答案

一、選擇題1.C

2.C

3.D8.B

4.C9.B

5.A10.B

6.C7.C

二、填空題1.(F+1)%m2.O(n)，O(n)3.2n，n+1

4.s-next=p-next;s-next=s5.n,2e6.7.8.9.

m=2eCBA4，16i-j+1，0

10.n-1

三、應(yīng)用題

1.鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)略，前序ABDEC，中序DBEAC，后序DEBCA。2.哈夫曼樹(shù)略，WPL=78

3.(18,5,16,19,21,23)，(5，16，21，19，18，23)4.線性探測(cè)：鏈地址法：

5.深度：125364，廣度：123456，最小生成樹(shù)T的邊集為E={(1，4)，(1，3)，(3，5)，(5，6)，(5,6)}

四、算法設(shè)計(jì)題

1.設(shè)計(jì)判斷單鏈表中結(jié)點(diǎn)是否關(guān)于中心對(duì)稱算法。typedefstruct{ints[100];inttop;}sqstack;

sqstackstack;stack.top=-1;lklist*p;

for(p=head;p!=0;p=p-next){stack.top++;stack.s[stack.top]=p-data;}

for(p=head;p!=0;p=p-next)if(p-data==stack.s[stack.top])stack.top=stack.top-1;elsereturn(0);return(1);}

2.設(shè)計(jì)在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上建立一棵二叉樹(shù)的算法。

typedefchardatatype;

typedefstructnode{datatypedata;structnode*lchild,*rchild;}bitree;voidcreatebitree(bitree*bt)

{

charch;scanf(%c,ch);if(ch=='#'){bt=0;return;}

bt=(bitree*)malloc(sizeof(bitree));bt-data=ch;createbitree(bt-lchild);createbitree(bt-rchild);}

3.設(shè)計(jì)判斷一棵二叉樹(shù)是否是二叉排序樹(shù)的算法。intminnum=-32768,flag=1;

typedefstructnode{intkey;structnode*lchild,*rchild;}bitree;voidinorder(bitree*bt){

if(bt!=0)

{inorder(bt-lchild);if(minnumbt-key)flag=0;minnum=bt-key;inorder(bt-rchild);}}

數(shù)據(jù)結(jié)構(gòu)試卷（二）

一、選擇題(24分)

1．下面關(guān)于線性表的表達(dá)錯(cuò)誤的是（）。

(A)線性表采用順序存儲(chǔ)必需占用一片連續(xù)的存儲(chǔ)空間(B)線性表采用鏈?zhǔn)酱鎯?chǔ)不必占用一片連續(xù)的存儲(chǔ)空間

(C)線性表采用鏈?zhǔn)酱鎯?chǔ)便于插入和刪除操作的實(shí)現(xiàn)(D)線性表采用順序存儲(chǔ)便于插入和刪除操作的實(shí)現(xiàn)

2．設(shè)哈夫曼樹(shù)中的葉子結(jié)點(diǎn)總數(shù)為m，若用二叉鏈表作為存儲(chǔ)結(jié)構(gòu)，則該哈夫曼樹(shù)中總共有（）個(gè)空指針域。(A)2m-1(B)2m(C)2m+1(D)4m

3．設(shè)順序循環(huán)隊(duì)列Q[0：M-1]的頭指針和尾指針?lè)謩e為F和R，頭指針F總是指向隊(duì)頭元素的前一位置，尾指針R總是指向隊(duì)尾元素的當(dāng)前位置，則該循環(huán)隊(duì)列中的元素個(gè)數(shù)為（）。(A)R-F(B)F-R(C)(R-F+M)％M(D)(F-R+M)％M

4．設(shè)某棵二叉樹(shù)的中序遍歷序列為ABCD，前序遍歷序列為CABD，則后序遍歷該二叉樹(shù)得到序列為（）。(A)BADC(B)BCDA(C)CDAB(D)CBDA

5．設(shè)某完全無(wú)向圖中有n個(gè)頂點(diǎn)，則該完全無(wú)向圖中有（）條邊。(A)n(n-1)/2(B)n(n-1)(C)n2(D)n2-1

6．設(shè)某棵二叉樹(shù)中有2000個(gè)結(jié)點(diǎn)，則該二叉樹(shù)的最小高度為（）。

7．設(shè)某有向圖中有n個(gè)頂點(diǎn)，則該有向圖對(duì)應(yīng)的鄰接表中有（）個(gè)表頭結(jié)點(diǎn)。

(A)n-1(B)n(C)n+1(D)2n-1

8．設(shè)一組初始記錄關(guān)鍵字序列(5，2，6，3，8)，以第一個(gè)記錄關(guān)鍵字5為基準(zhǔn)進(jìn)行一趟快速排序的結(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分)

1.為了能有效地應(yīng)用HASH查找技術(shù)，必需解決的兩個(gè)問(wèn)題是____________________和__________________________。

2.下面程序段的功能實(shí)現(xiàn)數(shù)據(jù)x進(jìn)棧，要求在下劃線處填上正確的語(yǔ)句。typedefstruct{ints[100];inttop;}sqstack;voidpush(sqstackstack,intx){

if(stack.top==m-1)printf(“overflow〞);

else{____________________;_________________;}}

3.中序遍歷二叉排序樹(shù)所得到的序列是___________序列（填有序或無(wú)序）。4.快速排序的最壞時(shí)間繁雜度為_(kāi)__________，平均時(shí)間繁雜度為_(kāi)_________。

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.設(shè)某無(wú)向圖中頂點(diǎn)數(shù)和邊數(shù)分別為n和e，所有頂點(diǎn)的度數(shù)之和為d，則e=_______。

7.設(shè)一組初始記錄關(guān)鍵字序列為(55，63，44，38，75，80，31，56)，則利用篩選法建立的初始堆為_(kāi)__________________________。

8.設(shè)某無(wú)向圖G的鄰接表為，則從頂點(diǎn)V1開(kāi)始的深度優(yōu)先遍歷序列為_(kāi)__________；廣度優(yōu)先遍歷序列為_(kāi)___________。

三、應(yīng)用題(36分)

1．設(shè)一組初始記錄關(guān)鍵字序列為(45，80，48，40，22，78)，則分別給出第4趟簡(jiǎn)單項(xiàng)選擇擇排序和第4趟直接插入排序后的結(jié)果。

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．設(shè)一組有序的記錄關(guān)鍵字序列為(13，18，24，35，47，50，62，83，90)，查找方法用二分查找，要求計(jì)算出查找關(guān)鍵字62時(shí)的比較次數(shù)并計(jì)算出查找成功時(shí)的平均查找長(zhǎng)度。

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．設(shè)有無(wú)向圖G（如右圖所示），要求給出用普里姆算法構(gòu)造最小生成樹(shù)所走過(guò)的邊的集合。6．設(shè)有一組初始記錄關(guān)鍵字為(45，80，48，40，22，78)，要求構(gòu)造一棵二叉排序樹(shù)并給出構(gòu)造過(guò)程。

四、算法設(shè)計(jì)題(16分)

1．設(shè)有一組初始記錄關(guān)鍵字序列（K1，K2，，Kn），要求設(shè)計(jì)一個(gè)算法能夠在O(n)的時(shí)間繁雜度內(nèi)將線性表劃分成兩部分，其中左半部分的每個(gè)關(guān)鍵字均小于Ki，右半部分的每個(gè)關(guān)鍵字均大于等于Ki。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.D

2.B

3.C

4.A

5.A

6.C

7.B

8.C

二、填空題

1.構(gòu)造一個(gè)好的HASH函數(shù)，確定解決沖突的方法2.stack.top++，stack.s[stack.top]=x3.有序

4.O(n2)，O(nlog2n)5.N0-1，2N0+N1

6.d/2

7.(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.3.4.5.

q-llink=p;q-rlink=p-rlink;p-rlink-llink=q;p-rlink=q;2,ASL=91*1+2*2+3*4+4*2)=25/9樹(shù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)略，二叉樹(shù)略

E={(1，3)，(1，2)，(3，5)，(5，6)，(6，4)}

6.略

四、算法設(shè)計(jì)題

1.設(shè)有一組初始記錄關(guān)鍵字序列（K1，K2，，Kn），要求設(shè)計(jì)一個(gè)算法能夠在O(n)的時(shí)間繁雜度內(nèi)將線性表劃分成兩部分，其中左半部分的每個(gè)關(guān)鍵字均小于Ki，右半部分的每個(gè)關(guān)鍵字均大于等于Ki。voidquickpass(intr[],ints,intt){

inti=s,j=t,x=r[s];while(ij){

while(ijr[j]x)j=j-1;if(ij){r[i]=r[j];i=i+1;}

while(ijr[i]x)i=i+1;if(ij){r[j]=r[i];j=j-1;}

}

r[i]=x;}

2.設(shè)有兩個(gè)集合A和集合B，要求設(shè)計(jì)生成集合C=A∩B的算法，其中集合A、B和C用鏈?zhǔn)酱鎯?chǔ)結(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-next)if(q-data==p-data)break;

if(q!=0){t=(lklist*)malloc(sizeof(lklist));t-data=p-data;t-next=hc;hc=t;}}}

數(shù)據(jù)結(jié)構(gòu)試卷（三）

一、選擇題(30分)

1．設(shè)某數(shù)據(jù)結(jié)構(gòu)的二元組形式表示為A=(D，R)，D={01，02，03，04，05，06，07，08，09}，R={r}，r={01，02，01，03，01，04，02，05，02，06，03，07，03，08，03，09}，則數(shù)據(jù)結(jié)構(gòu)A是（）。(A)線性結(jié)構(gòu)(B)樹(shù)型結(jié)構(gòu)(C)物理結(jié)構(gòu)(D)圖型結(jié)構(gòu)2．下面程序的時(shí)間繁雜為（）

for（i=1，s=0；i=n；i++）{t=1；for(j=1；j=i；j++)t=t*j；s=s+t；}

(A)O(n)(B)O(n2)(C)O(n3)(D)O(n4)

3．設(shè)指針變量p指向單鏈表中結(jié)點(diǎn)A，若刪除單鏈表中結(jié)點(diǎn)A，則需要修改指針的操作序列為（）。(A)q=p-next；p-data=q-data；p-next=q-next；free(q)；(B)q=p-next；q-data=p-data；p-next=q-next；free(q)；(C)q=p-next；p-next=q-next；free(q)；

(D)q=p-next；p-data=q-data；free(q)；

4．設(shè)有n個(gè)待排序的記錄關(guān)鍵字，則在堆排序中需要（）個(gè)輔助記錄單元。

(A)1(B)n(C)nlog2n(D)n2

5．設(shè)一組初始關(guān)鍵字記錄關(guān)鍵字為(20，15，14，18，21，36，40，10)，則以20為基準(zhǔn)記錄的一趟快速排序終止后的結(jié)果為()。

(A)10，15，14，18，20，36，40，21(B)10，15，14，18，20，40，36，21

(C)10，15，14，20，18，40，36，2l(D)15，10，14，18，20，36，40，21

6．設(shè)二叉排序樹(shù)中有n個(gè)結(jié)點(diǎn)，則在二叉排序樹(shù)的平均平均查找長(zhǎng)度為（）。

(A)O(1)(B)O(log2n)(C)(D)O(n2)

7．設(shè)無(wú)向圖G中有n個(gè)頂點(diǎn)e條邊，則其對(duì)應(yīng)的鄰接表中的表頭結(jié)點(diǎn)和表結(jié)點(diǎn)的個(gè)數(shù)分別為（）。(A)n，e(B)e，n(C)2n，e(D)n，2e

8.設(shè)某強(qiáng)連通圖中有n個(gè)頂點(diǎn)，則該強(qiáng)連通圖中至少有（）條邊。

(A)n(n-1)(B)n+1(C)n(D)n(n+1)

9．設(shè)有5000個(gè)待排序的記錄關(guān)鍵字，假使需要用最快的方法選出其中最小的10個(gè)記錄關(guān)鍵字，則用以下（）方法可以達(dá)到此目的。(A)快速排序(B)堆排序(C)歸并排序(D)插入排序10.以下四種排序中（）的空間繁雜度最大。(A)插入排序(B)冒泡排序(C)堆排序(D)歸并排序

二、填空殖(48分，其中最終兩小題各6分)

1.數(shù)據(jù)的物理結(jié)構(gòu)主要包括_____________和______________兩種狀況。

2.設(shè)一棵完全二叉樹(shù)中有500個(gè)結(jié)點(diǎn)，則該二叉樹(shù)的深度為_(kāi)_________；若用二叉鏈表作為該完全二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)，則共有___________個(gè)空指針域。

3.設(shè)輸入序列為1、2、3，則經(jīng)過(guò)棧的作用后可以得到___________種不同的輸出序列。4.設(shè)有向圖G用鄰接矩陣A[n][n]作為存儲(chǔ)結(jié)構(gòu)，則該鄰接矩陣中第i行上所有元素之和等于頂點(diǎn)i的________，第i列上所有元素之和等于頂點(diǎn)i的________。

5.設(shè)哈夫曼樹(shù)中共有n個(gè)結(jié)點(diǎn)，則該哈夫曼樹(shù)中有________個(gè)度數(shù)為1的結(jié)點(diǎn)。

6.設(shè)有向圖G中有n個(gè)頂點(diǎn)e條有向邊，所有的頂點(diǎn)入度數(shù)之和為d，則e和d的關(guān)系為_(kāi)________。7.__________遍歷二叉排序樹(shù)中的結(jié)點(diǎn)可以得到一個(gè)遞增的關(guān)鍵字序列（填先序、中序或后序）。8.設(shè)查找表中有100個(gè)元素，假使用二分法查找方法查找數(shù)據(jù)元素X，則最多需要比較________次就可以斷定數(shù)據(jù)元素X是否在查找表中。

9.不管是順序存儲(chǔ)結(jié)構(gòu)的棧還是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的棧，其入棧和出棧操作的時(shí)間繁雜度均為

10.設(shè)有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)，假使依照從自上到下、從左到右從1開(kāi)始順序編號(hào)，則第i個(gè)結(jié)點(diǎn)的雙親結(jié)點(diǎn)編號(hào)為_(kāi)___________，右孩子結(jié)點(diǎn)的編號(hào)為_(kāi)__________。

11.設(shè)一組初始記錄關(guān)鍵字為(72，73，71，23，94，16，5)，則以記錄關(guān)鍵字72為基準(zhǔn)的一趟快速排序結(jié)果為_(kāi)__________________________。

12.設(shè)有向圖G中有向邊的集合E={1，2，2，3，1，4，4，2，4，3}，則該圖的一種拓?fù)湫蛄袨開(kāi)___________________。

13.以下算法實(shí)現(xiàn)在順序散列表中查找值為x的關(guān)鍵字，請(qǐng)?jiān)谙聞澗€處填上正確的語(yǔ)句。structrecord{intkey;intothers;};

inthashsqsearch(structrecordhashtable[],intk){

inti,j;j=i=k%p;

while(hashtable[j].key!=khashtable[j].flag!=0){j=(____)%m;if(i==j)return(-1);}if(_______________________)return(j);elsereturn(-1);}

14.以下算法實(shí)現(xiàn)在二叉排序樹(shù)上查找關(guān)鍵值k，請(qǐng)?jiān)谙聞澗€處填上正確的語(yǔ)句。typedefstructnode{intkey;structnode*lchild;structnode*rchild;}bitree;bitree*bstsearch(bitree*t,intk){

if(t==0)return(0);elsewhile(t!=0)

if(t-key==k)_____________;elseif(t-keyk)t=t-lchild;else_____________;}

三、算法設(shè)計(jì)題(22分)

1．設(shè)計(jì)在單鏈表中刪除值一致的多余結(jié)點(diǎn)的算法。2．設(shè)計(jì)一個(gè)求結(jié)點(diǎn)x在二叉樹(shù)中的雙親結(jié)點(diǎn)算法。

數(shù)據(jù)結(jié)構(gòu)試卷（三）參考答案

一、選擇題1.B

2.B

3.A

4.A

5.A

6.B7.D8.C9.B10.D

第3小題分析：首先用指針變量q指向結(jié)點(diǎn)A的后繼結(jié)點(diǎn)B，然后將結(jié)點(diǎn)B的值復(fù)制到結(jié)點(diǎn)A中，最終刪除結(jié)點(diǎn)B。

第9小題分析：9快速排序、歸并排序和插入排序必需等到整個(gè)排序終止后才能夠求出最小的10個(gè)數(shù)，而堆排序只需要在初始堆的基礎(chǔ)上再進(jìn)行10次篩選即可，每次篩選的時(shí)間繁雜度為O(log2n)。

二、填空題

1.順序存儲(chǔ)結(jié)構(gòu)、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)2.9，5013.5

4.出度，入度5.06.e=d7.中序8.79.O(1)

11.(5，16，71，23，72，94，73)12.(1，4，3，2)

13.j+1，hashtable[j].key==k14.return(t)，t=t-rchild

第8小題分析：二分查找的過(guò)程可以用一棵二叉樹(shù)來(lái)描述，該二叉樹(shù)稱為二叉判定樹(shù)。在有序表上進(jìn)行二分查找時(shí)的查找長(zhǎng)度不超過(guò)二叉判定樹(shù)的高度1+log2n。

三、算法設(shè)計(jì)題

1.設(shè)計(jì)在單鏈表中刪除值一致的多余結(jié)點(diǎn)的算法。typedefintdatatype;

typedefstructnode{datatypedata;structnode*next;}lklist;voiddelredundant(lklist*head){

lklist*p,*q,*s;

for(p=head;p!=0;p=p-next){

for(q=p-next,s=q;q!=0;)

if(q-data==p-data){s-next=q-next;free(q);q=s-next;}else{s=q,q=q-next;}}

}

2.設(shè)計(jì)一個(gè)求結(jié)點(diǎn)x在二叉樹(shù)中的雙親結(jié)點(diǎn)算法。

typedefstructnode{datatypedata;structnode*lchild,*rchild;}bitree;bitree*q[20];intr=0,f=0,flag=0;

voidpreorder(bitree*bt,charx){

if(bt!=0flag==0)

if(bt-data==x){flag=1;return;}

else{r=(r+1)%20;q[r]=bt;preorder(bt-lchild,x);preorder(bt-rchild,x);}}

voidparent(bitree*bt,charx){

inti;

preorder(bt,x);

for(i=f+1;i=r;i++)if(q[i]-lchild-data==x||q[i]-rchild-data)break;if(flag==0)printf(notfoundx\n);

elseif(i=r)printf(%c,bt-data);elseprintf(notparent);}

數(shù)據(jù)結(jié)構(gòu)試卷（四）

一、選擇題(30分)

1．設(shè)一維數(shù)組中有n個(gè)數(shù)組元素，則讀取第i個(gè)數(shù)組元素的平均時(shí)間繁雜度為（(A)O(n)(B)O(nlog2n)(C)O(1)(D)O(n2)

2．設(shè)一棵二叉樹(shù)的深度為k，則該二叉樹(shù)中最多有（）個(gè)結(jié)點(diǎn)。

(A)2k-1(B)2k(C)2k-1(D)2k-1

。）

(A)n(B)e(C)2n(D)2e

4．在二叉排序樹(shù)中插入一個(gè)結(jié)點(diǎn)的時(shí)間繁雜度為（）。

(A)O(1)(B)O(n)(C)O(log2n)(D)O(n2)

5．設(shè)某有向圖的鄰接表中有n個(gè)表頭結(jié)點(diǎn)和m個(gè)表結(jié)點(diǎn)，則該圖中有（）條有向邊。

(A)n(B)n-1(C)m(D)m-1

6．設(shè)一組初始記錄關(guān)鍵字序列為(345，253，674，924，627)，則用基數(shù)排序需要進(jìn)行（）趟的分派和回收才能使得初始關(guān)鍵字序列變成有序序列。(A)3(B)4(C)5(D)8

7．設(shè)用鏈表作為棧的存儲(chǔ)結(jié)構(gòu)則退棧操作（）。(A)必需判別棧是否為滿(B)必需判別棧是否為空(C)判別棧元素的類型(D)對(duì)棧不作任何判別8．以下四種排序中（）的空間繁雜度最大。

(A)快速排序(B)冒泡排序(C)希爾排序(D)堆

9．設(shè)某二叉樹(shù)中度數(shù)為0的結(jié)點(diǎn)數(shù)為N0，度數(shù)為1的結(jié)點(diǎn)數(shù)為Nl，度數(shù)為2的結(jié)點(diǎn)數(shù)為N2，則以下等式成立的是（）。(A)N0=N1+1(B)N0=Nl+N2(C)N0=N2+1(D)N0=2N1+l

10.設(shè)有序順序表中有n個(gè)數(shù)據(jù)元素，則利用二分查找法查找數(shù)據(jù)元素X的最多比較次數(shù)不超過(guò)（）。(A)log2n+1(B)log2n-1(C)log2n(D)log2(n+1)

二、填空題(42分)

1．設(shè)有n個(gè)無(wú)序的記錄關(guān)鍵字，則直接插入排序的時(shí)間繁雜度為_(kāi)_______，快速排序的平均時(shí)間繁雜度為_(kāi)________。

2．設(shè)指針變量p指向雙向循環(huán)鏈表中的結(jié)點(diǎn)X，則刪除結(jié)點(diǎn)X需要執(zhí)行的語(yǔ)句序列為_(kāi)________________________________________________________（設(shè)結(jié)點(diǎn)中的兩個(gè)指針域分別為llink和rlink）。

3．根據(jù)初始關(guān)鍵字序列(19，22，01，38，10)建立的二叉排序樹(shù)的高度為_(kāi)___________。4．深度為k的完全二叉樹(shù)中最少有____________個(gè)結(jié)點(diǎn)。

5．設(shè)初始記錄關(guān)鍵字序列為(K1，K2，，Kn)，則用篩選法思想建堆必需從第______個(gè)元素開(kāi)始進(jìn)行篩選。

6．設(shè)哈夫曼樹(shù)中共有99個(gè)結(jié)點(diǎn)，則該樹(shù)中有_________個(gè)葉子結(jié)點(diǎn)；若采用二叉鏈表作為存儲(chǔ)結(jié)構(gòu)，則該樹(shù)中有_____個(gè)空指針域。

7．設(shè)有一個(gè)順序循環(huán)隊(duì)列中有M個(gè)存儲(chǔ)單元，則該循環(huán)隊(duì)列中最多能夠存儲(chǔ)________個(gè)隊(duì)列元素；當(dāng)前實(shí)際存儲(chǔ)________________個(gè)隊(duì)列元素（設(shè)頭指針F指向當(dāng)前隊(duì)頭元素的前一個(gè)位置，尾指針指向當(dāng)前隊(duì)尾元素的位置）。

8．設(shè)順序線性表中有n個(gè)數(shù)據(jù)元素，則第i個(gè)位置上插入一個(gè)數(shù)據(jù)元素需要移動(dòng)表中_______個(gè)數(shù)據(jù)元素；刪除第i個(gè)位置上的數(shù)據(jù)元素需要移動(dòng)表中_______個(gè)元素。

9．設(shè)一組初始記錄關(guān)鍵字序列為(20，18，22，16，30，19)，則以20為中軸的一趟快速排序結(jié)果為_(kāi)_____________________________。10．設(shè)一組初始記錄關(guān)鍵字序列為(20，18，22，16，30，19)，則根據(jù)這些初始關(guān)鍵字序列建成的初始堆為_(kāi)_______________________。

11．設(shè)某無(wú)向圖G中有n個(gè)頂點(diǎn)，用鄰接矩陣A作為該圖的存儲(chǔ)結(jié)構(gòu)，則頂點(diǎn)i和頂點(diǎn)j互為鄰接點(diǎn)的條件是______________________。

12．設(shè)無(wú)向圖對(duì)應(yīng)的鄰接矩陣為A，則A中第i上非0元素的個(gè)數(shù)_________第i列上非0元素的個(gè)數(shù)（填等于，大于或小于）。13．設(shè)前序遍歷某二叉樹(shù)的序列為ABCD，中序遍歷該二叉樹(shù)的序列為BADC，則后序遍歷該二叉樹(shù)的序列為_(kāi)____________。

句完成在散列表hashtalbe中查找關(guān)鍵字值等于k的結(jié)點(diǎn)，成功時(shí)返回指向關(guān)鍵字的指針，不成功時(shí)返回標(biāo)志0。

typedefstructnode{intkey;structnode*next;}lklist;voidcreatelkhash(lklist*hashtable[]){

inti,k;lklist*s;

for(i=0;im;i++)_____________________;for(i=0;in;i++){

s=(lklist*)malloc(sizeof(lklist));s-key=a[i];

k=a[i]%p;s-next=hashtable[k];_______________________;}}

三、算法設(shè)計(jì)題(28分)

1．設(shè)單鏈表中有僅三類字符的數(shù)據(jù)元素(大寫字母、數(shù)字和其它字符)，要求利用原單鏈表中結(jié)點(diǎn)空間設(shè)計(jì)出三個(gè)單鏈表的算法，使每個(gè)單鏈表只包含同類字符。

2.設(shè)計(jì)在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上交換二叉樹(shù)中所有結(jié)點(diǎn)左右子樹(shù)的算法。3.在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上建立一棵二叉排序樹(shù)。

數(shù)據(jù)結(jié)構(gòu)試卷（四）參考答案

一、選擇題1．C2．D6．A

7．B

二、填空題

1.O(n2)，O(nlog2n)

2.pllink-rlink=p-rlink;p-rlink-llink=p-rlink3.34.5.6.7.8.

2k-1n/250，51

m-1，(R-F+M)%Mn+1-i，n-i

3．D8．A

4．B9．C

5．C10．A

9.(19，18，16，20，30，22)10.(16，18，19，20，32，22)11.A[i][j]=112.等于

13.BDCA

14.hashtable[i]=0，hashtable[k]=s

三、算法設(shè)計(jì)題

1.設(shè)單鏈表中有僅三類字符的數(shù)據(jù)元素(大寫字母、數(shù)字和其它字符)，要求利用原單鏈表中結(jié)點(diǎn)空間設(shè)計(jì)出三個(gè)單鏈表的算法，使每個(gè)單鏈表只包含同類字符。typedefchardatatype;

(D)15，25，35，50，80，20，36，40，70，854．函數(shù)substr(“DATASTRUCTURE〞，5，9)的返回值為（）。

(A)“STRUCTURE〞(B)“DATA〞(C)“ASTRUCTUR〞(D)“DATASTRUCTURE〞

5．設(shè)一個(gè)有序的單鏈表中有n個(gè)結(jié)點(diǎn)，現(xiàn)要求插入一個(gè)新結(jié)點(diǎn)后使得單鏈表依舊保持有序，則該操作的時(shí)間繁雜度為（）。(A)O(log2n)(B)O(1)(C)O(n2)(D)O(n)6．設(shè)一棵m叉樹(shù)中度數(shù)為0的結(jié)點(diǎn)數(shù)為N0，度數(shù)為1的結(jié)點(diǎn)數(shù)為Nl，，度數(shù)為m的結(jié)點(diǎn)數(shù)為Nm，則N0=（）。

(A)Nl+N2+……+Nm

(B)l+N2+2N3+3N4+……+(m-1)Nm

(C)N2+2N3+3N4+……+(m-1)Nm(D)2Nl+3N2+……+(m+1)Nm

7．設(shè)有序表中有1000個(gè)元素，則用二分查找查找元素X最多需要比較（）次。

(A)25(B)10(C)7(D)1

8．設(shè)連通圖G中的邊集E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，則從頂點(diǎn)a出發(fā)可以得到一種深度優(yōu)先遍歷的頂點(diǎn)序列為（）。(A)abedfc(B)acfebd(C)aebdfc(D)aedfcb

9．設(shè)輸入序列是1、2、3、、n，經(jīng)過(guò)棧的作用后輸出序列的第一個(gè)元素是n，則輸出序列中第i個(gè)輸出元素是（）。(A)n-i(B)n-1-i(C)n+1-i

(D)不能確定

10設(shè)一組初始記錄關(guān)鍵字序列為(45，80，55，40，42，85)，則以第一個(gè)記錄關(guān)鍵字45為基準(zhǔn)而得到一趟快速排序的結(jié)果是（）。(A)40，42，45，55，80，83(B)42，40，45，80，85，88(C)42，40，45，55，80，85(D)42，40，45，85，55，80

二、填空題(共30分)

1.設(shè)有一個(gè)順序共享?xiàng)[0：n-1]，其中第一個(gè)棧項(xiàng)指針top1的初值為-1，其次個(gè)棧頂指針top2的初值為n，則判斷共享?xiàng)M的條件是____________________。

2.在圖的鄰接表中用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)表頭結(jié)點(diǎn)的優(yōu)點(diǎn)是____________________。

3.設(shè)有一個(gè)n階的下三角矩陣A，假使依照行的順序?qū)⑾氯蔷仃囍械脑兀ò▽?duì)角線上元素）存放在n(n+1)個(gè)連續(xù)的存儲(chǔ)單元中，則A[i][j]與A[0][0]之間有_______個(gè)數(shù)據(jù)元素。

4.棧的插入和刪除只能在棧的棧頂進(jìn)行，后進(jìn)棧的元素必定先出棧，所以又把棧稱為_(kāi)_________表；隊(duì)列的插入和刪除運(yùn)算分別在隊(duì)列的兩端進(jìn)行，先進(jìn)隊(duì)列的元素必定先出隊(duì)列，所以又把隊(duì)列稱為_(kāi)________表。

5.設(shè)一棵完全二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)中存儲(chǔ)數(shù)據(jù)元素為ABCDEF，則該二叉樹(shù)的前序遍歷序列為_(kāi)__________，中序遍歷序列為_(kāi)__________，后序遍歷序列為_(kāi)__________。

6.設(shè)一棵完全二叉樹(shù)有128個(gè)結(jié)點(diǎn)，則該完全二叉樹(shù)的深度為_(kāi)_______，有__________個(gè)葉子結(jié)點(diǎn)。7.設(shè)有向圖G的存儲(chǔ)結(jié)構(gòu)用鄰接矩陣A來(lái)表示，則A中第i行中所有非零元素個(gè)數(shù)之和等于頂點(diǎn)i的________，第i列中所有非零元素個(gè)數(shù)之和等于頂點(diǎn)i的__________。

8.設(shè)一組初始記錄關(guān)鍵字序列(k1，k2，，kn)是堆，則對(duì)i=1，2，，n/2而言滿足的條件為_(kāi)______________________________。

9.下面程序段的功能是實(shí)現(xiàn)冒泡排序算法，請(qǐng)?jiān)谙聞澗€處填上正確的語(yǔ)句。voidbubble(intr[n]){

for(i=1;i=n-1;i++)

{

for(exchange=0,j=0;j_____________;j++)

if(exchange==0)return；}

}

10.下面程序段的功能是實(shí)現(xiàn)二分查找算法，請(qǐng)?jiān)谙聞澗€處填上正確的語(yǔ)句。structrecord{intkey;intothers;};intbisearch(structrecordr[],intk){

intlow=0,mid,high=n-1;while(low=high){

________________________________;

if(r[mid].key==k)return(mid+1);elseif(____________)high=mid-1;elselow=mid+1;}

return(0);}

三、應(yīng)用題(24分)

1.設(shè)某棵二叉樹(shù)的中序遍歷序列為DBEAC，前序遍歷序列為ABDEC，要求給出該二叉樹(shù)的的后序遍歷序列。

2.設(shè)無(wú)向圖G（如右圖所示），給出該圖的最小生成樹(shù)上邊的集合并計(jì)算最小生成樹(shù)各邊上的權(quán)值之和。

3.設(shè)一組初始記錄關(guān)鍵字序列為(15，17，18，22，35，51，60)，要求計(jì)算出成功查找時(shí)的平均查找長(zhǎng)度。

4.設(shè)散列表的長(zhǎng)度為8，散列函數(shù)H(k)=kmod7，初始記錄關(guān)鍵字序列為(25，31，8，27，13，68)，要求分別計(jì)算出用線性探測(cè)法和鏈地址法作為解決沖突方法的平均查找長(zhǎng)度。

四、算法設(shè)計(jì)題(16分)

1．設(shè)計(jì)判斷兩個(gè)二叉樹(shù)是否一致的算法。2．設(shè)計(jì)兩個(gè)有序單鏈表的合并排序算法。

數(shù)據(jù)結(jié)構(gòu)試卷（五）參考答案

一、選擇題1．A2．B6．B7．B

二、填空題

1.top1+1=top2

2.可以隨機(jī)訪問(wèn)到任一個(gè)頂點(diǎn)的簡(jiǎn)單鏈表3.i(i+1)/2+j-14.FILO，F(xiàn)IFO

5.ABDECF，DBEAFC，DEBFCA6.8，64

7.出度，入度

8.ki=k2iki=k2i+19.n-i，r[j+1]=r[j]

3．A8．B4．A9．C5．D10．C

三、應(yīng)用題

1.DEBCA

2.E={(1,5),(5,2),(5,3),(3,4)},W=103.ASL=(1*1+2*2+3*4)/7=17/74.ASL1=7/6，ASL2=4/3四、算法設(shè)計(jì)題

1.設(shè)計(jì)判斷兩個(gè)二叉樹(shù)是否一致的算法。

typedefstructnode{datatypedata;structnode*lchild,*rchild;}bitree;intjudgebitree(bitree*bt1,bitree*bt2)

{

if(bt1==0bt2==0)return(1);

elseif(bt1==0||bt2==0||bt1-data!=bt2-data)return(0);

elsereturn(judgebitree(bt1-lchild,bt2-lchild)*judgebitree(bt1-rchild,bt2-rchild));}

2.設(shè)計(jì)兩個(gè)有序單鏈表的合并排序算法。voidmergelklist(lklist*ha,lklist*hb,lklist*hc){

lklist*s=hc=0;while(ha!=0hb!=0)

if(ha-datahb-data){if(s==0)hc=s=ha;else{s-next=ha;s=ha;};ha=ha-next;}else{if(s==0)hc=s=hb;else{s-next=hb;s=hb;};hb=hb-next;}if(ha==0)s-next=hb;elses-next=ha;}

數(shù)據(jù)結(jié)構(gòu)試卷（六）

一、選擇題(30分)1．設(shè)一組權(quán)值集合W={2，3，4，5，6}，則由該權(quán)值集合構(gòu)造的哈夫曼樹(shù)中帶權(quán)路徑長(zhǎng)度之和為（(A)20(B)30(C)40(D)45

2．執(zhí)行一趟快速排序能夠得到的序列是（）。(A)[41，12，34，45，27]55[72，63](B)[45，34，12，41]55[72，63，27](C)[63，12，34，45，27]55[41，72]

(D)[12，27，45，41]55[34，63，72]

3．設(shè)一條單鏈表的頭指針變量為head且該鏈表沒(méi)有頭結(jié)點(diǎn)，則其判空條件是（）。(A)head==0(B)head-next==0(C)head-next==head(D)head!=0

4．時(shí)間繁雜度不受數(shù)據(jù)初始狀態(tài)影響而恒為O(nlog2n)的是（）。

(A)堆排序(B)冒泡排序(C)希爾排序(D)快速排序

5．設(shè)二叉樹(shù)的先序遍歷序列和后序遍歷序列正好相反，則該二叉樹(shù)滿足的條件是（）。(A)空或只有一個(gè)結(jié)點(diǎn)(B)高度等于其結(jié)點(diǎn)數(shù)(C)任一結(jié)點(diǎn)無(wú)左孩子(D)任一結(jié)點(diǎn)無(wú)右孩子

6．一趟排序終止后不一定能夠選出一個(gè)元素放在其最終位置上的是（）。(A)堆排序(B)冒泡排序(C)快速排序(D)希爾排序

7．設(shè)某棵三叉樹(shù)中有40個(gè)結(jié)點(diǎn)，則該三叉樹(shù)的最小高度為（）。。）

8．順序查找不管在順序線性表中還是在鏈?zhǔn)骄€性表中的時(shí)間繁雜度為（）。(A)O(n)(B)O(n2)(C)O(n1/2)(D)O(1og2n)9．二路歸并排序的時(shí)間繁雜度為（）。(A)O(n)(B)O(n2)(C)O(nlog2n)(D)O(1og2n)10.深度為k的完全二叉樹(shù)中最少有（）個(gè)結(jié)點(diǎn)。

(A)2k-1-1(B)2k-1(C)2k-1+1(D)2k-1

11.設(shè)指針變量front表示鏈?zhǔn)疥?duì)列的隊(duì)頭指針，指針變量rear表示鏈?zhǔn)疥?duì)列的隊(duì)尾指針，指針變量s指向?qū)⒁腙?duì)列的結(jié)點(diǎn)X，則入隊(duì)列的操作序列為（）。(A)front-next=s；front=s；(B)s-next=rear；rear=s；(C)rear-next=s；rear=s；(D)s-next=front；front=s；

12.設(shè)某無(wú)向圖中有n個(gè)頂點(diǎn)e條邊，