數據結構練習2

1、.數據結構練習（二）答案一、填空題：1若一棵樹的括號表示為A（B（E，F），C（ G（H,I,J,K）,L）,D（ M（N ），則該樹的度為（1）4 ，樹的深度為（2）4 ，樹中葉子結點的個數為（ 3）8。2一棵滿二叉樹中有m 個葉子， n 個結點，深度為 h，請寫出 m、n、h 之間關系的表達式（ 4）n= 2h-1,m=n+1-2h-1n=2m-1。3一棵二叉樹中如果有n 個葉子結點，則這棵樹上最少有（5）2n-1 個結點。一棵深度為 k 的完全二叉樹中最少有k-1k個2 （6） 個結點，最多有（7）2 -1結點。4具有 n 個結點的二叉樹，當它是一棵(8)完全二叉樹時具有最小高度（9）l

2、og2n+1，當它為一棵單支樹時具有高度(10) n。5對具有 n個結點的完全二叉樹按照層次從上到下，每一層從左到右的次序對所有結點進行編號， 編號為 i的結點的雙親結點的編號為 _(11)_i/2 _，左孩子的編號為 _2i_，右孩子的編號為 _2i+1_。6若具有 n個結點的二叉樹采用二叉鏈表存儲結構，則該鏈表中有 _2n_個指針域，其中有 _n-1_個指針域用于鏈接孩子結點， _n+1_個指針域空閑存放著 NULL 。7二叉樹的遍歷方式通常有_先序 _、 _中序 _、 _后序 _和_層序 _四種。8已知二叉樹的前序遍歷序列為ABDCEFG ，中序遍歷序列為 DBCAFEG ，其后序遍歷序

3、列為 _DCBFGEA _。9已知某完全二叉樹采用順序存儲結構，結點的存放次序為A,B,C,D,E,F,G,H,I,J，該完全二叉樹的后序序列為_HIDJEBFGCA _。10若具有 n個結點的非空二叉樹有 n0個葉結點，則該二叉樹有 _n0-1_個度為 2的結點， _n-2n0+1_個度為 1的結點。11任何非空樹中有且僅有一個結點沒有前驅結點，該結點就是樹的 _根_。度為 k的樹中第 i層最多有 _ki-1_個結點 (i>=1) ，深度為 h的k叉樹最多有 _k0+k1+.+k h-1_個結點。12非空二叉樹一共有 _4_種基本形態(tài)，第 i層最多有 _ 2i-1_個結點。13在一棵完

4、全二叉樹中，編號i 和編號 j 的兩個結點處于同一層的條件是_log2i=log2j_14有 n 個頂點的強連通圖至少有（7）n弧，有 n 個頂點的連通圖至少有（8）n-1邊。15設無向圖 G 的頂點數為 n，圖 G 最少有(12) 0邊，最多有(13) n(n-1)/2條邊；若邊數為 e，用鄰接矩陣表示圖， 求每一頂點度的時間復雜性為(14)整理文檔.O(n2)；若用鄰接表表示圖，訪問一個頂點的所有鄰接頂點的時間復雜性為(15) O(n) 。一個有 n 個頂點的有向圖中，最少有(16)0弧，最多有(17) n(n-1) 弧。二、選擇題1.樹型結構最適合用來描述 _A 有序的數據元素B無序的數

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

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

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

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

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

10、接矩陣中主對角線上的元素均為0，其余元素全為 1，則可以斷定該圖一定 _。A 是無向圖B 是有向圖C 是完全圖 D 不是帶權圖28有向圖的鄰接表的第 i個鏈表中的邊結點數目是第 i個頂點的 _。A 度數B出度C人數D 邊數29若某圖的鄰接表中的邊結點數目為奇數，則該圖_。A 一定有奇數個頂點B一定有偶數個頂點C一定是有向圖D 可能是無向圖30若某圖的鄰接表中的邊結點數目為偶數，則該圖_。A 一定是無向圖B可能是有向圖C可能是無向圖，也可能是有向圖D一定有偶數個頂點31若無向圖有 k條邊，則相應的鄰接表中就有 _個邊結點。A.k-1B.kC.2kD.k232若有向圖有 k條邊，則相應的鄰接表中就

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

