1、數據結構數據結構專升本考試試卷專升本考試試卷1 1、單項選擇題、單項選擇題(15 (15 個小題個小題) )a ad da aa ad dc cc ca ab bd da ab ba ac cd d2 2、判斷題、判斷題(10 (10 個小題個小題) )1 2 3 4 5 6 7 8 9 10 11 12 13 14 151 2 3 4 5 6 7 8 9 10 11 12 13 14 151 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 三、填空題三、填空題 1.1.在帶有頭結點的雙鏈表在帶有頭結點的雙鏈表L L中，指針中，指針P P所指結點是第一個元素結點

2、的條件是所指結點是第一個元素結點的條件是: : L-front=pL-front=p或或p-back=Lp-back=L 。 2.2.在具有在具有n n個單元、順序存儲的循環個單元、順序存儲的循環隊列中，隊滿時共有隊列中，隊滿時共有 n-1n-1 個元素。個元素。 3. 3.設設sq1.maxsizesq1.maxsize為順序存儲的棧，為順序存儲的棧，變量變量toptop指示棧頂元素的位置。能作入指示棧頂元素的位置。能作入棧操作的條件是棧操作的條件是 TopMAXSIZETopMAXSIZE 。如果。如果把棧頂元素彈出并送到把棧頂元素彈出并送到x x中，則需執行中，則需執行下列語句下列語句:

3、 : x=sqTop;Topx=sqTop;Top=Top-1=Top-1 。 4.4.二維數組二維數組A1020A1020采用列為主序采用列為主序方式存儲，每個元素占用一個存儲單元方式存儲，每個元素占用一個存儲單元, ,并且并且A00A00的存儲地址是的存儲地址是200,200,則則A612A612的地址是的地址是: :1212* *10+6+200=32610+6+200=326。 5. 5.樹樹t t的存儲結構為二叉鏈表的存儲結構為二叉鏈表btbt，樹，樹t t中一個非葉子結點在中一個非葉子結點在btbt中滿足條件：中滿足條件： 其左右子樹不能同時為空其左右子樹不能同時為空 。 6.6.

4、如果含如果含n n個頂點的圖式一個環，則個頂點的圖式一個環，則它有它有 n n 棵生成樹。棵生成樹。 7.7.對有對有1717個元素的有序表個元素的有序表1.171.17作作折半查找，在查找值等于折半查找，在查找值等于A8A8的元素時，的元素時，被比較的元素的下標依次為被比較的元素的下標依次為: : 9,4,6,7,89,4,6,7,8 。 8. 8.一個單鏈表一個單鏈表P P結點之后插入結點之后插入S S結點時，結點時，應執行應執行S-next=S-next= P-nextP-next 和和 P-next=P-next= S S 的操作。的操作。 9.9.利用線性利用線性- -交換選擇排序算

5、法對有交換選擇排序算法對有n n個記錄的數據表進行排序，最壞的情況個記錄的數據表進行排序，最壞的情況下，記錄的交換次數為下，記錄的交換次數為 n n2 2 。 10.10.算術式算術式(A+B)-C+D/E(A+B)-C+D/E的前序式為的前序式為: : +-+ABC/DE+-+ABC/DE , ,后序式為后序式為: : AB+C-DE/+AB+C-DE/+ 。 11.11.設行列的下三角矩陣已經設行列的下三角矩陣已經壓縮到一維數組壓縮到一維數組S1.nS1.n* *(n-1)/2(n-1)/2中，中，若按行序為主序存儲，則若按行序為主序存儲，則AijAij 對應對應的中的存儲位置是的中的存儲

6、位置是 i i* *(i-1)/2+j(i-1)/2+j 。 12. 12. 432112113211211 432112113211211 。四、解答下列各題四、解答下列各題、已知一棵二叉樹的前序、中序列、已知一棵二叉樹的前序、中序列是是ABCDEFGHIJKABCDEFGHIJK，CDBGFEAHJIKCDBGFEAHJIK，請構造，請構造出該二叉樹。出該二叉樹。A AB BH HC CE EI IF FG GD DJ JK K、對下面給出的數據序列，構造一、對下面給出的數據序列，構造一棵哈夫曼樹，并求出其帶權路徑長度。棵哈夫曼樹，并求出其帶權路徑長度。4,5,6,7,10,12,15,1

7、8,234,5,6,7,10,12,15,18,23100100424219199 94 45 51010232358582525333312121313151518186 67 7WPL=(4+5)WPL=(4+5)* *4+4+ 10 10* *3+3+ 23 23* *2+2+ 12 12* *3+3+ (6+7) (6+7)* *4+4+ (15+18) (15+18)* *3 3 = =299299 、設圖、設圖G=(V,E),G=(V,E), V=1,2,3,4,5,6), V=1,2,3,4,5,6), E=, E=, , , , 請寫出圖請寫出圖G G中頂點的所有拓撲序列。中頂

