【正文】 夫曼樹如圖513所示。 zzzz 樹的帶權路徑長度為： WPL=24+34+53+73+83+92+112 =120 9．已知某字符串S中共有8種字符，各種字符分別出現(xiàn)2次、1次、4次、5次、7次、3次、4次和9次，對該字符串用[0，1]進行前綴編碼，問該字符串的編碼至少有多少位。 【解答】以各字符出現(xiàn)的次數作為葉子結點的權值構造的哈夫曼編碼樹如圖514所示。其帶權路徑長度=25+15+34+53+92+43+43+72=98，所以，該字符z 10．算法設計 ⑴ 設計算法求二叉樹的結點個數。 【解答】本算法不是要打印每個結點的值，而是求出結點的個數。所以可將遍歷算法中的“訪問”操作改為“計數操作”，將結點的數目累加到一個全局變量中，每個結點累加一次即完成了結點個數的求解。 具體算法如下： ⑵ 設計算法按前序次序打印二叉樹中的葉子結點。 【解答】本算法的要求與前序遍歷算法既有相同之處，又有不同之處。相同之處是打印次序均為前序，不同之處是此處不是打印每個結點的值，而是打印出其中的葉子結點，即為有條件打印。為此，將前序遍歷算法中的訪問操作改為條件打印即可。算法如下： ⑶ 設計算法求二叉樹的深度。 【解答】當二叉樹為空時，深度為0；若二叉樹不為空，深度應是其左右子樹深度的最大值加1，而其左右子樹深度的求解又可通過遞歸調用本算法來完成。具體算法如下：  ⑷ 編寫算法，要求輸出二叉樹后序遍歷序列的逆序。 【解答】要想得到后序的逆序，只要按照后序遍歷相反的順序即可，即先訪問根結點，再遍歷根結點的右子樹，最后遍歷根結點的左子樹。注意和前序遍歷的區(qū)別，具體算法如下： ⑸ 以二叉鏈表為存儲結構，編寫算法求二叉樹中結點x的雙親。 【解答】對二叉鏈表進行遍歷，在遍歷的過程中查找結點x并記載其雙親。具體算法如下： ⑹ 以二叉鏈表為存儲結構，在二叉樹中刪除以值x為根結點的子樹。 【解答】對二叉鏈表進行遍歷，在遍歷的過程中查找結點x并記載其雙親，然后將結點x的雙親結點中指向結點x的指針置空。具體算法如下：  ⑺ 一棵具有n個結點的二叉樹采用順序存儲結構，編寫算法對該二叉樹進行前序遍歷。 【解答】按照題目要求，設置一個工作棧以完成對該樹的非遞歸算法，思路如下： ① 每訪問一個結點，將此結點壓棧，查看此結點是否有左子樹，若有，訪問左子樹，重復執(zhí)行該過程直到左子樹為空。 ② 從棧彈出一個結點，如果此結點有右子樹，訪問右子樹執(zhí)行步驟①，否則重復執(zhí)行步驟②。 具體算法如下： ⑻ 編寫算法交換二叉樹中所有結點的左右子樹。 【解答】對二叉樹進行后序遍歷，在遍歷過程中訪問某結點時交換該結點的左右子樹。 具體算法如下：  ⑼ 以孩子兄弟表示法做存儲結構，求樹中結點x的第i個孩子。 【解答】先在鏈表中進行遍歷，在遍歷過程中查找值等于x的結點，然后由此結點的最左孩子域firstchild找到值為x結點的第一個孩子，再沿右兄弟域rightsib找到值為x結點的第i個孩子并返回指向這個孩子的指針。 樹的孩子兄弟表示法中的結點結構定義如下： template struct TNode { T data。 TNode *firstchild, *rightsib。 }。 具體算法如下： 學習自測及答案 1．前序遍歷和中序遍歷結果相同的二叉樹是（ ）。 A 根結點無左孩子的二叉樹 B 根結點無右孩子的二叉樹 C 所有結點只有左子樹的二叉樹 D 所有結點只有右子樹的二叉樹 【解答】D 2．由權值為{3, 8, 6, 2, 5}的葉子結點生成一棵哈夫曼樹，其帶權路徑長度為（ ）。 A 24 B 48 C 53 D 72 【解答】C 3．用順序存儲的方法將完全二叉樹中的所有結點逐層存放在數組A[1] ~ A[n]中，結點A[i]若有左子樹，則左子樹的根結點是（ ）。 A A[2i1] B A[2i+1] C A[i/2] D A[2i] 【解答】D 4．對任何一棵二叉樹T，如果其終端結點的個數為n0，度為2的結點個數為n2，則（ ）。 A n0=n21 B n0=n2 C n0=n2+1 D 沒有規(guī)律 【解答】C 5．一棵滿二叉樹中共有n個結點，其中有m個葉子結點，深度為h，則（ ）。 A n=h+m B h+m=2n C m=h1 D n=2h1 【解答】D 6．對于完全二叉樹中的任一結點，若其右分支下的子孫的最大層次為h，則其左分支下的子孫的最大層次為（ ）。 A h B h+1 C h或h+1 D 任意 【解答】C 7．假定一棵度為3的樹中結點數為50，則其最小高度應為 。 A 3 B 4 C 5 D 6 【解答】C 8．在線索二叉樹中，一個結點是葉子結點的充要條件為（ ）。 A 左線索標志為0，右線索標志為1 B 左線索標志為1，右線索標志為0 C 左、右線索標志均為0 D 左、右線索標志均為1 【解答】C 9．對于一棵具有n個結點的樹，其所有結點的度之和為（ ）。 【解答】n1  10．在順序存儲的二叉樹中，編號為i和j的兩個結點處在同一層的條件是（ ）。 【解答】 11．現(xiàn)有按前序遍歷二叉樹的結果ABC，問有哪幾種不同的二叉樹可以得到這一結果？ 【解答】共有5種二叉樹可以得到這一結果，如圖515所示。 12．試找出分別滿足下列條件的所有二叉樹： ⑴ 前序序列和中序序列相同。 ⑵ 中序序列和后序序列相同。 ⑶ 前序序列和后序序列相同。 【解答】 ⑴ 空二叉樹、只有一個根結點的二叉樹和右斜樹。 ⑵ 空二叉樹、只有一個根結點的二叉樹和左斜樹。 ⑶ 空二叉樹、只有一個根結點的二叉樹 13．將下面圖516所示的樹轉換為二叉樹，圖517所示的二叉樹轉換為樹或森林。 【解答】圖516所示樹轉換的二叉樹如圖518所示，圖517所示二叉樹轉換的森林如圖519所示。  14．以孩子兄弟表示法作為存儲結構，編寫算法求樹的深度。 【解答】采用遞歸算法實現(xiàn)。若樹為空樹，則其深度為0，否則其深度等于第一棵子樹的深度+1和兄弟子樹的深度中的較大者。具體算法如下： 15．設計算法，判斷一棵二叉樹是否為完全二叉樹。 【解答】根據完全二叉樹的定義可知，對完全二叉樹按照從上到下、從左到右的次序（即層序）遍歷應該滿足： ⑴ 若某結點沒有左孩子，則其一定沒有右孩子； ⑵ 若某結點無右孩子，則其所有后繼結點一定無孩子。 若有一結點不滿足其中任意一條，則該二叉樹就一定不是完全二叉樹。因此可采用按層次遍歷二叉樹的方法依次對每個結點進行判斷是否滿足上述兩個條件。為此，需設兩個標志變量BJ和CM，其中BJ表示已掃描過的結點是否均有左右孩子，CM存放局部判斷結果及最后的結果。 具體算法如下： 第 6 章 圖 課后習題講解 1. 填空題 ⑴ 設無向圖G中頂點數為n，則圖G至少有（ ）條邊，至多有（ ）條邊；若G為有向圖，則至少有（ ）條邊，至多有（ ）條邊。 【解答】0，n(n1)/2，0，n(n1) 【分析】圖的頂點集合是有窮非空的，而邊集可以是空集；邊數達到最多的圖稱為完全圖，在完全圖中，任意兩個頂點之間都存在邊。 ⑵ 任何連通圖的連通分量只有一個，即是（ ）。 【解答】其自身 ⑶ 圖的存儲結構主要有兩種，分別是（ ）和（ ）。 【解答】鄰接矩陣，鄰接表 【分析】這是最常用的兩種存儲結構，此外，還有十字鏈表、鄰接多重表、邊集數組等。 ⑷ 已知無向圖G的頂點數為n，邊數為e，其鄰接表表示的空間復雜度為（ ）。 【解答】Ｏ(n+e) 【分析】在無向圖的鄰接表中，頂點表有n個結點，邊表有2e個結點，共有n+2e個結點，其空間復雜度為Ｏ(n+2e)=Ｏ(n+e)。 ⑸ 已知一個有向圖的鄰接矩陣表示，計算第j個頂點的入度的方法是（ ）。 【解答】求第j列的所有元素之和 ⑹ 有向圖G用鄰接矩陣A[n][n]存儲，其第i行的所有元素之和等于頂點i的（ ）。 【解答】出度 ⑺ 圖的深度優(yōu)先遍歷類似于樹的（ ）遍歷，它所用到的數據結構是（ ）；圖的廣度優(yōu)先遍歷類似于樹的（ ）遍歷，它所用到的數據結構是（ ）。 【解答】前序，棧，層序，隊列 ⑻ 對于含有n個頂點e條邊的連通圖，利用Prim算法求最小生成樹的時間復雜度為（ ），利用Kruskal算法求最小生成樹的時間復雜度為（ ）。 【解答】Ｏ(n2)，Ｏ(elog2e) 【分析】Prim算法采用鄰接矩陣做存儲結構，適合于求稠密圖的最小生成樹；Kruskal算法采用邊集數組做存儲結構，適合于求稀疏圖的最小生成樹。 ⑼ 如果一個有向圖不存在（ ），則該圖的全部頂點可以排列成一個拓撲序列。 【解答】回路 （10） 在一個有向圖中，若存在弧、則在其拓撲序列中，頂點vi, vj, vk的相對次序為（ ）。 【解答】vi, vj, vk 【分析】對由頂點vi, vj, vk組成的圖進行拓撲排序。 2. 選擇題 ⑴ 在一個無向圖中，所有頂點的度數之和等于所有邊數的（ ）倍。 A 1/2 B 1 C 2 D 4 【解答】C 【分析】設無向圖中含有n個頂點e條邊，則 。 ⑵ n個頂點的強連通圖至少有（ ）條邊，其形狀是（ ）。 A n B n+1 C n1 D n(n1) E 無回路 F 有回路 G 環(huán)狀 H 樹狀 【解答】A，G ⑶ 含n 個頂點的連通圖中的任意一條簡單路徑，其長度不可能超過（ ）。 A 1 B n/2 C n1 D n 【解答】C 【分析】若超過n1，則路徑中必存在重復的頂點。 ⑷ 對于一個具有n個頂點的無向圖，若采用鄰接矩陣存儲，則該矩陣的大小是（ ）。 A n B (n1)2 C n1 D n2 【解答】D ⑸ 圖的生成樹（ ），n個頂點的生成樹有（ ）條邊。 A 唯一 B 不唯一 C 唯一性不能確定 D n E n +1 F n1 【解答】C，F(xiàn) ⑹ 設無向圖G=(V, E)和G39。 =(V39。, E39。 )，如果G39。 是G的生成樹，則下面的說法中錯誤的是（ ）。 A G39。 為 G的子圖 B G39。 為 G的連通分量 C G39。 為G的極小連通子圖且V = V39。 D G39。 是G的一個無環(huán)子圖 【解答】B 【分析】連通分量是無向圖的極大連通子圖，其中極大的含義是將依附于連通分量中頂點的所有邊都加上，所以，連通分量中可能存在回路。 ⑺ G是一個非連通無向圖，共有28條邊，則該圖至少有（ ）個頂點。 A 6 B 7 C 8 D 9 【解答】D 【分析】n個頂點的無向圖中，邊數e≤n(n1)/2，將e=28代入，有n≥8，現(xiàn)已知無向圖非連通，則n=9。 ⑻ 最小生成樹指的是（ ） 。 A 由連通網所得到的邊數最少的生成樹 B 由連通網所得到的頂點數相對較少的生成樹 C 連通網中所有生成樹中權值之和為最小的生成樹 D 連通網的極小連通子圖 【解答】C ⑼ 判定一個有向圖是否存在回路除了可以利用拓撲排序方法外，還可以用（ ）。 A 求關鍵路徑的方法 B 求最短路徑的方法 C 廣度優(yōu)先遍歷算法 D 深度優(yōu)先遍歷算法 【解答】D 【分析】當有向圖中無回路時，從某頂點出發(fā)進行深度優(yōu)先遍歷時，出棧的順序（退出DFSTraverse算法）即為逆向的拓撲序列。 ⑽ 下面關于工程計劃的AOE網的敘述中，不正確的是（ ） A 關鍵活動不按期完成就會影響整個工程的完成時間 B 任何一個關鍵活動提前完成，那么整個工程將會提前完成 C 所有的關鍵活動都提前完成，那么整個工程將會提前完成 D 某些關鍵活動若提前完成，那么整個工程將會提前完 【解答】B 【分析】AOE網中的關鍵路徑可能不止一條，如果某一個關鍵活動提前完成，還不能提前整個工程，而必須同時提高在幾條關鍵路徑上的關鍵活動。 3. 判斷題 ⑴ 一個有向圖的鄰接表和逆鄰接表中的結點個數一定相等。 【解答】對。鄰接表和逆鄰接表的區(qū)別僅在于出邊和入邊，邊表中的結點個數都等于有向圖中邊的個數。 ⑵ 用鄰接矩陣存儲圖，所占用的存儲空間大小只與圖中頂點個數有關，而與圖的邊數無關。 【解答】對。鄰接矩陣的空間復雜度為Ｏ(n2)，與邊的個數無關。 ⑶ 圖G的生成樹是該圖的一個極小連通子圖 【解答】錯。必須包含全部頂點。 ⑷ 無向圖的鄰接矩陣一定是對稱的，有向圖的鄰接矩陣一定是不對稱的 【解答】錯。有向圖的鄰接矩陣不一定對稱，例如有向完全圖的鄰接矩陣就是對稱的。 ⑸ 對任意一個圖，從某頂點出發(fā)進行一次深度優(yōu)先或廣度優(yōu)先遍歷，可訪問圖的所有頂點。 【解答】錯。只有連通圖從某頂點出發(fā)進行一次遍歷，可訪問圖的所有頂點。 ⑹ 在一個有向圖的拓撲序列中，若頂點a在頂點b之前，則圖中必有一條弧。 【解答】錯。只能說明從頂點a到頂點b有一條路徑。 ⑺ 若一個有向圖的鄰接矩陣中對角線以下元素均為零，則該圖的拓撲序列必定存在。 【解答】對。參見第11題的證明