數(shù)據(jù)結(jié)構(gòu)-樹(shù)練習(xí)題.doc

數(shù)據(jù)結(jié)構(gòu)樹(shù)練習(xí)題一、選擇題1、二叉樹(shù)的深度為k，則二叉樹(shù)最多有（ C ）個(gè)結(jié)點(diǎn)。A. 2k B. 2k-1 C. 2k-1 D. 2k-12、用順序存儲(chǔ)的方法，將完全二叉樹(shù)中所有結(jié)點(diǎn)按層逐個(gè)從左到右的順序存放在一維數(shù)組R1.N中，若結(jié)點(diǎn)Ri有右孩子，則其右孩子是（ B ）。A. R2i-1 B. R2i+1C. R2i D. R2/i3、設(shè)a,b為一棵二叉樹(shù)上的兩個(gè)結(jié)點(diǎn)，在中序遍歷時(shí)，a在b前面的條件是（ B ）。A. a在b的右方 B. a在b的左方C. a是b的祖先D. a是b的子孫4、設(shè)一棵二叉樹(shù)的中序遍歷序列：badce，后序遍歷序列：bdeca，則二叉樹(shù)先序遍歷序列為（ ）。A. adbce B. decab C. debac D. abcde5、在一棵具有5層的滿二叉樹(shù)中結(jié)點(diǎn)總數(shù)為（ A ）。 A. 31 B. 32 C. 33 D. 166、由二叉樹(shù)的前序和后序遍歷序列（ B ）惟一確定這棵二叉樹(shù)。A. 能 B. 不能7、某二叉樹(shù)的中序序列為ABCDEFG，后序序列為BDCAFGE，則其左子樹(shù)中結(jié)點(diǎn)數(shù)目為（ C ）。A. 3B. 2C. 4D. 58、若以4,5,6,7,8作為權(quán)值構(gòu)造哈夫曼樹(shù)，則該樹(shù)的帶權(quán)路徑長(zhǎng)度為（ C ）。A. 67B. 68C. 69D. 709、將一棵有100個(gè)結(jié)點(diǎn)的完全二叉樹(shù)從根這一層開(kāi)始，每一層上從左到右依次對(duì)結(jié)點(diǎn)進(jìn)行編號(hào)，根結(jié)點(diǎn)的編號(hào)為1，則編號(hào)為49的結(jié)點(diǎn)的左孩子編號(hào)為（A ）。A. 98B. 99C. 50D. 4810、表達(dá)式a*(b+c)-d的后綴表達(dá)式是（ B ）。A. abcd+-B. abc+*d-C. abc*+d- D. -+*abcd11、對(duì)某二叉樹(shù)進(jìn)行先序遍歷的結(jié)果為ABDEFC，中序遍歷的結(jié)果為DBFEAC，則后序遍歷的結(jié)果是（ B ）。A. DBFEACB. DFEBCAC. BDFECAD. BDEFAC12、樹(shù)最適合用來(lái)表示（ C ）。A. 有序數(shù)據(jù)元素 B. 無(wú)序數(shù)據(jù)元素 C. 元素之間具有分支層次關(guān)系的數(shù)據(jù) D. 元素之間無(wú)聯(lián)系的數(shù)據(jù)13、表達(dá)式A*(B+C)/(D-E+F)的后綴表達(dá)式是（ C ）A. A*B+C/D-E+FB. AB*C+D/E-F+C. ABC+*DE-F+/D. ABCDED*+/-+14、任何一棵二叉樹(shù)的葉結(jié)點(diǎn)在先序、中序和后序遍歷序列中的相對(duì)次序（ ）。A. 不發(fā)生改變B. 發(fā)生改變C. 不能確定D. 以上都不對(duì)15、假定在一棵二叉樹(shù)中，度為2的結(jié)點(diǎn)數(shù)為15，度為1的結(jié)點(diǎn)數(shù)為30，則葉子結(jié)點(diǎn)數(shù)為（ ）個(gè)。A. 15B. 16C. 17D. 4716、由權(quán)值為3，6，7，2，5的葉子結(jié)點(diǎn)生成一棵哈夫曼樹(shù)，它的帶權(quán)路徑長(zhǎng)度為（ ）。A. 51B. 23C. 53 D. 74二、判斷題（ ）1、存在這樣的二叉樹(shù)，對(duì)它采用任何次序的遍歷，結(jié)果相同。（ ）2、中序遍歷一棵二叉排序樹(shù)的結(jié)點(diǎn)，可得到排好序的結(jié)點(diǎn)序列。（ ）3、對(duì)于任意非空二叉樹(shù)，要設(shè)計(jì)其后序遍歷的非遞歸算法而不使用堆棧結(jié)構(gòu)，最適合的方法是對(duì)該二叉樹(shù)采用三叉鏈表。（ ）4、在哈夫曼編碼中，當(dāng)兩個(gè)字符出現(xiàn)的頻率相同時(shí)，其編碼也相同，對(duì)于這種情況應(yīng)做特殊處理。（ T ）5、一個(gè)含有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)，它的高度是log2n1。（ T ）6、完全二叉樹(shù)的某結(jié)點(diǎn)若無(wú)左孩子，則它必是葉結(jié)點(diǎn)。三、填空題1、具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度是 log2n+1 。2、哈夫曼樹(shù)是其樹(shù)的帶權(quán)路徑長(zhǎng)度 最小 的二叉樹(shù)。3、在一棵二叉樹(shù)中，度為0的結(jié)點(diǎn)的個(gè)數(shù)是n0，度為2的結(jié)點(diǎn)的個(gè)數(shù)為n2，則有 n0= N2+1 。4、樹(shù)內(nèi)各結(jié)點(diǎn)度的 最大值 稱為樹(shù)的度。四、綜合題1、假設(shè)用于通訊的電文僅由8個(gè)字母A、B、C、D、E、F、G、H組成，字母在電文中出現(xiàn)的頻率分別為：0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10。請(qǐng)為這8個(gè)字母設(shè)計(jì)哈夫曼編碼。 2、已知權(quán)值集合為5,7,2,3,6,9，要求給出哈夫曼樹(shù)，并計(jì)算帶權(quán)路徑長(zhǎng)度WPL。WPL=12