數據結構第六章樹和二叉樹-資料下載頁

　　

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