第6章樹和二叉樹一、判斷題

1、二叉樹是度為2的有序樹。1、（×

）

2、完全二叉樹一定存在度為1的結點。2、（×）3、二叉樹的遍歷結果不是唯一的。3、（√

）4、二叉樹的遍歷是為了在應用中找到一種線性次序。4、（√

）5、一個樹的葉子結點，在前序遍歷和后序遍歷下，皆以相同的相對位置出現。5、（√）6、用二叉樹的前序遍歷和中序遍歷可以得出二叉樹的后序遍歷。6、（√

）7、完全二叉樹中，若一個結點沒有左孩子，則它必是葉子。7、（√）8、完全二叉樹的存儲結構通常采用順序存儲結構。8、（√

）9、赫夫曼樹的結點個數不能是偶數。9、（√）10、赫夫曼樹無左右子樹之分。10、（×）二、選擇題1、一個具有1025個結點的二叉樹的高h為（

）

A11B10C11~1025D10~1024答案：C

2、一棵二叉樹高度為h，所有結點的度或為0、或為2，則這棵二叉樹最少有（）個結點。

A．2hB．2h-1C．2h+1D．h+1答案：B

3、有關二叉樹下列說法正確的是（）

A．二叉樹的度為2B．一棵二叉樹的度可以小于2C．二叉樹中至少有一個結點的度為2D．二叉樹中任何一個結點的度都為2答案：B4、對二叉樹的結點從1開始進行連續編號，要求每個結點的編號大于其左、右孩子的編號，同一結點的左右孩子中，其左孩子的編號小于其右孩子的編號，可采用（）次序的遍歷實現編號。A．先序B.中序C.后序D.從根開始按層次遍歷答案：C

5、由3個結點可以構造出多少種不同的二叉樹？（）

A．2B．3C．4D．5答案：D

6、某二叉樹T有n個結點，設按某種順序對T中的每個結點進行編號，編號為1，2，…，n，且有如下性質：T中任一結點V，其編號等于左子樹上的最小編號減1，而V的右子樹的結點中，其最小編號等于V左子樹上結點的最大編號加1。這時是按（）編號的。

A.中序遍歷序列B.前序遍歷序列

C.后序遍歷序列D.層次順序答案：B7、一棵非空的二叉樹的先序遍歷序列與后序遍歷序列正好相反，則該二叉樹一定滿足（）A．所有的結點均無左孩子B．所有的結點均無右孩子C．只有一個葉子結點D．是任意一棵二叉樹答案：C8、在二叉樹結點的先序序列，中序序列和后序序列中，所有葉子結點的先后順序（）

A．都不相同

B．完全相同

C．先序和中序相同，而與后序不同

D．中序和后序相同，而與先序不同答案：B9、二叉樹的先序遍歷和中序遍歷如下：先序遍歷：EFHIGJK；中序遍歷:HFIEJKG。該二叉樹根的右子樹的根是：

A

EB

FC

GD

H答案：C10、已知一算術表達式的中綴形式為A+B*C-D/E，后綴形式為ABC*+DE/-，其前綴形式為()

A．-A+B*C/DE

B.-A+B*CD/E

C．-+*ABC/DED.-+A*BC/DE答案：D11、算術表達式a+b*（c+d/e）轉為后綴表達式后為（）

A．ab+cde/*

B．abcde/+*+

C．abcde/*++D．abcde*/++答案：B12、設樹T的度為4，其中度為1，2，3和4的結點個數分別為4、2、1、1則T中的葉子數為（）

A．5B．6C．7D．8答案：D13、在一棵三元樹中度為3的結點數為2個，度為2的結點數為1個，度為1的結點數為2個，則度為0的結點數為（）個

A．4

B．5C．6D．7

答案：C14、設給定權值總數有n個，其哈夫曼樹的結點總數為（）

A．不確定

B．2n

C．2n+1

D．2n-1答案：D15、有n個葉子的哈夫曼樹的結點總數為（）。

A．不確定

B．2n

C．2n+1

D．2n-1答案：D16、下述編碼中哪一個不是前綴碼（）。

A

（00，01，10，11）

B

（0，1，00，11）

C

（0，10，110，111）

D

（1，01，000，001）答案：B17、下面幾個符號串編碼集合中，不是前綴編碼的是（）。

A．{0，10，110，1111}

B．{11，10，001，101，0001}

C．{00，010，0110，1000}

D．{b，c，aa，ac，aba，abb，abc}答案：B三、二叉樹遍歷、構建、應用1、二叉樹遍歷

先序中序后序遍歷的序列遍歷的算法2、二叉樹構建已知二叉樹的前序（或后序）、中序，構建二叉樹已知二叉鏈表的先序訪問字符序列，構建二叉樹，如先序訪問串為：ABC??DE?G??F???3、二叉樹應用構建赫夫曼樹赫夫曼編碼

若一棵赫夫曼樹共有9個頂點，則其葉子節點的個數為多少？

因為：赫夫曼樹的構造過程是每權值小的結點產生一個新的根結點

所以：從赫夫曼樹的構造特征可知一個根結點要么