一、 填空題
1. 不相交的樹的聚集稱之為森林 。
2. 從概念上講，樹與二叉樹是兩種不同的資料結構，將樹轉化為二叉樹的基本目的是_樹可採用孩子-兄弟鍊錶（二叉鍊錶）做儲存結構，目的是利用二叉樹的已有演算法解決樹的有關問題。
3. 深度為k的完全二叉樹至少有2 k-1個結點。至多有2 k-1個結點，若按自上而下，從左到右次序給結點編號（從1開始），則編號最小的葉子結點的編號是2 k-2+1。
4. 在一棵二叉樹中，度為零的結點的個數為n 0，度為2的結點的個數為 n 2，則有n0= n2+1。
5. 一棵二叉樹的第i（i≥1）層最多有2 i-1個結點；一棵有n（n>0）個結點的滿二叉樹共有（n+1）/2個葉子和（n-1） /2個非終端結點。
6. 現有按中序遍歷二叉樹的結果為abc，問有5種不同形態的二叉樹可以得到這一遍歷結果。
7. 哈夫曼樹是帶權路徑最小的二叉樹。
8. 字首編碼是指任乙個字元的編碼都不是另乙個字元編碼的字首的一種編碼方法，是設計不等長編碼的前提。
9. 以給定的資料集合為結點權值構造的huffman樹的加權路徑長度是 165 。
10. 樹被定義為連通而不具有迴路的（無向）圖。
11. 若一棵根樹的每個結點最多只有兩個孩子，且孩子又有左、右之分，次序不能顛倒，則稱此根樹為二叉樹
12. 高度為k，且有個結點的二叉樹稱為二叉樹。
2k-1 滿
13. 帶權路徑長度最小的二叉樹稱為最優二叉樹，它又被稱為樹。
huffman
14. 在一棵根樹中，樹根是為零的結點，而為零的結點是結點。
入度出度樹葉
15. huffman樹中，結點的帶權路徑長度是指由到之間的路徑長度與結點權值的乘積。
結點樹根
16. 滿二叉樹是指高度為k，且有個結點的二叉樹。二叉樹的每一層i上，最多有個結點。
2k-1 2i-1
二、單選題
1. 具有10個葉結點的二叉樹中有 (b) 個度為2的結點。
(a)8 (b)9 (c)10 (d)11
2． 對二叉樹的結點從1開始進行連續編號，要求每個結點的編號大於其左右孩子的編號，同一結點的左右孩子中，其左孩子的編號小於其右孩子的編號，則可採用_（3）次序的遍歷實現編號。
（1）先序2）中序
（3）後序4）從根開始按層遍歷
3. 由2、3、4、7作為結點權值構造的樹的加權路徑長度 b 。
a、33b、30
c、36d、40
4. 高度為6的滿二叉樹，總共有的結點數是 b 。
a、15b、63
c、20d、25
5. 下面描述根樹轉換成二叉樹的特性中，正確的是 c
a、根樹轉換成的二叉樹是唯一的，二叉樹的根結點有左、右孩子。
b、根樹轉換成的二叉樹是不唯一的，二叉樹的根結點只有左孩子
c、根樹轉換成的二叉樹是唯一的，二叉樹的根結點只有左孩子。
d、根樹轉換成的二叉樹是不唯一的，二叉樹的根結點有左、右孩子。
6. 如圖所示的4棵二叉樹中，不是完全二叉樹的是ab
cd、 ○
c7.某二叉樹先序遍歷的結點序列是abdgcefh，中序遍歷的結點序列是dgbaechf，則其後序遍歷的結點序列是 d 。
a、bdgcefhab、gdbecfha
c、bdgaechfd、gdbehfca
8. 已知二叉樹按中序遍歷所得到的結點序列為dcbgeahfijk， 按後序遍歷所得到的結點序列為dcegbfhkjia， 按先序遍歷所得到的結點序列為 abcdgeihfjk 。
9. 設n，m為一棵二叉樹上的兩個結點，在中序遍歷時，n在m前的條件是 c 。
a、n在m右方b、n是m祖先
c、n在m左方d、n是m子孫
10. 二叉樹第i 層結點的結點個數最多是（設根的層數為1） ：a
a）2i-1b）2i-1c）2id） 2i-1
11. 樹的後根遍歷序列等同於該樹對應的二叉樹的： b
a）先序序列b）中序序列c）後序序列
12. 樹最適合用來表示_c___。
a. 有序資料元素 b. 無序資料元素
c. 元素之間具有分支層次關係的資料d. 元素之間無聯絡的資料
13. 由於二叉樹中每個結點的度最大為2，所以二叉樹是一種特殊的樹，這種說法_b___。
a. 正確 b. 錯誤
14. 假定在一棵二叉樹中，雙分支結點數為15，單分支結點數為30個，則葉子結點數為b 個。
a．15 b．16 c．17 d．47
15. 按照二叉樹的定義，具有3個結點的不同形狀的二叉樹有__c__種。
a. 3 b. 4 c. 5 d. 6
16. 深度為5的二叉樹至多有__c__個結點。
a. 16 b. 32 c. 31 d. 10
17. 對乙個滿二叉樹，m個樹葉，n個結點，深度為h，則__d__ 。
a. n=h+m b. h+m=2n c. m=h-1 d. n=2 h-1
18. 任何一棵二叉樹的葉結點在先序、中序和後序遍歷序列中的相對次序_a___。
a.不發生改變 b.發生改變 c.不能確定 d.以上都不對
19. 如果某二叉樹的前根次序遍歷結果為stuwv，中序遍歷為uwtvs，那麼該二叉樹的後序為__c__。
a. uwvts b. vwuts c. wuvts d. wutsv
20. 二叉樹的前序遍歷序列中，任意乙個結點均處在其子女結點的前面，這種說法__a__。
a. 正確 b. 錯誤
21. 在一非空二叉樹的中序遍歷序列中，根結點的右邊_a___。
a. 只有右子樹上的所有結點 b. 只有右子樹上的部分結點
c. 只有左子樹上的部分結點 d. 只有左子樹上的所有結點
22. 已知某二叉樹的後序遍歷序列是dabec，中序遍歷序列是debac，它的前序遍歷序列是__d__。
a. acbed b. decab c. deabc d. cedba
23. 實現任意二叉樹的後序遍歷的非遞迴演算法而不使用棧結構，最佳方案是二叉樹採用_c___儲存結構。
a. 二叉鍊錶b. 廣義表儲存結構 c. 三叉鍊錶d. 順序儲存結構
24. **索化二叉樹中，t所指結點沒有左子樹的充要條件是_b___。
a. t—＞left=null b. t—＞ltag=1
c. t—＞ltag=1且t—＞left=null d. 以上都不對
25. 二叉樹按某種順序線索化後，任一結點均有指向其前驅和後續的線索，這種說法_b___。
a. 正確 b. 錯誤
26. 樹的基本遍歷策略可分為先根遍歷和後根遍歷；二叉樹的基本遍歷策略可分為先序遍歷、中序遍歷和後序遍歷。這裡，我們把由樹轉化得到的二叉樹叫做這棵數對應的二叉樹。
結論__a__是正確的。
樹和二叉樹實驗任務書
實驗5 樹和二叉樹 一 實驗目的 1 掌握二叉樹的結構特徵，以及各種儲存結構的特點及適用範圍。2 掌握用指標型別描述 訪問和處理二叉樹的運算。二 實驗要求 1.認真閱讀和掌握本實驗的程式。2.上機執行本程式。3.儲存和列印出程式的執行結果，並結合程式進行分析。4.按照二叉樹的操作需要，重新改寫主程式...
二叉樹遍歷技巧
二叉樹先根序 後根序 中根序遍歷的速演算法 解題技巧 經過研究我找出了一種不用畫圖，由先 後 根序遍歷和中根序遍歷迅速確定遍歷結果的辦法。謹以此文獻給智商與我同級而又不得不研究演算法的朋友。抽象思維太差，用例子來說明吧。下面這個是後根遍歷的演算法。例1 已知某二叉樹的先根序遍歷為abcdefg,中根...
3最優二叉樹
計算機演算法的設計與分析實驗報告 1 描述 在權為wl，w2，wn的n個葉子所構成的所有二叉樹中，帶權路徑長度最小 即代價最小 的二叉樹稱為最優二叉樹或哈夫曼樹。例 給定4個葉子結點a，b，c和d，分別帶權7，5，2和4。構造如下圖所示的三棵二叉樹 還有許多棵 它們的帶權路徑長度分別為 a wpl ...