12、行拓撲排序的圖一定是_。A 連通圖B帶權連通圖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 的拓撲序列是_。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下面關于 AOE

13、網的敘述中，不正確的是_。A 若所有關鍵活動都提前完成，則整個工程一定能夠提前完成B即使所有非關鍵活動都未按時完成，整個工程仍有可能按時完成C任何一個關鍵活動的延期完成，都會導致整個工程的延期完成D 任何一個關鍵活動的提前完成，都會導致整個工程的提前完成39無向圖的鄰接矩陣是一個_.A 對稱矩陣B零矩陣C上三角矩陣D 對角矩陣40如果從無向圖的任一頂點出發(fā)進行一次深度優(yōu)先搜索即可訪問所有頂點，則該圖一定是 _。A 完全圖B連通圖C有回路D 一棵樹41采用鄰接表存儲的圖的深度優(yōu)先遍歷算法類似于二叉樹的_算法。A 先序遍歷B中序遍歷C后序遍歷D 按層遍歷42一個無向連通圖的生成樹是含有該連通圖的全

14、部頂點的A 極小聯通子圖B.極小子圖C極大連通子圖D 極大子圖43任何一個無向連通圖最小生成樹。A 只有一棵B有一棵或多棵C一定有多棵D 可能不存在44求最短路徑的 Dijkstra 算法的時間復雜度為。A O（n）B. O（n+e）CO（n2）DO（n3）45求最短路徑的 Floyd 算法的時間復雜度為。A O（n）B. O（ne）C O（n2）D O（ n3）45-2 有向網 G 用鄰接矩陣 A 存儲，則頂點 i 的入度等于 A 中。A)第 i 行非的元素之和C)第 i 列非的元素之和B)第 i 行非且非 0 的元素個數D) 第 i 列非且非 0 的元素個數46關鍵路徑是事件結點網中 _。

15、A 從起點到終點的最長路徑B從起點到終點的最短路徑C最長的回路D 最短的回路47已知一個有向圖如右圖所示，則從頂點a 出發(fā)進行深度優(yōu)先遍歷不可能得到的DFS 序列為 _。A） adbefcB）adcefbC）adcbfeD ） adefcb整理文檔.三、判斷題(1)在樹型結構中 ,每一個結點最多只有一個前驅結點,但可以有多個后繼結點 .(2)在樹型結構中，每一個結點不能沒有前驅結點。(3)在度為 k的樹中，至少有一個度為k的結點。(4)在度為 k的樹中，每個結點最多有k-1個兄弟結點。(5)度為 2的樹是二叉樹。(6)二叉樹的度一定為 2。(7)在非空完全二叉樹中，只有最下面一層的結點為葉結點

16、。(8)在完全二叉樹中，沒有左孩子的結點一定是葉結點。(9)在完全二叉樹中，沒有右孩子的結點一定是葉結點。(10)在結點數目一定的前提下,各種形態(tài)的二叉樹中 ,完全二叉樹具有最小深度。(11)滿二叉樹一定是完全二叉樹。(12)滿二叉樹中的每個結點的度不是0就是 2。(13)在所有深度相同的二叉樹中，滿二叉樹具有最大結點數目。(14)具有 n個結點的非空二叉樹一定有n-1個分支。(15)n個結點的二叉樹采用二叉鏈表結構,鏈表中有 n-1個存放 NULL 指針域。(16)由二叉樹的前序序列和中序序列可以惟一地確定一棵二叉樹。(17)由二叉樹的中序序列和后序序列可以惟一地確定一棵二叉樹。(18)由二

