第一篇：數據結構試題及答案

數據結構試卷

（二）一、選擇題(24分)1．下面關于線性表的敘述錯誤的是（）。

(A)線性表采用順序存儲必須占用一片連續的存儲空間

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

2．設哈夫曼樹中的葉子結點總數為m，若用二叉鏈表作為存儲結構，則該哈夫曼樹中總共有（）個空指針域。

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

(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)CBDA 5．設某完全無向圖中有n個頂點，則該完全無向圖中有（）條邊。

(A)n(n-1)/2(B)n(n-1)(C)n

2(D)n2-1 6．設某棵二叉樹中有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.1.為了能有效地應用HASH查找技術，必須解決的兩個問題是____________________和__________________________。

2.2.下面程序段的功能實現數據x進棧，要求在下劃線處填上正確的語句。

typedef struct {int s[100];int top;} sqstack;void push(sqstack &stack,int x){ if(stack.top==m-1)printf(“overflow”);

else {____________________;_________________;} } 3.3.中序遍歷二叉排序樹所得到的序列是___________序列（填有序或無序）。4.4.快速排序的最壞時間復雜度為___________，平均時間復雜度為__________。5.5.設某棵二叉樹中度數為0的結點數為N0，度數為1的結點數為N1，則該二叉樹中度數為2的結點數為_________；若采用二叉鏈表作為該二叉樹的存儲結構，則該二叉樹中共有_______個空指針域。

6.6.設某無向圖中頂點數和邊數分別為n和e，所有頂點的度數之和為d，則e=_______。

7.7.設一組初始記錄關鍵字序列為(55，63，44，38，75，80，31，56)，則利用篩選法建立的初始堆為___________________________。

v1??3??2??4v2??1??3v3??1??4??28.8.設某無向圖G的鄰接表為v4??1??3，則從頂點V1開始的深度優先遍歷序列為___________；廣度優先遍歷序列為____________。

三、應用題(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時的比較次數并計算出查找成功時的平均查找長度。

4． 4． 設一棵樹T中邊的集合為{(A，B)，(A，C)，(A，D)，(B，E)，(C，F)，(C，G)}，要求用孩子兄弟表示法（二叉鏈表）表示出該樹的存儲結構并將該樹轉化成對應的二叉樹。5． 5． 設有無向圖G（如右圖所示），要求給出用普里姆算法構造最小生成樹所走過的邊的集合。

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

數據結構試卷

（二）參考答案

一、選擇題 1.D 2.B 3.C 4.A 5.A 6.C 7.B 8.C

二、填空題

1.1.構造一個好的HASH函數，確定解決沖突的方法 2.2.stack.top++，stack.s[stack.top]=x 3.3.有序

4.4.O(n2)，O(nlog2n)5.5.N0-1，2N0+N1 6.6.d/2 7.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.q->llink=p;q->rlink=p->rlink;p->rlink->llink=q;p->rlink=q;3.3.2,ASL=91*1+2*2+3*4+4*2)=25/9 4.4.樹的鏈式存儲結構略，二叉樹略

5.5.E={(1，3)，(1，2)，(3，5)，(5，6)，(6，4)} 6.6.略

數據結構試卷

（三）一、選擇題(30分)1．設某數據結構的二元組形式表示為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>}，則數據結構A是（）。

(A)線性結構(B)樹型結構(C)物理結構(D)圖型結構 2．下面程序的時間復雜為（）

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．設指針變量p指向單鏈表中結點A，若刪除單鏈表中結點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．設有n個待排序的記錄關鍵字，則在堆排序中需要（）個輔助記錄單元。

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

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個結點，則在二叉排序樹的平均平均查找長度為（）。(A)O(1)(B)O(log2n)(C)(D)O(n)7．設無向圖G中有n個頂點e條邊，則其對應的鄰接表中的表頭結點和表結點的個數分別為（）。

(A)n，e(B)e，n(C)2n，e(D)n，2e 8.設某強連通圖中有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)歸并排序

二、填空殖(48分，其中最后兩小題各6分)1.1.數據的物理結構主要包括_____________和______________兩種情況。

2.2.設一棵完全二叉樹中有500個結點，則該二叉樹的深度為__________；若用二叉鏈表作為該完全二叉樹的存儲結構，則共有___________個空指針域。

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

4.4.設有向圖G用鄰接矩陣A[n][n]作為存儲結構，則該鄰接矩陣中第i行上所有元素之和等于頂點i的________，第i列上所有元素之和等于頂點i的________。

5.5.設哈夫曼樹中共有n個結點，則該哈夫曼樹中有________個度數為1的結點。6.6.設有向圖G中有n個頂點e條有向邊，所有的頂點入度數之和為d，則e和d的關系為_________。

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

8.8.設查找表中有100個元素，如果用二分法查找方法查找數據元素X，則最多需要比較________次就可以斷定數據元素X是否在查找表中。

9.9.不論是順序存儲結構的棧還是鏈式存儲結構的棧，其入棧和出棧操作的時間復雜度均為____________。

10.10.設有n個結點的完全二叉樹，如果按照從自上到下、從左到右從1開始順序編號，則第i個結點的雙親結點編號為____________，右孩子結點的編號為___________。11.11.設一組初始記錄關鍵字為(72，73，71，23，94，16，5)，則以記錄關鍵字72為基準的一趟快速排序結果為___________________________。

12.12.設有向圖G中有向邊的集合E={<1，2>，<2，3>，<1，4>，<4，2>，<4，3>}，則該圖的一種拓撲序列為____________________。

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

struct record{int key;int others;};int hashsqsearch(struct record hashtable[ ],int k){ int i,j;j=i=k % p;while(hashtable[j].key!=k&&hashtable[j].flag!=0){j=(____)%m;if(i==j)return(-1);}

if(_______________________)return(j);else return(-1);} 14.14.下列算法實現在二叉排序樹上查找關鍵值k，請在下劃線處填上正確的語句。

typedef struct node{int key;struct node *lchild;struct node *rchild;}bitree;bitree *bstsearch(bitree *t, int k){

if(t==0)return(0);else while(t!=0)if(t->key==k)_____________;else if(t->key>k)t=t->lchild;else_____________;}

數據結構試卷

（三）參考答案

一、選擇題

1.B 2.B 3.A 4.A 5.A 6.B 7.D 8.C 9.B 10.D 第3小題分析：首先用指針變量q指向結點A的后繼結點B，然后將結點B的值復制到結點A中，最后刪除結點B。

第9小題分析：9快速排序、歸并排序和插入排序必須等到整個排序結束后才能夠求出最小的10個數，而堆排序只需要在初始堆的基礎上再進行10次篩選即可，每次篩選的時間復雜度為O(log2n)。

