算法與數(shù)據(jù)結構試題及答案

1、數(shù)據(jù)結構試卷（一）一、單選題（每題2 分，共 20 分）1.棧和隊列的共同特點是()。只允許在端點處插入和刪除元素都是先進后出都是先進先出沒有共同點用鏈接方式存儲的隊列，在進行插入運算時( ).A.僅修改頭指針B.頭、尾指針都要修改C.僅修改尾指針D.頭、尾指針可能都要修改以下數(shù)據(jù)結構中哪一個是非線性結構？( )4.A. 隊列B. 棧C. 線性表D.二叉樹676，每個元設有一個二維數(shù)組Am n ，假設 A00 存放位置在644(10)，A22 存放位置在(10)素占一個空間，問A33 (10) 存放在什么位置？腳注(10)表示用 10 進制表示。A688B678C 692D6965.樹最適合用

2、來表示 ()。A. 有序數(shù)據(jù)元素B. 無序數(shù)據(jù)元素C.元素之間具有分支層次關系的數(shù)據(jù)D. 元素之間無聯(lián)系的數(shù)據(jù)二叉樹的第 k 層的結點數(shù)最多為 ( ).A 2k-1B.2K+1C.2K-1D. 2 k-1若有 18 個元素的有序表存放在一維數(shù)組A19 中，第一個元素放 A1 中，現(xiàn)進行二分查找，則查找 A 3的比較序列的下標依次為 ()A. 1，2，3B. 9，5，2， 3C. 9，5，3D. 9，4，2，3對 n 個記錄的文件進行快速排序，所需要的輔助存儲空間大致為對于線性表（ 7， 34，55， 25， 64，46， 20， 10）進行散列存儲時，若選用H（ K） =K %9作為散列函數(shù)，

3、則散列地址為1 的元素有（）個，A 1B2C 3D 410. 設有 6 個結點的無向圖，該圖至少應有()條邊才能確保是一個連通圖。A.5B.6C.7D.8二、填空題（每空1 分，共 26 分）通常從四個方面評價算法的質(zhì)量：_、 _ 、 _和 _。一個算法的時間復雜度為 (n3 +n2log 2n+14n)/n2，其數(shù)量級表示為 _。假定一棵樹的廣義表表示為A（ C，D（ E，F(xiàn)，G）， H（ I ，J），則樹中所含的結點數(shù)為 _個，樹的深度為 _，樹的度為 _。后綴算式 9 2 3 +- 10 2 / -的值為 _ 。中綴算式（ 3+4X ） -2Y/3 對應的后綴算式為_ 。若用鏈表存儲一棵

4、二叉樹時， 每個結點除數(shù)據(jù)域外， 還有指向左孩子和右孩子的兩個指針。 在這種存儲結構中， n 個結點的二叉樹共有 _個指針域，其中有 _個指針域是存放了地址，有 _ 個指針是空指針。對于一個具有 n 個頂點和 e 條邊的有向圖和無向圖，在其對應的鄰接表中，所含邊結點分別有_個和 _個。AOV 網(wǎng)是一種 _ 的圖。在一個具有 n 個頂點的無向完全圖中， 包含有 _條邊，在一個具有 n 個頂點的有向完全圖中，包含有 _條邊。假定一個線性表為 (12,23,74,55,63,40) ，若按 Key % 4 條件進行劃分， 使得同一余數(shù)的元素成為一個子 表 ， 則 得 到 的 四 個 子 表 分 別

5、為 _ 、 _ 、_ 和 _ 。10.向一棵 B_樹插入元素的過程中，若最終引起樹根結點的分裂，則新樹比原樹的高度_。在堆排序的過程中， 對任一分支結點進行篩運算的時間復雜度為 _，整個堆排序過程的時間復雜度為 _。在快速排序、堆排序、歸并排序中，_排序是穩(wěn)定的。三、計算題（每題6 分，共 24分）1. 在如下數(shù)組A 中鏈接存儲了一個線性表，表頭指針為A 0.next ，試寫出該線性表。A01234567data605078903440next3572041請畫出下圖的鄰接矩陣和鄰接表。已知一個圖的頂點集 V 和邊集 E 分別為： V=1,2,3,4,5,6,7; E=(1,2)3,(1,3)

6、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;用克魯斯卡爾算法得到最小生成樹，試寫出在最小生成樹中依次得到的各條邊。畫出向小根堆中加入數(shù)據(jù) 4, 2, 5, 8, 3 時，每加入一個數(shù)據(jù)后堆的變化。四、閱讀算法（每題7 分，共 14 分）1.LinkList mynote(LinkList L)/L 是不帶頭結點的單鏈表的頭指針if(L&L-next)q=L ； L=L next ； p=L ；S1：while(p next) p=p next；S2：p next=q ； qnext=

7、NULL；returnL；請回答下列問題：1）說明語句 S1 的功能；2）說明語句組 S2 的功能；3）設鏈表表示的線性表為（ a1,a2, ,an） ,寫出算法執(zhí)行后的返回值所表示的線性表。void ABC(BTNode * BT)ifBT ABC (BT-left);ABC (BT-right);coutdatadata)item=BST-data;/return _;查找成功else if(itemdata)return Find(_,item);else return Find(_,item);/if六、編寫算法（共8 分）統(tǒng)計出單鏈表HL 中結點的值等于給定值X 的結點數(shù)。int C

