數(shù)據(jù)結(jié)構(gòu)樹(shù)考試題

kkk一、選擇題、叉樹(shù)的深度，二叉樹(shù)最多有（）個(gè)結(jié)點(diǎn)。

、順序存儲(chǔ)的方法，將完全叉樹(shù)中所有結(jié)點(diǎn)按層逐個(gè)從左到右的順序存放在一維數(shù)組中若結(jié)點(diǎn)有孩子，則其右孩子是（、設(shè)為棵二叉樹(shù)上的兩結(jié)點(diǎn)，在中序遍歷時(shí)在前面的條件是（在的方在的左方的先是的孫、一棵二叉樹(shù)的中序遍歷序，后序遍歷序列，二叉樹(shù)先序遍歷序列為（、一棵具有層滿二叉樹(shù)中結(jié)點(diǎn)總數(shù)為（、二叉樹(shù)的前序和后序遍歷列（）一確定這棵二叉樹(shù)。能不能、某二叉樹(shù)的中序序列為，后序列為，則其左子樹(shù)中結(jié)點(diǎn)數(shù)目為（、以作為權(quán)值造哈夫曼樹(shù)，則該樹(shù)的帶權(quán)路徑長(zhǎng)度為（

、一棵有個(gè)點(diǎn)的完全二叉樹(shù)從根這一層開(kāi)始，每一層上從左到右依次對(duì)結(jié)點(diǎn)進(jìn)行編號(hào)，根結(jié)點(diǎn)的編號(hào)，編的結(jié)點(diǎn)的左孩子編號(hào)為、達(dá)的綴達(dá)式是（

、某二叉樹(shù)進(jìn)行先序遍歷的結(jié)果，序遍歷的結(jié)果，后序遍歷的結(jié)果是（、最適合用來(lái)表示（有序據(jù)元素

素元素間具有分支層次關(guān)系數(shù)據(jù)元素間無(wú)聯(lián)系的數(shù)據(jù)、達(dá)的后綴表達(dá)式是（）、何一棵二叉樹(shù)的葉結(jié)點(diǎn)在先序、中序和后序遍歷序列中的相對(duì)次序（

不發(fā)改變發(fā)改變不能定以上都不對(duì)在一棵二叉樹(shù)中的結(jié)點(diǎn)數(shù)的點(diǎn)數(shù)葉子結(jié)點(diǎn)數(shù)）個(gè)。、權(quán)值3，6，，的葉子結(jié)點(diǎn)生成一棵哈夫樹(shù)，它的帶權(quán)路徑長(zhǎng)度為（

/

22二、判斷題（）、在這樣的二叉樹(shù)，對(duì)采用任何次序的遍歷，結(jié)果相同。（）、序遍歷一棵二叉排序的結(jié)點(diǎn)，可得到排好序的結(jié)點(diǎn)序列。（）對(duì)于任意非空二叉樹(shù)，要設(shè)計(jì)其后序遍歷的非遞歸算法而不使用堆棧結(jié)構(gòu)，最適合的方法是對(duì)該二叉樹(shù)采用三叉鏈表。（）在哈夫曼編碼中，當(dāng)兩個(gè)字符出現(xiàn)的頻率相同時(shí)，其編碼也相同，對(duì)于這種情況應(yīng)做特殊處理。（）、個(gè)含有個(gè)結(jié)點(diǎn)的完全二叉樹(shù)，它的高度（）、全二叉樹(shù)的某結(jié)若無(wú)左孩子，則它必是葉結(jié)點(diǎn)。三、填空題、有個(gè)點(diǎn)的完全二叉樹(shù)深度是n

。、夫曼樹(shù)是其樹(shù)的帶權(quán)路徑度最小的叉樹(shù)。一棵二叉樹(shù)中為的點(diǎn)的個(gè)數(shù)的點(diǎn)的個(gè)數(shù)有

N2+1

。、內(nèi)各結(jié)點(diǎn)度的最值稱樹(shù)的度。四、綜合題1設(shè)用于通訊的電文僅由8個(gè)字A、B、、、、G、組成字母在電文中出現(xiàn)的頻率分別為：0.07，，0.020.06，0.32，0.030.21，0.10。請(qǐng)為這8個(gè)字設(shè)計(jì)哈夫曼編碼。100

A

B38

62

17

21

30

32

D7

10

11

19

A

H

B

5

6

D2

3

H、知權(quán)值集合，求給出哈夫曼樹(shù)，并計(jì)算帶權(quán)路徑長(zhǎng)度。3012

187

114

5

6312WPL=12*1+(4+5+6)*3+(1+2)*4=