1、數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)專升本考試試卷專升本考試試卷1 1、單項(xiàng)選擇題、單項(xiàng)選擇題(15 (15 個(gè)小題個(gè)小題) )a ad da aa ad dc cc ca ab bd da ab ba ac cd d2 2、判斷題、判斷題(10 (10 個(gè)小題個(gè)小題) )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é)點(diǎn)的雙鏈表在帶有頭結(jié)點(diǎn)的雙鏈表L L中，指針中，指針P P所指結(jié)點(diǎn)是第一個(gè)元素結(jié)點(diǎn)

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

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

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

5、法對(duì)有交換選擇排序算法對(duì)有n n個(gè)記錄的數(shù)據(jù)表進(jìn)行排序，最壞的情況個(gè)記錄的數(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中，中，若按行序?yàn)橹餍虼鎯?chǔ)，則若按行序?yàn)橹餍虼鎯?chǔ)，則AijAij 對(duì)應(yīng)對(duì)應(yīng)的中的存儲(chǔ)位置是的中的存儲(chǔ)

6、位置是 i i* *(i-1)/2+j(i-1)/2+j 。 12. 12. 432112113211211 432112113211211 。四、解答下列各題四、解答下列各題、已知一棵二叉樹(shù)的前序、中序列、已知一棵二叉樹(shù)的前序、中序列是是ABCDEFGHIJKABCDEFGHIJK，CDBGFEAHJIKCDBGFEAHJIK，請(qǐng)構(gòu)造，請(qǐng)構(gòu)造出該二叉樹(shù)。出該二叉樹(shù)。A AB BH HC CE EI IF FG GD DJ JK K、對(duì)下面給出的數(shù)據(jù)序列，構(gòu)造一、對(duì)下面給出的數(shù)據(jù)序列，構(gòu)造一棵哈夫曼樹(shù)，并求出其帶權(quán)路徑長(zhǎng)度。棵哈夫曼樹(shù)，并求出其帶權(quán)路徑長(zhǎng)度。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 、設(shè)圖、設(shè)圖G=(V,E),G=(V,E), V=1,2,3,4,5,6), V=1,2,3,4,5,6), E=, E=, , , , 請(qǐng)寫出圖請(qǐng)寫出圖G G中頂點(diǎn)的所有拓?fù)湫蛄小Ｖ许?/p>

8、點(diǎn)的所有拓?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、對(duì)下面給出的數(shù)據(jù)序列，寫出堆、對(duì)下面給出的數(shù)據(jù)序列，寫出堆排序過(guò)程。排序過(guò)程。(45,36,18,53,72,30,48,93,15)(45,36,18,53,72,30,48,93,15)454536361818535372723030484893931515939372724848535345453030181836361515大頂堆大頂堆151572724848535345453030181836369

9、393輸出輸出93727253534848363645453030181815159393調(diào)整調(diào)整151553534848363645453030181872729393輸出輸出7272535345454848363615153030181872729393調(diào)整調(diào)整請(qǐng)自己繼續(xù)完成請(qǐng)自己繼續(xù)完成、利用、利用DijkstraDijkstra算法求出下圖中從算法求出下圖中從頂點(diǎn)到其余頂點(diǎn)的最短路徑。頂點(diǎn)到其余頂點(diǎn)的最短路徑。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:當(dāng)前已確定了最短距離的頂點(diǎn)集合當(dāng)前已確定了最短距離的頂點(diǎn)集合。模擬試卷一模擬試卷一1 1、單項(xiàng)選擇題、單項(xiàng)選擇題(9 (9 個(gè)小題個(gè)小題) )3 34 41 11 12 24 41 14 44 42 2、判斷題、判斷題(4 (4 個(gè)小題個(gè)小題) )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é)點(diǎn)的單鏈表在帶有頭結(jié)點(diǎn)的單鏈表L L中，第一中，第一個(gè)元素結(jié)點(diǎn)的指針是個(gè)元素結(jié)點(diǎn)的指針是 L-nextL-next 。 2.2.在雙循環(huán)鏈表中，在指針在雙循環(huán)鏈表中，在指針P P所指結(jié)所指結(jié)點(diǎn)前插入指針點(diǎn)前插入指針S S所指的結(jié)點(diǎn)，需執(zhí)行下列所指的結(jié)點(diǎn)，需執(zhí)行下列語(yǔ)句：語(yǔ)句： 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為一個(gè)順序存為一

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

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