二、填空題

1.1.順序存儲結構、鏈式存儲結構 2.2.9，501 3.3.5 4.4.出度，入度 5.5.0 6.6.e=d 7.7.中序 8.8.7 9.9.O(1)10.10.i/2，2i+1 11.11.(5，16，71，23，72，94，73)12.12.(1，4，3，2)13.13.j+1，hashtable[j].key==k 14.14.return(t)，t=t->rchild 第8小題分析：二分查找的過程可以用一棵二叉樹來描述，該二叉樹稱為二叉判定樹。在有序表上進行二分查找時的查找長度不超過二叉判定樹的高度1+log2n。

}

數據結構試卷

（四）一、選擇題(30分)1．設一維數組中有n個數組元素，則讀取第i個數組元素的平均時間復雜度為（）。(A)O(n)(B)O(nlog2n)(C)O(1)(D)O(n)2．設一棵二叉樹的深度為k，則該二叉樹中最多有（）個結點。

(A)2k-1(B)2k(C)2k-1(D)2k-1 3．設某無向圖中有n個頂點e條邊，則該無向圖中所有頂點的入度之和為（）。

(A)n(B)e(C)2n(D)2e 4．在二叉排序樹中插入一個結點的時間復雜度為（）。

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

(A)n(B)n-1(C)m(D)m-1 6．設一組初始記錄關鍵字序列為(345，253，674，924，627)，則用基數排序需要進行（）趟的分配和回收才能使得初始關鍵字序列變成有序序列。

(A)3(B)4(C)5(D)8 7．設用鏈表作為棧的存儲結構則退棧操作（）。

(A)必須判別棧是否為滿(B)必須判別棧是否為空

(C)判別棧元素的類型(D)對棧不作任何判別 8．下列四種排序中（）的空間復雜度最大。

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

9．設某二叉樹中度數為0的結點數為N0，度數為1的結點數為Nl，度數為2的結點數為N2，則下列等式成立的是（）。

(A)N0=N1+1(B)N0=Nl+N2(C)N0=N2+1(D)N0=2N1+l 10.設有序順序表中有n個數據元素，則利用二分查找法查找數據元素X的最多比較次數不超過（）。

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

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

2． 2． 設指針變量p指向雙向循環鏈表中的結點X，則刪除結點X需要執行的語句序列為_________________________________________________________（設結點中的兩個指針域分別為llink和rlink）。3． 3． 根據初始關鍵字序列(19，22，01，38，10)建立的二叉排序樹的高度為____________。4． 4． 深度為k的完全二叉樹中最少有____________個結點。5． 5． 設初始記錄關鍵字序列為(K1，K2，…，Kn)，則用篩選法思想建堆必須從第______個元素開始進行篩選。

6． 6． 設哈夫曼樹中共有99個結點，則該樹中有_________個葉子結點；若采用二叉鏈表作為存儲結構，則該樹中有_____個空指針域。

7． 7． 設有一個順序循環隊列中有M個存儲單元，則該循環隊列中最多能夠存儲________個隊列元素；當前實際存儲________________個隊列元素（設頭指針F指向當前隊頭元素的前一個位置，尾指針指向當前隊尾元素的位置）。

8． 8． 設順序線性表中有n個數據元素，則第i個位置上插入一個數據元素需要移動表中_______個數據元素；刪除第i個位置上的數據元素需要移動表中_______個元素。9． 9． 設一組初始記錄關鍵字序列為(20，18，22，16，30，19)，則以20為中軸的一趟快速排序結果為______________________________。

10．10．設一組初始記錄關鍵字序列為(20，18，22，16，30，19)，則根據這些初始關鍵字序列建成的初始堆為________________________。

11．11．設某無向圖G中有n個頂點，用鄰接矩陣A作為該圖的存儲結構，則頂點i和頂點j互為鄰接點的條件是______________________。

12．12．設無向圖對應的鄰接矩陣為A，則A中第i上非0元素的個數_________第i列上非0元素的個數（填等于，大于或小于）。

13．13．設前序遍歷某二叉樹的序列為ABCD，中序遍歷該二叉樹的序列為BADC，則后序遍歷該二叉樹的序列為_____________。

14．14．設散列函數H(k)=k mod p，解決沖突的方法為鏈地址法。要求在下列算法劃線處填上正確的語句完成在散列表hashtalbe中查找關鍵字值等于k的結點，成功時返回指向關鍵字的指針，不成功時返回標志0。

typedef struct node {int key;struct node *next;} lklist;void createlkhash(lklist *hashtable[ ]){ int i,k;lklist *s;for(i=0;ikey=a[i];k=a[i] % p;s->next=hashtable[k];_______________________;} }

數據結構試卷

（四）參考答案

一、選擇題

1．C 2．D 3．D 4．B 5．C 6．A 7．B 8．A 9．C 10．A

二、填空題

1.1.O(n2)，O(nlog2n)2.2.p>llink->rlink=p->rlink;p->rlink->llink=p->rlink 3.3.3 4.4.2k-1 5.5.n/2 6.6.50，51 7.7.m-1，(R-F+M)%M 8.8.n+1-i，n-i 9.9.(19，18，16，20，30，22)10.10.(16，18，19，20，32，22)11.11.A[i][j]=1 12.12.等于 13.13.BDCA 14.14.hashtable[i]=0，hashtable[k]=s

數據結構試卷

（五）一、選擇題(30分)

1．數據的最小單位是（）。

(A)數據項(B)數據類型(C)數據元素(D)數據變量

2．設一組初始記錄關鍵字序列為(50，40，95，20，15，70，60，45)，則以增量d=4的一趟希爾排序結束后前4條記錄關鍵字為（）。

(A)40，50，20，95(B)15，40，60，20(C)15，20，40，45(D)45，40，15，20 3．設一組初始記錄關鍵字序列為(25，50，15，35，80，85，20，40，36，70)，其中含有5個長度為2的有序子表，則用歸并排序的方法對該記錄關鍵字序列進行一趟歸并后的結果為（）。

(A)15，25，35，50，20，40，80，85，36，70(B)15，25，35，50，80，20，85，40，70，36(C)15，25，35，50，80，85，20，36，40，70(D)15，25，35，50，80，20，36，40，70，85 4．函數substr(“DATASTRUCTURE”，5，9)的返回值為（）。

(A)“STRUCTURE”(B)“DATA”

(C)“ASTRUCTUR”(D)“DATASTRUCTURE” 5．設一個有序的單鏈表中有n個結點，現要求插入一個新結點后使得單鏈表仍然保持有序，則該操作的時間復雜度為（）。