8、ountX(LNode* HL,ElemType x)數(shù)據(jù)結構試卷（二）一、選擇題 (24 分 )1下面關于線性表的敘述錯誤的是（）。線性表采用順序存儲必須占用一片連續(xù)的存儲空間線性表采用鏈式存儲不必占用一片連續(xù)的存儲空間線性表采用鏈式存儲便于插入和刪除操作的實現(xiàn)線性表采用順序存儲便于插入和刪除操作的實現(xiàn)2設哈夫曼樹中的葉子結點總數(shù)為m，若用二叉鏈表作為存儲結構，則該哈夫曼樹中總共有（）個空指針域。(A) 2m-1(B) 2m(C) 2m+1(D) 4m3設順序循環(huán)隊列Q0： M-1 的頭指針和尾指針分別為F 和 R，頭指針 F 總是指向隊頭元素的前一位置，尾指針R 總是指向隊尾元素的當前位置

9、，則該循環(huán)隊列中的元素個數(shù)為（）。(A) R-F(B) F-R(C) (R-F+M) M (D) (F-R+M) M4設某棵二叉樹的中序遍歷序列為ABCD ，前序遍歷序列為CABD ，則后序遍歷該二叉樹得到序列為（）。(A) BADC(B) BCDA(C) CDAB(D) CBDA5設某完全無向圖中有 n 個頂點，則該完全無向圖中有（）條邊。(A) n(n-1)/2(B) n(n-1)(C) n 2(D) n 2-16設某棵二叉樹中有 2000 個結點，則該二叉樹的最小高度為（）。(A) 9(B) 10(C) 11(D) 127設某有向圖中有n 個頂點，則該有向圖對應的鄰接表中有（）個表頭結點

10、。(A) n-1(B) n(C) n+1(D) 2n-18設一組初始記錄關鍵字序列(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 分 )為了能有效地應用 HASH查找技術，必須解決的兩個問題是_和_。下面程序段的功能實現(xiàn)數(shù)據(jù) x 進棧，要求在下劃線處填上正確的語句。typedef struct int s100; int top; sqstack;void push(sqstack &stack,int x)if

11、 (stack.top=m- 1) printf(“ overflow ” );else _;_;中序遍歷二叉排序樹所得到的序列是 _序列（填有序或無序） 。快速排序的最壞時間復雜度為 _，平均時間復雜度為 _。設某棵二叉樹中度數(shù)為 0 的結點數(shù)為 N0，度數(shù)為 1 的結點數(shù)為 N1，則該二叉樹中度數(shù)為 2 的結點數(shù)為 _；若采用二叉鏈表作為該二叉樹的存儲結構，則該二叉樹中共有_個空指針域。6.設某無向圖中頂點數(shù)和邊數(shù)分別為n 和 e，所有頂點的度數(shù)之和為d，則e=_。設一組初始記錄關鍵字序列為 (55 ，63， 44， 38， 75， 80， 31， 56) ，則利用篩選法建立的初始堆為_。

12、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) ，查找方法用二分查找，要求計算出

13、查找關鍵字 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），要求設計一個算法能夠在的時間復雜度內(nèi)將線性表劃分成兩部