14、55 52 24 42,4,3,2,4,3,11(U,V)(U,V)代價(jià)代價(jià) 1 12,4,32,4,3(2,1)(2,1)1(U,V)(U,V)代價(jià)代價(jià)1,31,32,42,4(2,3)(2,3)4(4,1)(4,1)5 5(U,V)(U,V)代價(jià)代價(jià)1,3,1,3,4422(2,4)(2,4)3(2,3)(2,3)4(2,1)(2,1)(U,V)(U,V)代價(jià)代價(jià)V VU U4 43 31 1頂點(diǎn)頂點(diǎn)四、應(yīng)用題四、應(yīng)用題 1 1、已知一棵二叉樹(shù)的后序序列、中序序列、已知一棵二叉樹(shù)的后序序列、中序序列如下，請(qǐng)構(gòu)造該二叉樹(shù)。如下，請(qǐng)構(gòu)造該二叉樹(shù)。 后序序列：后序序列：ABCDEFGABCDEF

15、G 中序序列：中序序列：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 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、設(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、 , , 請(qǐng)寫出圖請(qǐng)寫出圖G G中頂點(diǎn)的所有拓?fù)湫蛄小Ｖ许旤c(diǎn)的所有拓?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、對(duì)下面兩棵二叉樹(shù)，分別畫出它們、對(duì)下面兩棵二叉樹(shù)，分別畫出它們的順序存儲(chǔ)結(jié)構(gòu)。的順序存儲(chǔ)結(jié)構(gòu)。 A AB BC CD DF FI IG GE EJ JK KA AB BC CD DF FE EJ JI I順序存儲(chǔ)結(jié)構(gòu)。順序存儲(chǔ)結(jié)構(gòu)。 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順序存儲(chǔ)結(jié)構(gòu)。順序存儲(chǔ)結(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 F模擬

19、試卷二模擬試卷二1 1、單項(xiàng)選擇題、單項(xiàng)選擇題(5 (5 個(gè)小題個(gè)小題) )2 2、判斷題、判斷題(9 (9 個(gè)小題個(gè)小題) )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é)點(diǎn)的所指結(jié)點(diǎn)的后繼結(jié)點(diǎn)的語(yǔ)句是后繼結(jié)點(diǎn)的語(yǔ)句是 P-next=P-next-P-next=P-next-nextnext 。 2.2.已知完全二叉樹(shù)的第八層有已知完全二叉樹(shù)的第八層有8 8個(gè)結(jié)點(diǎn)，個(gè)結(jié)點(diǎn)，則其葉子結(jié)點(diǎn)數(shù)是則其葉子結(jié)點(diǎn)數(shù)是 6868 。 3.3.將下三角

20、矩陣將下三角矩陣1.8,1.81.8,1.8的下三的下三角部分逐行地存儲(chǔ)到起始地址為角部分逐行地存儲(chǔ)到起始地址為10001000的的內(nèi)存單元中，已知每個(gè)元素占用內(nèi)存單元中，已知每個(gè)元素占用4 4個(gè)單元，個(gè)單元，則則A7,5A7,5的地址是的地址是 11041104 。 4. 4.有有n n個(gè)頂點(diǎn)的強(qiáng)連通有向圖個(gè)頂點(diǎn)的強(qiáng)連通有向圖G G至少至少有有 n n 條弧。條弧。 5.5.求最短路徑的求最短路徑的DijkstraDijkstra算法的時(shí)間算法的時(shí)間復(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)用題、已知一棵二叉樹(shù)的、已知一棵二叉樹(shù)的 前序序列是：前序序列是：ABCDEFGHIJABCDEFGHIJ， 中序序列是：中序序列是：CBEDAGHFJICBEDAGHFJI