(A)O(log2n)(B)O(1)(C)O(n2)(D)O(n)6．設一棵m叉樹中度數為0的結點數為N0，度數為1的結點數為Nl，……，度數為m的結點數為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．設有序表中有1000個元素，則用二分查找查找元素X最多需要比較（）次。

(A)25(B)10(C)7(D)1 8．設連通圖G中的邊集E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，則從頂點a出發可以得到一種深度優先遍歷的頂點序列為（）。

(A)abedfc(B)acfebd(C)aebdfc(D)aedfcb 9．設輸入序列是1、2、3、……、n，經過棧的作用后輸出序列的第一個元素是n，則輸出序列中第i個輸出元素是（）。

(A)n-i(B)n-1-i(C)n+1-i(D)不能確定 設一組初始記錄關鍵字序列為(45，80，55，40，42，85)，則以第一個記錄關鍵字45為基準而得到一趟快速排序的結果是（）。

(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.1.設有一個順序共享棧S[0：n-1]，其中第一個棧項指針top1的初值為-1，第二個棧頂指針top2的初值為n，則判斷共享棧滿的條件是____________________。

2.2.在圖的鄰接表中用順序存儲結構存儲表頭結點的優點是____________________。

3.3.設有一個n階的下三角矩陣A，如果按照行的順序將下三角矩陣中的元素（包括對角線上元素）存放在n(n+1)個連續的存儲單元中，則A[i][j]與A[0][0]之間有_______個數據元素。

4.4.棧的插入和刪除只能在棧的棧頂進行，后進棧的元素必定先出棧，所以又把棧稱為__________表；隊列的插入和刪除運算分別在隊列的兩端進行，先進隊列的元素必定先出隊列，所以又把隊列稱為_________表。

5.5.設一棵完全二叉樹的順序存儲結構中存儲數據元素為ABCDEF，則該二叉樹的前序遍歷序列為___________，中序遍歷序列為___________，后序遍歷序列為___________。

6.6.設一棵完全二叉樹有128個結點，則該完全二叉樹的深度為________，有__________個葉子結點。

7.7.設有向圖G的存儲結構用鄰接矩陣A來表示，則A中第i行中所有非零元素個數之和等于頂點i的________，第i列中所有非零元素個數之和等于頂點i的__________。

8.8.設一組初始記錄關鍵字序列(k1，k2，……，kn)是堆，則對i=1，2，…，n/2而言滿足的條件為_______________________________。

9.9.下面程序段的功能是實現冒泡排序算法，請在下劃線處填上正確的語句。void bubble(int r[n]){ for(i=1;i<=n-1;i++){ for(exchange=0,j=0;j<_____________;j++)

if(r[j]>r[j+1]){temp=r[j+1];______________;r[j]=temp;exchange=1;} if(exchange==0)return； } } 10.10.下面程序段的功能是實現二分查找算法，請在下劃線處填上正確的語句。struct record{int key;int others;};int bisearch(struct record r[ ], int k){

int low=0,mid,high=n-1;

while(low<=high){

________________________________;

if(r[mid].key==k)return(mid+1);else if(____________)high=mid-1;else low=mid+1;

}

return(0);}

三、應用題(24分)

1.1.設某棵二叉樹的中序遍歷序列為DBEAC，前序遍歷序列為ABDEC，要求給出該二叉樹的的后序遍歷序列。2.2.設無向圖G（如右圖所示），給出該圖的最小生成樹上邊的集合并計算最小生成樹各邊上的權值之和。

3.3.設一組初始記錄關鍵字序列為(15，17，18，22，35，51，60)，要求計算出成功查找時的平均查找長度。

4.4.設散列表的長度為8，散列函數H(k)=k mod 7，初始記錄關鍵字序列為(25，31，8，27，13，68)，要求分別計算出用線性探測法和鏈地址法作為解決沖突方法的平均查找長度。

數據結構試卷

（五）參考答案

一、選擇題 1．A 2．B 3．A 4．A 5．D 6．B 7．B 8．B 9．C 10．C

二、填空題

1.1.top1+1=top2 2.2.可以隨機訪問到任一個頂點的簡單鏈表

3.3.i(i+1)/2+j-1 4.4.FILO，FIFO 5.5.ABDECF，DBEAFC，DEBFCA 6.6.8，64 7.7.出度，入度

8.8.ki<=k2i && ki<=k2i+1 9.9.n-i，r[j+1]=r[j] 10.10.mid=(low+high)/2，r[mid].key>k

三、應用題

1.1.DEBCA 2.2.E={(1,5),(5,2),(5,3),(3,4)},W=10 3.3.ASL=(1*1+2*2+3*4)/7=17/7 4.4.ASL1=7/6，ASL2=4/3

數據結構試卷

（六）一、選擇題(30分)1． 設一組權值集合W={2，3，4，5，6}，則由該權值集合構造的哈夫曼樹中帶權路徑長度之和為（）。

(A)20(B)30(C)40(D)45 2．執行一趟快速排序能夠得到的序列是（）。

(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!=0 4．時間復雜度不受數據初始狀態影響而恒為O(nlog2n)的是（）。

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

5．設二叉樹的先序遍歷序列和后序遍歷序列正好相反，則該二叉樹滿足的條件是（）。

(A)空或只有一個結點(B)高度等于其結點數

(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．二路歸并排序的時間復雜度為（）。(A)O(n)(B)O(n)(C)O(nlog2n)(D)O(1og2n)10.深度為k的完全二叉樹中最少有（）個結點。

(A)2k-1-1(B)2k-1(C)2k-1+1(D)2k-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條邊，則建立該圖鄰接表的時間復雜度為（）。(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個結點，則在二叉排序樹上查找結點的平均時間復雜度為（）。(A)O(n)(B)O(n)(C)O(nlog2n)(D)O(1og2n)15.設用鄰接矩陣A表示有向圖G的存儲結構，則有向圖G中頂點i的入度為（）。

(A)第i行非0元素的個數之和(B)第i列非0元素的個數之和

(C)第i行0元素的個數之和(D)第i列0元素的個數之和

二、判斷題(20分)1．調用一次深度優先遍歷可以訪問到圖中的所有頂點。（）

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

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

7．設一棵樹T可以轉化成二叉樹BT，則二叉樹BT中一定沒有右子樹。（）8．線性表的順序存儲結構比鏈式存儲結構更好。（）

9．中序遍歷二叉排序樹可以得到一個有序的序列。（）10.快速排序是排序算法中平均性能最好的一種排序。（）

三、填空題(30分)1．for(i=1，t=1，s=0；i<=n；i++){t=t*i；s=s+t；}的時間復雜度為_________。

2．設指針變量p指向單鏈表中結點A，指針變量s指向被插入的新結點X，則進行插入操作的語句序列為__________________________（設結點的指針域為next）。3．設有向圖G的二元組形式表示為G =（D，R），D={1，2，3，4，5}，R={r}，r={<1,2>，<2,4>，<4,5>，<1,3>，<3,2>，<3,5>}，則給出該圖的一種拓撲排序序列__________。4．設無向圖G中有n個頂點，則該無向圖中每個頂點的度數最多是_________。5．設二叉樹中度數為0的結點數為50，度數為1的結點數為30，則該二叉樹中總共有_______個結點數。

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

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

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

數據結構試卷

（六）參考答案

一、選擇題 1．D 2．A 3．A 4．A 5．D 6．D 7．B 8．A 9．C 10．B 11．C 12．A 13．B 14．D 15．B

二、判斷題

1．錯 2．對 3．對 4．對 5．錯 6．錯 7．對 8．錯 9．對 10．對

三、填空題

1.1.O(n)2.2.s->next=p->next;p->next=s 3.3.(1，3，2，4，5)4.4.n-1 5.5.129 6.6.F==R 7.7.p->lchild==0&&p->rchild==0 8.8.O(n2)9.9.O(nlog2n)，O(n)10.10.開放定址法，鏈地址法

數據結構試卷

（七）一、選擇題(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，80 4．（）二叉排序樹可以得到一個從小到大的有序序列。

(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(i<=n)；的時間復雜度為（）。(A)O(n)(B)O(nlog2n)(C)O(n)(D)O(n/2)7．設帶有頭結點的單向循環鏈表的頭指針變量為head，則其判空條件是（）。

(A)head==0(B)head->next==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，115，134),則利用二分法查找關鍵字90需要比較的關鍵字個數為（）。

(A)1(B)2(C)3(D)4 10.設指針變量top指向當前鏈式棧的棧頂，則刪除棧頂元素的操作序列為（）。

(A)top=top+1;(B)top=top-1;(C)top->next=top;(D)top=top->next;

三、填空題(30分)1.1.設指針變量p指向雙向鏈表中的結點A，指針變量s指向被插入的結點X，則在結點A的后面插入結點X的操作序列為_________=p；s->right=p->right；__________=s； p->right->left=s；（設結點中的兩個指針域分別為left和right）。2.2.設完全有向圖中有n個頂點，則該完全有向圖中共有________條有向條；設完全無向圖中有n個頂點，則該完全無向圖中共有________條無向邊。

3.3.設關鍵字序列為(Kl，K2，…，Kn)，則用篩選法建初始堆必須從第______個元素開始進行篩選。

4.4.解決散列表沖突的兩種方法是________________和__________________。

5.5.設一棵三叉樹中有50個度數為0的結點，21個度數為2的結點，則該二叉樹中度數為3的結點數有______個。

6.6.高度為h的完全二叉樹中最少有________個結點，最多有________個結點。7.7.設有一組初始關鍵字序列為(24，35，12，27，18，26)，則第3趟直接插入排序結束后的結果的是__________________________________。

8.8.設有一組初始關鍵字序列為(24，35，12，27，18，26)，則第3趟簡單選擇排序結束后的結果的是__________________________________。

9.9.設一棵二叉樹的前序序列為ABC，則有______________種不同的二叉樹可以得到這種序列。

10.10.下面程序段的功能是實現一趟快速排序，請在下劃線處填上正確的語句。

struct record {int key;datatype others;};void quickpass(struct record r[], int s, int t, int &i){

int j=t;struct record x=r[s];i=s;

while(i

while(ix.key)j=j-1;if(i

while(____________________)i=i+1;if(i

}

_________________;}

數據結構試卷

（七）一、選擇題 1．B 2．B 3．C 4．B 6．A 7．C 8．C 9．B

三、填空題

1.1.s->left=p，p->right 2.2.n(n-1)，n(n-1)/2 3.3.n/2 4.4.開放定址法，鏈地址法 5.5.14 6.6.2h-1，2h-1 7.7.(12，24，35，27，18，26)8.8.(12，18，24，27，35，26)9.9.5 10.10.i

5．B 10．D

數據結構試卷

（八）一、選擇題(30分)1.1.字符串的長度是指（）。

(A)串中不同字符的個數(B)串中不同字母的個數

(C)串中所含字符的個數(D)串中不同數字的個數 2.2.建立一個長度為n的有序單鏈表的時間復雜度為（）

(A)O(n)(B)O(1)(C)O(n2)(D)O(log2n)3.3.兩個字符串相等的充要條件是（）。

(A)兩個字符串的長度相等(B)兩個字符串中對應位置上的字符相等

(C)同時具備(A)和(B)兩個條件(D)以上答案都不對 4.4.設某散列表的長度為100，散列函數H(k)=k % P，則P通常情況下最好選擇（）。

(A)99(B)97(C)91(D)93 5.5.在二叉排序樹中插入一個關鍵字值的平均時間復雜度為（）。(A)O(n)(B)O(1og2n)(C)O(nlog2n)(D)O(n)6.6.設一個順序有序表A[1:14]中有14個元素，則采用二分法查找元素A[4]的過程中比較元素的順序為()。

(A)A[1]，A[2]，A[3]，A[4](B)A[1]，A[14]，A[7]，A[4](C)A[7]，A[3]，A[5]，A[4](D)A[7]，A[5]，A[3]，A[4] 7.7.設一棵完全二叉樹中有65個結點，則該完全二叉樹的深度為（）。

(A)8(B)7(C)6(D)5 8.8.設一棵三叉樹中有2個度數為1的結點，2個度數為2的結點，2個度數為3的結點，則該三叉鏈權中有（）個度數為0的結點。

(A)5(B)6(C)7(D)8 9.9.設無向圖G中的邊的集合E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，則從頂點a出發進行深度優先遍歷可以得到的一種頂點序列為（）。

(A)aedfcb(B)acfebd(C)aebcfd(D)aedfbc 10.10.隊列是一種（）的線性表。

(A)先進先出(B)先進后出(C)只能插入(D)只能刪除

三、填空題(30分)1． 1． 設一組初始記錄關鍵字序列為(49，38，65，97，76，13，27，50)，則以d=4為增量的一趟希爾排序結束后的結果為_____________________________。

2． 2． 下面程序段的功能是實現在二叉排序樹中插入一個新結點，請在下劃線處填上正確的內容。

typedef struct node{int data;struct node *lchild;struct node *rchild;}bitree;void bstinsert(bitree *&t,int k){ if(t==0){____________________________;t->data=k;t->lchild=t->rchild=0;} else if(t->data>k)bstinsert(t->lchild,k);else__________________________;} 3． 3． 設指針變量p指向單鏈表中結點A，指針變量s指向被插入的結點X，則在結點A的后面插入結點X需要執行的語句序列：s->next=p->next;_________________。4． 4． 設指針變量head指向雙向鏈表中的頭結點，指針變量p指向雙向鏈表中的第一個結點，則指針變量p和指針變量head之間的關系是p=_________和head=__________（設結點中的兩個指針域分別為llink和rlink）。

5． 5． 設某棵二叉樹的中序遍歷序列為ABCD，后序遍歷序列為BADC，則其前序遍歷序列為__________。

6． 6． 完全二叉樹中第5層上最少有__________個結點，最多有_________個結點。7． 7． 設有向圖中不存在有向邊，則其對應的鄰接矩陣A中的數組元素A[i][j]的值等于____________。

8． 8． 設一組初始記錄關鍵字序列為(49，38，65，97，76，13，27，50)，則第4趟直接選擇排序結束后的結果為_____________________________。

9． 9． 設連通圖G中有n個頂點e條邊，則對應的最小生成樹上有___________條邊。10． 10． 設有一組初始記錄關鍵字序列為(50，16，23，68，94，70，73)，則將它們調整成初始堆只需把16與___________相互交換即可。

數據結構試卷

（八）參考答案

一、選擇題 1．C 2．C 3．C 4．B 5．B 6．C 7．B 8．C 9．A 10．A

三、填空題

1.1.(49，13，27，50，76，38，65，97)2.2.t=(bitree *)malloc(sizeof(bitree))，bstinsert(t->rchild,k)3.3.p->next=s 4.4.head->rlink，p->llink 5.5.CABD 6.6.1，16 7.7.0 8.8.(13，27，38，50，76，49，65，97)9.9.n-1 10.10.50

第二篇：2013臺灣省數據結構試題及答案（推薦）

1、串的邏輯結構與（D）的邏輯結構不相同。A）線性表 B）棧 C）隊列 D）集合

2、廣義表head(((a,b),(c,d)))的運算結果為（A）。A）(a,b)B）(c,d)C）空表 D）（（a,b）,(c,d)）

3、鏈式存儲的存儲結構所占存儲空間（A）。

A）分兩部分，一部分存放結點值，另一部分存放表示結點間關系的指針 B）只有一部分，存放結點值

C）只有一部分，存儲表示結點間關系的指針

D）分兩部分，一部分存放結點值，另一部分存放結點所占單元數

4、設單鏈表中指針p指向結點m，若要刪除m之后的結點（若存在），則需修改指針的操作為（A）。

A）p->next=p->next->next;B）p=p->next;C）p=p->next->next;D）p->next=p;

5、在一個具有n個單元的順序棧中，假定以地址低端（即0單元）作為棧底，以top作為棧頂指針，當做出棧處理時，top變化為（C）。

A）top不變 B）top=0 C）top--D）top++

6、數據結構研究的內容是（D）。

A）數據的邏輯結構 B）數據的存儲結構

C）建立在相應邏輯結構和存儲結構上的算法 D）包括以上三個方面

7、向一個棧頂指針為hs的鏈棧中插入一個s結點時，應執行（D）。A)hs->next=s;

B)s->next=hs->next;hs->next=s;C)s->next=hs;hs=s;D)s->next=hs;hs=hs->next;

8、設一數列的順序為1，2，3，4，5，6，通過棧結構不可能排成的順序數列為（B）。A）3，2，5，6，4，1 B）1，5，4，6，2，3 C）2，4，3，5，1，6 D）4，5，3，6，2，1

9、廣義表head(((a,b),(c,d)))的運算結果為（A）。A）(a,b)B）(c,d)C）空表 D）（（a,b）,(c,d)）

10、若一棵二叉樹具有10個度為2的結點，5個度為1的結點，則度為0的結點的個數是(B)。A）9 B）11 C）15 D）不能確定

11、在一個鏈隊列中，假定front和rear分別為隊首和隊尾指針，則刪除一個結點的操作為（B）。A)rear=rear->next;B)front=front->next;C)rear=front->next;

