第五章-樹-練習(xí)-答案

1、精選優(yōu)質(zhì)文檔-傾情為你奉上一、 單項選擇題（每題2分，共26分）1) 樹最適合用來表示（ C ）A有序數(shù)據(jù)元素 B.無序數(shù)據(jù)元素C. 元素之間具有分支層次關(guān)系的數(shù)據(jù) D.元素之間無聯(lián)系的數(shù)據(jù)2) 如圖所示的4棵二叉樹中，（ C ）不是完全二叉樹。（a）（b）（d）3) 二叉樹按某種順序線索化后，任一結(jié)點均有指向其前驅(qū)和后續(xù)的線索，這種說法（ B ）A. 正確 B.錯誤4) 如圖1-1所示二叉樹的中序遍歷序列是（ B ）。A. abdgcefh B. dgbaechf C. gdbehfca D. abcdefghacbdgehf圖1-15) 如果是T2是由有序樹T1轉(zhuǎn)換而來的二叉樹，那么T1中

2、結(jié)點的先序就是T2中結(jié)點的（ A ）。A. 先序 B. 中序 C. 后序 D. 層次序6) 某二叉樹的先序遍歷序列和后序遍歷序列正好相反，則該二叉樹一定是（ D ）。A. 空或只有一個結(jié)點 B. 完全二叉樹C. 二叉排序樹 D. 高度等于其結(jié)點數(shù)7) 樹的基本遍歷策略可分為先根遍歷和后根遍歷；二叉樹的基本遍歷策略可分為先序遍歷、中序遍歷和后序遍歷。這里，我們把由樹轉(zhuǎn)化得到的二叉樹叫做這棵樹對應(yīng)的二叉樹。結(jié)論（ A ）是正確的。A. 樹的先根遍歷序列與其對應(yīng)的二叉樹的先序遍歷序列相同。B. 樹的后根遍歷序列與其對應(yīng)的二叉樹的后序遍歷序列相同。C. 樹的先根遍歷序列與其對應(yīng)的二叉樹的中序遍歷序列相

3、同。D. 以上都不對8) 如圖所示的T2是由森林T1轉(zhuǎn)換而來的二叉樹，那么森里T1有（ C ）個葉子結(jié)點。A. 4 B. 5 C. 6 D. 7aebcdfihjg9) 深度為5的二叉樹至多有（ C ）個結(jié)點。A. 16 B. 32 C. 31 D. 1010) 在一非空二叉樹的中序遍歷序列中，根結(jié)點的右邊（ A ）。A. 只有右子樹上的所有結(jié)點 B. 只有右子樹的部分結(jié)點C. 只有左子樹上的部分結(jié)點 D. 只有左子樹上的所有結(jié)點11) 設(shè)n，m為一棵二叉樹上的兩個結(jié)點，在中序遍歷時，n在m前的條件是（ C ）。A. n在m右方 B. n是m是祖先 C. n在m左方 D. n是m子孫12) 線

4、索二叉樹是一種（ C ）結(jié)構(gòu)。A. 邏輯 B. 邏輯和存儲 C. 物理 D. 線性（說明：線索二叉樹是二叉樹的一種存儲（物理）結(jié)構(gòu)）13) 根據(jù)使用頻率為5個字符設(shè)計的哈夫曼編碼不可能是（ C ）。A. 111,110,10,01,00 B. 000,001,010,011,1C. 100,11,10,1,0 D. 001,000,01,11,10k1k2k3k4k5k6k7二、 填空題1) 有一棵樹如圖所示，回答下面的問題（7分）：(1) 這棵樹的根節(jié)點（k1）；(2) 這棵樹的葉子結(jié)點是（k2,k5,k7,k4）；(3) 結(jié)點k3的度是（2）；(4) 這棵樹的度是（3）；(5) 這棵樹的深

5、度是（4）；(6) 結(jié)點k3的孩子結(jié)點是（k5,k6）；(7) 結(jié)點k3的雙親結(jié)點是（k1）2) 指出樹和二叉樹的三個主要差別（樹的結(jié)點個數(shù)至少為1，而二叉樹的結(jié)點個數(shù)可以為0），樹中結(jié)點的最大度數(shù)沒有限制，而二叉樹結(jié)點的最大度數(shù)為2），（樹的結(jié)點無左、右之分，而二叉樹的結(jié)點有左右之分）。（3分）3) 一棵二叉樹的結(jié)點數(shù)據(jù)采用順序存儲結(jié)構(gòu)，存儲于數(shù)組t中，如圖所示，則該二叉樹的鏈式存儲表示形式為（ ）。（5分）123456789101112131415161718192021eafdgcjihb4) 在一棵二叉樹中，度為零的結(jié)點的個數(shù)為n0，度為2的結(jié)點的個數(shù)為n2，則有 n0=（n2+1）（

6、2分）5) 現(xiàn)有按中序遍歷二叉樹的結(jié)果為abc，問有（5）種不同形態(tài)的二叉樹可以得到這一遍歷結(jié)果，這些二叉樹分別是（ ）。（6分）acbdgehfi6) 由如圖所示的二叉樹，回答以下問題。（1） 其中序遍歷序列為（dgbaechif）；（2分）（2） 其先序遍歷序列為（Abdgcefhi）；（2分）（3） 其后序遍歷序列為（gdbeihfca）；（2分）（4） 該二叉樹的中序線索二叉樹為（）；（5分）NULLNULLabdcefhig（5） 該二叉樹的后序線索二叉鏈表為（）；（5分）0a00b10c00f11e11d01h01g11i1NULL（6） 該二叉樹對應(yīng)的森林是（）。（3分）abdg

7、cefhi三、 簡答題1) 假設(shè)二叉樹采用順序存儲結(jié)構(gòu)，如圖所示1234567891011121314151617181920eafdgcjhib（1） 畫出二叉樹表示；（5分）（2） 寫出先序遍歷，中序遍歷和后序遍歷的結(jié)果； 解：先序遍歷序列：eadcbjfghi（3分） 中序遍歷序列：abcdjefhgi（3分） 后序遍歷序列：bcjdahigfe（3分）（3） 寫出結(jié)點值c的雙親結(jié)點，其左、右孩子；（3分）解：c的雙親結(jié)點為d，左孩子為b，沒有右孩子。（4） 畫出把此二叉樹還原成森林的圖（4分）2) 已知某二叉樹的后序遍歷序列是dabec，中序遍歷序列是debac，給出它的先序遍歷序列。（5分）解：該二叉樹的先序遍歷序列為cedba3) 有一份電文中共使用5個字符：a、b、c、d、e，它們的出現(xiàn)頻率依次為4、7、5、2、9，試畫出對應(yīng)的哈夫曼樹（請按左子樹根結(jié)點的權(quán)小于等于右子樹根結(jié)點的權(quán)次序構(gòu)造），并求出每個字符的哈夫曼編碼。（6分）271116c6beda00001111解：a：011b