22、，請(qǐng)構(gòu)造出該二叉樹(shù)。請(qǐng)構(gòu)造出該二叉樹(shù)。A AB BF FC CD DG GI IE EH HJ J、對(duì)下面給出的數(shù)據(jù)序列，構(gòu)造一、對(duì)下面給出的數(shù)據(jù)序列，構(gòu)造一棵哈夫曼樹(shù)，并求出其帶權(quán)路徑長(zhǎng)度。棵哈夫曼樹(shù)，并求出其帶權(quán)路徑長(zhǎng)度。 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)畫出從頂畫出從頂點(diǎn)點(diǎn)5 5出發(fā)進(jìn)行廣度出發(fā)進(jìn)行廣度遍歷所生成的生遍歷所生成的生成樹(shù)。成樹(shù)。 (2)(2)判斷其中判斷其中

23、是否存在有向回是否存在有向回路，若不存在，路，若不存在，求出其拓?fù)渑判蚯蟪銎渫負(fù)渑判?21110987654321325467989108111291011125 510109 98 811111212(1)(1)從頂點(diǎn)從頂點(diǎn)5 5出發(fā)廣度遍歷所生成的生成樹(shù)。出發(fā)廣度遍歷所生成的生成樹(shù)。(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、對(duì)下列數(shù)據(jù)表，寫出采用快速排、對(duì)下列數(shù)據(jù)表，寫出采用快速排序的每一趟的結(jié)果。序的每一趟的結(jié)果。(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、單項(xiàng)選擇題、單項(xiàng)選擇題(9 (9 個(gè)小題個(gè)小題) )d db bd dc ca ac cc cd db b2 2、判斷題、判斷題(7 (7 個(gè)小題個(gè)小題) )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é)點(diǎn)所指結(jié)點(diǎn)為尾結(jié)點(diǎn)的條件是為尾結(jié)點(diǎn)的條件是 P-front=LP-front=L 。 2.2.在單鏈表中，刪除指針在單鏈表中，刪除指針P P所指結(jié)點(diǎn)所指結(jié)點(diǎn)的后繼結(jié)點(diǎn)的語(yǔ)句是的后繼結(jié)點(diǎn)的語(yǔ)句是: : P-next=P-next-nextP-next=P-next-next 。 3.3.隊(duì)列的特性是隊(duì)列的特性是 先進(jìn)先出先進(jìn)先出 。 4.4.有有n n個(gè)葉子結(jié)點(diǎn)的哈夫曼樹(shù)，總結(jié)個(gè)葉子結(jié)點(diǎn)的哈夫曼樹(shù)，總結(jié)點(diǎn)數(shù)是點(diǎn)數(shù)是 2 2* *n-1n-1 。 5. 5.有有n n個(gè)頂點(diǎn)的無(wú)向圖其邊數(shù)最多為個(gè)頂點(diǎn)的無(wú)向圖其邊數(shù)最多為

30、 n n* *(n-1)/2(n-1)/2 。 6.6.對(duì)矩陣采用壓縮存儲(chǔ)是為了對(duì)矩陣采用壓縮存儲(chǔ)是為了 節(jié)省節(jié)省存儲(chǔ)空間存儲(chǔ)空間 。 四、應(yīng)用題四、應(yīng)用題、分別畫出滿足下列條件的所有二、分別畫出滿足下列條件的所有二叉樹(shù)。叉樹(shù)。 前序序列和中序序列均為前序序列和中序序列均為ABCDEABCDE。 前序序列為前序序列為ABCDEABCDE，并且與其相對(duì)于，并且與其相對(duì)于應(yīng)的樹(shù)高度為應(yīng)的樹(shù)高度為5 5。1)1)A AB BC CD DE E2)2)A AB BC CD DE E2 2、對(duì)下列數(shù)據(jù)表，寫出采用、對(duì)下列數(shù)據(jù)表，寫出采用shellshell排排序的每一趟的結(jié)果。序的每一趟的結(jié)果。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若有交換且可以回溯則必須進(jìn)行若有交換且可以回溯則必須進(jìn)行比較，直到不必交換或不可回溯比較，直到不必交換或不可回溯為止，然后再接著從剛才的位置為止，然后再接著從剛才的位置繼續(xù)比較。