8、點的所有拓撲序列。1 13 32 26 65 54 41,2,3,6,5,41,2,3,6,5,41,3,6,2,5,41,3,6,2,5,41,3,2,6,5,41,3,2,6,5,4、對下面給出的數據序列，寫出堆、對下面給出的數據序列，寫出堆排序過程。排序過程。(45,36,18,53,72,30,48,93,15)(45,36,18,53,72,30,48,93,15)454536361818535372723030484893931515939372724848535345453030181836361515大頂堆大頂堆151572724848535345453030181836369

9、393輸出輸出93727253534848363645453030181815159393調整調整151553534848363645453030181872729393輸出輸出7272535345454848363615153030181872729393調整調整請自己繼續完成請自己繼續完成、利用、利用DijkstraDijkstra算法求出下圖中從算法求出下圖中從頂點到其余頂點的最短路徑。頂點到其余頂點的最短路徑。33082541252010 第第1趟趟 第第2趟趟 第第3趟趟 第第4趟趟V2 3 v1,v2V3 28 15 v1,v3 v1,v2,v3 v1,v2,v4,v3V4 11

10、v1,v4 v1,v2,v4 V5 30 30 23 23 v1,v5 v1,v5 v1,v2,v4,v5 v1,v2,v4,v5Vj V2 V4 V3 V5 S v1,v2 v1,v2,v4 v1,v2,v4, v3 v1,v2,v4,v5, S:S:當前已確定了最短距離的頂點集合當前已確定了最短距離的頂點集合。模擬試卷一模擬試卷一1 1、單項選擇題、單項選擇題(9 (9 個小題個小題) )3 34 41 11 12 24 41 14 44 42 2、判斷題、判斷題(4 (4 個小題個小題) )1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 1 2 3 4 1 2 3

11、 4 三、填空題三、填空題 1.1.在帶有頭結點的單鏈表在帶有頭結點的單鏈表L L中，第一中，第一個元素結點的指針是個元素結點的指針是 L-nextL-next 。 2.2.在雙循環鏈表中，在指針在雙循環鏈表中，在指針P P所指結所指結點前插入指針點前插入指針S S所指的結點，需執行下列所指的結點，需執行下列語句：語句： S-front=P; S-back=P-back;S-front=P; S-back=P-back; P-back=S; P-back=S; S-back-frontS-back-front=S=S。 3. 3.設設sq1.maxsizesq1.maxsize為一個順序存為一

12、個順序存儲的棧，變量儲的棧，變量toptop指示棧頂元素的位置。指示棧頂元素的位置。棧為空的條件是棧為空的條件是 top=0top=0 ，棧為滿的條，棧為滿的條件是件是 top=maxsizetop=maxsize 。 4.4.具有具有100100個結點的完全二叉樹的個結點的完全二叉樹的深度為深度為 7 7 。 5.5.有向圖有向圖G G用鄰接矩陣用鄰接矩陣A1.n,1.nA1.n,1.n存儲，其第存儲，其第i i行的所有元素之和等于頂行的所有元素之和等于頂點點i i的的 出度出度 。 6. 6. 對下面的二叉樹，按中序遍歷所得對下面的二叉樹，按中序遍歷所得到的結點序列為到的結點序列為 DBH

13、EACFDBHEACF 。 A AB BC CD DH HF FE E 7 7、分別采用堆、快速、插入和歸并、分別采用堆、快速、插入和歸并排序算法對初始狀態為遞增序列的表按排序算法對初始狀態為遞增序列的表按遞增排序，遞增排序， 最省時間的算法是最省時間的算法是 插入插入 算法，算法， 最費時間的算法是最費時間的算法是 快速快速 算法。算法。 8. 8.對下圖所示的網，執行對下圖所示的網，執行primprim算法可得到算法可得到最小生成樹，試在下表的空白處填上適當的最小生成樹，試在下表的空白處填上適當的內容，以說明該算法的執行過程。內容，以說明該算法的執行過程。1 13 34 42 21 15

14、55 52 24 42,4,3,2,4,3,11(U,V)(U,V)代價代價 1 12,4,32,4,3(2,1)(2,1)1(U,V)(U,V)代價代價1,31,32,42,4(2,3)(2,3)4(4,1)(4,1)5 5(U,V)(U,V)代價代價1,3,1,3,4422(2,4)(2,4)3(2,3)(2,3)4(2,1)(2,1)(U,V)(U,V)代價代價V VU U4 43 31 1頂點頂點四、應用題四、應用題 1 1、已知一棵二叉樹的后序序列、中序序列、已知一棵二叉樹的后序序列、中序序列如下，請構造該二叉樹。如下，請構造該二叉樹。 后序序列：后序序列：ABCDEFGABCDEF

15、G 中序序列：中序序列：ACBGEDFACBGEDFG GC CF FA AE EB BD D 2 2、有一組關鍵字序列、有一組關鍵字序列 (38,19,65,13,97,49,41,95,1,73)(38,19,65,13,97,49,41,95,1,73)采用冒泡排序方法按從小到大的次序進采用冒泡排序方法按從小到大的次序進行排序，寫出每趟排序的結果。行排序，寫出每趟排序的結果。38 19 19 13 13 13 13 13 1338 19 19 13 13 13 13 13 13 1 119 38 13 19 19 19 19 1919 38 13 19 19 19 19 19 1 1 1

