數(shù)據(jù)結(jié)構(gòu)-第六章-樹和二叉樹作業(yè)及答案

第六章樹和二叉樹作業(yè)一、選擇題（每題2分，共24分）。1.一棵二叉樹的順序存儲(chǔ)情況如下：樹中，度為2的結(jié)點(diǎn)數(shù)為（C）。A．1B．2C．3D．42.一棵“完全二叉樹”結(jié)點(diǎn)數(shù)為25，高度為（B）。A．4B．5C．6D．不確定3．下列說法中，（B）是正確的。A.二叉樹就是度為2的樹B.二叉樹中不存在度大于2的結(jié)點(diǎn)C.二叉樹是有序樹D.二叉樹中每個(gè)結(jié)點(diǎn)的度均為24.一棵二叉樹的前序遍歷序列為ABCDEFG,它的中序遍歷序列可能是（B）。A.CABDEFGB.BCDAEFGC.DACEFBGD.ADBCFEG5．線索二叉樹中的線索指的是（C）。A．左孩子B.遍歷C.指針D.標(biāo)志6.建立線索二叉樹的目的是（A）。A.方便查找某結(jié)點(diǎn)的前驅(qū)或后繼B.方便二叉樹的插入與刪除C.方便查找某結(jié)點(diǎn)的雙親D.使二叉樹的遍歷結(jié)果唯一7.有abc三個(gè)結(jié)點(diǎn)的右單枝二叉樹的順序存儲(chǔ)結(jié)構(gòu)應(yīng)該用（D）示意。A.abcB.ab^cC.ab^^cD.a^b^^^c8.一顆有2046個(gè)結(jié)點(diǎn)的完全二叉樹的第10層上共有（B）個(gè)結(jié)點(diǎn)。A.511B.512C.1023D.10249.一棵完全二叉樹一定是一棵（A）。A.平衡二叉樹B.二叉排序樹C.堆D.哈夫曼樹10．某二叉樹的中序遍歷序列和后序遍歷序列正好相反，則該二叉樹一定是（C）的二叉樹。A．空或只有一個(gè)結(jié)點(diǎn)B．高度等于其結(jié)點(diǎn)數(shù)C．任一結(jié)點(diǎn)無左孩子D．任一結(jié)點(diǎn)無右孩子11．一棵二叉樹的順序存儲(chǔ)情況如下：123456789101112131415ABCDE0F00GH000X結(jié)點(diǎn)D的左孩子結(jié)點(diǎn)為（D）。A．EB．CC．FD．沒有12．一棵“完全二叉樹”結(jié)點(diǎn)數(shù)為25，高度為（B）。A．4B．5C．6D．不確定二、填空題（每空3分，共18分）。1.樹的路徑長度：是從樹根到每個(gè)結(jié)點(diǎn)的路徑長度之和。對(duì)結(jié)點(diǎn)數(shù)相同的樹來說，路徑長度最短的是完全二叉樹。2.在有n個(gè)葉子結(jié)點(diǎn)的哈夫曼樹中，總結(jié)點(diǎn)數(shù)是2n-1。3.在有n個(gè)結(jié)點(diǎn)的二叉鏈表中，值為非空的鏈域的個(gè)數(shù)為n-1。4.某二叉樹的中序遍歷序列和后序遍歷序列正好相反，則該二叉樹一定是任一結(jié)點(diǎn)無左孩子的二叉樹。5.深度為k的二叉樹最多有個(gè)結(jié)點(diǎn)，最少有k個(gè)結(jié)點(diǎn)。三、綜合題（共58分）。1.假定字符集{a，b，c，d，e，f}中的字符在電碼中出現(xiàn)的次數(shù)如下：字符abcdef頻度9122023155構(gòu)造一棵哈夫曼樹（6分），給出每個(gè)字符的哈夫曼編碼（4分），并計(jì)算哈夫曼樹的加權(quán)路徑長度WPL（2分）。（符合WPL最小的均為哈夫曼樹，答案不唯一）哈夫曼編碼:a:1110b:10c:00d:10e:01f:1111WPL=2082.假設(shè)用于通信的電文由字符集{a,b,c,d,e,f,g}中的字符構(gòu)成，它們在電文中出現(xiàn)的頻率分別為{0.31,0.16,0.10,0.08,0.11,0.20,0.04}。要求：(1)為這7個(gè)字符設(shè)計(jì)哈夫曼樹（6分）。(2)據(jù)此哈夫曼樹設(shè)計(jì)哈夫曼編碼（4分）。(3)假設(shè)電文的長度為100字符，使用哈夫曼編碼比使用3位二進(jìn)制數(shù)等長編碼使電文總長壓縮多少？（4分）(1)為這7個(gè)字符設(shè)計(jì)哈夫曼樹為（符合WPL最小的均為哈夫曼樹，答案不唯一）：(2)哈夫曼編碼為：a:01;b:001;c:100;d:0001;e:101;f:11;g:0000(3)假設(shè)電文的長度為100字符，使用哈夫曼編碼比使用3位二進(jìn)制數(shù)等長編碼使電文總長壓縮多少？采用等長碼，100個(gè)字符需要300位二進(jìn)制數(shù)，采用哈夫曼編碼發(fā)送這100個(gè)字符需要261二進(jìn)制位，壓縮了300-261=39個(gè)字符。壓縮比為39/300=13%。3.二叉數(shù)T的（雙親到孩子的）邊集為：{<A,B>,<A,C>,<D,A>,<D,E>,<E,F>,<F,G>}請(qǐng)回答下列問題：（1）T的根結(jié)點(diǎn)（2分）：（2）T的葉結(jié)點(diǎn)（2分）：（3）T的深度（2分）：（4）如果上述列出邊集中，某個(gè)結(jié)點(diǎn)只有一個(gè)孩子時(shí)，均為其左孩子；某個(gè)結(jié)點(diǎn)有兩個(gè)孩子時(shí)，則先列出了連接左孩子的邊后列出了連接右孩子的邊。畫出該二叉樹其及前序線索（6分）。(1)T的根結(jié)點(diǎn)：D(2)T的葉結(jié)點(diǎn)：B，C，G,(3)T的深度：4(4)該二叉樹其及前序線索為：4．現(xiàn)有以下按前序和中序遍歷二叉樹的結(jié)果：前序：ABCEDFGHI中序：CEBGFHDAI畫出該二叉樹的邏輯結(jié)構(gòu)圖（5分），并在圖中加入中序線索（5分）。5．有電文：ABCDBCDCBDDBACBCCFCDBBBEBB。用Huffman樹構(gòu)造電文中每一字符的最