1、第6章 樹和二叉樹 姓名 班級 題號一二三四五六總分題分101511202024100得分一、下面是有關二叉樹的敘述，請判斷正誤（ ）3.二叉樹中每個結點的兩棵子樹是有序的。 （ × ）4.二叉樹中每個結點有兩棵非空子樹或有兩棵空子樹。 （ × ）6.二叉樹中所有結點個數是2k-1-1，其中k是樹的深度。（應2i-1） （ × ）7.二叉樹中所有結點，如果不存在非空左子樹，則不存在非空右子樹。 （ × ）8.對于一棵非空二叉樹，它的根結點作為第一層，則它的第i層上最多能有2i1個結點。（應2i-1）二、填空2. 【計算機研2000】 一棵深度為6的滿二叉

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

3、零的結點的個數為N0,度為2的結點的個數為N2,則有N0 =_N2+1。四、單項選擇題（每小題1分，共11分）（ C ）1 不含任何結點的空樹 。（）是一棵樹; （）是一棵二叉樹; （）是一棵樹也是一棵二叉樹; （）既不是樹也不是二叉樹答：以前的標答是B，因為那時樹的定義是n1（ C ）2二叉樹是非線性數據結構，所以 。（）它不能用順序存儲結構存儲; （）它不能用鏈式存儲結構存儲; （）順序存儲結構和鏈式存儲結構都能存儲; （）順序存儲結構和鏈式存儲結構都不能使用 （ C ）3. 01年計算機研題 具有n(n>0)個結點的完全二叉樹的深度為 。() élog2(n)ù

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

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

6、叉樹如圖所示。請分別寫出按前序、中序、后序和層次遍歷是得到的頂點序列。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六、算法設計題（前5題中任選2題，第6題必做，每題8分，共24分）1.【嚴題集6.26】假設用于通信的電文僅由8個字母組成，字母在電文中出現的頻率分別為0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10。試為這8個字母設計哈夫曼編碼。使用07的二進制表示形式是另一種編碼方案。對于上述實例，比較兩種方案的優缺點。解：方案1；哈夫曼編碼先將概率

7、放大100倍，以方便構造哈夫曼樹。 w=7,19,2,6,32,3,21,10，按哈夫曼規則：【（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方案比較：字母編號對應編碼出現頻率10000.0720010.1930100.0240110.0651000.3261010.0371100.2181110.10字母編號對應編碼出現頻率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結論：哈夫曼編碼優于等長二進制編碼331518789945232. 有一份電文中共使用 6個字符:a,b,c,d,e,f,它們的出現頻率依次為2,3,4,7,8,9，試構造一棵哈夫曼樹，并求其加權路徑長度WPL，字符c的編碼。解：哈夫曼樹如右：WPL=(7+8+9)×2+4×3+（2+3）