16、31365 13 38 38 38 38 3865 13 38 38 38 38 38 1 1 191913 65 49 41 41 4113 65 49 41 41 41 1 1 383897 49 41 49 4997 49 41 49 49 1 1 414149 41 65 1 1 49 41 65 1 1 494941 95 1 65 41 95 1 65 656595 1 73 95 1 73 73731 73 1 73 9595 73 73 97973 3、設圖、設圖G=(V,E),G=(V,E), V=1,2,3,4,5,6), V=1,2,3,4,5,6), E=, E=, ,

17、 , , 請寫出圖請寫出圖G G中頂點的所有拓撲序列。中頂點的所有拓撲序列。1 12 23 36 65 54 41 1：1 2 3 6 5 41 2 3 6 5 42 2：1 3 6 2 5 41 3 6 2 5 43 3：1 3 2 6 5 41 3 2 6 5 44 4、對下面兩棵二叉樹，分別畫出它們、對下面兩棵二叉樹，分別畫出它們的順序存儲結構。的順序存儲結構。 A AB BC CD DF FI IG GE EJ JK KA AB BC CD DF FE EJ JI I順序存儲結構。順序存儲結構。 A AB BC CD DF FI IG GE EJ JK KK KJ JI IH HG G

18、F FE ED DC CB BA A1 2 3 4 5 6 7 8 9 10 111 2 3 4 5 6 7 8 9 10 11順序存儲結構。順序存儲結構。 A AB BC CD DF FE EJ JI IJ JI IF FE ED DC CB BA A1 2 3 4 5 6 7 8 9 10 111 2 3 4 5 6 7 8 9 10 11、圖、圖G G的鄰接表如下，畫出圖的鄰接表如下，畫出圖G G的所有的所有連通分量。連通分量。IHGFEDCBA5476727193 26 31 12 23 34 45 56 67 78 89 99 34A AE EB BD DG GC CI IF F模擬

19、試卷二模擬試卷二1 1、單項選擇題、單項選擇題(5 (5 個小題個小題) )2 2、判斷題、判斷題(9 (9 個小題個小題) )cabdd1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 三、填空題三、填空題 1.1.在單鏈表中，刪除指針在單鏈表中，刪除指針P P所指結點的所指結點的后繼結點的語句是后繼結點的語句是 P-next=P-next-P-next=P-next-nextnext 。 2.2.已知完全二叉樹的第八層有已知完全二叉樹的第八層有8 8個結點，個結點，則其葉子結點數是則其葉子結點數是 6868 。 3.3.將下三角

20、矩陣將下三角矩陣1.8,1.81.8,1.8的下三的下三角部分逐行地存儲到起始地址為角部分逐行地存儲到起始地址為10001000的的內存單元中，已知每個元素占用內存單元中，已知每個元素占用4 4個單元，個單元，則則A7,5A7,5的地址是的地址是 11041104 。 4. 4.有有n n個頂點的強連通有向圖個頂點的強連通有向圖G G至少至少有有 n n 條弧。條弧。 5.5.求最短路徑的求最短路徑的DijkstraDijkstra算法的時間算法的時間復雜度為復雜度為 O(nO(n2 2) ) 。 6.6.在有序表在有序表1.201.20中，采用折半查中，采用折半查找算法查找元素等于找算法查找