33、繼續(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、單項(xiàng)選擇題、單項(xiàng)選擇題(6 (6 個(gè)小題個(gè)小題) )a ab bc ca ac ca a2 2、判斷題、判斷題(6 (6 個(gè)小題個(gè)小題) )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.帶頭結(jié)點(diǎn)的雙循環(huán)鏈表帶頭結(jié)點(diǎn)的雙循環(huán)鏈表L L為空表的為空表的條件是條件是 L-front=LL-front=L 。 2.2.在雙鏈表中，在指針在雙鏈表中，在指針P P所指結(jié)點(diǎn)前所指結(jié)點(diǎn)前面插入一個(gè)結(jié)點(diǎn)面插入一個(gè)結(jié)點(diǎn)S S的語(yǔ)句序列是：的語(yǔ)句序列是：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.已知完全二叉樹(shù)的第已知完全二叉樹(shù)的第7 7層有層有1

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

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

37、起始地址10001000的連續(xù)內(nèi)存單元中，則的連續(xù)內(nèi)存單元中，則A5,6A5,6的地址為的地址為 1270 1270 。四、應(yīng)用題四、應(yīng)用題、已知一棵二叉樹(shù)的、已知一棵二叉樹(shù)的 中序序列是：中序序列是：DCEFBHGAKJLIMDCEFBHGAKJLIM 后序序列是：后序序列是：DFECHGBKLJMIADFECHGBKLJMIA請(qǐng)構(gòu)造出該二叉樹(shù)。請(qǐng)構(gòu)造出該二叉樹(shù)。A AB BI IC CJ JG GM MD DE EK KL LE EK K、以下面的數(shù)據(jù)作為葉子結(jié)點(diǎn)構(gòu)造、以下面的數(shù)據(jù)作為葉子結(jié)點(diǎn)構(gòu)造一棵哈夫曼樹(shù)，并求出其帶權(quán)路徑長(zhǎng)度。一棵哈夫曼樹(shù)，并求出其帶權(quán)路徑長(zhǎng)度。 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、對(duì)下列數(shù)據(jù)表，寫出采用快速排、對(duì)下列數(shù)據(jù)表，寫出采用快速排序的每一趟的結(jié)果。并標(biāo)明每一趟排序序的每一趟的結(jié)果。并標(biāo)明每一趟排序過(guò)程的數(shù)據(jù)移動(dòng)情況。第二種方法：過(guò)程的數(shù)據(jù)移動(dòng)情況。第二種方法：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、求出下圖的所有拓?fù)湫蛄小！⑶蟪鱿聢D的所有拓?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、單項(xiàng)選擇題、單項(xiàng)選擇題(7 (7 個(gè)小題個(gè)小題) )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é)點(diǎn)為尾結(jié)點(diǎn)的中某結(jié)點(diǎn)為尾結(jié)點(diǎn)的條件是條件是 P-f

