數(shù)據(jù)結(jié)構(gòu)練習(xí)2

1、數(shù)據(jù)結(jié)構(gòu)練習(xí)(二)答案一、填空題：1 若一棵樹的括號(hào)表示為 A (B (E, F), C (G (H,I,J,K) ,L) ,D ( M (N), 則該樹的度為(1) 4，樹的深度為(2) 4，樹中葉子結(jié)點(diǎn)的個(gè)數(shù)為(3) 8。2. 棵滿二叉樹中有 m個(gè)葉子，n個(gè)結(jié)點(diǎn)，深度為h,請(qǐng)寫出m、n、h之間hh-1關(guān)系的表達(dá)式(4) n=2 -1,m=n+1-2n=2m-1 。3. 棵二叉樹中如果有n個(gè)葉子結(jié)點(diǎn)，則這棵樹上最少有(5) 2n-1個(gè)結(jié)點(diǎn)。k-1k一棵深度為k的完全二叉樹中最少有_2 (6)個(gè)結(jié)點(diǎn)，最多有(7)2-1個(gè) 結(jié)點(diǎn)。4. 具有n個(gè)結(jié)點(diǎn)的二叉樹，當(dāng)它是一棵_(8)完全二叉樹時(shí)具有最小

2、高度 (9) log 2n+1_，當(dāng)它為一棵單支樹時(shí)具有高度 _(10) n _。5. 對(duì)具有n個(gè)結(jié)點(diǎn)的完全二叉樹按照層次從上到下，每一層從左到右的次序?qū)λ薪Y(jié)點(diǎn)進(jìn)行編號(hào)，編號(hào)為i的結(jié)點(diǎn)的雙親結(jié)點(diǎn)的編號(hào)為_(11)_i/2 _， 左孩子的編號(hào)為_2i，右孩子的編號(hào)為_2i+1。6. 若具有n個(gè)結(jié)點(diǎn)的二叉樹采用二叉鏈表存儲(chǔ)結(jié)構(gòu)，則該鏈表中有_2n_個(gè)指針域，其中有_n-1_個(gè)指針域用于孩子結(jié)點(diǎn)，_n+1_個(gè)指針域空閑存放著 NULL。7. 二叉樹的遍歷方式通常有 先序_、_中序_、后序_和層序_四種。8. 已知二叉樹的前序遍歷序列為 ABDCEFG中序遍歷序列為DBCAFEG其后序遍歷序列為DC

3、BFGEA。9. 已知某完全二叉樹采用順序存儲(chǔ)結(jié)構(gòu)，結(jié)點(diǎn)的存放次序?yàn)锳, B,C,D,E,F,G,H,I,J ，該完全二叉樹的后序序列為 _HIDJEBFGCA 。10. 若具有n個(gè)結(jié)點(diǎn)的非空二叉樹有n0個(gè)葉結(jié)點(diǎn)，則該二叉樹有_n°-1_個(gè)度為2的結(jié)點(diǎn)，n-2n°+1個(gè)度為1的結(jié)點(diǎn)。11. 任何非空樹中有且僅有一個(gè)結(jié)點(diǎn)沒有前驅(qū)結(jié)點(diǎn)，該結(jié)點(diǎn)就是樹的根。度為k的樹中第i層最多有 ki-1 結(jié)點(diǎn)(i>=1)，深度為h的k叉樹最多有k°+k+.+k h 1個(gè)結(jié)點(diǎn)。12. 非空二叉樹一共有_4種基本形態(tài)，第i層最多有_ 2i-1個(gè)結(jié)點(diǎn)。13. 在一棵完全二叉樹中，編號(hào)