21、元素等于A12A12的元素，所的元素，所比較的元素的下標依次為比較的元素的下標依次為 10,15,1210,15,12 。 7. 7.交換交換- -線性選擇排序算法所執行的線性選擇排序算法所執行的元素交換次數最多為元素交換次數最多為 n-1n-1 。 8.8.下列排序算法中，穩定的算法是：下列排序算法中，穩定的算法是： 中心插入中心插入 排序排序( (選擇、堆、快速、中選擇、堆、快速、中心插入）。心插入）。四、應用題四、應用題、已知一棵二叉樹的、已知一棵二叉樹的 前序序列是：前序序列是：ABCDEFGHIJABCDEFGHIJ， 中序序列是：中序序列是：CBEDAGHFJICBEDAGHFJI

22、，請構造出該二叉樹。請構造出該二叉樹。A AB BF FC CD DG GI IE EH HJ J、對下面給出的數據序列，構造一、對下面給出的數據序列，構造一棵哈夫曼樹，并求出其帶權路徑長度。棵哈夫曼樹，并求出其帶權路徑長度。 4,5,6,7,10,12,15,18,234,5,6,7,10,12,15,18,23 數據結構數據結構專升本考試試題專升本考試試題 第四大題的第二小題第四大題的第二小題、圖、圖G G的鄰接表的鄰接表如下，完成下列如下，完成下列各題各題 (1)(1)畫出從頂畫出從頂點點5 5出發進行廣度出發進行廣度遍歷所生成的生遍歷所生成的生成樹。成樹。 (2)(2)判斷其中判斷其中

23、是否存在有向回是否存在有向回路，若不存在，路，若不存在，求出其拓撲排序求出其拓撲排序121110987654321325467989108111291011125 510109 98 811111212(1)(1)從頂點從頂點5 5出發廣度遍歷所生成的生成樹。出發廣度遍歷所生成的生成樹。(2)(2)其拓撲排序：其拓撲排序： 1,2,4,5,8,9,10,3,7,6,11,121,2,4,5,8,9,10,3,7,6,11,12、對下列數據表，寫出采用快速排、對下列數據表，寫出采用快速排序的每一趟的結果。序的每一趟的結果。(60,20,31,1,5,44,55,61,200,30,80,150,

24、4,29)(60,20,31,1,5,44,55,61,200,30,80,150,4,29) 29 61 29 61 4 200 4 200 30 60 30 60(30 20 31 1 5 44 55 29 4)(30 20 31 1 5 44 55 29 4)6060(80 150 200 61)(80 150 200 61) 4 31 4 31 29 44 29 44(29 20 4 1 5)(29 20 4 1 5)3030(55 44 31)(55 44 31)(5 20 4 1)(5 20 4 1)2929() () (4 1)(4 1)5 5(20)(20) 1 4 5 20

25、29 30 1 4 5 20 29 30 (29 20 4 1 5)(29 20 4 1 5)3030(55 44 31)(55 44 31)(5 20 4 1)(5 20 4 1)2929() () (4 1)(4 1)5 5(20)(20) 1 4 5 20 29 30 1 4 5 20 29 30 (31 44)55 (31 44)55 31 44 55 31 44 55 6060(80 150 200 61) (80 150 200 61) (61) 80 (200 150) (61) 80 (200 150) 150 200 150 2001 4 5 20 29 30 31 44 5

26、5 60 61 80 150 200 1 4 5 20 29 30 31 44 55 60 61 80 150 200 另一種方法：另一種方法： (60,20,31,1,5,44,55,61,200,30,80,150,4,29)(60,20,31,1,5,44,55,61,200,30,80,150,4,29) 29 60 29 60 60 61 60 61 4 60 4 60 60 200 60 200 30 60 30 60 (29 20 31 1 5 44 55 4 30) (29 20 31 1 5 44 55 4 30)6060(80 150 200 61)(80 150 200

27、61) 4 29 4 29 29 31 29 31 5 29 5 29 (4 20 5 1) (4 20 5 1)2929(44 55 31 30)(44 55 31 30) 1 4 1 4 4 20 4 20 (1 4)5(20) (1 4)5(20) 2929(44 55 31 30)(44 55 31 30) 30 44 30 44 31 55 31 55 (30 31) (30 31)4444(55)(55) 30(31)44 30(31)44 30 31 30 55 30 31 30 55 6060(80 150 200 61)(80 150 200 61) 61 80 61 80

28、80 150 80 150 (61) (61)8080(150 200)(150 200) 150150(200)(200) 1 4 5 20 29 30 31 44 55 61 80 150 200 1 4 5 20 29 30 31 44 55 61 80 150 200 模擬試卷三模擬試卷三1 1、單項選擇題、單項選擇題(9 (9 個小題個小題) )d db bd dc ca ac cc cd db b2 2、判斷題、判斷題(7 (7 個小題個小題) )1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 1 2 3 4 5 6 7 三、填空

29、題三、填空題 1.1.在雙循環鏈表在雙循環鏈表L L中，指針中，指針P P所指結點所指結點為尾結點的條件是為尾結點的條件是 P-front=LP-front=L 。 2.2.在單鏈表中，刪除指針在單鏈表中，刪除指針P P所指結點所指結點的后繼結點的語句是的后繼結點的語句是: : P-next=P-next-nextP-next=P-next-next 。 3.3.隊列的特性是隊列的特性是 先進先出先進先出 。 4.4.有有n n個葉子結點的哈夫曼樹，總結個葉子結點的哈夫曼樹，總結點數是點數是 2 2* *n-1n-1 。 5. 5.有有n n個頂點的無向圖其邊數最多為個頂點的無向圖其邊數最多為

30、 n n* *(n-1)/2(n-1)/2 。 6.6.對矩陣采用壓縮存儲是為了對矩陣采用壓縮存儲是為了 節省節省存儲空間存儲空間 。 四、應用題四、應用題、分別畫出滿足下列條件的所有二、分別畫出滿足下列條件的所有二叉樹。叉樹。 前序序列和中序序列均為前序序列和中序序列均為ABCDEABCDE。 前序序列為前序序列為ABCDEABCDE，并且與其相對于，并且與其相對于應的樹高度為應的樹高度為5 5。1)1)A AB BC CD DE E2)2)A AB BC CD DE E2 2、對下列數據表，寫出采用、對下列數據表，寫出采用shellshell排排序的每一趟的結果。序的每一趟的結果。100,

31、12,20,31,1,5,44,66,61,200,30,80,150,4,8100,12,20,31,1,5,44,66,61,200,30,80,150,4,8d1=7:d1=7:100 12 20 31 1 5 44 66 61 200 30 80 150 4 8100 12 20 31 1 5 44 66 61 200 30 80 150 4 866661001008 81001008 866661 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 8,8,12,20,31,1,5,44,12,2