14、分，其中左半部分的每個關鍵字均小于右半部分的每個關鍵字均大于等于Ki 。O(n)Ki ，2 設有兩個集合 A 和集合 B，要求設計生成集合 C=A B 的算法，其中集合 A、B 和C用鏈式存儲結構表示。數(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 是（）。線性結構 (B) 樹型結構 (C) 物理結構 (D) 圖型結構2下面程序的時間復雜為（）for （ i=1 ， s=0； i=n ；i+ ）t=1 ；

15、for(j=1； jnext ；p-data=q-data ； p-next=q-next ；free(q) ；q=p-next ；q-data=p-data ； p-next=q-next ；free(q) ；q=p-next ；p-next=q-next ； free(q) ；q=p-next ；p-data=q-data ； free(q) ；4設有 n 個待排序的記錄關鍵字，則在堆排序中需要（）個輔助記錄單元。(A) 1(B) n(C) nlog 2n(D) n 25設一組初始關鍵字記錄關鍵字為(20 ，15，14， 18， 21，36，40，10) ，則以20為基準記錄的一趟快速排序

16、結束后的結果為( )。10 ， 15， 14， 18， 20， 36， 40， 2110 ， 15， 14， 18， 20， 40， 36， 2110 ， 15， 14， 20， 18， 40， 36， 2l15 ， 10， 14， 18， 20， 36， 40， 216設二叉排序樹中有n 個結點，則在二叉排序樹的平均平均查找長度為（）。(A) O(1)(B) O(log2 n)(C)(D) O(n2 )7設無向圖 G中有 n 個頂點 e 條邊，則其對應的鄰接表中的表頭結點和表結點的個數(shù)分別為（）。(A) n， e(B) e ， n(C) 2n ， e(D) n ， 2e8. 設某強連通圖中有

17、 n 個頂點，則該強連通圖中至少有（）條邊。(A) n(n-1)(B) n+1(C) n(D) n(n+1)9設有 5000 個待排序的記錄關鍵字，如果需要用最快的方法選出其中最小的10個記錄關鍵字，則用下列（）方法可以達到此目的。快速排序 (B) 堆排序(C) 歸并排序 (D) 插入排序下列四種排序中（）的空間復雜度最大。(A)插入排序(B)冒泡排序 (C)堆排序(D)歸并排序二、填空殖 (每空 1 分 共 20分)數(shù)據(jù)的物理結構主要包括 _和 _兩種情況。設一棵完全二叉樹中有 500 個結點，則該二叉樹的深度為 _；若用二叉鏈表作為該完全二叉樹的存儲結構，則共有_個空指針域。設輸入序列為

18、1、2、 3，則經(jīng)過棧的作用后可以得到 _種不同的輸出序列。設有向圖 G用鄰接矩陣 Ann 作為存儲結構， 則該鄰接矩陣中第 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 是否在查找表中。不論

19、是順序存儲結構的棧還是鏈式存儲結構的棧，其入棧和出棧操作的時間復雜度均為 _。10. 設有 n 個結點的完全二叉樹，如果按照從自上到下、從左到右從1 開始順序編號，則第i個結點的雙親結點編號為_，右孩子結點的編號為_。設一組初始記錄關鍵字為 (72 ， 73，71， 23， 94， 16， 5) ，則以記錄關鍵字 72為基準的一趟快速排序結果為 _。設有向圖 G中有向邊的集合 E=， ， ，則該圖的一種拓撲序列為 _。13. 下列算法實現(xiàn)在順序散列表中查找值為x 的關鍵字，請在下劃線處填上正確的語句。struct recordint key; int others;int hashsqsear

20、ch(struct record hashtable ,int k)int i,j;j=i=k % p;while(hashtablej.key!=k&hashtablej.flag!=0)j=(_)%m;if(i=j)return(-1);if (_ ) return(j); else return(-1);14. 下列算法實現(xiàn)在二叉排序樹上查找關鍵值k，請在下劃線處填上正確的語句。typedef struct nodeint key; struct node *lchild; struct node *rchild;bitree;bitree*bstsearch(bitree *t, in

21、tk)if (t=0 ) return(0);elsewhile (t!=0)if(t-key=k)_;elseif(t-keyk)t=t-lchild;else_;三、計算題 ( 每題 10 分，共 30 分 )1.已知二叉樹的前序遍歷序列是AEFBGCDHIKJ ，中序遍歷序列是EFAGBCHKIJD ，畫出此二叉樹，并畫出它的后序線索二叉樹。2已知待散列的線性表為（ 36， 15， 40， 63， 22），散列用的一維地址空間為 0.6，假定選用的散列函數(shù)是 H（ K ） = K mod 7 ，若發(fā)生沖突采用線性探查法處理，試：（ 1）計算出每一個元素的散列地址并在下圖中填寫出散列表：0

22、123456（ 2）求出在查找每一個元素概率相等情況下的平均查找長度。3已知序列（10，18， 4，3， 6， 12， 1， 9，18， 8）請用快速排序寫出每一趟排序的結果。四、算法設計題 ( 每題 15 分，共 30 分 )1 設計在單鏈表中刪除值相同的多余結點的算法。2 設計一個求結點x 在二叉樹中的雙親結點算法。數(shù)據(jù)結構試卷（四）一、選擇題 ( 每題 1 分共 20 分)1設一維數(shù)組中有n 個數(shù)組元素，則讀取第 i 個數(shù)組元素的平均時間復雜度為（）。(A) O(n)(B) O(nlog2n)(C) O(1)(D) O(n 2 )2設一棵二叉樹的深度為k，則該二叉樹中最多有（）個結點。(

23、A) 2k-1(B) 2 k(C) 2 k-1(D) 2 k-13設某無向圖中有n 個頂點 e 條邊，則該無向圖中所有頂點的入度之和為（）。(A) n(B) e(C) 2n(D) 2e4在二叉排序樹中插入一個結點的時間復雜度為（）。(A) O(1)(B) O(n)(C) O(log 2n)(D) O(n 2 )5設某有向圖的鄰接表中有n 個表頭結點和m 個表結點，則該圖中有（）條有向邊。(A) n(B) n-1(C) m(D) m-16設一組初始記錄關鍵字序列為(345 ， 253，674， 924， 627) ，則用基數(shù)排序需要進行（）趟的分配和回收才能使得初始關鍵字序列變成有序序列。(A)

24、 3(B) 4(C) 5(D) 87設用鏈表作為棧的存儲結構則退棧操作（）。(A)必須判別棧是否為滿(B)必須判別棧是否為空(C)判別棧元素的類型(D)對棧不作任何判別8下列四種排序中（）的空間復雜度最大?？焖倥判?(B) 冒泡排序 (C) 希爾排序 (D) 堆9設某二叉樹中度數(shù)為0 的結點數(shù)為N0 ，度數(shù)為 1 的結點數(shù)為Nl ，度數(shù)為 2 的結點數(shù)為 N2，則下列等式成立的是（）。(A) N 0=N1+1(B) N 0=Nl +N2(C) N 0=N2+1(D) N 0=2N1 +l10. 設有序順序表中有n 個數(shù)據(jù)元素，則利用二分查找法查找數(shù)據(jù)元素X 的最多比較次數(shù)不超過（）。(A) l

25、og2 n+1(B) log2n-1(C) log2 n(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 設初始記錄關鍵字序列為(K 1，K2， ，Kn) ，則用篩選法思想建堆必須從第_個元素開始進行篩選。6 設哈夫曼樹中共

26、有99 個結點，則該樹中有_個葉子結點；若采用二叉鏈表作為存儲結構，則該樹中有_個空指針域。7 設有一個順序循環(huán)隊列中有M 個存儲單元，則該循環(huán)隊列中最多能夠存儲_個隊列元素； 當前實際存儲 _個隊列元素 （設頭指針 F指向當前隊頭元素的前一個位置，尾指針指向當前隊尾元素的位置）。8 設順序線性表中有n 個數(shù)據(jù)元素，則第i 個位置上插入一個數(shù)據(jù)元素需要移動表中元素；刪除第i 個位置上的數(shù)據(jù)元素需要移動表中_個元素。_個數(shù)據(jù)9 設一組初始記錄關鍵字序列為(20， 18， 22， 16， 30， 19)，則以20 為中軸的一趟快速排序結果為_ 。10設一組初始記錄關鍵字序列為(20，18， 22，

27、 16， 30， 19)，則根據(jù)這些初始關鍵字序列建成的初始堆為 _ 。11設某無向圖G 中有 n 個頂點， 用鄰接矩陣條件是 _ 。A 作為該圖的存儲結構，則頂點i 和頂點j 互為鄰接點的12設無向圖對應的鄰接矩陣為A ，則 A 中第 i 上非 0 元素的個數(shù) _第 i 列上非 0 元素的個數(shù)（填等于，大于或小于）。13設前序遍歷某二叉樹的序列為ABCD ，中序遍歷該二叉樹的序列為BADC ，則后序遍歷該二叉樹的序列為 _ 。14設散列函數(shù)H(k)=k mod p ，解決沖突的方法為鏈地址法。要求在下列算法劃線處填上正確的語句完成在散列表hashtalbe 中查找關鍵字值等于k 的結點，成功

28、時返回指向關鍵字的指針，不成功時返回標志 0。typedef struct node int key; struct node *next; lklist; void createlkhash(lklist *hashtable ) int i,k;lklist *s;for(i=0;im;i+)_;for(i=0;ikey=ai;k=ai % p; s-next=hashtablek;_;三、計算題 ( 每題 10 分，共 30 分 )1、畫出廣義表LS=( ) , (e) , (a , (b , c , d )的頭尾鏈表存儲結構。2、下圖所示的森林：求樹（ a）的先根序列和后根序列；求森林

29、先序序列和中序序列；3）將此森林轉換為相應的二叉樹；3、設散列表的地址范圍是 0.9 ，散列函數(shù)為H（key ） = （key 2 +2）MOD 9,并采用鏈表處理沖突，請畫出元素7、4、 5、 3、6、2、8、 9 依次插入散列表的存儲結構。四、算法設計題 ( 每題 10 分，共 30 分 )1 設單鏈表中有僅三類字符的數(shù)據(jù)元素( 大寫字母、數(shù)字和其它字符) ，要求利用原單鏈表中結點空間設計出三個單鏈表的算法，使每個單鏈表只包含同類字符。設計在鏈式存儲結構上交換二叉樹中所有結點左右子樹的算法。在鏈式存儲結構上建立一棵二叉排序樹。數(shù)據(jù)結構試卷（五）一、選擇題 (20 分 )1數(shù)據(jù)的最小單位是（

30、）。數(shù)據(jù)項(B) 數(shù)據(jù)類型 (C) 數(shù)據(jù)元素 (D) 數(shù)據(jù)變量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， 203設一組初始記錄關鍵字序列為 (25， 50， 15，35， 80，85，20，40， 36，70)，其中含有的有序子表，則用歸并排序的方法對該記錄關鍵字序列進行一趟歸并后的結果為（5 個長度為）。215 ， 25， 35， 50， 2

31、0， 40， 80， 85， 36， 7015 ，25， 35，50， 80， 20， 85， 40， 70， 3615 ，25， 35，50， 80， 85， 20， 36， 40， 7015 ， 25， 35， 50， 80， 20， 36， 40， 70， 854函數(shù)substr(“DATASTRUCTURE”， 5，9)的返回值為（）。(A)“ STRUCTURE”(B)“ DATA”(C)“ ASTRUCTUR”(D)“ DATASTRUCTURE”5設一個有序的單鏈表中有的時間復雜度為（）。n 個結點，現(xiàn)要求插入一個新結點后使得單鏈表仍然保持有序，則該操作(A) O(log2n)(

32、B) O(1)(C) O(n2)(D) O(n)6設一棵m 叉樹中度數(shù)為0 的結點數(shù)為N0，度數(shù)為1 的結點數(shù)為Nl ， ，度數(shù)為 m的結點數(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)Nm7設有序表中有1000個元素，則用二分查找查找元素X 最多需要比較（）次。(A) 25(B) 10(C) 7(D) 18設連通圖G 中的邊集E=(a ，b) ，(a，e)，(a，c)，(b，e)，(e，d) ，(d，f) ，(f ， c) ，則從頂點a 出發(fā)可以得到一種

33、深度優(yōu)先遍歷的頂點序列為（）。(A) abedfc(B) acfebd(C) aebdfc(D) aedfcb9設輸入序列是1、 2、3、 、n，經(jīng)過棧的作用后輸出序列的第一個元素是n，則輸出序列中第i個輸出元素是（）。(A) n-i(B) n-1-i(C) n+1-i(D)不能確定10設一組初始記錄關鍵字序列為(45 ，80，55，40，42，85) ，則以第一個記錄關鍵字一趟快速排序的結果是（）。(A) 40 ， 42， 45， 55， 80， 83(B) 42 ， 40， 45， 80， 85， 8845 為基準而得到(C) 42 ，40， 45， 55， 80，85 (D) 42 ，

34、40， 45， 85， 55， 80二、填空題 ( 共 20 分)1.設有一個順序共享棧S0 ： n-1 ，其中第一個棧項指針top1 的初值為 -1 ，第二個棧頂指針 top2 的初值為 n，則判斷共享棧滿的條件是_。在圖的鄰接表中用順序存儲結構存儲表頭結點的優(yōu)點是_。設有一個 n 階的下三角矩陣 A，如果按照行的順序將下三角矩陣中的元素 （包括對角線上元素） 存放在 n(n+1) 個連續(xù)的存儲單元中， 則 Aij與 A00之間有_個數(shù)據(jù)元素。棧的插入和刪除只能在棧的棧頂進行，后進棧的元素必定先出棧，所以又把棧稱為 _表；隊列的插入和刪除運算分別在隊列的兩端進行，先進隊列的元素必定先出隊列，

35、所以又把隊列稱為 _表。設一棵完全二叉樹的順序存儲結構中存儲數(shù)據(jù)元素為ABCDEF，則該二叉樹的前序遍歷序列為_，中序遍歷序列為_，后序遍歷序列為_。設一棵完全二叉樹有128 個結點，則該完全二叉樹的深度為_，有_個葉子結點。設有向圖 G 的存儲結構用鄰接矩陣 A 來表示，則 A 中第 i 行中所有非零元素個數(shù)之和等于頂點i的 _，第i列中所有非零元素個數(shù)之和等于頂點i的_。設一組初始記錄關鍵字序列 (k 1 ， k2， ， kn) 是堆，則對 i=1 ， 2， ， n/2 而言滿足的條件為 _。下面程序段的功能是實現(xiàn)冒泡排序算法，請在下劃線處填上正確的語句。void bubble(intrn

36、)for(i=1;i=n-1; i+)for(exchange=0,j=0; jrj+1)temp=rj+1;_;rj=temp;exchange=1;if (exchange=0) return ；下面程序段的功能是實現(xiàn)二分查找算法，請在下劃線處填上正確的語句。struct recordint key; int others; int bisearch(struct record r , int k)int low=0,mid,high=n-1;while(lownext=0(C) head-next=head(D) head!=04時間復雜度不受數(shù)據(jù)初始狀態(tài)影響而恒為O(nlog2n) 的

37、是（）。堆排序(B) 冒泡排序 (C) 希爾排序 (D) 快速排序5設二叉樹的先序遍歷序列和后序遍歷序列正好相反，則該二叉樹滿足的條件是（）。(A)空或只有一個結點(B)高度等于其結點數(shù)(C)任一結點無左孩子(D)任一結點無右孩子6一趟排序結束后不一定能夠選出一個元素放在其最終位置上的是（）。堆排序(B) 冒泡排序 (C) 快速排序 (D) 希爾排序7設某棵三叉樹中有40 個結點，則該三叉樹的最小高度為（）。(A) 3(B) 4(C) 5(D) 68順序查找不論在順序線性表中還是在鏈式線性表中的時間復雜度為（）。(A) O(n)21/2(D) O(1og 2n)(B) O(n )(C) O(n

38、 )9二路歸并排序的時間復雜度為（）。(A) O(n)(B) O(n2)(C) O(nlog2n) (D) O(1og2n)10. 深度為 k 的完全二叉樹中最少有（）個結點。(A) 2 k-1 -1(B) 2 k-1(C) 2 k-1 +1(D) 2 k-111. 設指針變量 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=fro

39、nt； front=s ；12. 設某無向圖中有n 個頂點 e 條邊，則建立該圖鄰接表的時間復雜度為（）。(A) O(n+e)(B) O(n2)(C) O(ne)(D) O(n 3 )13. 設某哈夫曼樹中有 199 個結點，則該哈夫曼樹中有（）個葉子結點。(A) 99(B) 100(C) 101(D) 102設二叉排序樹上有 n 個結點，則在二叉排序樹上查找結點的平均時間復雜度為（）。(A) O(n)(B) O(n 2)(C) O(nlog2 n)(D) O(1og 2n)設用鄰接矩陣 A 表示有向圖 G的存儲結構， 則有向圖 G中頂點 i 的入度為（ ）。(A)第 i 行非 0 元素的個數(shù)

40、之和(B)第 i 列非 0 元素的個數(shù)之和(C)第 i 行 0 元素的個數(shù)之和(D)第 i 列 0 元素的個數(shù)之和二、判斷題 (20 分 )1調(diào)用一次深度優(yōu)先遍歷可以訪問到圖中的所有頂點。（）2分塊查找的平均查找長度不僅與索引表的長度有關，而且與塊的長度有關。 （）3冒泡排序在初始關鍵字序列為逆序的情況下執(zhí)行的交換次數(shù)最多。（）4滿二叉樹一定是完全二叉樹，完全二叉樹不一定是滿二叉樹。（）5設一棵二叉樹的先序序列和后序序列，則能夠唯一確定出該二叉樹的形狀。（）6層次遍歷初始堆可以得到一個有序的序列。（）7設一棵樹T 可以轉化成二叉樹BT，則二叉樹BT中一定沒有右子樹。 （）8線性表的順序存儲結構

41、比鏈式存儲結構更好。（）9中序遍歷二叉排序樹可以得到一個有序的序列。（）快速排序是排序算法中平均性能最好的一種排序。 （ ）三、填空題 (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= ， ，則給出該圖的一種拓撲排序序列_。4設無向圖G中有 n 個頂點，則該無向圖中每個頂點的度數(shù)

42、最多是_。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)二分查找的算法。設計判斷二叉樹是否為二叉排序樹的算法。在鏈式存儲結構上設計直

43、接插入排序算法數(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-13設一組初始記錄關鍵字序列為(60 ，80，55，40，42，85) ，則以第一個關鍵字45 為基準而得到的一趟快速排序結果是（）。(A) 40 ， 42， 60， 55， 80， 85(B) 42 ， 45， 55， 60， 85， 8042 ， 40， 55， 60， 80， 85 (D) 42 ，

44、 40， 60， 85， 55， 80 4（ ）二叉排序樹可以得到一個從小到大的有序序列。先序遍歷 (B) 中序遍歷 (C) 后序遍歷 (D) 層次遍歷5設按照從上到下、從左到右的順序從1 開始對完全二叉樹進行順序編號，則編號為i 結點的左孩子結點的編號為（）。(A) 2i+1(B) 2i(C) i/2(D) 2i-16程序段 s=i=0 ；do i=i+1 ； s=s+i； while(inext=0(C) head-next=head(D) head!=08設某棵二叉樹的高度為10，則該二叉樹上葉子結點最多有（）。(A) 20(B) 256(C) 512(D) 10249設一組初始記錄關鍵

45、字序列為(13 ，18，24， 35，47，50，62，83，90，115， 134), 則利用二分法查找關鍵字 90 需要比較的關鍵字個數(shù)為（）。(A) 1(B) 2(C) 3(D) 410. 設指針變量 top 指向當前鏈式棧的棧頂，則刪除棧頂元素的操作序列為（）。(A) top=top+1;(B) top=top-1;(C) top-next=top;(D) top=top-next;二、判斷題 (20 分 )1不論是入隊列操作還是入棧操作，在順序存儲結構上都需要考慮“溢出”情況。（）2當向二叉排序樹中插入一個結點，則該結點一定成為葉子結點。（）3設某堆中有n 個結點，則在該堆中插入一個

46、新結點的時間復雜度為O(log 2 n) 。（）4完全二叉樹中的葉子結點只可能在最后兩層中出現(xiàn)。（）5哈夫曼樹中沒有度數(shù)為1 的結點。（）6對連通圖進行深度優(yōu)先遍歷可以訪問到該圖中的所有頂點。（）7先序遍歷一棵二叉排序樹得到的結點序列不一定是有序的序列。（）8由樹轉化成二叉樹，該二叉樹的右子樹不一定為空。（）9線性表中的所有元素都有一個前驅元素和后繼元素。（）帶權無向圖的最小生成樹是唯一的。 （ ）三、填空題 (30 分 )1.設指針變量 p 指向雙向鏈表中的結點A，指針變量 s 指向被插入的結點X，則在結點 A 的后面插入結點X 的操作序列為_=p； s-right=p-right；_=s；

47、 p-right-left=s；（設結點中的兩個指針域分別為left和right ）。設完全有向圖中有 n 個頂點，則該完全有向圖中共有 _條有向條；設完全無向圖中有n 個頂點，則該完全無向圖中共有_條無向邊。3.設關鍵字序列為 (K l ，K2， ， Kn) ，則用篩選法建初始堆必須從第_個元素開始進行篩選。4.解決散列表沖突的兩種方法是_和 _。設一棵三叉樹中有 50 個度數(shù)為 0 的結點， 21 個度數(shù)為 2 的結點，則該二叉樹中度數(shù)為 3 的結點數(shù)有 _個。高度為 h 的完全二叉樹中最少有 _個結點，最多有 _個結點。設有一組初始關鍵字序列為 (24 ， 35， 12， 27， 18，

48、 26) ，則第 3 趟直接插入排序結束后的結果的是 _。設有一組初始關鍵字序列為 (24 ， 35， 12， 27， 18， 26) ，則第 3 趟簡單選擇排序結束后的結果的是 _。設一棵二叉樹的前序序列為 ABC，則有 _種不同的二叉樹可以得到這種序列。下面程序段的功能是實現(xiàn)一趟快速排序，請在下劃線處填上正確的語句。struct record int key;datatype others;void quickpass(struct record r, int s, int t, int &i)int j=t; struct record x=rs; i=s;while(ij)while

49、(ix.key) j=j-1; while (_) i=i+1;if (ij) ri=rj;i=i+1;if (idata=k;t-lchild=t-rchild=0;else if (t-datak) bstinsert(t-lchild,k);else_;3 設指針變量 p 指向單鏈表中結點A，指針變量 s 指向被插入的結點X，則在結點的 后 面 插 入 結 點 X 需 要 執(zhí) 行 的 語 句 序 列 ： s-next=p-next;_; 。4 設指針變量 head 指向雙向鏈表中的頭結點，指針變量 p 指向雙向鏈表中的第一個結 點 ，則 指針 變 量 p 和 指 針變 量 head 之

50、間的 關系 是 p=_和head=_（設結點中的兩個指針域分別為 llink 和 rlink ）。5 設某棵二叉樹的中序遍歷序列為ABCD，后序遍歷序列為列為 _。BADC，則其前序遍歷序6 完全二叉樹中第5 層上最少有 _個結點，最多有 _個結點。7 設有向圖中不存在有向邊，則其對應的鄰接矩陣A 中的數(shù)組元素Aij的值等于 _。8 設一組初始記錄關鍵字序列為(49 ， 38， 65，97，76，13，27， 50) ，則第4 趟直接選擇排序結束后的結果為_。9 設連通圖 G中有 n 個頂點 e 條邊，則對應的最小生成樹上有_條邊。10設有一組初始記錄關鍵字序列為(50 ，16，23，68，9

51、4， 70，73) ，則將它們調(diào)整成初始堆只需把16 與_相互交換即可。四、算法設計題 (20 分)設計一個在鏈式存儲結構上統(tǒng)計二叉樹中結點個數(shù)的算法。設計一個算法將無向圖的鄰接矩陣轉為對應鄰接表的算法。數(shù)據(jù)結構試卷（九）一、選擇題 (30 分 )1下列程序段的時間復雜度為（）。for(i=0 ； im ； i+) for(j=0 ； jt ； j+) cij=0 ；for(i=0 ；im ；i+)for(j=0 ；jt ；j+)for(k=0 ；kright=s ； s-left=p ； p-right-left=s ； s-right=p-right ；s-left=p ； s-right

52、=p-right ；p-right=s ； p-right-left=s ；p-right=s ； p-right-left=s ； s-left=p ； s-right=p-right ；s-left=p ； s-right=p-right ； p-right-left=s ； p-right=s ；6下列各種排序算法中平均時間復雜度為O(n2 ) 是（）。(A)快速排序(B)堆排序(C)歸并排序 (D)冒泡排序7設輸入序列1、2、 3、 、 n 經(jīng)過棧作用后，輸出序列中的第一個元素是n，則輸出序列中的第i 個輸出元素是（）。(A) n-i(B) n-1-i(C) n+l -i(D)不能確定

53、8設散列表中有m 個存儲單元，散列函數(shù)H(key)= key % p ，則 p 最好選擇（）。(A)小于等于 m的最大奇數(shù)(B)小于等于 m的最大素數(shù)小于等于 m的最大偶數(shù)(D) 小于等于 m的最大合數(shù)9設在一棵度數(shù)為3 的樹中，度數(shù)為3 的結點數(shù)有2 個，度數(shù)為2 的結點數(shù)有1個，度數(shù)為 1 的結點數(shù)有2 個，那么度數(shù)為0 的結點數(shù)有（）個。(A) 4(B) 5(C) 6(D) 710. 設完全無向圖中有n 個頂點，則該完全無向圖中有（）條邊。(A) n(n-1)/2 (B) n(n-1)(C) n(n+1)/2 (D) (n-1)/2設順序表的長度為 n，則順序查找的平均比較次數(shù)為（）。(

54、A) n(B) n/2(C) (n+1)/2(D) (n-1)/2設有序表中的元素為 (13 ，18， 24， 35， 47， 50， 62) ，則在其中利用二分法查找值為 24 的元素需要經(jīng)過（）次比較。(A) 1(B) 2(C) 3(D) 4設順序線性表的長度為 30，分成 5 塊，每塊 6 個元素，如果采用分塊查找，則其平均查找長度為（）。(A) 6(B) 11(C) 5(D) 6.5設有向無環(huán)圖 G中的有向邊集合 E=， ， ，則下列屬于該有向圖G的一種拓撲排序序列的是（）。(A) 1 ，2，3，4(B) 2 ，3，4， 1(C) 1 ，4， 2， 3(D) 1，2，4，3設有一組初始

55、記錄關鍵字序列為 (34 ，76， 45， 18， 26， 54， 92) ，則由這組記錄關鍵字生成的二叉排序樹的深度為（）。(A) 4(B) 5(C) 6(D) 7二、填空題(30分 )1 設指針p 指向單鏈表中結點A，指針s 指向被插入的結點X，則在結點A 的前面插入結點X 時的操作序列為：1) s-next=_；2) p-next=s；3) t=p-data；4) p-data=_；5) s-data=t；2 設某棵完全二叉樹中有100 個結點，則該二叉樹中有_個葉子結點。3 設某順序循環(huán)隊列中有m個元素，且規(guī)定隊頭指針F 指向隊頭元素的前一個位置，隊尾指針R 指向隊尾元素的當前位置，則

56、該循環(huán)隊列中最多存儲_隊列元素。4 對一組初始關鍵字序列（40， 50， 95，20，15，70，60， 45， 10）進行冒泡排序，則第一趟需要進行相鄰記錄的比較的次數(shù)為_，在整個排序過程中最多需要進行 _趟排序才可以完成。5 在堆排序和快速排序中，如果從平均情況下排序的速度最快的角度來考慮應最好選擇 _排序，如果從節(jié)省存儲空間的角度來考慮則最好選擇_排序。6 設一組初始記錄關鍵字序列為(20 ，12，42，31，18， 14， 28) ，則根據(jù)這些記錄關鍵字構造的二叉排序樹的平均查找長度是_。7 設一棵二叉樹的中序遍歷序列為BDCA，后序遍歷序列為DBAC，則這棵二叉樹的前序序列為 _。8

57、 設用于通信的電文僅由 8 個字母組成，字母在電文中出現(xiàn)的頻率分別為7、19、2、 6、 32、 3、 21、 10，根據(jù)這些頻率作為權值構造哈夫曼樹，則這棵哈夫曼樹的高度為 _。9 設一組記錄關鍵字序列為(80 ， 70， 33， 65， 24， 56， 48) ，則用篩選法建成的初始堆為_。10設無向圖G（如右圖所示），則其最小生成樹上所有邊的權值之和為_。三、判斷題 (20 分 )1 有向圖的鄰接表和逆鄰接表中表結點的個數(shù)不一定相等。( )2 對鏈表進行插入和刪除操作時不必移動鏈表中結點。( )3 子串“ ABC”在主串“ AABCABCD”中的位置為2。( )4 若一個葉子結點是某二叉

58、樹的中序遍歷序列的最后一個結點，則它必是該二叉樹的先序遍歷序列中的最后一個結點。( )5 希爾排序算法的時間復雜度為O(n2) 。( )6 用鄰接矩陣作為圖的存儲結構時，則其所占用的存儲空間與圖中頂點數(shù)無關而與圖中邊數(shù)有關。( )7 中序遍歷一棵二叉排序樹可以得到一個有序的序列。( )8 入棧操作和入隊列操作在鏈式存儲結構上實現(xiàn)時不需要考慮棧溢出的情況。( )9 順序表查找指的是在順序存儲結構上進行查找。（）10堆是完全二叉樹，完全二叉樹不一定是堆。（）五、算法設計題 (20 分)1 設計計算二叉樹中所有結點值之和的算法。2 設計將所有奇數(shù)移到所有偶數(shù)之前的算法。3 設計判斷單鏈表中元素是否是

59、遞增的算法。數(shù)據(jù)結構試卷（十）一、選擇題 (24 分 )1下列程序段的時間復雜度為（）。i=0 ， s=0；while (snext=p-next ； p-next=-s ； (B) q-next=s ； s-next=p (C) p-next=s-next ； s-next=p ； (D) p-next=s ；s-next=q 4設輸入序列為 1、2、3、4、5、6，則通過棧的作用后可以得到的輸出序列為；（）。(A) 5，3，4，6，1，2(B) 3，2，5，6， 4，1(C) 3，1，2，5，4，6(D) 1，5，4，6， 2，35設有一個 10 階的下三角矩陣A（包括對角線），按照從上到

60、下、從左到右的順序存儲到連續(xù)的55 個存儲單元中，每個數(shù)組元素占1 個字節(jié)的存儲空間， 則 A54地址與A00的地址之差為（）。(A) 10(B) 19(C) 28(D) 556設一棵m叉樹中有N1 個度數(shù)為1 的結點，N2 個度數(shù)為2 的結點， ，Nm個度數(shù)為m的結點，則該樹中共有（）個葉子結點。mmmm(A)(i1) Ni(B)Ni(C)Ni(D)1(i1) Nii1i1i2i27.二叉排序樹中左子樹上所有結點的值均（）根結點的值。(A) (C) =(D) !=設一組權值集合 W=(15，3， 14， 2，6，9， 16， 17) ，要求根據(jù)這些權值集合構造一棵哈夫曼樹，則這棵哈夫曼樹的帶