41、ront=LP-front=L 。 2.2.已知二叉樹(shù)中葉子結(jié)點(diǎn)數(shù)為已知二叉樹(shù)中葉子結(jié)點(diǎn)數(shù)為5050，僅，僅有一個(gè)孩子的結(jié)點(diǎn)數(shù)為有一個(gè)孩子的結(jié)點(diǎn)數(shù)為3030，則整個(gè)二叉，則整個(gè)二叉樹(shù)的結(jié)點(diǎn)數(shù)是樹(shù)的結(jié)點(diǎn)數(shù)是 129129 。三、解答下列各題三、解答下列各題、一棵二叉樹(shù)的前序、中序和后序、一棵二叉樹(shù)的前序、中序和后序分別如下，其中有一部分未顯示出來(lái)，分別如下，其中有一部分未顯示出來(lái)，試求出空格處的內(nèi)容，并畫出該二叉樹(shù)。試求出空格處的內(nèi)容，并畫出該二叉樹(shù)。 前序：前序：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該二叉樹(shù)該二叉樹(shù)、對(duì)下面的遞歸算法，要求：、對(duì)下面的遞歸算法，要求： (1)(1)寫出調(diào)用寫出調(diào)用p(4)p(4)的執(zhí)行過(guò)程。的執(zhí)行過(guò)程。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、已知二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)為二叉鏈表，、已知二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)為二叉鏈表，閱讀下面算法。對(duì)如下所示的二叉樹(shù)。閱讀下面算法。對(duì)如下所示的二叉樹(shù)。 (1)(1)畫出執(zhí)行上述算法后所建立的結(jié)。畫出執(zhí)行上述算法后所建立的結(jié)。 (2)(2)說(shuō)明該算法的功能。說(shuō)明該算法的功能。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)功能：功能： 將中序遍歷二叉樹(shù)的葉子結(jié)點(diǎn)按將中序遍歷二叉樹(shù)的葉子結(jié)點(diǎn)按頭插入方式建立一個(gè)單鏈表。頭插入方式建立一個(gè)單鏈表。leafhea

45、dleafheadF F H H G G D D (1)(1)所建立的結(jié)構(gòu)：所建立的結(jié)構(gòu)：模擬試卷六模擬試卷六1 1、單項(xiàng)選擇題、單項(xiàng)選擇題(4 (4 個(gè)小題個(gè)小題) )d dc ca ad d2 2、判斷題、判斷題(7 (7 個(gè)小題個(gè)小題) )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é)點(diǎn)的語(yǔ)句序列是點(diǎn)的語(yǔ)句序列是 P-front-back=P-back P-front-back=P-back 和和 P-back-front=P-front P-back

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

47、所的元素，所比較過(guò)的元素下標(biāo)依次為比較過(guò)的元素下標(biāo)依次為 9,4,6,79,4,6,7 。 7.7.冒泡排序算法在最好的情況下的元冒泡排序算法在最好的情況下的元素交換次數(shù)為素交換次數(shù)為 0 0 。 四、解答下列各題四、解答下列各題、已知一棵樹(shù)的、已知一棵樹(shù)的 前序序列是：前序序列是：ABCDEFGHIJKLMNABCDEFGHIJKLMN 后序序列是：后序序列是：CDEBHIGKMLNJFACDEBHIGKMLNJFA請(qǐng)構(gòu)造出該樹(shù)。請(qǐng)構(gòu)造出該樹(shù)。 該樹(shù)為：該樹(shù)為：A AB BF FC CE ED DK KG GJ JH HI IL LN NM M. .對(duì)下面的數(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到其他頂點(diǎn)的最短路徑。到其他頂點(diǎn)的最短路徑。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、對(duì)下面的遞歸算法，要求：、對(duì)下面的遞歸算法，要求： (1)(1)寫出調(diào)用寫出調(diào)用p(4)p(4)的執(zhí)行過(guò)程。的執(zhí)行過(guò)程。 (2)(2)將其轉(zhuǎn)換為等價(jià)的非遞歸算法。將其轉(zhuǎn)換為等價(jià)的非遞歸算法。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)輸出結(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、已知一個(gè)無(wú)向圖的頂點(diǎn)集為：、已知一個(gè)無(wú)向圖的頂點(diǎn)集為： 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)根據(jù)鄰接矩陣從頂點(diǎn)根據(jù)鄰接矩陣從頂點(diǎn)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、單項(xiàng)選擇題、單項(xiàng)選擇題(4 (4 個(gè)小題個(gè)小題) )c cb bc cd d2 2、判斷題、判斷題(6 (6 個(gè)小題個(gè)小題) )1 2 3 41 2 3 41 2 3 4 5 6 1 2 3 4 5 6 三、填空題三、填空題 1.1.帶頭結(jié)點(diǎn)的雙循環(huán)鏈表帶頭結(jié)點(diǎn)的雙循環(huán)鏈表L L中，最后中，最后一個(gè)結(jié)點(diǎn)的指針是一個(gè)結(jié)點(diǎn)的指針是 L-front=LL-front=L 。 2.2

