第6章 樹和二叉樹

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

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

）

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

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

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

）7、完全二叉樹中，若一個結(jié)點(diǎn)沒有左孩子，則它必是葉子。7、（√）8、完全二叉樹的存儲結(jié)構(gòu)通常采用順序存儲結(jié)構(gòu)。8、（√

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

）

A11B10C11~1025D10~1024答案：C

2、一棵二叉樹高度為h，所有結(jié)點(diǎn)的度或?yàn)?、或?yàn)?，則這棵二叉樹最少有（）個結(jié)點(diǎn)。

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

3、有關(guān)二叉樹下列說法正確的是（）

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

5、由3個結(jié)點(diǎn)可以構(gòu)造出多少種不同的二叉樹？（）

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

6、某二叉樹T有n個結(jié)點(diǎn)，設(shè)按某種順序?qū)中的每個結(jié)點(diǎn)進(jìn)行編號，編號為1，2，…，n，且有如下性質(zhì)：T中任一結(jié)點(diǎn)V，其編號等于左子樹上的最小編號減1，而V的右子樹的結(jié)點(diǎn)中，其最小編號等于V左子樹上結(jié)點(diǎn)的最大編號加1。這時是按（）編號的。

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

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

A．都不相同

B．完全相同

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

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

A

EB

FC

GD

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

A．-A+B*C/DE

B.-A+B*CD/E

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

A．a(chǎn)b+cde/*

B．a(chǎn)bcde/+*+

C．a(chǎn)bcde/*++D．a(chǎn)bcde*/++答案：B12、設(shè)樹T的度為4，其中度為1，2，3和4的結(jié)點(diǎn)個數(shù)分別為4、2、1、1則T中的葉子數(shù)為（）

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

A．4

B．5C．6D．7

答案：C14、設(shè)給定權(quán)值總數(shù)有n個，其哈夫曼樹的結(jié)點(diǎn)總數(shù)為（）

A．不確定

B．2n

C．2n+1

D．2n-1答案：D15、有n個葉子的哈夫曼樹的結(jié)點(diǎn)總數(shù)為（）。

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三、二叉樹遍歷、構(gòu)建、應(yīng)用1、二叉樹遍歷

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

若一棵赫夫曼樹共有9個頂點(diǎn)，則其葉子節(jié)點(diǎn)的個數(shù)為多少？

因?yàn)椋汉辗蚵鼧涞臉?gòu)造過程是每權(quán)值小的結(jié)點(diǎn)產(chǎn)生一個新的根結(jié)點(diǎn)

所以：從赫夫曼樹的構(gòu)造特征可知一個根結(jié)點(diǎn)要么