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

1、.數(shù)據(jù)結(jié)構(gòu)練習(xí)（二）答案一、填空題：1若一棵樹的括號(hào)表示為A（B（E，F(xiàn)），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 之間關(guān)系的表達(dá)式（ 4）n= 2h-1,m=n+1-2h-1n=2m-1。3一棵二叉樹中如果有n 個(gè)葉子結(jié)點(diǎn)，則這棵樹上最少有（5）2n-1 個(gè)結(jié)點(diǎn)。一棵深度為 k 的完全二叉樹中最少有k-1k個(gè)2 （6） 個(gè)結(jié)點(diǎn)，最多有（7）2 -1結(jié)點(diǎn)。4具有 n 個(gè)結(jié)點(diǎn)的二叉樹，當(dāng)它是一棵(8)完全二叉樹時(shí)具有最小高度（9）l

2、og2n+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 ，其后序遍歷序

3、列為 _DCBFGEA _。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)，則該二叉樹有 _n0-1_個(gè)度為 2的結(jié)點(diǎn)， _n-2n0+1_個(gè)度為 1的結(jié)點(diǎn)。11任何非空樹中有且僅有一個(gè)結(jié)點(diǎn)沒有前驅(qū)結(jié)點(diǎn)，該結(jié)點(diǎn)就是樹的 _根_。度為 k的樹中第 i層最多有 _ki-1_個(gè)結(jié)點(diǎn) (i>=1) ，深度為 h的k叉樹最多有 _k0+k1+.+k h-1_個(gè)結(jié)點(diǎn)。12非空二叉樹一共有 _4_種基本形態(tài)，第 i層最多有 _ 2i-1_個(gè)結(jié)點(diǎn)。13在一棵完

4、全二叉樹中，編號(hào)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)整理文檔.O(n2)；若用鄰接表表示圖，訪問一個(gè)頂點(diǎn)的所有鄰接頂點(diǎn)的時(shí)間復(fù)雜性為(15) O(n) 。一個(gè)有 n 個(gè)頂點(diǎn)的有向圖中，最少有(16)0弧，最多有(17) n(n-1) 弧。二、選擇題1.樹型結(jié)構(gòu)最適合用來描述 _A 有序的數(shù)據(jù)元素B無序的數(shù)

5、據(jù)元素C數(shù)據(jù)元素之間具有層次關(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×(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 9B11C 15D 不確定6.一個(gè)具有 1025 個(gè)結(jié)點(diǎn)的二叉樹的高h(yuǎn)

6、為。A11B10C111025D 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 有_個(gè)葉子結(jié)點(diǎn)。A4B5C6D710設(shè) n，m 為一棵二叉樹上的兩個(gè)結(jié)點(diǎn)，在中序遍歷時(shí)， n 在 m 前的條件是 _。A n 在 m 右方Bn 是 m 祖先Cn 在 m 左方D n 是

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

8、A 2nBn-1C n+1Dn16根據(jù)使用頻率為 5 個(gè)字符設(shè)計(jì)的哈夫曼編碼不可能是 _。A 000，001，010，011，1B0000，0001，001，01， 1C 000，001，01， 10，11D 00，100，101， 110， 11118設(shè)有 13 個(gè)值，用它們組成一棵哈夫曼樹， 則該哈夫曼樹共有 _個(gè)結(jié)點(diǎn)。A13B12C 26D2519在一個(gè)圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)的 _倍。A.1/2B.1C.2D.420一個(gè)具有 n個(gè)頂點(diǎn)的無向圖最多有 _條邊。A .n(n-1)/2B.n(n-1)C.n(n+1)/2D.n221一個(gè)具有 n個(gè)頂點(diǎn)的有向圖最多有 _條邊。A.n

9、(n-1)/2B.n(n-1)C.n(n+1)/2D.n222在一個(gè)具有 n個(gè)頂點(diǎn)的無向圖中，要連通全部頂點(diǎn)至少需要_條邊A.nB.n+1C.n-1D.2n23具有 n個(gè)頂點(diǎn)的連通圖的生成樹一定有 _條邊。A.nB.n+1C.n-1D.2n24若一個(gè)非連通的無向圖最多有28條邊，則該無向圖至少有_個(gè)項(xiàng)點(diǎn)。A.6B.7C.8D.925在帶權(quán)圖中，兩個(gè)頂點(diǎn)之間的路徑長(zhǎng)度是_。A 路徑上的頂點(diǎn)數(shù)目B路徑上的邊的數(shù)目C路徑上頂點(diǎn)和邊的數(shù)目D路徑上所有邊上的權(quán)值之和26若具有 n個(gè)頂點(diǎn)的元向圖采用鄰接矩陣存儲(chǔ)方法,該鄰接矩陣一定為一個(gè)_。整理文檔.A 一般矩陣B對(duì)稱矩陣C對(duì)角矩陣D 稀疏矩陣27若圖的鄰

10、接矩陣中主對(duì)角線上的元素均為0，其余元素全為 1，則可以斷定該圖一定 _。A 是無向圖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ù)，則該圖_。A 一定有奇數(shù)個(gè)頂點(diǎn)B一定有偶數(shù)個(gè)頂點(diǎn)C一定是有向圖D 可能是無向圖30若某圖的鄰接表中的邊結(jié)點(diǎn)數(shù)目為偶數(shù)，則該圖_。A 一定是無向圖B可能是有向圖C可能是無向圖，也可能是有向圖D一定有偶數(shù)個(gè)頂點(diǎn)31若無向圖有 k條邊，則相應(yīng)的鄰接表中就有 _個(gè)邊結(jié)點(diǎn)。A.k-1B.kC.2kD.k232若有向圖有 k條邊，則相應(yīng)的鄰接表中就