17、叉樹的前序序列和后序序列可以惟一地確定一棵二叉樹。(19)實現二叉樹的按層次遍歷算法時需要用到隊列結構。(20)實現二叉樹的遍歷算法時不需要用到堆棧結構。(21)線索二叉樹對應的二叉鏈表中不存在空的指針域。(22)給定一組權值，構造出來的哈夫曼樹是惟一的。(23)哈夫曼樹中不存在度為 1的結點。(24)在哈夫曼樹中，權值相同的葉結點都在同一層上。(25)沒有頂點的圖稱為空圖。(26)圖的度是圖中所有頂點的度的最大值。(27)邊上帶權值的圖稱為網 (絡)。(28)圖中一個頂點的度應該是它的出度與人度之和。(29)n個頂點的無向圖最多有 n(n-1)條邊。(30)在有向圖中，所有頂點的人度之和等于

18、所有頂點的出度之和。(31)在無向圖中，若頂點 i到頂點 j有路徑，則這兩個頂點之間是連通的。(32)在有向圖中，若頂點 i到頂點 j有路徑，則這兩個頂點之間是連通的。整理文檔.(33)連通圖的最小生成樹是惟一的。(34)鄰接矩陣主要用來表示頂點之間的關系。(35)若表示某圖的鄰接矩陣不是對稱矩陣，則該圖一定是有向圖。(36)若表示某圖的鄰接矩陣中出現了全零行或者全零列， 則該圖一定是非連通圖或者非強連通圖。(37)對于同一個有向圖， 鄰接表中的邊結點數目與逆鄰接表中邊結點數目相等。(38)無向圖的鄰接表中邊結點數目一定為偶數。(39)鄰接表中邊結點數目為奇數的圖一定是有向圖。(40)鄰接表中

19、邊結點數目為偶數的圖一定是無向圖。(41)對圖進行廣度優(yōu)先搜索的過程中要用到隊列。(42)對圖進行深度優(yōu)先搜索的過程中要用到堆找。(43)帶權連通圖的最小生成樹是惟一的。(44)最短路徑一定是簡單路徑。(45)求源點到各點的最短路徑的迪杰斯特拉算法不適用于存在回路的有向網絡。(46)若 AOV 網中存在拓撲序列，則一般情況下，拓撲序列不是惟一的。(47)關鍵路徑是由權值最大的邊構成的。(48)給定的 AOE 網的關鍵路徑一定是惟一的。四、簡答題：1已知森林的先序遍歷序列為 ABDJCEFHK ，中序序列為 DJBAECHKF ，請畫出該森林。2若一棵度為 4 的樹中度為 1、2、3、4 的結點

20、個數分別為4、3、2、2，則該樹葉子結點的個數是多少？總結點個數是多少？14253一棵度為 2的樹與一棵二叉樹有什么區(qū)別?將樹轉化為二叉樹的基本目的是什么？可以采用二叉樹的結構并利用已有的算法解決樹的有關問題。4已知一棵完全二叉樹共有892 個結點，試求：（1）樹的高度10（2）葉子結點數446（3）單支結點數1（4）最后一個非終端結點的序號446整理文檔.5畫出二叉樹的后序前驅線索。6一文件中只出現9 種字符： a、b、c、d、e、f 、g、h，它們出現的頻率分別為 8、9、3、5、6、4、2、1，請根據書上算法畫出相應的哈夫曼樹 (葉子結點用相應字母表示 ,左子樹的權小于右子樹的權 )，給出哈夫曼編碼，并計算其帶權的路徑長度 WPL。7已知某二叉樹的中序遍歷序列為CBGEAFHD ，后序遍歷序列為CGEBHFDA ，請畫出該二叉樹的前序線索二叉樹的二叉鏈表結構的表示。8.已知按前序遍歷二叉樹的結果為 ABC。試問，有幾種不同的二叉樹可以得到這一遍歷結果 ?59.將圖所示的樹林轉換為一棵二叉樹。10.分別寫出如圖所示的樹的前序遍歷序列與后序遍歷