4、i和編號(hào)j的兩個(gè)結(jié)點(diǎn)處于同一層的條件是_lOg2i=lOg2j_14. 有n個(gè)頂點(diǎn)的強(qiáng)連通圖至少有(7) n _弧，有n個(gè)頂點(diǎn)的連通圖至少有(8) n-1 邊。15. 設(shè)無向圖G的頂點(diǎn)數(shù)為n,圖G最少有 (12) 0 邊,最多有 (13) n(n-1)/2條邊；若邊數(shù)為e,用鄰接矩陣表示圖，求每一頂點(diǎn)度的時(shí)間復(fù)雜性為(14)0(n2);若用鄰接表表示圖，訪問一個(gè)頂點(diǎn)的所有鄰接頂點(diǎn)的時(shí)間復(fù)雜性為 (15) 0(n)。一個(gè)有n個(gè)頂點(diǎn)的有向圖中，最少有 (16)0 弧，最多有 (17) n(n-1)弧。二、選擇題1. 樹型結(jié)構(gòu)最適合用來描述A. 有序的數(shù)據(jù)元素B.無序的數(shù)據(jù)元素C數(shù)據(jù)元素之間具有層次

5、關(guān)系的數(shù)據(jù)D.數(shù)據(jù)元素之間沒有關(guān)系的數(shù)據(jù)2. 對(duì)于一棵具有n個(gè)結(jié)點(diǎn)、度為4的樹而言，。A. 樹的深度最多是n-4B.樹的深度最多是n-3C.第i層上最多有4 x (i-1)個(gè)結(jié)點(diǎn)3. ”二叉樹為空”意味著二叉樹 A.由一些未賦值的空結(jié)點(diǎn)組成B.根結(jié)點(diǎn)無子樹c.不存在D，沒有結(jié)點(diǎn)4. 按照二叉樹的定義，具有3個(gè)結(jié)點(diǎn)的二叉樹有_種形態(tài)(不考慮數(shù)據(jù)信息的 組合情況)。A.2B.3C.4D.55. 若一棵二叉樹具有10個(gè)度為2的結(jié)點(diǎn)，5個(gè)度為1的結(jié)點(diǎn)，則度為0的結(jié) 點(diǎn)個(gè)數(shù)為。A . 9B. 11C. 15D .不確定6. 一個(gè)具有1025個(gè)結(jié)點(diǎn)的二叉樹的高h(yuǎn)為。A. 11B. 10C . 111025

6、D . 1210247. 若二叉樹的前序序列與后序序列的次序正好相反,則該二叉樹一定是 _樹。A.空或僅有一個(gè)結(jié)點(diǎn)B .其分支結(jié)點(diǎn)無左子樹C.其分支結(jié)點(diǎn)無右子樹D.其分支結(jié)點(diǎn)的度都為18. 任何一棵非空二叉樹中的葉結(jié)點(diǎn)在前序遍歷、中序遍歷與后序遍歷中的相 對(duì)位置_A.都會(huì)發(fā)生改變B .不會(huì)發(fā)生改變C.有可能會(huì)發(fā)生改變D.部分會(huì)發(fā)生改變9 .如圖所示的二叉樹T2是由森林T1轉(zhuǎn)換而來的二叉樹，那么森林T1有 葉子結(jié)點(diǎn)。A . 4 B . 5 C . 6 D . 710 .設(shè)n，m為一棵二叉樹上的兩個(gè)結(jié)點(diǎn)，在中序遍歷時(shí)，n在m前的條件是。A . n在m右方 B . n是m祖先C . n在m左方 D

7、. n是m子11 . 一棵二叉樹的先序遍歷序列為 ABCDEFG，它的中序遍歷序列可能是 。A. CABDEFG囘.ABCDEFG C. DACEFBG D. ADCFEGB12. 引入線索二叉樹的目的是 。A .加快查找結(jié)點(diǎn)的前驅(qū)或后繼結(jié)點(diǎn)的速度C.為了能方便找到雙親B. 為了能在二叉樹中方便插入和刪除D .使二叉樹的遍歷結(jié)果唯一13. 線索二叉樹是一種 吉構(gòu)。A .邏輯B .邏輯和存儲(chǔ)C .物理D .線性14 .判斷線索二叉樹中*p結(jié)點(diǎn)有右孩子結(jié)點(diǎn)的條件是 。A . p! =NULLB . P >rchild!=NULLC . p>rtag=0D . p>rtag=115