D)front=rear->next;

12、n個頂點的圖的最小生成樹必定（D），是不正確的描述。A）不唯一 B）權的總和唯一 C）不含回路 D）有n條邊

13、串的邏輯結構與（D）的邏輯結構不同。A）線性表 B）棧 C）隊列 D）樹

第三篇：數據結構試題及答案10

《數據結構》自考復習思考試題

一、單項選擇題(本大題共15小題，每小題2分，共30分)在每小題列出的四個備選項中只有一個是符合題目要求的，請將其代碼填寫在題后的括號內。錯選、多選或未選均無分。

1.若將數據結構形式定義為二元組(K，R)，其中K是數據元素的有限集合，則R是K上（）

A.操作的有限集合B.映象的有限集合 C.類型的有限集合D.關系的有限集合

2.在長度為n的順序表中刪除第i個元素(1≤i≤n)時，元素移動的次數為（）A.n-i+1

B.i C.i+1

D.n-i 3.若不帶頭結點的單鏈表的頭指針為head，則該鏈表為空的判定條件是（）A.head==NULL

B.head->next==NULL C.head!=NULL

D.head->next==head 4.引起循環隊列隊頭位置發生變化的操作是（）A.出隊

B.入隊

C.取隊頭元素

D.取隊尾元素

5.若進棧序列為1，2，3，4，5，6，且進棧和出棧可以穿插進行，則不可能出現的出棧序列是（）A.2，4，3，1，5，6

