【正文】 __________________。 A） abdgcefh B） dgbaechf C） gdbehfca D） abcdefgh 深度為 5的二叉樹至多有 ____________________個(gè)結(jié)點(diǎn)。 A） 16 B） 32 C） 31 D） 10 在一非空二叉樹的中序遍歷序列中，根結(jié)點(diǎn)的右邊 _______________。 A）只有右子樹上的所有結(jié)點(diǎn) B）只有右子樹上的部分結(jié)點(diǎn) C）只有左子樹上的部分結(jié)點(diǎn) D）只有左子樹上的所有結(jié)點(diǎn) 如下圖所示的 T2是由森林 T1轉(zhuǎn)換而來的二叉樹，那么森林 T1有 _________個(gè)葉結(jié)點(diǎn)。 A） 4 B） 5 C） 6 D） 7 1設(shè) n、 m為一棵二叉樹上的兩個(gè)結(jié)點(diǎn)，在中序遍歷時(shí)， n在 m前的條件是 ________。 A） n在 m右方 B） n是 m祖先 C） n在 m左方 D） n是 m子孫 1有 n個(gè)葉子結(jié)點(diǎn)的哈夫曼樹的結(jié)點(diǎn)總數(shù)為 ____________________。 A）不確定 B） 2n C） 2n＋ 1 D） 2n－ 1 1設(shè)樹 T的度為 4，其中度為 4的結(jié)點(diǎn)個(gè)數(shù)分別為 1， 則 T中的葉子數(shù)為 _________________。 A） 5 B） 6 C） 7 D） 8 1有 n個(gè)葉子的哈夫曼樹的結(jié)點(diǎn)總數(shù)為 _____________ A）不確定 B） 2n C） 2n＋ 1 D） 2n－ 1 1樹的先序遍歷是 _________________________ A）先訪問樹的根結(jié)點(diǎn)，再?gòu)淖蟮接乙来蜗刃虮闅v根結(jié)點(diǎn)的各子樹 B）先序遍歷根結(jié)點(diǎn)的各子樹，最后訪問根結(jié)點(diǎn) C）先從左到右依次先序遍歷根結(jié)點(diǎn)的各子樹 D）先訪問樹的根結(jié)點(diǎn)，再?gòu)挠业阶笠来蜗刃虮闅v根結(jié)點(diǎn)的各子樹 1除根結(jié)點(diǎn)外，樹上每個(gè)結(jié)點(diǎn) _________________ A）可有任意多個(gè)孩子，任意多個(gè)雙親 B）可有任意多個(gè)孩子、一個(gè)雙親 C）可有一個(gè)孩子、任意多個(gè)雙親 D）只有一個(gè)孩子、一個(gè)雙親 1現(xiàn)有一棵結(jié)點(diǎn)總數(shù)為 20的二叉樹，它含有 4個(gè)度為 2的結(jié)點(diǎn)， 由此可知其葉子結(jié)點(diǎn)數(shù)為 _____________ A） 20 B） 16 C） 11 D） 5 1若由一棵一般樹轉(zhuǎn)化得到的二叉樹是非空二叉樹， 則該二叉樹的形狀是 __________ A）根結(jié)點(diǎn)無右子樹的二叉樹 B）根結(jié)點(diǎn)無左子樹的二叉樹 C）根結(jié)點(diǎn)可能有左子樹和右子樹 D）各結(jié)點(diǎn)只有一個(gè)孩子的二叉樹 若由森林轉(zhuǎn)化得到的二叉樹是非空二叉樹， 則該二叉樹的形狀是 _______________ A）根結(jié)點(diǎn)無右子樹的二叉樹 B）根結(jié)點(diǎn)無左子樹的二叉樹 C）根結(jié)點(diǎn)可能有左子樹和右子樹 D）各結(jié)點(diǎn)只有一個(gè)孩子的二叉樹 2哈夫曼樹是訪問葉子結(jié)點(diǎn)的外部路徑長(zhǎng)度 _______________的二叉樹。 A）最短 B）最長(zhǎng) C）可變 D）固定 2從 1開始對(duì)二叉樹進(jìn)行連續(xù)編號(hào)，要求每個(gè)結(jié)點(diǎn)的編號(hào)大于其左、 右孩子的編號(hào)。在同一個(gè)結(jié)點(diǎn)的左、右孩子中，其左孩子的編號(hào)小于 其右孩子的編號(hào)，則可采用 __________遍歷實(shí)現(xiàn)編號(hào)。 A）先序 B）中序 C）后序 D）從根開始的層次遍歷 2二叉樹在線索化后，下列問題中相對(duì)較難解決的是 ________________ A）先序線索二叉樹中求先序后繼 B）中序線索二叉樹中求中序后繼 C）中序線索二叉樹中求中序前趨 D）后序線索二叉樹中求后序后繼 2一棵左子樹為空的二叉樹在先序線索化后，其空指針域數(shù)為 _______ A） 0 B） 1 C） 2 D）不確定 2對(duì)具有 100個(gè)結(jié)點(diǎn)的二叉樹，若用二叉鏈表存儲(chǔ)，則其指針域部分用 來指向結(jié)點(diǎn)的左、右孩子，其余 _________個(gè)指針域?yàn)榭铡? A） 50 B） 99 C） 100 D） 101 2設(shè)有 13個(gè)值，用它們組成一棵哈夫曼樹，則該哈夫曼樹中共有 ___________個(gè)結(jié)點(diǎn)。 A） 13 B） 12 C） 26 D） 25 二、填空題 若已知一棵二叉樹的先序序列和中序序列分別是 BEFCGDH和 FEBGCHD，則它的后序序列是 ________________， 層次遍歷序列是 _____________________ 二叉樹的先序遍歷順序是 ABDGEHICE，則該二叉樹的根結(jié)點(diǎn)是 _____ 二叉樹的后序遍歷順序是 GFCDBFIBA，則該二叉樹的根結(jié)點(diǎn)是 ______ 樹與二叉樹之間的轉(zhuǎn)換方法中，樹的根結(jié)點(diǎn)變成二叉樹的 ____________ 樹與二叉樹之間的轉(zhuǎn)換方法中，樹的 B結(jié)點(diǎn)的右邊相鄰的兄弟結(jié)點(diǎn)是 C， 在變成二叉樹后， C結(jié)點(diǎn)是 B結(jié)點(diǎn)的 ____________結(jié)點(diǎn)。 已知一棵二叉樹的中序遍歷序列為 DBEHAFCIG，后序遍歷序列為 DHEBFIGCA，該二叉樹的前序序列為 _______________，層次遍歷序 列是 _____________________。 三、簡(jiǎn)答題 下述編碼哪一組不是前綴碼？ {00， 01， 10， 11}， {0， 1， 00， 11}， {0， 10， 110， 111} 四、綜合題 采用順序存儲(chǔ)方法和鏈接存儲(chǔ)方法分別畫出下圖所示的 二叉樹的存儲(chǔ)結(jié)構(gòu)。并寫出該樹的前序、中序和后序序列。 4 2 5 3 1 6 7 8 若二叉樹中各結(jié)點(diǎn)的值均不相同，則由二叉樹的前序序列和 中序序列，或由其后序序列和中序序列均能唯一地確定一棵二叉樹， 但由前序序列和后序序列卻不一定能唯一地確定一棵二叉樹。 （ 1）已知一棵二叉樹的前序序列和中序序列分別為 ABDGHCEFI和 GDHBAECIF，請(qǐng)畫出此二叉樹。 （ 2）已知一棵二叉樹的中序序列和后序序列分別為 BDCEAFHG和 DECBHGFA，請(qǐng)畫出該二叉樹。 （ 3）已知兩棵二叉樹的前序序列和后序序列均為 AB和 BA， 請(qǐng)畫出這兩棵不同的二叉樹。 C A B C A B D （ a） （ b） 試畫出如下圖中兩棵二叉樹的先根次序、中根次序、后根次序的線索樹。 對(duì)如下圖所示的森林： （ 1）求各樹的前序序列和后序序列； （ 2）求森林的前序序列和后序序列； （ 3）將此森林轉(zhuǎn)換為相應(yīng)的二叉樹； （ 4）給出（ a）所示樹的雙親鏈表表示、孩子鏈表表示、帶雙親的孩子 鏈表表示及孩子兄弟鏈表表示等四種存儲(chǔ)結(jié)構(gòu)，并指出哪些存儲(chǔ)結(jié)構(gòu)易 于求指定結(jié)點(diǎn)的祖先，哪些易于求指定結(jié)點(diǎn)的后代？ F C D E B A K H I J G O L M N Q P R （ a） （ b） （ c） 畫出如下圖所示的二叉樹所對(duì)應(yīng)的森林。 A B C D G H J K F I L E 假設(shè)用于通信的電文由字符集 {a， b， c， d， e， f， g， h}中的字母 構(gòu)成，這 8個(gè)字母在電文中出現(xiàn)的概率分別為 {， ， ， ， ， ， ， }。 （ 1）為這 8個(gè)字母設(shè)計(jì)哈夫曼編碼。 （ 2）若用三位二進(jìn)制數(shù)（ 0～ 7）對(duì)這個(gè) 8個(gè)字母進(jìn)行等長(zhǎng)編碼， 則哈夫曼編碼的平均碼長(zhǎng)是等長(zhǎng)編碼的百分之幾？它使電文總 長(zhǎng)平均壓縮多少？ 設(shè)一棵二叉樹的中序遍歷序列為 DGBAECHIF、后序遍歷序列 為 GDBEIHFCA （ 1）畫出這棵二叉樹。 （ 2）畫出該二叉樹的中序線索二叉樹。 （ 3）畫出該二叉樹對(duì)應(yīng)的森林。 對(duì)二叉樹中的結(jié)點(diǎn)進(jìn)行按層次順序（每一層自左至右）訪問的操作稱 為二叉樹的層次遍歷，得到的結(jié)點(diǎn)序列稱為二叉樹的層次序列。 現(xiàn)已知一棵二叉樹的層次序列為 ABCDEFGHIJ，中序序列為 DBGEHJACIF，請(qǐng)畫出該二叉樹。 設(shè)一棵二叉樹的先序遍歷序列為 ABDFCEGH，中序遍歷序列 為 BFDAGEHC。 （ 1）畫出這棵二叉樹。 （ 2）畫出該二叉樹的后序線索二叉樹。 （ 3）畫出該二叉樹對(duì)應(yīng)的森林。