數(shù)據(jù)結(jié)構(gòu)模擬試題

1、數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)專升本考試試卷專升本考試試卷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.在帶有頭結(jié)點的雙鏈表在帶有頭結(jié)點的雙鏈表L L中，指針中，指針P P所指結(jié)點是第一個元素結(jié)點

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

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

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

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

6、置是 i i* *(i-1)/2+j(i-1)/2+j 。 12. 12. 432112113211211 432112113211211 。四、解答下列各題四、解答下列各題、已知一棵二叉樹的前序、中序列、已知一棵二叉樹的前序、中序列是是ABCDEFGHIJKABCDEFGHIJK，CDBGFEAHJIKCDBGFEAHJIK，請構(gòu)造，請構(gòu)造出該二叉樹。出該二叉樹。A AB BH HC CE EI IF FG GD DJ JK K、對下面給出的數(shù)據(jù)序列，構(gòu)造一、對下面給出的數(shù)據(jù)序列，構(gòu)造一棵哈夫曼樹，并求出其帶權(quán)路徑長度?？霉蚵鼧洌⑶蟪銎鋷?quán)路徑長度。4,5,6,7,10,12,15,18

7、,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 、設(shè)圖、設(shè)圖G=(V,E),G=(V,E), V=1,2,3,4,5,6), V=1,2,3,4,5,6), E=, E=, , , , 請寫出圖請寫出圖G G中頂點的所有拓?fù)湫蛄?。中頂點

8、的所有拓?fù)湫蛄小? 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、對下面給出的數(shù)據(jù)序列，寫出堆、對下面給出的數(shù)據(jù)序列，寫出堆排序過程。排序過程。(45,36,18,53,72,30,48,93,15)(45,36,18,53,72,30,48,93,15)454536361818535372723030484893931515939372724848535345453030181836361515大頂堆大頂堆1515727248485353454530301818363693

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

10、1,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:當(dāng)前已確定了最短距離的頂點集合當(dāng)前已確定了最短距離的頂點集合。模擬試卷一模擬試卷一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.在帶有頭結(jié)點的單鏈表在帶有頭結(jié)點的單鏈表L L中，第一中，第一個元素結(jié)點的指針是個元素結(jié)點的指針是 L-nextL-next 。 2.2.在雙循環(huán)鏈表中，在指針在雙循環(huán)鏈表中，在指針P P所指結(jié)所指結(jié)點前插入指針點前插入指針S S所指的結(jié)點，需執(zhí)行下列所指的結(jié)點，需執(zhí)行下列語句：語句： 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.設(shè)設(shè)sq1.maxsizesq1.maxsize為一個順序存為一個

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

13、ACFDBHEACF 。 A AB BC CD DH HF FE E 7 7、分別采用堆、快速、插入和歸并、分別采用堆、快速、插入和歸并排序算法對初始狀態(tài)為遞增序列的表按排序算法對初始狀態(tài)為遞增序列的表按遞增排序，遞增排序， 最省時間的算法是最省時間的算法是 插入插入 算法，算法， 最費時間的算法是最費時間的算法是 快速快速 算法。算法。 8. 8.對下圖所示的網(wǎng)，執(zhí)行對下圖所示的網(wǎng)，執(zhí)行primprim算法可得到算法可得到最小生成樹，試在下表的空白處填上適當(dāng)?shù)淖钚∩蓸?，試在下表的空白處填上適當(dāng)?shù)膬?nèi)容，以說明該算法的執(zhí)行過程。內(nèi)容，以說明該算法的執(zhí)行過程。1 13 34 42 21 15 5

14、5 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頂點頂點四、應(yīng)用題四、應(yīng)用題 1 1、已知一棵二叉樹的后序序列、中序序列、已知一棵二叉樹的后序序列、中序序列如下，請構(gòu)造該二叉樹。如下，請構(gòu)造該二叉樹。 后序序列：后序序列：ABCDEFGABCDEFG

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

16、131365 13 38 38 38 38 38 1 65 13 38 38 38 38 38 1 191913 65 49 41 41 41 1 13 65 49 41 41 41 1 383897 49 41 49 49 1 97 49 41 49 49 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、設(shè)圖、設(shè)圖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中頂點的所有拓?fù)湫蛄?。中頂點的所有拓?fù)湫蛄小? 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、對下面兩棵二叉樹，分別畫出它們、對下面兩棵二叉樹，分別畫出它們的順序存儲結(jié)構(gòu)。的順序存儲結(jié)構(gòu)。 A AB BC CD DF FI IG GE EJ JK KA AB BC CD DF FE EJ JI I順序存儲結(jié)構(gòu)。順序存儲結(jié)構(gòu)。 A AB BC CD DF FI IG GE EJ JK KK KJ JI IH