B.3，2，4，1，6，5 C.4，3，2，1，5，6

D.2，3，5，1，6，4 6.字符串通常采用的兩種存儲方式是（）A.散列存儲和索引存儲

B.索引存儲和鏈式存儲 C.順序存儲和鏈式存儲

D.散列存儲和順序存儲

7.設主串長為n，模式串長為m(m≤n)，則在匹配失敗情況下，樸素匹配算法進行的無效位移次數為（）A.m

B.n-m C.n-m+1

D.n 8.二維數組A［12］［18］采用列優先的存儲方法，若每個元素各占3個存儲單元，且第1個元素的地址為150，則元素A［9］［7］的地址為（）A.429

B.432 C.435

D.438 9.對廣義表L=((a,b),(c,d),(e,f))執行操作tail(tail(L))的結果是（）A.(e,f)

B.((e,f))C.(f)

D.()10.下列圖示的順序存儲結構表示的二叉樹是（）11.n個頂點的強連通圖中至少含有（）A.n-1條有向邊

B.n條有向邊 C.n(n-1)/2條有向邊

D.n(n-1)條有向邊

12.對關鍵字序列(56，23，78，92，88，67，19，34)進行增量為3的一趟希爾排序的結果為（）A.(19，23，56，34，78，67，88，92)