53、.在僅有尾指針在僅有尾指針p p的單循環(huán)鏈表中，的單循環(huán)鏈表中，在表尾插入一個(gè)結(jié)點(diǎn)在表尾插入一個(gè)結(jié)點(diǎn)S S的語(yǔ)句序列是的語(yǔ)句序列是 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.已知循環(huán)隊(duì)列用數(shù)組已知循環(huán)隊(duì)列用數(shù)組data1.ndata1.n存存儲(chǔ)元素，用儲(chǔ)元素，用f,rf,r分別作為頭尾指針，則分別作為頭尾指針，則當(dāng)前的元素個(gè)數(shù)是當(dāng)前的

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

55、少為 n-1n-1 。 8.8.已知數(shù)組已知數(shù)組A1.10,1.10A1.10,1.10為對(duì)稱矩為對(duì)稱矩陣，其中每個(gè)元素占用陣，其中每個(gè)元素占用5 5個(gè)單元，現(xiàn)將個(gè)單元，現(xiàn)將其下三角按行優(yōu)先次序存儲(chǔ)在起始地址其下三角按行優(yōu)先次序存儲(chǔ)在起始地址10001000的連續(xù)內(nèi)存單元中，則的連續(xù)內(nèi)存單元中，則A6,5A6,5對(duì)應(yīng)對(duì)應(yīng)的地址為的地址為 11001100 。9.9.線性線性- -選擇排序算法在最好的情況下選擇排序算法在最好的情況下所交換元素的次數(shù)為所交換元素的次數(shù)為 0 0 。 10. 10.已知一個(gè)圖的廣度優(yōu)先生成樹(shù)如已知一個(gè)圖的廣度優(yōu)先生成樹(shù)如圖所示，則與此相應(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四、解答下列各題四、解答下列各題、已知一棵樹(shù)的雙親表示法如、已知一棵樹(shù)的雙親表示法如下，其中各兄弟結(jié)點(diǎn)是依次出現(xiàn)的，下，其中各兄弟結(jié)點(diǎn)是依次出現(xiàn)的，畫出該樹(shù)及其對(duì)應(yīng)的二叉樹(shù)。畫出該樹(shù)及其對(duì)應(yīng)的二叉樹(shù)。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該樹(shù)該樹(shù)A AB BC CD DE EF FG GH HI IJ JK KL LM MN NO O對(duì)應(yīng)的二叉樹(shù)對(duì)應(yīng)的二叉樹(shù)、一棵二叉排序樹(shù)，各結(jié)點(diǎn)的值從、一棵二叉排序樹(shù)，各結(jié)點(diǎn)的值從小到大依次為小到大依次為1 18,8,請(qǐng)標(biāo)出各結(jié)點(diǎn)的值。請(qǐng)標(biāo)出各結(jié)點(diǎn)的值。6 61 18 85 57 73 32 24 4 3 3、對(duì)下列數(shù)據(jù)表，寫出采用冒泡排、對(duì)下列數(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、求出下圖的最小生成樹(shù)。、求出下圖的最小生成樹(shù)。 68 87 76574535865384 4 4、求出下圖的最小生成樹(shù)。、求出下圖的最小生成樹(shù)。 65435634模擬試卷八模擬試卷八1 1、單項(xiàng)選擇題、單項(xiàng)選擇題(3 (3 個(gè)小題個(gè)小題) )2 2、判斷題、判斷題(5 (5 個(gè)小題個(gè)小題) )1 2 3 1 2 3 1 2 3 4 5 1 2 3 4 5 三、填空題三、填空題 1.1.在單鏈表中，在指針在單鏈表中，在指針P P所指結(jié)點(diǎn)的后所指結(jié)點(diǎn)的后插入一個(gè)結(jié)點(diǎn)插入一個(gè)結(jié)點(diǎn)S

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

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