11、有_個(gè)邊結(jié)點(diǎn)。A.k-1B.kC.2kD.k233對(duì)于一個(gè)不帶權(quán)的無向圖的鄰接矩陣而言，_A 矩陣中非零元素的數(shù)目等于圖中邊的數(shù)目B矩陣中非全零的行的數(shù)目等于圖中頂點(diǎn)的數(shù)目C第i 行的非零元素的數(shù)目與第 i列的非零元素的數(shù)目相等 D 第 i行與第 i 列的非零元素的總數(shù)等于第 i個(gè)頂點(diǎn)的度數(shù)34導(dǎo)致圖的遍歷序列不惟一的因素有 _。A 出發(fā)點(diǎn)不同、遍歷方法不同B出發(fā)點(diǎn)不同、存儲(chǔ)結(jié)構(gòu)不同C遍歷方法不同、存儲(chǔ)結(jié)構(gòu)不同D 出發(fā)點(diǎn)不同、存儲(chǔ)結(jié)構(gòu)不同、遍歷方法不同35若從無向圖的任意一個(gè)頂點(diǎn)出發(fā)進(jìn)行一次深度優(yōu)先搜索便可以訪問該圖的所有頂點(diǎn)，則該圖一定是一個(gè)_圖。A 非連通B連通C.強(qiáng)連通D.完全36可以進(jìn)

12、行拓?fù)渑判虻膱D一定是_。A 連通圖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>,<v3,v4>,<v4,v5>,<v5,v2><v5,v6>,G 的拓?fù)湫蛄惺莀。A. v3,v1,v4,v5,v2,v6B v3,v4,v1,v5,v2,v6C. v1,v3,v4,v5,v2,v6D. v1,v4,v3,v5,v2,v6整理文檔.38下面關(guān)于 AOE

13、網(wǎng)的敘述中，不正確的是_。A 若所有關(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采用鄰接表存儲(chǔ)的圖的深度優(yōu)先遍歷算法類似于二叉樹的_算法。A 先序遍歷B中序遍歷C后序遍歷D 按層遍歷42一個(gè)無向連通圖的生成樹是含有該連通圖的全

14、部頂點(diǎn)的A 極小聯(lián)通子圖B.極小子圖C極大連通子圖D 極大子圖43任何一個(gè)無向連通圖最小生成樹。A 只有一棵B有一棵或多棵C一定有多棵D 可能不存在44求最短路徑的 Dijkstra 算法的時(shí)間復(fù)雜度為。A O（n）B. O（n+e）CO（n2）DO（n3）45求最短路徑的 Floyd 算法的時(shí)間復(fù)雜度為。A O（n）B. O（ne）C O（n2）D O（ n3）45-2 有向網(wǎng) G 用鄰接矩陣 A 存儲(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)中 _。

15、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） adbefcB）adcefbC）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)。(4)在度為 k的樹中，每個(gè)結(jié)點(diǎn)最多有k-1個(gè)兄弟結(jié)點(diǎn)。(5)度為 2的樹是二叉樹。(6)二叉樹的度一定為 2。(7)在非空完全二叉樹中，只有最下面一層的結(jié)點(diǎn)為葉結(jié)點(diǎn)

16、。(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)的二叉樹采用二叉鏈表結(jié)構(gòu),鏈表中有 n-1個(gè)存放 NULL 指針域。(16)由二叉樹的前序序列和中序序列可以惟一地確定一棵二叉樹。(17)由二叉樹的中序序列和后序序列可以惟一地確定一棵二叉樹。(18)由二

17、叉樹的前序序列和后序序列可以惟一地確定一棵二叉樹。(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)圖的度是圖中所有頂點(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)的人度之和等于

18、所有頂點(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)了全零行或者全零列， 則該圖一定是非連通圖或者非強(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)鄰接表中

19、邊結(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)若 AOV 網(wǎng)中存在拓?fù)湫蛄校瑒t一般情況下，拓?fù)湫蛄胁皇俏┮坏摹?47)關(guān)鍵路徑是由權(quán)值最大的邊構(gòu)成的。(48)給定的 AOE 網(wǎng)的關(guān)鍵路徑一定是惟一的。四、簡(jiǎn)答題：1已知森林的先序遍歷序列為 ABDJCEFHK ，中序序列為 DJBAECHKF ，請(qǐng)畫出該森林。2若一棵度為 4 的樹中度為 1、2、3、4 的結(jié)點(diǎn)

20、個(gè)數(shù)分別為4、3、2、2，則該樹葉子結(jié)點(diǎn)的個(gè)數(shù)是多少？總結(jié)點(diǎn)個(gè)數(shù)是多少？14253一棵度為 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)446整理文檔.5畫出二叉樹的后序前驅(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)度 WPL。7已知某二叉樹的中序遍歷序列為CBGEAFHD ，后序遍歷序列為CGEBHFDA ，請(qǐng)畫出該二叉樹的前序線索二叉樹的二叉鏈表結(jié)構(gòu)的表示。8.已知按前序遍歷二叉樹的結(jié)果為 ABC。試問，有幾種不同的二叉樹可以得到這一遍歷結(jié)果 ?59.將圖所示的樹林轉(zhuǎn)換為一棵二叉樹。10.分別寫出如圖所示的樹的前序遍歷序列與后序遍歷