習題八 根及其應(yīng)用 - 煙臺大學計算機與控制工程學院

1、習題八: 根樹及其應(yīng)用1從簡單有向圖的鄰接矩陣怎樣去決定它是否為根樹。如果是根樹，怎樣定出它的樹根和樹葉。2求出對應(yīng)于圖7-8.9所給出的樹的二叉樹。1413983124567101112圖7-8.93證明在完全二叉樹中，邊的總數(shù)等于，式中是樹葉數(shù)。4在一棵叉樹中，其外部通路長度與內(nèi)部通路長度之間有什么關(guān)系。5給定權(quán)1，4，9，16，25，36，49，64，81，100a）構(gòu)造一棵最優(yōu)二叉樹。b）構(gòu)造一棵最優(yōu)三叉樹。c）說明如何構(gòu)造一棵最優(yōu)叉樹。6構(gòu)造一個與英文字母對應(yīng)的前綴碼，并畫出該前綴碼對應(yīng)的二叉樹，再用此六個字母構(gòu)成一個英文短語，寫出此短語的編碼信息。7設(shè)是二進制序列的集合。我們將劃分

2、為兩個子集和，這里是中第一個數(shù)字是0的序列的集合，是中第一個數(shù)字是1的序列的集合，然后我們根據(jù)序列中的第二個數(shù)字將劃分成兩個子集，對也用同樣方法加以劃分。運用不斷的將序列的集合劃分成子集的方法來證明：如果是前綴碼，則存在一棵二叉樹，其中從每個分枝點射出的兩條邊分別標號0和1，使得賦于樹葉的0和1的序列是中的序列。8給出公式（的根樹表示。9（1）求帶權(quán)為1，1，2，3，3，4，5，6，7的最優(yōu)三元樹。 （2）求帶權(quán)為1，1，2，3，3，4，5，6，7，8的最優(yōu)三元樹。10在通信中要傳輸八進制數(shù)字0，1，2，7。這些數(shù)字出現(xiàn)的頻率為0：30%；1：20%；2：15%；3：10%；4：10%；5：6

3、%；6：5%；7：4%。 編一個最佳前綴碼，使通信中出現(xiàn)的二進制數(shù)字盡可能地少。具體要求如下：（1） 畫出相應(yīng)的二元樹。（2） 寫出每個數(shù)字對應(yīng)的前綴碼。（3） 傳輸按上述比例出現(xiàn)的數(shù)字10000個時，至少要用多少個二進制數(shù)字？11如何由有向圖G的鄰接矩陣判定G是否為根樹，若為根樹，如何定出它的樹根和樹葉。12非平凡的無向連通圖G是樹當且僅當G的每條邊都是割邊。13根數(shù)中最長路徑的端點都是樹葉嗎？為什么？14證明：若T是有n個結(jié)點的完全二元樹，則T有片樹葉。15設(shè)T為高為h的r元正則樹，證明T的樹葉數(shù)t滿足： 。16（1）求帶權(quán)為2，3，5，7，8的最優(yōu)二元樹T。 （2）求T對應(yīng)的二元前綴碼。

4、17將圖7-9所示的有序樹表示成二叉樹并求出相應(yīng)的前綴碼。 52678910413圖7-918根據(jù)圖7-10中所示的兩棵二元樹，產(chǎn)生兩個前綴碼。圖7-10（1）（2）19. 在下面給出的3個符號串集合中，哪些是前綴碼？哪些不是前綴碼？若是前綴碼，構(gòu)造二叉樹，其樹葉代表二進制編碼。若不是前綴碼，則說明理由。（1）B1=0，10，110，1111；（2）B2=1，01，001，000；（3）B3=1，11，101，001，0011。20連通圖G的樹圖是一個圖，它的結(jié)點為G的生成樹，與相鄰的充要條件是它們恰好有v-2條公共邊（其中v為G的結(jié)點數(shù)）。證明：連通圖的樹圖是連通圖。21在圖7-11中，（1

5、），（2）所示的連通圖G1，G2中各有幾棵非同構(gòu)的生成樹？（1）（2）圖7-1122畫出具有7個結(jié)點的所有非同構(gòu)的樹。23結(jié)點已標定的，和各有多少棵生成樹？24（1）證明完全二元樹的樹葉數(shù)比內(nèi)部結(jié)點數(shù)大1。 （2）找出完全n元樹的樹葉數(shù)的表達式，該表達式用樹的內(nèi)部結(jié)點數(shù)的項表示。25證明一棵完全二元樹必有奇數(shù)個結(jié)點。26在圖7-12（1）、（2）所示的兩圖中各求一棵最小生成樹，將生成樹用粗邊給出并計算它們的權(quán)。7-12 4ae54143d63c2babc9d125e8516798f56（1）（2）7-12 4ae54143d63c2babc9d125e8516798f567-12 4ae54143d63c2babc9d125e8516798f5627在圖7-13所示的帶權(quán)圖G中共有多少棵生成樹，它們的權(quán)各為多少？其中哪些是圖中的最小生成樹？adbcv3v6v8v9v7v5v4v1v0v2圖7-13圖7-144122328分別用先根、中根、和后根的次序通過如圖7-14所示的二叉樹。29設(shè)G是一無向加權(quán)圖且各邊的權(quán)不相等，V，E分