32、0,31,1,5,44,6666,61,200,30,80,150,4,61,200,30,80,150,4,100100303031314 44444整理后：整理后：d=3d=38,12,20,30,1,5,4,66,61,200,31,80,150,44,1008,12,20,30,1,5,4,66,61,200,31,80,150,44,1001 115015012122002004 44 48 85 52020若有交換且可以回溯則必須進行若有交換且可以回溯則必須進行比較，直到不必交換或不可回溯比較，直到不必交換或不可回溯為止，然后再接著從剛才的位置為止，然后再接著從剛才的位置繼續比較。

33、繼續比較。整理后：整理后：4,1,5,8,12,20,30,31,61,150,44,80,200,66,1004,1,5,8,12,20,30,31,61,150,44,80,200,66,100最后一趟最后一趟 d=1d=11,4,5,8,12,20,30,31,44,61,66,80,100,150,2001,4,5,8,12,20,30,31,44,61,66,80,100,150,200模擬試卷四模擬試卷四1 1、單項選擇題、單項選擇題(6 (6 個小題個小題) )a ab bc ca ac ca a2 2、判斷題、判斷題(6 (6 個小題個小題) )1 2 3 4 5 6 1 2

34、3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6 三、填空題三、填空題 1.1.帶頭結點的雙循環鏈表帶頭結點的雙循環鏈表L L為空表的為空表的條件是條件是 L-front=LL-front=L 。 2.2.在雙鏈表中，在指針在雙鏈表中，在指針P P所指結點前所指結點前面插入一個結點面插入一個結點S S的語句序列是：的語句序列是：S-S-front=P;S-back=P-back;Pfront=P;S-back=P-back;P-back=S;-back=S; S-back-front=SS-back-front=S 。 3.3.已知完全二叉樹的第已知完全二叉樹的第7 7層有層有1

35、010個結點，個結點，則整個二叉樹的結點最多是則整個二叉樹的結點最多是 235235 。 4. 4.有有n n個頂點并且高度為個頂點并且高度為n n的二叉樹的二叉樹的數目是的數目是 2 2n-1n-1 。 5. 5. 循環隊列采用數組循環隊列采用數組data1.ndata1.n來存儲元素的值，并用來存儲元素的值，并用frontfront和和rearrear分分別作為其指針，為區分隊列的滿和空，別作為其指針，為區分隊列的滿和空，約定：隊中能夠存放的元素個數最大約定：隊中能夠存放的元素個數最大n-n-1 1，也即至少一個元素空間不用，則在，也即至少一個元素空間不用，則在任意時刻，至少知道一個空元素

36、的下標任意時刻，至少知道一個空元素的下標是是 frontfront , ,可用語句可用語句 rear=(rear+1rear=(rear+1)%n)%n 求出新元素在數組求出新元素在數組datadata中的下標。中的下標。 6. 6.高度為高度為8 8的平衡二叉樹的結點至少的平衡二叉樹的結點至少是是 5454 。 7.7.在有在有n n個結點的有向圖中，每個頂個結點的有向圖中，每個頂點的度最大可達點的度最大可達 2(n-1)2(n-1) 。 8.8.數組數組1.10,1.101.10,1.10的每個元素的每個元素占用占用5 5個單元，將其按列優先次序存儲個單元，將其按列優先次序存儲在起始地址在

37、起始地址10001000的連續內存單元中，則的連續內存單元中，則A5,6A5,6的地址為的地址為 1270 1270 。四、應用題四、應用題、已知一棵二叉樹的、已知一棵二叉樹的 中序序列是：中序序列是：DCEFBHGAKJLIMDCEFBHGAKJLIM 后序序列是：后序序列是：DFECHGBKLJMIADFECHGBKLJMIA請構造出該二叉樹。請構造出該二叉樹。A AB BI IC CJ JG GM MD DE EK KL LE EK K、以下面的數據作為葉子結點構造、以下面的數據作為葉子結點構造一棵哈夫曼樹，并求出其帶權路徑長度。一棵哈夫曼樹，并求出其帶權路徑長度。 5,6,7,8,9,

38、10,15,18,225,6,7,8,9,10,15,18,22WPL=304 WPL=304 5 56 67 78 8111115159 9101019192626151534341818222240406060100100 3 3、對下列數據表，寫出采用快速排、對下列數據表，寫出采用快速排序的每一趟的結果。并標明每一趟排序序的每一趟的結果。并標明每一趟排序過程的數據移動情況。第二種方法：過程的數據移動情況。第二種方法：5050,12,20,31,1,5,44,166,61,100,30,80,150,4,8,12,20,31,1,5,44,166,61,100,30,80,150,4,88

39、,12,20,31,1,5,44,4,30,8,12,20,31,1,5,44,4,30,5050,100,80,150,61,166,100,80,150,61,1664,5,1,4,5,1,8 8,31,20,44,12,30,31,20,44,12,30,50501,1,4 4,5,5,8 8 30,20,12,30,20,12,3131,44,44 12,20, 12,20,30,30, 61,80,61,80,100100,150,166,150,1661,4,5,8,12,20,30,31,44,50,61,66,100,150,1661,4,5,8,12,20,30,31,44,