18、HG GF 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順序存儲結(jié)構(gòu)。順序存儲結(jié)構(gòu)。 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

19、 F模擬試卷二模擬試卷二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所指結(jié)點的所指結(jié)點的后繼結(jié)點的語句是后繼結(jié)點的語句是 P-next=P-next-P-next=P-next-nextnext 。 2.2.已知完全二叉樹的第八層有已知完全二叉樹的第八層有8 8個結(jié)點，個結(jié)點，則其葉子結(jié)點數(shù)是則其葉子結(jié)點數(shù)是 6868 。 3.3.

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

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

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

23、判斷其中是否存在有向回是否存在有向回路，若不存在，路，若不存在，求出其拓?fù)渑判蚯蟪銎渫負(fù)渑判?21110987654321325467989108111291011125 510109 98 811111212(1)(1)從頂點從頂點5 5出發(fā)廣度遍歷所生成的生成樹。出發(fā)廣度遍歷所生成的生成樹。(2)(2)其拓?fù)渑判颍浩渫負(fù)渑判颍?1,2,4,5,8,9,10,3,7,6,11,121,2,4,5,8,9,10,3,7,6,11,12、對下列數(shù)據(jù)表，寫出采用快速排、對下列數(shù)據(jù)表，寫出采用快速排序的每一趟的結(jié)果。序的每一趟的結(jié)果。(60,20,31,1,5,44,55,61,200,30,80,

24、150,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

25、 20 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

26、44 55 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

27、200 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

28、 80 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.在雙循環(huán)鏈表在雙循環(huán)鏈表L L中，指針中，指針P P所指結(jié)點所指結(jié)點為尾結(jié)點的條件是為尾結(jié)點的條件是 P-front=LP-front=L 。 2.2.在單鏈表中，刪除指針在單鏈表中，刪除指針P P所指結(jié)點所指結(jié)點的后繼結(jié)點的語句是的后繼結(jié)點的語句是: : P-next=P-next-nextP-next=P-next-next 。 3.3.隊列的特性是隊列的特性是 先進(jìn)先出先進(jìn)先出 。 4.4.有有n n個葉子結(jié)點的哈夫曼樹，總結(jié)個葉子結(jié)點的哈夫曼樹，總結(jié)點數(shù)是點數(shù)是 2 2* *n-1n-1 。 5. 5.有有n n個頂點的無向圖其邊數(shù)最多為個頂點的無向圖其邊

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

31、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,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,

32、12,20,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若有交換且可以回溯則必須進(jìn)行若有交換且可以回溯則必須進(jìn)行比較，直到不必交換或不可回溯比較，直到不必交換或不可回溯為止，然后再接著從剛才的位置為止，然后再接著從剛才的位置繼

33、續(xù)比較。繼續(xù)比較。整理后：整理后：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

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

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

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

37、始地址在起始地址10001000的連續(xù)內(nèi)存單元中，則的連續(xù)內(nèi)存單元中，則A5,6A5,6的地址為的地址為 1270 1270 。四、應(yīng)用題四、應(yīng)用題、已知一棵二叉樹的、已知一棵二叉樹的 中序序列是：中序序列是：DCEFBHGAKJLIMDCEFBHGAKJLIM 后序序列是：后序序列是：DFECHGBKLJMIADFECHGBKLJMIA請構(gòu)造出該二叉樹。請構(gòu)造出該二叉樹。A AB BI IC CJ JG GM MD DE EK KL LE EK K、以下面的數(shù)據(jù)作為葉子結(jié)點構(gòu)造、以下面的數(shù)據(jù)作為葉子結(jié)點構(gòu)造一棵哈夫曼樹，并求出其帶權(quán)路徑長度。一棵哈夫曼樹，并求出其帶權(quán)路徑長度。 5,6,7,

38、8,9,10,15,18,225,6,7,8,9,10,15,18,22WPL=304 WPL=304 5 56 67 78 8111115159 9101019192626151534341818222240406060100100 3 3、對下列數(shù)據(jù)表，寫出采用快速排、對下列數(shù)據(jù)表，寫出采用快速排序的每一趟的結(jié)果。并標(biāo)明每一趟排序序的每一趟的結(jié)果。并標(biāo)明每一趟排序過程的數(shù)據(jù)移動情況。第二種方法：過程的數(shù)據(jù)移動情況。第二種方法：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,

39、4,88,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

40、,44,50,61,66,100,150,166 4 4、求出下圖的所有拓?fù)湫蛄?。、求出下圖的所有拓?fù)湫蛄小?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.雙循環(huán)鏈表雙循環(huán)鏈表L L中某結(jié)點為尾結(jié)點的中某結(jié)點為尾結(jié)點的條件是條件是

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