B.(23，56，78，66，88，92，19，34)C.(19，23，34，56，67，78，88，92)

D.(19，23，67，56，34，78，92，88)13.若在9階B-樹中插入關鍵字引起結點分裂，則該結點在插入前含有的關鍵字個數為（）

A.4

B.5 C.8

D.9 14.由同一關鍵字集合構造的各棵二叉排序樹（）A.其形態不一定相同，但平均查找長度相同

B.其形態不一定相同，平均查找長度也不一定相同 C.其形態均相同，但平均查找長度不一定相同 D.其形態均相同，平均查找長度也都相同

15.ISAM文件和VSAM文件的區別之一是（）A.前者是索引順序文件，后者是索引非順序文件 B.前者只能進行順序存取，后者只能進行隨機存取 C.前者建立靜態索引結構，后者建立動態索引結構 D.前者的存儲介質是磁盤，后者的存儲介質不是磁盤

二、填空題(本大題共10小題，每空2分，共20分)16.數據的邏輯結構在計算機存儲器內的表示，稱為數據的____________。17.刪除雙向循環鏈表中*p的前驅結點(存在)應執行的語句是____________。18.棧下溢是指在____________時進行出棧操作。

19.已知substr(s,i,len)函數的功能是返回串s中第i個字符開始長度為len的子串，strlen(s)函數的功能是返回串s的長度。若s=″ABCDEFGHIJK″,t=″ABCD″,執行運算substr(s,strlen(t), strlen(t))后的返回值為____________。

20.去除廣義表LS=(a1,a2,a3,??，an)中第1個元素，由其余元素構成的廣義表稱為LS的____________。

21.已知完全二叉樹T的第5層只有7個結點，則該樹共有____________個葉子結點。22.在有向圖中，以頂點v為終點的邊的數目稱為v的____________。

23.當關鍵字的取值范圍是實數集合時，無法進行箱排序和____________排序。24.產生沖突現象的兩個關鍵字稱為該散列函數的____________。

25.假設散列文件中一個桶能存放m個記錄，則桶“溢出”的含義是，當需要插入新的記錄時，該桶中____________。

三、解答題(本大題共4小題，每小題5分，共20分)26.假設以數組seqn［m］存放循環隊列的元素，設變量rear和quelen分別指示循環隊列中隊尾元素的位置和元素的個數。(1)寫出隊滿的條件表達式；(2)寫出隊空的條件表達式；

(3)設m=40,rear=13,quelen=19,求隊頭元素的位置；(4)寫出一般情況下隊頭元素位置的表達式。

27.已知一棵二叉樹的中序序列為ABCDEFG，層序序列為BAFEGCD，請畫出該二叉樹。28.畫出下圖所示有向圖的所有強連通分量。

29.對7個關鍵字進行快速排序，在最好的情況下僅需進行10次關鍵字的比較。(1)假設關鍵字集合為{1,2,3,4,5,6,7}，試舉出能達到上述結果的初始關鍵字序列；(2)對所舉序列進行快速排序，寫出排序過程。

四、算法閱讀題(本大題共4小題，每小題5分，共20分)30.閱讀下列算法，并回答問題：(1)設順序表L=(3,7,11,14,20,51)，寫出執行f30(&L,15)之后的L；(2)設順序表L=(4,7,10,14,20,51)，寫出執行f30(&L,10)之后的L；(3)簡述算法的功能。

void f30(SeqList*L, DataType x){

int i =0, j;

while(ilength && x>L->data［i］)i++;

if(ilength && x==L->data［i］){

for(j=i+1;jlength;j++)

L->data［j-1］=L->data［j］;

L->length--;

} else {

for(j=L->length;j>i;j--)

L->data［j］=L->data［j-1］;

L->data［i］=x;

L->length++;

} } 31.已知圖的鄰接表表示的形式說明如下：

#define MaxNum

//圖的最大頂點數 typedef struct node {

int

adjvex;

//鄰接點域

struct node *next;

//鏈指針域

} EdgeNode;

//邊表結點結構描述 typedef struct {

char vertex;

//頂點域

EdgeNode

*firstedge;

//邊表頭指針 } VertexNode;

//頂點表結點結構描述 typedef struct {

VertexNode adjlist［MaxNum］;

//鄰接表

int n, e;

//圖中當前的頂點數和邊數 } ALGraph;

//鄰接表結構描述

下列算法輸出圖G的深度優先生成樹(或森林)的邊。閱讀算法，并在空缺處填入合適的內容，使其成為一個完整的算法。

typedef enum {FALSE, TRUE} Boolean;Boolean visited［MaxNum］;void DFSForest(ALGraph *G){

int i;

for(i=0;in;i++)visited［i］=

(1)

;

for(i=0;in;i++)if(!visited［i］)DFSTree(G,i);} void DFSTree(ALGraph *G, int i){

EdgeNode *p;

visited［i］=TRUE;

p=G->adjlist［i］.firstedge;

while(p!=NULL){

if(!visited［p->adjvex］){

printf(″<%c,%c>″,G->adjlist［i］.vertex，G->adjlist［p->adjvex］.vertex);

(2)

;

}

(3)

;

} } 32.閱讀下列算法，并回答問題：

