2023福建專升本數(shù)據(jù)結構復習資料

本文格式為Word版，下載可任意編輯——2023福建專升本數(shù)據(jù)結構復習資料

數(shù)據(jù)結構十套練習題！

（答案在后面）

數(shù)據(jù)結構試卷（一）1數(shù)據(jù)結構試卷（二）4數(shù)據(jù)結構試卷（三）6數(shù)據(jù)結構試卷（四）9數(shù)據(jù)結構試卷（五）12數(shù)據(jù)結構試卷（六）15數(shù)據(jù)結構試卷（七）17數(shù)據(jù)結構試卷（八）19數(shù)據(jù)結構試卷（九）21數(shù)據(jù)結構試卷（十）24數(shù)據(jù)結構試卷（一）參考答案27數(shù)據(jù)結構試卷（二）參考答案28數(shù)據(jù)結構試卷（三）參考答案29數(shù)據(jù)結構試卷（四）參考答案31數(shù)據(jù)結構試卷（五）參考答案33數(shù)據(jù)結構試卷（六）參考答案34數(shù)據(jù)結構試卷（七）37數(shù)據(jù)結構試卷（八）參考答案38數(shù)據(jù)結構試卷（九）參考答案39數(shù)據(jù)結構試卷（十）參考答案40

1

數(shù)據(jù)結構試卷（一）

一、單項選擇題（每題2分，共20分）

1.棧和隊列的共同特點是()。A.只允許在端點處插入和刪除元素B.都是先進后出C.都是先進先出D.沒有共同點

2.用鏈接方式存儲的隊列，在進行插入運算時().

A.僅修改頭指針B.頭、尾指針都要修改C.僅修改尾指針D.頭、尾指針可能都要修改

3.以下數(shù)據(jù)結構中哪一個是非線性結構？()

A.隊列B.棧C.線性表D.二叉樹

4.設有一個二維數(shù)組A[m][n]，假設A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每個元素占一個空間，問A[3][3](10)存放在什么位置？腳注(10)表示用10進制表示。

A．688B．678C．692D．696

5.樹最適合用來表示()。

A.有序數(shù)據(jù)元素B.無序數(shù)據(jù)元素

C.元素之間具有分支層次關系的數(shù)據(jù)D.元素之間無聯(lián)系的數(shù)據(jù)6.二叉樹的第k層的結點數(shù)最多為().

kk-1

A．2-1B.2K+1C.2K-1D.2

7.若有18個元素的有序表存放在一維數(shù)組A[19]中，第一個元素放A[1]中，現(xiàn)進行二分查找，則查找A［3］的比較序列的下標依次為()

A.1，2，3B.9，5，2，3C.9，5，3D.9，4，2，3

8.對n個記錄的文件進行快速排序，所需要的輔助存儲空間大致為

A.O（1）B.O（n）C.O（1og2n）D.O（n2）

9.對于線性表（7，34，55，25，64，46，20，10）進行散列存儲時，若選用H（K）=K%9作為散列函數(shù)，則散列地址為1的元素有（）個，

A．1B．2C．3D．4

10.設有6個結點的無向圖，該圖至少應有()條邊才能確保是一個連通圖。A.5B.6C.7D.8二、填空題（每空1分，共26分）

1.尋常從四個方面評價算法的質量：_________、_________、_________和_________。2.一個算法的時間繁雜度為(n3+n2log2n+14n)/n2，其數(shù)量級表示為________。3.假定一棵樹的廣義表表示為A（C，D（E，F(xiàn)，G），H（I，J）），則樹中所含的結點數(shù)

為__________個，樹的深度為___________，樹的度為_________。

4.后綴算式923+-102/-的值為__________。中綴算式（3+4X）-2Y/3對應的后綴算式

為_______________________________。5.若用鏈表存儲一棵二叉樹時，每個結點除數(shù)據(jù)域外，還有指向左孩子和右孩子的兩個指

針。在這種存儲結構中，n個結點的二叉樹共有________個指針域，其中有________個指針域是存放了地址，有________________個指針是空指針。

6.對于一個具有n個頂點和e條邊的有向圖和無向圖，在其對應的鄰接表中，所含邊結點

分別有_______個和________個。

7.AOV網(wǎng)是一種___________________的圖。8.在一個具有n個頂點的無向完全圖中，包含有________條邊，在一個具有n個頂點的有

向完全圖中，包含有________條邊。

1

9.假定一個線性表為(12,23,74,55,63,40)，若按Key%4條件進行劃分，使得同一余數(shù)的元

素成為一個子表，則得到的四個子表分別為____________________________、___________________、_______________________和__________________________。10.向一棵B_樹插入元素的過程中，若最終引起樹根結點的分裂，則新樹比原樹的高度