42、G， 后序：后序：D DKIKIF FBHJBHJE EG GC CA A。A AB BC CD DF FK KI IE EG GH HJ J該二叉樹該二叉樹、對下面的遞歸算法，要求：、對下面的遞歸算法，要求： (1)(1)寫出調(diào)用寫出調(diào)用p(4)p(4)的執(zhí)行過程。的執(zhí)行過程。void p(int w)void p(int 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

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

44、-rchild) 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=s; leafhead=s; inorder(T-rchild) inorder(T-rchild)；/ /* *頭插入頭插入/ /(2)(2)功能：功能： 將中序遍歷二叉樹的葉子結(jié)點按將中序遍歷二叉樹的葉子結(jié)點按頭插入方式建立一個單鏈表。頭插入方式建立一個單鏈表。leafhea

45、dleafheadF F H H G G D D (1)(1)所建立的結(jié)構(gòu)：所建立的結(jié)構(gòu)：模擬試卷六模擬試卷六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.在雙循環(huán)鏈表中，刪除指針在雙循環(huán)鏈表中，刪除指針P P所指結(jié)所指結(jié)點的語句序列是點的語句序列是 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個結(jié)點，個結(jié)點，則其葉子結(jié)點數(shù)是則其葉子結(jié)點數(shù)是 3636 。 3.3.在有在有n n個葉子結(jié)點的哈夫曼樹中，結(jié)個葉子結(jié)點的哈夫曼樹中，結(jié)點總數(shù)是點總數(shù)是 2n-12n-1 。 4.4.有有n n個頂點的有向圖最多有個頂點的有向圖最多有 n(n-1)n(n-1) 條弧。條弧。 5. 5.高度為高度為7 7的平衡二叉樹至少有的平衡二叉樹至少有 33 33 個結(jié)點。個結(jié)點。 6.6.在有序表在有序表A1.18A1.18中，采用二分查中，采用二分查找算法查找元素值等于找算法查找元素值等于A7A7的元素，

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

48、，寫出采用快速排序算法排序的每一趟結(jié)果。算法排序的每一趟結(jié)果。 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)寫出調(diào)用寫出調(diào)用p(4)p(4)的執(zhí)行過程。的執(zhí)行過程。 (2)(2)將其轉(zhuǎn)換為等價的非遞歸算法。將其轉(zhuǎn)換為等價的非遞歸算法。void p(int w)void p(int 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)輸出結(jié)果：輸出結(jié)果：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,e,a,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)根據(jù)鄰接矩陣從頂點根據(jù)鄰接矩陣從頂點a a出發(fā)進(jìn)行出發(fā)進(jìn)行深度優(yōu)先遍歷和廣度優(yōu)先遍歷，寫出相深度優(yōu)先遍歷和廣度優(yōu)先遍

52、歷，寫出相應(yīng)的遍歷序列。應(yīng)的遍歷序列。深度優(yōu)先遍歷深度優(yōu)先遍歷:a b d c e:a b d c e廣度優(yōu)先遍歷廣度優(yōu)先遍歷: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.帶頭結(jié)點的雙循環(huán)鏈表帶頭結(jié)點的雙循環(huán)鏈表L L中，最后中，最后一個結(jié)點的指針是一個結(jié)點的指針是 L-front=LL-front=L 。 2.

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

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

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

56、相應(yīng)的廣度優(yōu)先遍歷序列為列為 a b e f c d ga b e f c d g 。a ad db bf fg ge ec c四、解答下列各題四、解答下列各題、已知一棵樹的雙親表示法如、已知一棵樹的雙親表示法如下，其中各兄弟結(jié)點是依次出現(xiàn)的，下，其中各兄弟結(jié)點是依次出現(xiàn)的，畫出該樹及其對應(yīng)的二叉樹。畫出該樹及其對應(yīng)的二叉樹。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 12

57、 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對應(yīng)的二叉樹對應(yīng)的二叉樹、一棵二叉排序樹，各結(jié)點的值從、一棵二叉排序樹，各結(jié)點的值從小到大依次為小到大依次為1 18,8,請標(biāo)出各結(jié)點的值。請標(biāo)出各結(jié)點的值。6 61 18 85 57 73 32 24 4 3 3、對下列數(shù)據(jù)表，寫出采用冒泡排、對下列數(shù)據(jù)表，寫出采用冒泡排序的每一趟的結(jié)果。序的每一趟的結(jié)果。(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所指結(jié)點的后所指結(jié)點的后插入一個結(jié)點插入一個結(jié)點S S

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

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