(1)假設數組L［8］={3,0,5,1,6,4,2,7}，寫出執行函數調用f32(L，8)后的L；(2)寫出上述函數調用過程中進行元素交換操作的總次數。void f32(int R［］,int n){

int i,t;

for(i=0;i

while(R［i］!=i){

t=R［R［i］］;

R［R［i］］=R［i］;

R［i］=t;

} } 33.已知帶頭結點的單鏈表中的關鍵字為整數，為提高查找效率，需將它改建為采用拉鏈法處理沖突的散列表。設散列表的長度為m，散列函數為Hash(key)=key%m。鏈表的結點結構為：。請在空缺處填入適當內容，使其成為一個完整算法。void f33(LinkList L, LinkList H［］, int m){//由帶頭結點的單鏈表L生成散列表H，散列表生成之后原鏈表不再存在 int i,j;

LinkList p,q;

for(i=0;i

H［i］=

(1)

;

p=L->next;

while(p)

{

q=p->next;

j=p->key%m;

(2)

;

H［j］=p;

(3)

;

}

free(L);

}

五、算法設計題(本大題10分)34.假設以帶雙親指針的二叉鏈表作為二叉樹的存儲結構，其結點結構的類型說明如下所示： typedef char DataType;typedef struct node {

DataType data;

struct node *lchild, *rchild;

//左右孩子指針

struct node *parent;

//指向雙親的指針 } BinTNode;typedef BinTNode *BinTree;若px為指向非空二叉樹中某個結點的指針，可借助該結構求得px所指結點在二叉樹的中序序列中的后繼。

(1)就后繼的不同情況，簡要敘述實現求后繼操作的方法；

(2)編寫算法求px所指結點的中序序列后繼，并在算法語句中加注注釋。數據結構標準答案

一、單項選擇題 1.(B)2.(D)3.(A)4.(A)5.(D)6.(C)7.(C)8.(A)9.(B)10.(A)11.(B)12.(D)13.(C)14.(B)15.(C)

二、填空題(本大題共10小題，每空2分，共20分)16.存儲結構 17.q = p->pre;q->pre->next = p;p->pre = q->pre;free(q);18.棧空

19.“DEFG” //注意雙引號不能少 20.表尾

21.２^(I-2)+M/2 葉子結點． 22.入度 23.基數 24.同義詞

25.已有m個同義詞記錄

三、解答題(本大題共4小題，每小題5分，共20分)26.(1)quelen == m(2)quelen == 0(3)(13quelen + m)% m 27.B

/

A F

/

E G

/

C

D 28.3個: a、bce、dfg 29.我們知道，對n個關鍵自序列進行一趟快速排序，要進行n-1次比較，也就是基準和其他n-1個關鍵字比較。

這里要求10次，而71)= 10，這就要求2趟快速排序后，算法結束。所以，列舉出來的序列，要求在做partition的時候，正好將序列平分(1)4 1 3 2 6 5 7

或 4 1 3 7 6 5 2 或 4 5 3 7 6 1 2 或 4 1 3 5 6 2 7.......(2)自己列吧 :)

四、算法閱讀題(本大題共4小題，每小題5分，共20分)30.(1)L=(3,7,11,14,15,20,51)(2)L=(4,7,14,20,51)(3)在順序表L中查找數x, 找到，則刪除x，沒找到，則在適當的位置插入x，插入后，L依然有序.31.(1)FALSE //初始化為未訪問

(2)DSFTree(G, p->adjvex);//從相鄰結點往下繼續深度搜索(3)p = p->next;//下一個未訪問的相鄰結點

32.(1)L = { 0, 1, 2, 3, 4, 5, 6, 7 };(2)5次

33.(1)NULL

//初始化

(2)p->next = H[ j ] //和下面一句完成頭插法(3)p = q;

//繼續遍歷L

五、算法設計題(本大題10分)34.1)

a)*px 有右孩子，則其右孩子為其中序序列中的后繼