8、. n個(gè)結(jié)點(diǎn)的線索二叉樹上含有的線索數(shù)為 。A . 2nB . n-1C . n+1D . n16 .根據(jù)使用頻率為5個(gè)字符設(shè)計(jì)的哈夫曼編碼不可能是 oA. 000, 001, 010, 011, 1C. 000, 001, 01, 10, 11B. 0000, 0001, 001, 01, 1D. 00, 100, 101, 110, 111個(gè)結(jié)點(diǎn)18 .設(shè)有13個(gè)值，用它們組成一棵哈夫曼樹，則該哈夫曼樹共有 A . 13B . 12C . 26D . 2519 .在一個(gè)圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)的 倍D.4A.1/2B.1C.220 . 一個(gè)具有n個(gè)頂點(diǎn)的無向圖最多有 邊。A.n

9、(n-1)/2B. n(n-1)C. n(n+1)/2D.n21 . 一個(gè)具有n個(gè)頂點(diǎn)的有向圖最多有 邊。A.n(n-1)/2血 n(n-1)C.n(n+1)/2 D.n22 .在一個(gè)具有n個(gè)頂點(diǎn)的無向圖中，要連通全部頂點(diǎn)至少需要 邊A.nB.n+1C.n-1D.2 n23 .具有n個(gè)頂點(diǎn)的連通圖的生成樹一定有 邊。A.nB.n+1C.n-1D.2 n24 .若一個(gè)非連通的無向圖最多有28條邊，則該無向圖至少有 個(gè)項(xiàng)點(diǎn)A.6B.7C.8D.925 .在帶權(quán)圖中，兩個(gè)頂點(diǎn)之間的路徑長(zhǎng)度是 oA.路徑上的頂點(diǎn)數(shù)目B.路徑上的邊的數(shù)目C路徑上頂點(diǎn)和邊的數(shù)目D .路徑上所有邊上的權(quán)值之和26 .若具有

10、n個(gè)頂點(diǎn)的元向圖采用鄰接矩陣存儲(chǔ)方法，該鄰接矩陣一定為一個(gè)OA. 一般矩陣B .對(duì)稱矩陣C.對(duì)角矩陣D.稀疏矩陣27 .若圖的鄰接矩陣中主對(duì)角線上的元素均為 0,其余元素全為1,則可以斷定該圖一定_oA.是無向圖 B .是有向圖C.是完全圖D.不是帶權(quán)圖28. 有向圖的鄰接表的第i個(gè)鏈表中的邊結(jié)點(diǎn)數(shù)目是第i個(gè)頂點(diǎn)的_A.度數(shù)B.出度C.人數(shù)D.邊數(shù)29. 若某圖的鄰接表中的邊結(jié)點(diǎn)數(shù)目為奇數(shù)，貝U該圖 oA. 定有奇數(shù)個(gè)頂點(diǎn)B. 定有偶數(shù)個(gè)頂點(diǎn)C 一定是有向圖D.可能是無向圖30. 若某圖的鄰接表中的邊結(jié)點(diǎn)數(shù)目為偶數(shù)，則該圖 oA.定是無向圖B.可能是有向圖C可能是無向圖，也可能是有向圖D. 定

11、有偶數(shù)個(gè)頂點(diǎn)31. 若無向圖有k條邊，則相應(yīng)的鄰接表中就有 邊結(jié)點(diǎn)。A.k-1B.kC.2kD.k232. 若有向圖有k條邊，則相應(yīng)的鄰接表中就有 邊結(jié)點(diǎn)。A.k-1B.kC.2kD.k233. 對(duì)于一個(gè)不帶權(quán)的無向圖的鄰接矩陣而言， A.矩陣中非零元素的數(shù)目等于圖中邊的數(shù)目矩陣中非全零的行的數(shù)目等于圖中頂點(diǎn)的數(shù)目第i行的非零元素的數(shù)目與第i列的非零元素的數(shù)目相等第i行與第i列的非零元素的總數(shù)等于第i個(gè)頂點(diǎn)的度數(shù)導(dǎo)致圖的遍歷序列不惟一的因素有 。出發(fā)點(diǎn)不同、遍歷方法不同B.出發(fā)點(diǎn)不同、存儲(chǔ)結(jié)構(gòu)不同遍歷方法不同、存儲(chǔ)結(jié)構(gòu)不同D.出發(fā)點(diǎn)不同、存儲(chǔ)結(jié)構(gòu)不同、遍歷方法不同35. 若從無向圖的任意一個(gè)頂