40、50,61,66,100,150,166 4 4、求出下圖的所有拓撲序列。、求出下圖的所有拓撲序列。 6 1 2 3 4 5 6; 1 2 4 3 5 6;1 2 3 4 5 6; 1 2 4 3 5 6; 2 1 3 4 5 6; 2 1 4 3 5 6 2 1 3 4 5 6; 2 1 4 3 5 6。 模擬試卷五模擬試卷五1 1、單項選擇題、單項選擇題(7 (7 個小題個小題) )c cc cc cb bb bd d1 2 3 4 5 6 7 1 2 3 4 5 6 7 a a二、填空題二、填空題 1.1.雙循環鏈表雙循環鏈表L L中某結點為尾結點的中某結點為尾結點的條件是條件是 P-f

41、ront=LP-front=L 。 2.2.已知二叉樹中葉子結點數為已知二叉樹中葉子結點數為5050，僅，僅有一個孩子的結點數為有一個孩子的結點數為3030，則整個二叉，則整個二叉樹的結點數是樹的結點數是 129129 。三、解答下列各題三、解答下列各題、一棵二叉樹的前序、中序和后序、一棵二叉樹的前序、中序和后序分別如下，其中有一部分未顯示出來，分別如下，其中有一部分未顯示出來，試求出空格處的內容，并畫出該二叉樹。試求出空格處的內容，并畫出該二叉樹。 前序：前序：A AB BD DF FK KICEHICEHJ JG G， 中序：中序：D DB BKFIAKFIAH HEJCEJCG G， 后

42、序：后序：D DKIKIF FBHJBHJE EG GC CA A。A AB BC CD DF FK KI IE EG GH HJ J該二叉樹該二叉樹、對下面的遞歸算法，要求：、對下面的遞歸算法，要求： (1)(1)寫出調用寫出調用p(4)p(4)的執行過程。的執行過程。void p(intvoid p(int w) w) if (w0) if (w0) printf(“%d”,w printf(“%d”,w);); p(w-1); p(w-1); p(w-1); p(w-1); P(4):4 3 2 1 1 2 1 1 3 2 1 1 2 1 1P(4):4 3 2 1 1 2 1 1 3

