數(shù)據(jù)結(jié)構(gòu)作業(yè)：第6章二叉樹作業(yè)答案

1、第6章 樹和二叉樹 姓名 班級(jí) 題號(hào)一二三四五六總分題分101511202024100得分一、下面是有關(guān)二叉樹的敘述，請(qǐng)判斷正誤（ ）3.二叉樹中每個(gè)結(jié)點(diǎn)的兩棵子樹是有序的。 （ × ）4.二叉樹中每個(gè)結(jié)點(diǎn)有兩棵非空子樹或有兩棵空子樹。 （ × ）6.二叉樹中所有結(jié)點(diǎn)個(gè)數(shù)是2k-1-1，其中k是樹的深度。（應(yīng)2i-1） （ × ）7.二叉樹中所有結(jié)點(diǎn)，如果不存在非空左子樹，則不存在非空右子樹。 （ × ）8.對(duì)于一棵非空二叉樹，它的根結(jié)點(diǎn)作為第一層，則它的第i層上最多能有2i1個(gè)結(jié)點(diǎn)。（應(yīng)2i-1）二、填空2. 【計(jì)算機(jī)研2000】 一棵深度為6的滿二叉

2、樹有26-1 =32 個(gè)葉子。3 一棵具有個(gè)結(jié)點(diǎn)的完全二叉樹，它的深度為 9 。（ 注：用ë log2(n) û+1= ë 8.xx û+1=94. 【計(jì)算機(jī)研2001】 用5個(gè)權(quán)值3, 2, 4, 5, 1構(gòu)造的哈夫曼（Huffman）樹的帶權(quán)路徑長(zhǎng)度是 33 。解：先構(gòu)造哈夫曼樹，得到各葉子的路徑長(zhǎng)度之后便可求出WPL（453）×2（12）×3=33 (15)(9) (6) （注：兩個(gè)合并值先后不同會(huì)導(dǎo)致編碼不同，即哈夫曼編碼不唯一） 4 5 3 (3) 1 2（注：原題為選擇題：32 33 34 15）5. 在一棵二叉樹中，度為

3、零的結(jié)點(diǎn)的個(gè)數(shù)為N0,度為2的結(jié)點(diǎn)的個(gè)數(shù)為N2,則有N0 =_N2+1。四、單項(xiàng)選擇題（每小題1分，共11分）（ C ）1 不含任何結(jié)點(diǎn)的空樹 。（）是一棵樹; （）是一棵二叉樹; （）是一棵樹也是一棵二叉樹; （）既不是樹也不是二叉樹答：以前的標(biāo)答是B，因?yàn)槟菚r(shí)樹的定義是n1（ C ）2二叉樹是非線性數(shù)據(jù)結(jié)構(gòu)，所以 。（）它不能用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ); （）它不能用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)存儲(chǔ); （）順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)都能存儲(chǔ); （）順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)都不能使用 （ C ）3. 01年計(jì)算機(jī)研題 具有n(n>0)個(gè)結(jié)點(diǎn)的完全二叉樹的深度為 。() élog2(n)ù

4、 () ë log2(n)û () ë log2(n) û+1 () élog2(n)+1ù注1：éx ù表示不小于x的最小整數(shù)；ë xû表示不大于x的最大整數(shù)，它們與 含義不同！注2：選（A）是錯(cuò)誤的。例如當(dāng)n為2的整數(shù)冪時(shí)就會(huì)少算一層。似乎ë log2(n) +1û是對(duì)的？4. 除第一層外，滿二叉樹中每一層結(jié)點(diǎn)個(gè)數(shù)是上一層結(jié)點(diǎn)個(gè)數(shù)的（C）A)1/2倍B)1倍C) 2倍D) 3倍5. 權(quán)值為1,2,6,8的四個(gè)結(jié)點(diǎn)構(gòu)成的哈夫曼樹的帶權(quán)路徑長(zhǎng)度是（ D ）。A) 18 B)

5、28 C) 19 D) 295. 【94程P11】 從供選擇的答案中，選出應(yīng)填入下面敘述 ？ 內(nèi)的最確切的解答，把相應(yīng)編號(hào)寫在答卷的對(duì)應(yīng)欄內(nèi)。樹是結(jié)點(diǎn)的有限集合，它A 根結(jié)點(diǎn)，記為T。其余的結(jié)點(diǎn)分成為m（m0）個(gè) B 的集合T1，T2，Tm，每個(gè)集合又都是樹，此時(shí)結(jié)點(diǎn)T稱為Ti的父結(jié)點(diǎn)，Ti稱為T的子結(jié)點(diǎn)（1im）。一個(gè)結(jié)點(diǎn)的子結(jié)點(diǎn)個(gè)數(shù)為該結(jié)點(diǎn)的 C 。供選擇的答案A： 有0個(gè)或1個(gè) 有0個(gè)或多個(gè) 有且只有1個(gè) 有1個(gè)或1個(gè)以上 B: 互不相交 允許相交 允許葉結(jié)點(diǎn)相交 允許樹枝結(jié)點(diǎn)相交C： 權(quán) 維數(shù) 次數(shù)（或度） 序答案：ABC1，1，3五、閱讀分析題（每題5分，共20分）(1) 已知一棵二

6、叉樹如圖所示。請(qǐng)分別寫出按前序、中序、后序和層次遍歷是得到的頂點(diǎn)序列。ABECFHDG前序：A,B,D,G,C,E,F,H中序：D,G,B,A,E,C,H,F后序：G,D,B,E,H,F,C,A層次：A,B,C,D,E,F,G,H六、算法設(shè)計(jì)題（前5題中任選2題，第6題必做，每題8分，共24分）1.【嚴(yán)題集6.26】假設(shè)用于通信的電文僅由8個(gè)字母組成，字母在電文中出現(xiàn)的頻率分別為0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10。試為這8個(gè)字母設(shè)計(jì)哈夫曼編碼。使用07的二進(jìn)制表示形式是另一種編碼方案。對(duì)于上述實(shí)例，比較兩種方案的優(yōu)缺點(diǎn)。解：方案1；哈夫曼編碼先將概率

7、放大100倍，以方便構(gòu)造哈夫曼樹。 w=7,19,2,6,32,3,21,10，按哈夫曼規(guī)則：【（2,3），6, (7,10)】, 19, 21, 32 0 1 0 1 0 119 21 32 0 10 1 0 17 10 6 0 12 3 （100）（40） （60）19 21 32 （28）（17） （11） 7 10 6 （5） 2 3方案比較：字母編號(hào)對(duì)應(yīng)編碼出現(xiàn)頻率10000.0720010.1930100.0240110.0651000.3261010.0371100.2181110.10字母編號(hào)對(duì)應(yīng)編碼出現(xiàn)頻率111000.072000.193111100.02411100.06

8、5100.326111110.037010.21811010.10方案1的WPL2(0.19+0.32+0.21)+4(0.07+0.06+0.10)+5(0.02+0.03)=1.44+0.92+0.25=2.61方案2的WPL3(0.19+0.32+0.21+0.07+0.06+0.10+0.02+0.03)=3結(jié)論：哈夫曼編碼優(yōu)于等長(zhǎng)二進(jìn)制編碼331518789945232. 有一份電文中共使用 6個(gè)字符:a,b,c,d,e,f,它們的出現(xiàn)頻率依次為2,3,4,7,8,9，試構(gòu)造一棵哈夫曼樹，并求其加權(quán)路徑長(zhǎng)度WPL，字符c的編碼。解：哈夫曼樹如右：WPL=(7+8+9)×2+4×3+（2+3）