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