43、2 1 1 2 1 13 3、已知二叉樹的存儲結構為二叉鏈表，、已知二叉樹的存儲結構為二叉鏈表，閱讀下面算法。對如下所示的二叉樹。閱讀下面算法。對如下所示的二叉樹。 (1)(1)畫出執行上述算法后所建立的結。畫出執行上述算法后所建立的結。 (2)(2)說明該算法的功能。說明該算法的功能。ACBDFEGHVoid inorder(bintreeVoid inorder(bintree T) T)if(Tif(T) ) inorder(T-lchild inorder(T-lchild) )； if(!T-lchild)&(!T-rchildif(!T-lchild)&(!T-rc

44、hild) s=(listnode s=(listnode * *)malloc(sizeof(listnode)malloc(sizeof(listnode);); s-data=T-data; s-data=T-data; s-next=leafhead s-next=leafhead; ; leafhead leafhead=s; =s; inorder(T-rchild inorder(T-rchild) )；/ /* *頭插入頭插入/ /(2)(2)功能：功能： 將中序遍歷二叉樹的葉子結點按將中序遍歷二叉樹的葉子結點按頭插入方式建立一個單鏈表。頭插入方式建立一個單鏈表。leafhea

45、dleafheadF F H H G G D D (1)(1)所建立的結構：所建立的結構：模擬試卷六模擬試卷六1 1、單項選擇題、單項選擇題(4 (4 個小題個小題) )d dc ca ad d2 2、判斷題、判斷題(7 (7 個小題個小題) )1 2 3 4 1 2 3 4 1 2 3 4 5 6 7 1 2 3 4 5 6 7 三、填空題三、填空題 1.1.在雙循環鏈表中，刪除指針在雙循環鏈表中，刪除指針P P所指結所指結點的語句序列是點的語句序列是 P-front-back=P-back P-front-back=P-back 和和 P-back-front=P-front P-back

46、-front=P-front 。 2.2.已知完全二叉樹的第已知完全二叉樹的第7 7層有層有8 8個結點，個結點，則其葉子結點數是則其葉子結點數是 3636 。 3.3.在有在有n n個葉子結點的哈夫曼樹中，結個葉子結點的哈夫曼樹中，結點總數是點總數是 2n-12n-1 。 4.4.有有n n個頂點的有向圖最多有個頂點的有向圖最多有 n(n-1)n(n-1) 條弧。條弧。 5. 5.高度為高度為7 7的平衡二叉樹至少有的平衡二叉樹至少有 33 33 個結點。個結點。 6.6.在有序表在有序表A1.18A1.18中，采用二分查中，采用二分查找算法查找元素值等于找算法查找元素值等于A7A7的元素，

47、所的元素，所比較過的元素下標依次為比較過的元素下標依次為 9,4,6,79,4,6,7 。 7.7.冒泡排序算法在最好的情況下的元冒泡排序算法在最好的情況下的元素交換次數為素交換次數為 0 0 。 四、解答下列各題四、解答下列各題、已知一棵樹的、已知一棵樹的 前序序列是：前序序列是：ABCDEFGHIJKLMNABCDEFGHIJKLMN 后序序列是：后序序列是：CDEBHIGKMLNJFACDEBHIGKMLNJFA請構造出該樹。請構造出該樹。 該樹為：該樹為：A AB BF FC CE ED DK KG GJ JH HI IL LN NM M. .對下面的數據，寫出采用快速排序對下面的數據

48、，寫出采用快速排序算法排序的每一趟結果。算法排序的每一趟結果。 70,12,20,31,1,5,44,66,61,200,30,80,150,4,2870,12,20,31,1,5,44,66,61,200,30,80,150,4,283.3.求求V1V1到其他頂點的最短路徑。到其他頂點的最短路徑。1 12 23 34 47 75 56 68 89 9101014148 812125 53 37 76 65 54 46 63 35 52 26 65 54 43 32 28 8V1 1 2 3 4 5 6 7V1 1 2 3 4 5 6 7V2V2V3V3V4V4V5V5V6V6V7V7V8V8

49、 14 8 12 11 12 13 14 1213 14 20 13 14 20 14 16 22 16 16 16 V3 V3,V2 V3,V2,V4 V3,V2,V4,V5 V3,V2,V4,V5,V6 22V3,V2,V4,V5,V6,V7V3,V2,V4,V5,V6,V7,V8 22 23 18再選再選V10V10加入，最后為加入，最后為V9V9. .V3,V2,V4,V5,V6,V7,V8,V10,V9V3,V2,V4,V5,V6,V7,V8,V10,V9 =8; =8; = 11; 11; =12;=12; = 13;13;= =14; = =14; =16; =16; = = =

50、 16; 16; = = = 18;18; = = = 22;22;V9V9V10V104 4、對下面的遞歸算法，要求：、對下面的遞歸算法，要求： (1)(1)寫出調用寫出調用p(4)p(4)的執行過程。的執行過程。 (2)(2)將其轉換為等價的非遞歸算法。將其轉換為等價的非遞歸算法。void p(intvoid p(int w) w) if (w0) if (w0) p(w-1); p(w-1); printf(“%d”,w printf(“%d”,w);); p(w-1); p(w-1); P(4)P(4)輸出結果：輸出結果：2 1 3 1 2 1 4 1 2 1 3 1 2 12 1 3

51、 1 2 1 4 1 2 1 3 1 2 15 5、已知一個無向圖的頂點集為：、已知一個無向圖的頂點集為： a,b,c,d,ea,b,c,d,e,其鄰接矩陣如下所示其鄰接矩陣如下所示 a 0 1 0 0 1a 0 1 0 0 1 b 1 0 0 1 0 b 1 0 0 1 0 c 0 0 0 1 1 c 0 0 0 1 1 d 0 1 1 0 1 d 0 1 1 0 1 e 1 0 1 1 0 e 1 0 1 1 0 (1) (1)畫出該圖的圖形。畫出該圖的圖形。 (2)(2)根據鄰接矩陣從頂點根據鄰接矩陣從頂點a a出發進行出發進行深度優先遍歷和廣度優先遍歷，寫出相深度優先遍歷和廣度優先遍歷

52、，寫出相應的遍歷序列。應的遍歷序列。深度優先遍歷深度優先遍歷:a b d c e:a b d c e廣度優先遍歷廣度優先遍歷:a b e d c:a b e d ca ad db be ec c模擬試卷七模擬試卷七1 1、單項選擇題、單項選擇題(4 (4 個小題個小題) )c cb bc cd d2 2、判斷題、判斷題(6 (6 個小題個小題) )1 2 3 41 2 3 41 2 3 4 5 6 1 2 3 4 5 6 三、填空題三、填空題 1.1.帶頭結點的雙循環鏈表帶頭結點的雙循環鏈表L L中，最后中，最后一個結點的指針是一個結點的指針是 L-front=LL-front=L 。 2.2

53、.在僅有尾指針在僅有尾指針p p的單循環鏈表中，的單循環鏈表中，在表尾插入一個結點在表尾插入一個結點S S的語句序列是的語句序列是 R-next=S;R=SR-next=S;R=S 。 3.3.已知棧的輸入序列為已知棧的輸入序列為1,2,3,1,2,3,n,n,輸出序列為輸出序列為a a1 1,a,a2 2,a,a3 3, ,a,an n, ,符合符合a a2 2=n=n的的輸出序列共有輸出序列共有 n-1n-1 種。種。 4. 4.已知循環隊列用數組已知循環隊列用數組data1.ndata1.n存存儲元素，用儲元素，用f,rf,r分別作為頭尾指針，則分別作為頭尾指針，則當前的元素個數是當前的

54、元素個數是: : (rear-front+n)%n(rear-front+n)%n 。 5.5.在二叉鏈表中，判斷某指針在二叉鏈表中，判斷某指針p p所指所指結點位葉子結點的條件是結點位葉子結點的條件是: : P-lchild=NULL&P-rchildP-lchild=NULL&P-rchild=NULL=NULL 。 6.6.已知二叉樹中葉子結點數為已知二叉樹中葉子結點數為2020，僅，僅有一個孩子的結點數為有一個孩子的結點數為3030，則整個二叉，則整個二叉樹的結點數是樹的結點數是 6969 。 7. 7.有有n n個頂點的連通圖中，其邊數最個頂點的連通圖中，其邊數最少為

55、少為 n-1n-1 。 8.8.已知數組已知數組A1.10,1.10A1.10,1.10為對稱矩為對稱矩陣，其中每個元素占用陣，其中每個元素占用5 5個單元，現將個單元，現將其下三角按行優先次序存儲在起始地址其下三角按行優先次序存儲在起始地址10001000的連續內存單元中，則的連續內存單元中，則A6,5A6,5對應對應的地址為的地址為 11001100 。9.9.線性線性- -選擇排序算法在最好的情況下選擇排序算法在最好的情況下所交換元素的次數為所交換元素的次數為 0 0 。 10. 10.已知一個圖的廣度優先生成樹如已知一個圖的廣度優先生成樹如圖所示，則與此相應的廣度優先遍歷序圖所示，則與

56、此相應的廣度優先遍歷序列為列為 a b e f c d ga b e f c d g 。a ad db bf fg ge ec c四、解答下列各題四、解答下列各題、已知一棵樹的雙親表示法如、已知一棵樹的雙親表示法如下，其中各兄弟結點是依次出現的，下，其中各兄弟結點是依次出現的，畫出該樹及其對應的二叉樹。畫出該樹及其對應的二叉樹。8 87 76 66 65 54 44 43 33 32 22 21 11 11 10 0O ON NM ML LK KJ JI IH HG GF FE ED DC CB BA Adatadataparentparent1 2 3 4 5 6 7 8 9 10 11 1

57、2 13 14 151 2 3 4 5 6 7 8 9 10 11 12 13 14 15A AB BC CD DE EF FG GH HI IJ JK KL LM MN NO O該樹該樹A AB BC CD DE EF FG GH HI IJ JK KL LM MN NO O對應的二叉樹對應的二叉樹、一棵二叉排序樹，各結點的值從、一棵二叉排序樹，各結點的值從小到大依次為小到大依次為1 18,8,請標出各結點的值。請標出各結點的值。6 61 18 85 57 73 32 24 4 3 3、對下列數據表，寫出采用冒泡排、對下列數據表，寫出采用冒泡排序的每一趟的結果。序的每一趟的結果。(25,10

58、,20,31,5,44,16,61,100,3)(25,10,20,31,5,44,16,61,100,3) 4 4、求出下圖的最小生成樹。、求出下圖的最小生成樹。 68 87 76574535865384 4 4、求出下圖的最小生成樹。、求出下圖的最小生成樹。 65435634模擬試卷八模擬試卷八1 1、單項選擇題、單項選擇題(3 (3 個小題個小題) )2 2、判斷題、判斷題(5 (5 個小題個小題) )1 2 3 1 2 3 1 2 3 4 5 1 2 3 4 5 三、填空題三、填空題 1.1.在單鏈表中，在指針在單鏈表中，在指針P P所指結點的后所指結點的后插入一個結點插入一個結點S

59、S的語句是的語句是: : S-next=P-next;PS-next=P-next;P-next=S-next=S 。 2.2.已知棧的輸入序列為已知棧的輸入序列為1,2,3,1,2,3,n,n,其其輸出序列的第二個元素為輸出序列的第二個元素為n n的輸出序列的的輸出序列的個數是：個數是： n-1n-1 。 3.3.以以4,5,6,7,84,5,6,7,8作為葉子結點的權值作為葉子結點的權值構造哈夫曼樹，則其帶權路徑長度是構造哈夫曼樹，則其帶權路徑長度是: : 6969 。 4. 4.在順序存儲的二叉樹中，編號為在順序存儲的二叉樹中，編號為i i和和j j的兩個結點處在同一層的條件是的兩個結點

60、處在同一層的條件是 loglog2 2i=logi=log2 2j j 。 5.5.已知二叉樹有已知二叉樹有5050個葉子結點，則整個葉子結點，則整個二叉樹的總結點數至少是個二叉樹的總結點數至少是 9999 。 6.6.已知數組已知數組A1.10,1.9A1.10,1.9中每個元中每個元素占用素占用4 4個單元，現將其按行優先次序個單元，現將其按行優先次序存儲在起始地址存儲在起始地址10001000的連續內存單元中，的連續內存單元中，則則A5,9A5,9對應的地址為對應的地址為 11061106 。 7. 7.有有n n個球隊參加足球聯賽按主客場個球隊參加足球聯賽按主客場制進行比賽，共需進行制進行比賽，共需進行 n(n-1