12、點(diǎn)出發(fā)進(jìn)行一次深度優(yōu)先搜索便可以訪問該圖的所有頂點(diǎn)，則該圖一定是一個(gè) 0A.非連通B.連通C .強(qiáng)連通D.完全36. 可以進(jìn)行拓?fù)渑判虻膱D一定是 oA.連通圖 B .帶權(quán)連通圖C.無回路的圖 D.無回路的有向圖37. 已知某有向圖 G=(V,E)，其中 V=v1,v2,v3,v4,v5,v6, E=<v1,v2>,<v1,v4>,<v2,v6> , <v3,v1>,vv3,v4>,vv4,v5>,vv5,v2>vv5,v6>,G的拓?fù)湫虼醮缡莖A. v3,v1,v4,v5,v2,v6B. v3,v4,v1,v5,v2,v6

13、C. v1,v3,v4,v5,v2,v6D. v1,v4,v3,v5,v2,v638. 下面關(guān)于AO網(wǎng)的敘述中，不正確的是 oA. 若所有關(guān)鍵活動(dòng)都提前完成，則整個(gè)工程一定能夠提前完成B. 即使所有非關(guān)鍵活動(dòng)都未按時(shí)完成，整個(gè)工程仍有可能按時(shí)完成C. 任何一個(gè)關(guān)鍵活動(dòng)的延期完成，都會(huì)導(dǎo)致整個(gè)工程的延期完成 D任何一個(gè)關(guān)鍵活動(dòng)的提前完成，都會(huì)導(dǎo)致整個(gè)工程的提前完成39. 無向圖的鄰接矩陣是一個(gè) .A .對(duì)稱矩陣B .零矩陣C. 上三角矩陣D .對(duì)角矩陣40 .如果從無向圖的任一頂點(diǎn)出發(fā)進(jìn)行一次深度優(yōu)先搜索即可訪問所有頂點(diǎn)，則該圖一定是。A .完全圖B.連通圖C.有回路D .一棵樹41 .采用鄰接

14、表存儲(chǔ)的圖的深度優(yōu)先遍歷算法類似于二叉樹的 法。A .先序遍歷B .中序遍歷C.后序遍歷D .按層遍歷42. 一個(gè)無向連通圖的生成樹是含有該連通圖的全部頂點(diǎn)的 A .極小聯(lián)通子圖B.極小子圖C.極通子圖 D.極大子圖43. 任何一個(gè)無向連通圖 最小生成樹。A .只有一棵旦.有一棵或多棵C. 一定有多棵D .可能不存在44. 求最短路徑的Dijkstra算法的時(shí)間復(fù)雜度為 。A. O (n)B. O (n+e)C. O (n2)D. O (n3)45. 求最短路徑的Floyd算法的時(shí)間復(fù)雜度為。A. O (n)B. O (ne)C. O (n2)D . O (n3)45-2有向網(wǎng)G用鄰接矩陣A存

