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

1、數(shù)據(jù)結(jié)構(gòu)樹練習(xí)題一、選擇題1、二叉樹的深度為k，則二叉樹最多有（ c ）個(gè)結(jié)點(diǎn)。a. 2k b. 2k-1 c. 2k-1 d. 2k-12、用順序存儲(chǔ)的方法，將完全二叉樹中所有結(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為一棵二叉樹上的兩個(gè)結(jié)點(diǎn)，在中序遍歷時(shí)，a在b前面的條件是（ b ）。a. a在b的右方 b. a在b的左方c. a是b的祖先d. a是b的子孫4、設(shè)一棵二叉樹的中序遍歷序列：badce，后序遍歷序列：bdeca，則二叉樹先序遍歷序列為（ ）。a. a

2、dbce b. decab c. debac d. abcde5、在一棵具有5層的滿二叉樹中結(jié)點(diǎn)總數(shù)為（ a ）。 a. 31 b. 32 c. 33 d. 166、由二叉樹的前序和后序遍歷序列（ b ）惟一確定這棵二叉樹。a. 能 b. 不能7、某二叉樹的中序序列為abcdefg，后序序列為bdcafge，則其左子樹中結(jié)點(diǎn)數(shù)目為（ c ）。a. 3b. 2c. 4d. 58、若以4,5,6,7,8作為權(quán)值構(gòu)造哈夫曼樹，則該樹的帶權(quán)路徑長(zhǎng)度為（ c ）。a. 67b. 68c. 69d. 709、將一棵有100個(gè)結(jié)點(diǎn)的完全二叉樹從根這一層開始，每一層上從左到右依次對(duì)結(jié)點(diǎn)進(jìn)行編號(hào)，根結(jié)點(diǎn)的編號(hào)為

3、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ì)某二叉樹進(jìn)行先序遍歷的結(jié)果為abdefc，中序遍歷的結(jié)果為dbfeac，則后序遍歷的結(jié)果是（ b ）。a. dbfeacb. dfebcac. bdfecad. bdefac12、樹最適合用來(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á)式是（

4、 c ）a. a*b+c/d-e+fb. ab*c+d/e-f+c. abc+*de-f+/d. abcded*+/-+14、任何一棵二叉樹的葉結(jié)點(diǎn)在先序、中序和后序遍歷序列中的相對(duì)次序（ ）。a. 不發(fā)生改變b. 發(fā)生改變c. 不能確定d. 以上都不對(duì)15、假定在一棵二叉樹中，度為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)生成一棵哈夫曼樹，它的帶權(quán)路徑長(zhǎng)度為（ ）。a. 51b. 23c. 53 d. 74二、判斷題（ ）1、存在這樣的二叉樹，對(duì)它采用任何次序的遍歷，結(jié)果相同。（ ）2、中

5、序遍歷一棵二叉排序樹的結(jié)點(diǎn)，可得到排好序的結(jié)點(diǎn)序列。（ ）3、對(duì)于任意非空二叉樹，要設(shè)計(jì)其后序遍歷的非遞歸算法而不使用堆棧結(jié)構(gòu)，最適合的方法是對(duì)該二叉樹采用三叉鏈表。（ ）4、在哈夫曼編碼中，當(dāng)兩個(gè)字符出現(xiàn)的頻率相同時(shí)，其編碼也相同，對(duì)于這種情況應(yīng)做特殊處理。（ t ）5、一個(gè)含有n個(gè)結(jié)點(diǎn)的完全二叉樹，它的高度是log2n1。（ t ）6、完全二叉樹的某結(jié)點(diǎn)若無(wú)左孩子，則它必是葉結(jié)點(diǎn)。三、填空題1、具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度是 log2n+1 。2、哈夫曼樹是其樹的帶權(quán)路徑長(zhǎng)度 最小 的二叉樹。3、在一棵二叉樹中，度為0的結(jié)點(diǎn)的個(gè)數(shù)是n0，度為2的結(jié)點(diǎn)的個(gè)數(shù)為n2，則有 n0= n2+1 。4、樹內(nèi)各結(jié)點(diǎn)度的 最大值 稱為樹的度。四、綜合題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，要求給出哈夫曼樹，并計(jì)算帶權(quán)路徑長(zhǎng)度wpl。wpl=1