___________。

11.在堆排序的過程中，對任一分支結點進行篩運算的時間繁雜度為________，整個堆排序

過程的時間繁雜度為________。

12.在快速排序、堆排序、歸并排序中，_________排序是穩(wěn)定的。三、計算題（每題6分，共24分）

1.在如下數(shù)組A中鏈接存儲了一個線性表，表頭指針為A[0].next，試寫出該線性表。

A01234567data

605078903440next35720412.請畫出下圖的鄰接矩陣和鄰接表。

3.已知一個圖的頂點集V和邊集E分別為：V={1,2,3,4,5,6,7};E={(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15,

(3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25};

用克魯斯卡爾算法得到最小生成樹，試寫出在最小生成樹中依次得到的各條邊。4.畫出向小根堆中參與數(shù)據(jù)4,2,5,8,3時，每參與一個數(shù)據(jù)后堆的變化。四、閱讀算法（每題7分，共14分）

1.LinkListmynote(LinkListL)

{//L是不帶頭結點的單鏈表的頭指針if(LABC(BT->right);coutdatadata){

item=BST->data;//查找成功return___________;}elseif(itemdata)

returnFind(______________,item);elsereturnFind(_______________,item);}//if}

六、編寫算法（共8分）

統(tǒng)計出單鏈表HL中結點的值等于給定值X的結點數(shù)。intCountX(LNode*HL,ElemTypex)

3

數(shù)據(jù)結構試卷（二）

一、選擇題(24分)

1．下面關于線性表的表達錯誤的是（）。

(A)線性表采用順序存儲必需占用一片連續(xù)的存儲空間(B)線性表采用鏈式存儲不必占用一片連續(xù)的存儲空間(C)線性表采用鏈式存儲便于插入和刪除操作的實現(xiàn)(D)線性表采用順序存儲便于插入和刪除操作的實現(xiàn)

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

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

4．設某棵二叉樹的中序遍歷序列為ABCD，前序遍歷序列為CABD，則后序遍歷該二叉樹得到序列為（）。(A)BADC(B)BCDA(C)CDAB(D)CBDA5．設某完全無向圖中有n個頂點，則該完全無向圖中有（）條邊。

22

(A)n(n-1)/2(B)n(n-1)(C)n(D)n-16．設某棵二叉樹中有2000個結點，則該二叉樹的最小高度為（）。(A)9(B)10(C)11(D)12

7．設某有向圖中有n個頂點，則該有向圖對應的鄰接表中有（）個表頭結點。(A)n-1(B)n(C)n+1(D)2n-1

8．設一組初始記錄關鍵字序列(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.為了能有效地應用HASH查找技術，必需解決的兩個問題是____________________和

__________________________。

2.下面程序段的功能實現(xiàn)數(shù)據(jù)x進棧，要求在下劃線處填上正確的語句。

typedefstruct{ints[100];inttop;}sqstack;voidpush(sqstack

else{____________________;_________________;}}

3.中序遍歷二叉排序樹所得到的序列是___________序列（填有序或無序）。4.快速排序的最壞時間繁雜度為___________，平均時間繁雜度為__________。

4

5.設某棵二叉樹中度數(shù)為0的結點數(shù)為N0，度數(shù)為1的結點數(shù)為N1，則該二叉樹中度數(shù)為

2的結點數(shù)為_________；若采用二叉鏈表作為該二叉樹的存儲結構，則該二叉樹中共有_______個空指針域。

6.設某無向圖中頂點數(shù)和邊數(shù)分別為n和e，所有頂點的度數(shù)之和為d，則e=_______。7.設一組初始記錄關鍵字序列為(55，63，44，38，75，80，31，56)，則利用篩選法建立

的初始堆為___________________________。

8．已知一有向圖的鄰接表存儲結構如下：從頂點1出發(fā)，DFS遍歷的輸出序列是

，BFS遍歷的輸出序列是

三、應用題(36分)

1．設一組初始記錄關鍵字序列為(45，80，48，40，22，78)，則分別給出第4趟簡單項選擇擇

排序和第4趟直接插入排序后的結果。2．設指針變量p指向雙向鏈表中結點A，指針變量q指向被插入結點B，要求給出在結點A

的后面插入結點B的操作序列（設雙向鏈表中結點的兩個指針域分別為llink和rlink）。3．設一組有序的記錄關鍵字序列為(13，18，24，35，47，50，62，83，90)，查找方法用

二分查找，要求計算出查找關鍵字62時的比較次數(shù)并計算出查找成功時的平均查找長度。

4．設一棵樹T中邊的集合為{(A，B)，(A，C)，(A，D)，(B，E)，(C，F(xiàn))，(C，G)}，要求

用孩子兄弟表示法（二叉鏈表）表示出該樹的存儲結構并將該樹轉化成對應的二叉樹。5．設有無向圖G，要求給出用普里姆算法構造最小生成樹所走過的邊的集合。

6．設有一組初始記錄關鍵字為(45，80，48，40，22，78)，要求構造一棵二叉排序樹并給

出構造過程。

四、算法設計題(16分)

1．設有一組初始記錄關鍵字序列（K1，K2，?，Kn），要求設計一個算法能夠在O(n)的時間

繁雜度內將線性表劃分成兩部分，其中左半部分的每個關鍵字均小于Ki，右半部分的每個關鍵字均大于等于Ki。

2．設有兩個集合A和集合B，要求設計生成集合C=A∩B的算法，其中集合A、B和C用鏈

式存儲結構表示。

5

數(shù)據(jù)結構試卷（三）

一、選擇題(每題1分，共20分)

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

for（i=1，s=0；inext；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．設有n個待排序的記錄關鍵字，則在堆排序中需要（）個輔助記錄單元。

2

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

5．設一組初始關鍵字記錄關鍵字為(20，15，14，18，21，36，40，10)，則以20為基準記錄的一趟快速排序終止后的結果為()。(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．設二叉排序樹中有n個結點，則在二叉排序樹的平均平均查找長度為（）。

2

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

7．設無向圖G中有n個頂點e條邊，則其對應的鄰接表中的表頭結點和表結點的個數(shù)分別為（）。(A)n，e(B)e，n(C)2n，e(D)n，2e8.設某強連通圖中有n個頂點，則該強連通圖中至少有（）條邊。(A)n(n-1)(B)n+1(C)n(D)n(n+1)

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

二、填空殖(每空1分共20分)

1.數(shù)據(jù)的物理結構主要包括_____________和______________兩種狀況。2.設一棵完全二叉樹中有500個結點，則該二叉樹的深度為__________；若用二叉鏈表作

為該完全二叉樹的存儲結構，則共有___________個空指針域。

3.設輸入序列為1、2、3，則經(jīng)過棧的作用后可以得到___________種不同的輸出序列。

6

4.設有向圖G用鄰接矩陣A[n][n]作為存儲結構，則該鄰接矩陣中第i行上所有元素之和

等于頂點i的________，第i列上所有元素之和等于頂點i的________。5.設哈夫曼樹中共有n個結點，則該哈夫曼樹中有________個度數(shù)為1的結點。

6.設有向圖G中有n個頂點e條有向邊，所有的頂點入度數(shù)之和為d，則e和d的關系為

_________。

7.__________遍歷二叉排序樹中的結點可以得到一個遞增的關鍵字序列（填先序、中序或

后序）。

8.設查找表中有100個元素，假使用二分法查找方法查找數(shù)據(jù)元素X，則最多需要比較

________次就可以斷定數(shù)據(jù)元素X是否在查找表中。9.不管是順序存儲結構的棧還是鏈式存儲結構的棧，其入棧和出棧操作的時間繁雜度均為

____________。

10.設有n個結點的完全二叉樹，假使依照從自上到下、從左到右從1開始順序編號，則第

i個結點的雙親結點編號為____________，右孩子結點的編號為___________。

11.設一組初始記錄關鍵字為(72，73，71，23，94，16，5)，則以記錄關鍵字72為基準的

一趟快速排序結果為___________________________。

12.設有向圖G中有向邊的集合E={，，，，}，則該圖

的一種拓撲序列為____________________。

13.以下算法實現(xiàn)在順序散列表中查找值為x的關鍵字，請在下劃線處填上正確的語句。

structrecord{intkey;intothers;};

inthashsqsearch(structrecordhashtable[],intk){

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

while(hashtable[j].key!=kif(i==j)return(-1);}if(_______________________)return(j);elsereturn(-1);}

14.以下算法實現(xiàn)在二叉排序樹上查找關鍵值k，請在下劃線處填上正確的語句。

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->key>k)t=t->lchild;else_____________;}

三、計算題(每題10分，共30分)

1.已知二叉樹的前序遍歷序列是AEFBGCDHIKJ，中序遍歷序列是EFAGBCHKIJD，畫出此二叉樹，并畫出它的后序線索二叉樹。

2．已知待散列的線性表為（36，15，40，63，22），散列用的一維地址空間為[0..6]，假定選用的散列函數(shù)是H（K）=Kmod7，若發(fā)生沖突采用線性探查法處理，試：（1）計算出每一個元素的散列地址并在下圖中填寫出散列表：

`0123456（2）求出在查找每一個元素概率相等狀況下的平均查找長度。3．已知序列（10，18，4，3，6，12，1，9，18，8）請用快速排序寫出每一趟排序的結果。四、算法設計題(每題15分，共30分)

7

1．設計在單鏈表中刪除值一致的多余結點的算法。2．設計一個求結點x在二叉樹中的雙親結點算法。

8

數(shù)據(jù)結構試卷（四）

一、選擇題(每題1分共20分)

1．設一維數(shù)組中有n個數(shù)組元素，則讀取第i個數(shù)組元素的平均時間繁雜度為（）。

2

(A)O(n)(B)O(nlog2n)(C)O(1)(D)O(n)2．設一棵二叉樹的深度為k，則該二叉樹中最多有（）個結點。

kk-1k

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

3．設某無向圖中有n個頂點e條邊，則該無向圖中所有頂點的入度之和為（）。(A)n(B)e(C)2n(D)2e4．在二叉排序樹中插入一個結點的時間繁雜度為（）。

2

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

5．設某有向圖的鄰接表中有n個表頭結點和m個表結點，則該圖中有（）條有向邊。(A)n(B)n-1(C)m(D)m-1

6．設一組初始記錄關鍵字序列為(345，253，674，924，627)，則用基數(shù)排序需要進行（）趟的分派和回收才能使得初始關鍵字序列變成有序序列。(A)3(B)4(C)5(D)87．設用鏈表作為棧的存儲結構則退棧操作（）。(A)必需判別棧是否為滿(B)必需判別棧是否為空(C)判別棧元素的類型(D)對棧不作任何判別8．以下四種排序中（）的空間繁雜度最大。(A)快速排序(B)冒泡排序(C)希爾排序(D)堆

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

10.設有序順序表中有n個數(shù)據(jù)元素，則利用二分查找法查找數(shù)據(jù)元素X的最多比較次數(shù)不

超過（）。(A)log2n+1(B)log2n-1(C)log2n(D)log2(n+1)

二、填空題(每空1分共20分)1．設有n個無序的記錄關鍵字，則直接插入排序的時間繁雜度為________，快速排序的平

均時間繁雜度為_________。

2．設指針變量p指向雙向循環(huán)鏈表中的結點X，則刪除結點X需要執(zhí)行的語句序列為

_________________________________________________________（設結點中的兩個指針域分別為llink和rlink）。

3．根據(jù)初始關鍵字序列(19，22，01，38，10)建立的二叉排序樹的高度為____________。4．深度為k的完全二叉樹中最少有____________個結點。

5．設初始記錄關鍵字序列為(K1，K2，?，Kn)，則用篩選法思想建堆必需從第______個元

素開始進行篩選。

6．設哈夫曼樹中共有99個結點，則該樹中有_________個葉子結點；若采用二叉鏈表作為

存儲結構，則該樹中有_____個空指針域。7．設有一個順序循環(huán)隊列中有M個存儲單元，則該循環(huán)隊列中最多能夠存儲________個隊

列元素；當前實際存儲________________個隊列元素（設頭指針F指向當前隊頭元素的前一個位置，尾指針指向當前隊尾元素的位置）。

9

數(shù)據(jù)結構試卷（六）

一、選擇題(30分)

1．設一組權值集合W={2，3，4，5，6}，則由該權值集合構造的哈夫曼樹中帶權路徑長度

之和為（）。(A)20(B)30(C)40(D)452．執(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．設一條單鏈表的頭指針變量為head且該鏈表沒有頭結點，則其判空條件是（）。(A)head==0(B)head->next==0(C)head->next==head(D)head!=04．時間繁雜度不受數(shù)據(jù)初始狀態(tài)影響而恒為O(nlog2n)的是（）。(A)堆排序(B)冒泡排序(C)希爾排序(D)快速排序

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

6．一趟排序終止后不一定能夠選出一個元素放在其最終位置上的是（）。(A)堆排序(B)冒泡排序(C)快速排序(D)希爾排序7．設某棵三叉樹中有40個結點，則該三叉樹的最小高度為（）。(A)3(B)4(C)5(D)6

8．順序查找不管在順序線性表中還是在鏈式線性表中的時間繁雜度為（）。

21/2

(A)O(n)(B)O(n)(C)O(n)(D)O(1og2n)9．二路歸并排序的時間繁雜度為（）。

2

(A)O(n)(B)O(n)(C)O(nlog2n)(D)O(1og2n)10.深度為k的完全二叉樹中最少有（）個結點。

k-1k-1k-1k

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

11.設指針變量front表示鏈式隊列的隊頭指針，指針變量rear表示鏈式隊列的隊尾指針，

指針變量s指向將要入隊列的結點X，則入隊列的操作序列為（）。(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.設某無向圖中有n個頂點e條邊，則建立該圖鄰接表的時間繁雜度為（）。

23

(A)O(n+e)(B)O(n)(C)O(ne)(D)O(n)

13.設某哈夫曼樹中有199個結點，則該哈夫曼樹中有（）個葉子結點。(A)99(B)100(C)101(D)102

14.設二叉排序樹上有n個結點，則在二叉排序樹上查找結點的平均時間繁雜度為（）。

2

(A)O(n)(B)O(n)(C)O(nlog2n)(D)O(1og2n)

15.設用鄰接矩陣A表示有向圖G的存儲結構，則有向圖G中頂點i的入度為（）。(A)第i行非0元素的個數(shù)之和(B)第i列非0元素的個數(shù)之和(C)第i行0元素的個數(shù)之和(D)第i列0元素的個數(shù)之和

15

二、判斷題(20分)

1．調用一次深度優(yōu)先遍歷可以訪問到圖中的所有頂點。（）

2．分塊查找的平均查找長度不僅與索引表的長度有關，而且與塊的長度有關。（）3．冒泡排序在初始關鍵字序列為逆序的狀況下執(zhí)行的交換次數(shù)最多。（）4．滿二叉樹一定是完全二叉樹，完全二叉樹不一定是滿二叉樹。（）

5．設一棵二叉樹的先序序列和后序序列，則能夠唯一確定出該二叉樹的形狀。（）6．層次遍歷初始堆可以得到一個有序的序列。（）

7．設一棵樹T可以轉化成二叉樹BT，則二叉樹BT中一定沒有右子樹。（）8．線性表的順序存儲結構比鏈式存儲結構更好。（）9．中序遍歷二叉排序樹可以得到一個有序的序列。（）10.快速排序是排序算法中平均性能最好的一種排序。（）

三、填空題(30分)

1．for(i=1，t=1，s=0；i，，，，，}，則給出該圖的一種拓撲排序序列__________。4．設無向圖G中有n個頂點，則該無向圖中每個頂點的度數(shù)最多是_________。5．設二叉樹中度數(shù)為0的結點數(shù)為50，度數(shù)為1的結點數(shù)為30，則該二叉樹中總共有_______個結點數(shù)。

6．設F和R分別表示順序循環(huán)隊列的頭指針和尾指針，則判斷該循環(huán)隊列為空的條件為_____________________。

7．設二叉樹中結點的兩個指針域分別為lchild和rchild，則判斷指針變量p所指向的結點為葉子結點的條件是_____________________________________________。8．簡單項選擇擇排序和直接插入排序算法的平均時間繁雜度為___________。

9．快速排序算法的空間繁雜度平均狀況下為__________，最壞的狀況下為__________。10.散列表中解決沖突的兩種方法是_____________和_____________。

四、算法設計題(20分)

１．設計在順序有序表中實現(xiàn)二分查找的算法。２．設計判斷二叉樹是否為二叉排序樹的算法。３．在鏈式存儲結構上設計直接插入排序算法

16

數(shù)據(jù)結構試卷（七）

一、選擇題(30分)

1．設某無向圖有n個頂點，則該無向圖的鄰接表中有（）個表頭結點。(A)2n(B)n(C)n/2(D)n(n-1)2．設無向圖G中有n個頂點，則該無向圖的最小生成樹上有（）條邊。(A)n(B)n-1(C)2n(D)2n-1

3．設一組初始記錄關鍵字序列為(60，80，55，40，42，85)，則以第一個關鍵字45為基準而得到的一趟快速排序結果是（）。(A)40，42，60，55，80，85(B)42，45，55，60，85，80(C)42，40，55，60，80，85(D)42，40，60，85，55，804．（）二叉排序樹可以得到一個從小到大的有序序列。(A)先序遍歷(B)中序遍歷(C)后序遍歷(D)層次遍歷

5．設依照從上到下、從左到右的順序從1開始對完全二叉樹進行順序編號，則編號為i結點的左孩子結點的編號為（）。(A)2i+1(B)2i(C)i/2(D)2i-1

6．程序段s=i=0；do{i=i+1；s=s+i；}while(inext==0(C)head->next==head(D)head!=0

8．設某棵二叉樹的高度為10，則該二叉樹上葉子結點最多有（）。(A)20(B)256(C)512(D)1024

9．設一組初始記錄關鍵字序列為(13，18，24，35，47，50，62，83，90