15、儲(chǔ)，則頂點(diǎn)i的入度等于A中。A) 第i行非的元素之和C)第i列非的元素之和B) 第i行非 且非0的元素個(gè)數(shù)D)第i列非 且非0的元素個(gè)數(shù)46. 關(guān)鍵路徑是事件結(jié)點(diǎn)網(wǎng)中 。A從起點(diǎn)到終點(diǎn)的最長(zhǎng)路徑B從起點(diǎn)到終點(diǎn)的最短路徑C.最長(zhǎng)的回路D.最短的回路47. 已知一個(gè)有向圖如右圖所示，則從頂點(diǎn)a出發(fā)進(jìn)行深度優(yōu)先遍歷不可能得到的DFS序列為。A) adbefc B) adcefb C ) adcbfeD)adefcb三、判斷題(1) 在樹型結(jié)構(gòu)中，每一個(gè)結(jié)點(diǎn)最多只有一個(gè)前驅(qū)結(jié)點(diǎn)， 但可以有多個(gè)后繼結(jié)點(diǎn).(2) 在樹型結(jié)構(gòu)中，每一個(gè)結(jié)點(diǎn)不能沒有前驅(qū)結(jié)點(diǎn)。(3) 在度為k的樹中，至少有一個(gè)度為k的結(jié)點(diǎn)。(

16、4) 在度為k的樹中，每個(gè)結(jié)點(diǎn)最多有k-1個(gè)兄弟結(jié)點(diǎn)。(5) 度為2的樹是二叉樹。(6) 二叉樹的度一定為2。(7) 在非空完全二叉樹中，只有最下面一層的結(jié)點(diǎn)為葉結(jié)點(diǎn)(8) 在完全二叉樹中，沒有左孩子的結(jié)點(diǎn)一定是葉結(jié)點(diǎn)。(9) 在完全二叉樹中，沒有右孩子的結(jié)點(diǎn)一定是葉結(jié)點(diǎn)。(10) 在結(jié)點(diǎn)數(shù)目一定的前提下 , 各種形態(tài)的二叉樹中 , 完全二叉樹具有最小 深度。(11) 滿二叉樹一定是完全二叉樹。(12) 滿二叉樹中的每個(gè)結(jié)點(diǎn)的度不是 0就是 2。(13) 在所有深度相同的二叉樹中，滿二叉樹具有最大結(jié)點(diǎn)數(shù)目。(14) 具有n個(gè)結(jié)點(diǎn)的非空二叉樹一定有n-1個(gè)分支。(15) n個(gè)結(jié)點(diǎn)的二叉樹采用二叉

17、鏈表結(jié)構(gòu),鏈表中有n-1個(gè)存放NUL指針域(16) 由二叉樹的前序序列和中序序列可以惟一地確定一棵二叉樹。(17) 由二叉樹的中序序列和后序序列可以惟一地確定一棵二叉樹。(18) 由二叉樹的前序序列和后序序列可以惟一地確定一棵二叉樹。(19) 實(shí)現(xiàn)二叉樹的按層次遍歷算法時(shí)需要用到隊(duì)列結(jié)構(gòu)。(20) 實(shí)現(xiàn)二叉樹的遍歷算法時(shí)不需要用到堆棧結(jié)構(gòu)。(21) 線索二叉樹對(duì)應(yīng)的二叉鏈表中不存在空的指針域。(22) 給定一組權(quán)值，構(gòu)造出來的哈夫曼樹是惟一的。(23) 哈夫曼樹中不存在度為 1的結(jié)點(diǎn)。(24) 在哈夫曼樹中，權(quán)值相同的葉結(jié)點(diǎn)都在同一層上。(25) 沒有頂點(diǎn)的圖稱為空?qǐng)D。(26) 圖的度是圖中所

18、有頂點(diǎn)的度的最大值。(27) 邊上帶權(quán)值的圖稱為網(wǎng) (絡(luò))。(28) 圖中一個(gè)頂點(diǎn)的度應(yīng)該是它的出度與人度之和。(29) n 個(gè)頂點(diǎn)的無向圖最多有 n(n-1) 條邊。(30) 在有向圖中，所有頂點(diǎn)的人度之和等于所有頂點(diǎn)的出度之和。(31) 在無向圖中，若頂點(diǎn)i到頂點(diǎn)j有路徑，則這兩個(gè)頂點(diǎn)之間是連通的。(32) 在有向圖中，若頂點(diǎn)i到頂點(diǎn)j有路徑，則這兩個(gè)頂點(diǎn)之間是連通的。(33) 連通圖的最小生成樹是惟一的。(34) 鄰接矩陣主要用來表示頂點(diǎn)之間的關(guān)系。(35) 若表示某圖的鄰接矩陣不是對(duì)稱矩陣，則該圖一定是有向圖。(36) 若表示某圖的鄰接矩陣中出現(xiàn)了全零行或者全零列，則該圖一定是非 連通

