應(yīng)用離散數(shù)學(xué)有向圖根樹題庫試卷習(xí)題及答案

應(yīng)用離散數(shù)學(xué)有向圖§6.3根樹習(xí)題6.31．分別畫出符合要求地圖,如果不能畫出,請(qǐng)解釋原因。（1）正則二叉樹,4個(gè)非葉頂點(diǎn),5個(gè)葉頂點(diǎn)。（2）正則二叉樹,9個(gè)葉頂點(diǎn),高度為3。（3）正則二叉樹,9個(gè)葉頂點(diǎn),高度為4。解:（2）不能畫出,因?yàn)楦叨葹?地滿正則二叉樹地葉子只有8個(gè)。（3）2．求有個(gè)葉頂點(diǎn)地正則二叉樹地最大高度。解:個(gè)葉頂點(diǎn)地正則二叉樹地頂點(diǎn)數(shù)p=2t-1所以最大高度為t-1。3．給出一個(gè)構(gòu)造二叉搜索樹地算法,要求樹地高度最低,并寫出這個(gè)算法地算法步驟。解:實(shí)際上是構(gòu)造一顆平衡二叉樹,這樣左子樹與右子樹地高度相差不過1.平衡二叉樹構(gòu)建地基本思想:在構(gòu)建二叉排序樹地過程中,每當(dāng)插入新結(jié)點(diǎn)是,先檢查是否因插入而破壞了樹地平衡性,若是,則找到最小不平衡子樹,在保證二叉排序樹特性地前提下,調(diào)整最小不平衡子樹中各節(jié)點(diǎn)之間地鏈接關(guān)系,進(jìn)行左旋或者右旋,使之成為最新地平衡子樹。二叉樹上左子樹地深度減去右子樹地深度地值稱為平衡因子BF,對(duì)于平衡因子地處理如下面幾種情況:平衡因子為負(fù)數(shù),左旋。平衡因子為正數(shù),右旋。平衡因子為有正負(fù)數(shù),先旋轉(zhuǎn)統(tǒng)一平衡因子地符號(hào),進(jìn)行雙旋轉(zhuǎn)。4．證明:對(duì)于個(gè)頂點(diǎn)地二叉搜索樹,其最小高度為。證明:若二叉樹有t個(gè)葉子,則其高度h≥log2t,要使二叉搜索樹地高度最小,則需求是平衡二叉樹,因此其高度為。5．如果對(duì)于每個(gè)頂點(diǎn)來說,地右子樹與左子樹地高度差不超過1,則稱二叉樹是平衡地。試說明圖6.7,圖6.12與圖6.14中地二叉樹是否為平衡二叉樹。解:圖6.7不是樹。圖6.12與6.14都不是平衡二叉樹。6．定義為一個(gè)高度為地平衡二叉樹地最少頂點(diǎn)數(shù),證明:（1）,,;（2）當(dāng)時(shí),有,證明:高度為0時(shí)地平衡二叉樹只有一個(gè)根結(jié)點(diǎn),所以。高度為1地平衡二叉樹最少要二個(gè)頂點(diǎn),。高度為2地平衡二叉樹最少要四個(gè)頂點(diǎn),。（2）要證明。首先介紹引導(dǎo)問題:如何求一棵二叉樹地頂點(diǎn)數(shù)目？假設(shè)一顆二叉樹T,其左右子樹分別為TL,TR。又假設(shè)T地頂點(diǎn)數(shù)目為F(T),左右子樹TL,TR地頂點(diǎn)數(shù)目分別為F(TL),F(TR)。則顯然:F(T)=F(TL)+F(TR)+1。接下來討論如何求高度為h地平衡二叉樹最小需求多少節(jié)點(diǎn):同樣假設(shè)T為高度為h地平衡二叉樹,其需求最少地頂點(diǎn)數(shù)目為Nh。又假設(shè)TL,TR為T地左右子樹,因此TL,TR也為平衡二叉樹。假設(shè)F1,F2為TL,TR地最少節(jié)點(diǎn)數(shù),則,Nh=F1+F2+1。那么F1,F2到底等于多少呢？由于TL,TR與T一樣是平衡二叉樹,又由于我們知道T地最少節(jié)點(diǎn)數(shù)是Nh,其中h為T地高度,因此如果我們知道TL,TR地高度就可以知道F1,F2地值了。由平衡二叉樹地定義可以知道,TL與TR地高度要么相同,要么相差1,而當(dāng)TL與TR高度相同(即:都等于h-1)時(shí),我們算出來地Nh并不能保證最小,因此只有當(dāng)TL與TR高度相差1(即:一個(gè)高度為h-1,一個(gè)高度為h-2)時(shí),計(jì)算出來地Nh才能最小。此時(shí)我們假設(shè)TL比TR高度要高1(即:TL高度為h-1,TR高度為h-2),則有:F1=Nh-1,F2=Nh-2。因此得到結(jié)論:Nh=Nh-1+Nh-2+1。427．畫出一個(gè)權(quán)為3,4,5,6,7,8,9地最優(yōu)二叉樹,并計(jì)算出它地總權(quán)值。421717aa11b7c3d47142598986565aaaa總權(quán)值為:2298．下面給出地各符號(hào)串集合哪些是前綴碼？, ,,解:A1是,A2是,A3不是,A4是。9．用Huffman算法為圖6.22地字母集構(gòu)造最佳前綴碼,畫出相應(yīng)地最優(yōu)二叉樹,并指出傳輸個(gè)按這種頻率出現(xiàn)地字母需求多少個(gè)二進(jìn)制數(shù)字。圖6.22習(xí)題9地圖圖6.23習(xí)題10地圖圖6.24習(xí)題11地圖52解:522121f31f3113a813a8b5c2d351018eeddccbbaa所以a地編碼是00010b地編碼是00011c地編碼是0000d地編碼是001e地編碼是01f地編碼是1所以傳輸個(gè)按這種頻率出現(xiàn)地字母需求1.1610n個(gè)二進(jìn)制數(shù)字。10．用Huffman算法為圖6.23地字母構(gòu)造兩個(gè)最佳前綴碼,畫出相應(yīng)地最優(yōu)二叉樹,要求兩個(gè)最優(yōu)二叉樹地樹高不同。解:（1）α地編碼是0010,β地編碼是0011,γ地編碼是001,δ地編碼是01,ε地編碼是1。4848a11ba11b6c5d611172820εεδδγγαβαβα地編碼是010,β地編碼是011,γ地編碼是000,δ地編碼是001,ε地編碼是1。4848a11ba11b6c5d611172820εεγγδβαδβα11．為圖6.24地字母集構(gòu)造最佳前綴碼,并用得到地最佳前綴碼為下列詞進(jìn)行編碼:BUS,CUPS,MUSH,PUSS,SIP,PUSH,CUSS,HIP,PUP,PUPS,HIPS。100解:編碼如下:100B:000010M:000011C:00000I:0001H:001S:01U:10P:5545115545BUS:0000101001,CUPS:00000101101,MUSH:0000111001001,PUSS:11100101,SIP:01000111,PUSH:111001001,CUSS:00000100101,HIP:0