b)*px 無右孩子，從*px開始回溯其祖先結點，找到第1個身份為左孩子的結點，找到，則該結點的父結點為*px的中序序列中的后繼。找不到，則無后繼。2)BinTNode * fintNext(BinTNode * px){ if(px-> rchild)return px->rchild;//*px 有右孩子

BinTNode *q, *qp;

q = px;while(qp = q->parent){ //未回溯到根結點

if(qp->lchild == q)return qp;//找到1)b)所述結點

q = qp;//往上回溯 }

return NULL;//未找到 }

第四篇：全國2012年10月數據結構導論試題及答案

全國2012年10月高等教育自學考試

數據結構導論試題及答案

課程代碼：02142 請考生按規定用筆將所有試題的答案涂、寫在答題紙上。

選擇題部分

注意事項：

1.答題前，考生務必將自己的考試課程名稱、姓名、準考證號用黑色字跡的簽字筆或鋼筆填寫在答題紙規定的位置上。

2.每小題選出答案后，用2B鉛筆把答題紙上對應題目的答案標號涂黑。如需改動，用橡皮擦干凈后，再選涂其他答案標號。不能答在試題卷上。

一、單項選擇題(本大題共15小題，每小題2分，共30分)在每小題列出的四個備選項中只有一個是符合題目要求的。錯選、多選或未選均無分。1.下面幾種算法時間復雜度階數中，值最大的是

D A.O(nlog2n)C.O(n)

B.O(n2)D.O(2n)2.即使輸入非法數據，算法也能適當地做出反應或進行處理，不會產生預料不到的運行結果，這種算法好壞的評價因素稱為 C A.正確性

C.健壯性

B.易讀性

D.時空性

3.設順序表的長度為100，則在第40個元素之后插入一個元素所需移動元素的個數為 B A.40 C.61

B.60 D.100 4.設帶頭結點的單循環鏈表的頭指針為head，則判斷該鏈表是否為空的條件是 A A.head->next==head C.head!=NULL

B.head->next==NULL D.head==NULL 5.在鏈棧的運算中，不需要判斷棧是否為空的是B ．．．A.出棧

C.取棧頂元素

B.進棧

D.求鏈棧的元素個數

6.一個隊列的輸入序列是A，B，C，D，則該隊列的輸出序列是A A.A，B，C，D C.D，C，B，A

B.B，C，D，A D.C，D，B，A 7.以行序為主序的二維數組a［3］［5］中，第一個元素a［0］［0］的存儲地址是100，每個元素占2個存儲單元，則a［1］［2］的存儲地址是C A.100 C.114

B.108 D.116 8.對任何一棵二叉樹T，若葉結點數為5個，則度為2的結點個數為A A.4 C.6

9.m個葉結點的哈夫曼樹中，其結點總數為D A.m C.2m

B.2m+1 D.2m-1 B.5 D.無法確定

10.二叉樹的中序遍歷序列中，結點P排在結點Q之前的條件是A A.在二叉樹中P在Q的左邊

C.在二叉樹中P是Q的祖先

11.有10個頂點的無向完全圖的邊數是B A.11 C.55

B.45 D.90

B.在二叉樹中P在Q的右邊

D.在二叉樹中P是Q的子孫

12.在帶權有向圖中求兩個結點之間的最短路徑可以采用的算法是A A.迪杰斯特拉（Dijkstra）算法

C.普里姆（Prim）算法

B.克魯斯卡爾（Kruskal）算法 D.深度優先搜索（DFS）算法

13.二分查找（Binary Search）算法的時間復雜度是D A.O（n2）

C.O（n）

B.O（nlog2n）

D.O（log2n）

14.在一棵初始時為空的二叉樹中，依次插入鍵值序列50，72，43，85，75，20，38，45，65，60，構造對應的二叉排序樹以后，查找元素60要進行的比較次數是C A.2 C.4

15.快速排序屬于B A.插入排序

C.選擇排序

B.交換排序

D.歸并排序 B.3 D.5

非選擇題部分

注意事項：

用黑色字跡的簽字筆或鋼筆將答案寫在答題紙上，不能答在試題卷上。

二、填空題(本大題共13小題，每小題2分，共26分)

16.下面算法程序段的時間復雜度為_ for(i=1;i<=n;i++)for(j=1;j<=n;j++)for(k=1;k<=n;k++)x++；

___。

17.所有存儲結點存放在一個連續的存儲區里，利用結點在存儲器中的相對位置來表示數據元素之間的邏輯關系。這種存儲方式是___順序存儲方式___。

18.單鏈表中指針p指向結點A，若要刪除A之后的結點（存在且不釋放存儲空間），則需要修改指針的操作為p->next=__ ___。

19.在帶有頭結點的單鏈表head中，首結點的指針為_head->next___。20.在棧結構中，允許插入和刪除的一端稱為__棧頂___。

21.C程序中，將對稱矩陣A［n］［n］的下三角元素壓縮存儲到n(n+1)/2個元素的一維數組M中，設a［i］［j］（i≥j）存放在數組M［k］中，則k的值（用i,j表示）為__ 22.具有64個結點的完全二叉樹的深度為___ 7__。

23.某二叉樹的先序遍歷序列為AJKLMNO，中序遍歷序列為JLKANMO，則根結點A的右子樹中的結點個數為_3___。?011???24.三個頂點v1,v2,v3的圖的鄰接矩陣為?101?，則該圖中頂點v2的出度為__2__。

?000???__。

25.除第一個頂點和最后一個頂點相同外，其余頂點不重復的回路，稱為__簡單回路或簡單環____。

26.在順序查找、二分查找、散列查找和索引順序查找四種查找方法中，平均查找長度與元素個數沒有關系的查找方法是_散列查找____。

27.堆排序算法的時間復雜度為__

____。

28.如果要將序列{60，18，28，69，99，75，78}建成堆，則只需把60與__ 18____相互交換。

三、應用題(本大題共5小題，每小題6分，共30分)29.如題29圖所示，在棧的輸入端依次輸入元素A，B，C，試寫出在棧的輸出端可以得到的所有輸出序列，并給出每個序列的操作過程（用push（A）表示A進棧，pop(A)表示A出棧）。

題29圖

答：

30.將題30圖所示的一棵樹轉換為對應的二叉樹。

題30圖

答：

31.已知含五個頂點A，B，C，D，E的連通帶權圖的鄰接矩陣如題31圖所示，試畫出它所表示的連通帶權圖及該連通帶權圖的最小生成樹。

題31圖

答：

32.題32圖所示二叉排序樹的各結點的值為1~10中的數，試標出各結點的數值。

題32圖

33.設散列函數H（key）=key mod 11(mod表示求余運算)，給出鍵值序列為66,13,41,15,44,6,68,17,26,31,39,46,用鏈地址法解決沖突，試畫出相應的散列表，并計算在等概率情況下查找成功時的平均查找長度。

四、算法設計題(本大題共2小題，每小題7分，共14分)34.帶頭結點的單鏈表的結點結構如下：

typedef struct node { int data;struct node *next;}Node,*LinkList;試編寫單鏈表的刪除運算算法void DeleteLinklist(LinkList head，int i)

35.寫出直接選擇排序算法。

第五篇：2012廣西壯族自治區JAVA版數據結構試題及答案

1、下列序列中，執行第一趟快速排序后得到的序列是（A）。A）[d,a,e,d,b]f[h,g] B)[c,e,a,d]f[h,g,b] C)[g,a,e,c,b]f[d,h] D)[a,b,c,d,]f[e,g,h]

2、設給定問題的規模為變量n，解決該問題的算法所需時間為Tn=O(f(n)),Tn表示式中記號O表示（A）。

A）一個數量級別 B）一個平均值 C）一個最大值 D）一個均方值

3、（C）在進行插入操作時，常產生假溢出現象。A）順序棧 B）循環隊列 C）順序隊列 D）鏈隊列

4、設有一個10階的對稱矩陣A，采用壓縮存儲方式，以行序為主存儲，a??11為第一個元素，其存儲地址為1，每元素占1個地址空間，則a85的地址為（B）。A）13 B）33 C）18 D）40

5、n個頂點的圖的最小生成樹必定（D），是不正確的描述。A）不唯一 B）權的總和唯一

C）不含回路 D）有n條邊

6、用一維數組A進行順序存儲時，若起始地址為loc(A1)，元素長度為c，則A的第i個數組單元在存放地址loc(Ai)，等于（B）。A）loc(A1)+i*c B）loc(A1)+(i-1)*c C）loc(A1)+i*c+1 D）loc(A1)+(i+1)*c

7、與無向圖相關的術語有（C）。A）強連通圖 B）入度 C）路徑 D）弧

8、鏈式存儲的存儲結構所占存儲空間（A）。

A）分兩部分，一部分存放結點值，另一部分存放表示結點間關系的指針 B）只有一部分，存放結點值

C）只有一部分，存儲表示結點間關系的指針

D）分兩部分，一部分存放結點值，另一部分存放結點所占單元數

9、若采用鄰接矩陣法存儲一個n個頂點的無向圖，則該鄰接矩陣是一個（D）。A）上三角矩陣 B)稀疏矩陣 C)對角矩陣 D)對稱矩陣

10、在一個具有n個單元的順序棧中，假定以地址低端（即0單元）作為棧底，以top作為棧頂指針，當做出棧處理時，top變化為（C）。

A）top不變 B）top=0 C）top--D）top++

11、棧進行插入和刪除操作的特點是（A）。A）LIFO B）FIFO C）FCFS D）HPF

12、與無向圖相關的術語有（C）。A）強連通圖 B）入度 C）路徑 D）弧

13、n個頂點，e條邊的有向圖的鄰接矩陣中非零元素有（C）個。A）n B）2e C）e D）n+e

14、已知棧的最大容量為4。若進棧序列為1，2，3，4，5，6，且進棧和出棧可以穿插進行,則可能出現的出棧序列為（C）。

A)5，4，3，2，1，6

B)2，3，5，6，1，4 C)3，2，5，4，1，6

D)1，4，6，5，2，3

15、在一個鏈隊列中，假定front和rear分別為隊首和隊尾指針，則刪除一個結點的操作為（B）。

A)rear=rear->next;B)front=front->next;C)rear=front->next;

D)front=rear->next;