19、圖或者非強(qiáng)連通圖。(37) 對(duì)于同一個(gè)有向圖，鄰接表中的邊結(jié)點(diǎn)數(shù)目與逆鄰接表中邊結(jié)點(diǎn)數(shù)目 相等。(38) 無向圖的鄰接表中邊結(jié)點(diǎn)數(shù)目一定為偶數(shù)。(39) 鄰接表中邊結(jié)點(diǎn)數(shù)目為奇數(shù)的圖一定是有向圖。(40) 鄰接表中邊結(jié)點(diǎn)數(shù)目為偶數(shù)的圖一定是無向圖。(41) 對(duì)圖進(jìn)行廣度優(yōu)先搜索的過程中要用到隊(duì)列。(42) 對(duì)圖進(jìn)行深度優(yōu)先搜索的過程中要用到堆找。(43) 帶權(quán)連通圖的最小生成樹是惟一的。(44) 最短路徑一定是簡(jiǎn)單路徑。(45) 求源點(diǎn)到各點(diǎn)的最短路徑的迪杰斯特拉算法不適用于存在回路的有向 網(wǎng)絡(luò)。(46) 若AON網(wǎng)中存在拓?fù)湫蛄?，則一般情況下，拓?fù)湫蛄胁皇俏┮坏摹?47) 關(guān)鍵路徑是由權(quán)值最

20、大的邊構(gòu)成的。(48) 給定的AO網(wǎng)的關(guān)鍵路徑一定是惟一的。四、簡(jiǎn)答題：1已知森林的先序遍歷序列為 ABDJCEFHK，中序序列為DJBAECHKF ,請(qǐng) 畫出該森林。2若一棵度為4的樹中度為1 2、3、4的結(jié)點(diǎn)個(gè)數(shù)分別為4、3、2、2,則 該樹葉子結(jié)點(diǎn)的個(gè)數(shù)是多少？總結(jié)點(diǎn)個(gè)數(shù)是多少？14 253. 棵度為2的樹與一棵二叉樹有什么區(qū)別？將樹轉(zhuǎn)化為二叉樹的基本目的是 什么？可以采用二叉樹的結(jié)構(gòu)并利用已有的算法解決樹的有關(guān)問題。4. 已知一棵完全二叉樹共有892個(gè)結(jié)點(diǎn)，試求：(1) 樹的高度10(2) 葉子結(jié)點(diǎn)數(shù)446(3) 單支結(jié)點(diǎn)數(shù)1(4) 最后一個(gè)非終端結(jié)點(diǎn)的序號(hào)4465. 畫出二叉樹的后序前驅(qū)線索。6. 文件中只出現(xiàn)9種字符：a b、c、d、e、f、g、h,它們出現(xiàn)的頻率分 別為8、9、3、5、6、4、2、1,請(qǐng)根據(jù)書上算法畫出相應(yīng)的哈夫曼樹(葉子 結(jié)點(diǎn)用相應(yīng)字母表示，左子樹的權(quán)小于右子樹的權(quán))，給出哈夫曼編碼，并計(jì) 算其帶權(quán)的路徑長(zhǎng)度WPL7. 已知某二叉樹的中序遍歷序列為 CBGEAFHD后序遍歷序列為CGEBHFDA青 畫出該二叉樹的前序線索二叉樹的二叉鏈表結(jié)構(gòu)的表示。8. 已知按前序遍歷二叉樹的結(jié)果為 ABC試問，有幾種不同的二叉樹可以得