數(shù)據結構-二叉樹練習題答案

PAGEPAGE10數(shù)據結構第6章樹和二叉樹下面是有關二叉樹的敘述，請判斷正誤（√）1.若二叉樹用二叉鏈表作存貯結構，則在n個結點的二叉樹鏈表中只有n-1個非空指針域。n個結點的二叉樹有n-1條分支（×）2.二叉樹中每個結點的兩棵子樹的高度差等于1。（√）3.二叉樹中每個結點的兩棵子樹是有序的。（×）4.二叉樹中每個結點有兩棵非空子樹或有兩棵空子樹。（×）5.二叉樹中每個結點的關鍵字值大于其左非空子樹（若存在的話）所有結點的關鍵字值，且小于其右非空子樹（若存在的話）所有結點的關鍵字值。（應當是二叉排序樹的特點）（×）6.二叉樹中所有結點個數(shù)是2k-1-1，其中k是樹的深度。（應2k-1）（×）7.二叉樹中所有結點，如果不存在非空左子樹，則不存在非空右子樹。（×）8.對于一棵非空二叉樹，它的根結點作為第一層，則它的第i層上最多能有2i-1個結點。（應2i-1）（√）9.用二叉鏈表法（link-rlink）存儲包含n個結點的二叉樹，結點的2n個指針區(qū)域中有n+1個為空指針。（用二叉鏈表存儲包含n個結點的二叉樹，結點共有2n個鏈域。由于二叉樹中，除根結點外，每一個結點有且僅有一個雙親，所以只有n-1個結點的鏈域存放指向非空子女結點的指針，即有后繼鏈接的指針僅n-1個，還有n+1個空指針。）采用二叉鏈表存儲有2n個鏈域，空鏈域為：2n-（n-1）=n+1（√）10.具有12個結點的完全二叉樹有5個度為2的結點。最快方法：用葉子數(shù)＝[n/2]＝6，再求n2=n0-1=5[n/2]除的結果四舍五入填空1．由３個結點所構成的二叉樹有5種形態(tài)。2.一棵深度為6的滿二叉樹有n1+n2=0+n2=n0-1=31個分支結點和26-1=32個葉子。注：滿二叉樹沒有度為1的結點，所以分支結點數(shù)就是二度結點數(shù)。(或：總結點數(shù)為n=2k-1=26-1=63，葉子數(shù)為n0=[n/2]=32，滿二叉數(shù)沒有度為1的結點，由n0=n2+1得n2=n0-1=32-1=31)3．一棵具有２５７個結點的完全二叉樹，它的深度為9。（注：用log2(n)+1=8.xx+1=9證明：根據性質2，深度為k的二叉樹至多有2k-1個結點。最小的一棵完全二叉樹的結點數(shù)：（2k-1-1）+1=2k-1最大的一棵完全二叉樹（滿二叉樹）的結點數(shù)：（2k-1）則：2k-1<=n<2k,取對數(shù):k-1<=log2n<k,因為k是整數(shù),所以:k=log2(n)+14.一棵完全二叉樹有700個結點，則共有350個葉子結點。答：最快方法：用葉子數(shù)＝[n/2]＝3505.設一棵完全二叉樹具有1000個結點，則此完全二叉樹有500個葉子結點，有499個度為2的結點，有1個結點只有非空左子樹，有0個結點只有非空右子樹。答：最快方法：用葉子數(shù)＝[n/2]＝500，n2=n0-1=499。另外，最后一結點為2i屬于左葉子，右葉子是空的，所以有1個非空左子樹。完全二叉樹的特點決定不可能有左空右不空的情況，所以非空右子樹數(shù)＝0.6.一棵含有n個結點的k叉樹，可能達到的最大深度為n，最小深度為2。答：當k=1(單叉樹)時應該最深，深度＝n（層）；當k=n-1（n-1叉樹）時應該最淺，深度＝2（層），但不包括n=0或1時的特例情況。7.二叉樹的基本組成部分是：根（N）、左子樹（L）和右子樹（R）。因而二叉樹的遍歷次序有六種。最常用的是三種：前序法（即按DLR次序），后序法（即按LRD次序）和中序法（也稱對稱序法，即按LDR次序）。這三種方法相互之間有關聯(lián)。若已知一棵二叉樹的前序序列是BEFCGDH，中序序列是FEBGCHD，則它的后序序列必是FEGHDCB。

解：法1：先由已知條件畫圖，再后序遍歷得到結果；法2：不畫圖也能快速得出后序序列，只要找到根的位置特征。由前序先確定root，由中序先確定左子樹。例如，前序遍歷BEFCGDH中，根結點在最前面，是B；則后序遍歷中B一定在最后面。法3：遞歸計算。如B在前序序列中第一，中序中在中間（可知左右子樹上有哪些元素），則在后序中必為最后。如法對B的左右子樹同樣處理，則問題得解。8.用5個權值{3,2,4,5,1}構造的哈夫曼（Huffman）樹的帶權路徑長度是33。解：先構造哈夫曼樹，得到各葉子的路徑長度之后便可求出WPL＝（4＋5＋3）×2＋（1＋2）×3=33(15)(9)(6)453(3)12三、單項選擇題（C）1．不含任何結點的空樹。（Ａ）是一棵樹;（Ｂ）是一棵二叉樹;（Ｃ）是一棵樹也是一棵二叉樹;（Ｄ）既不是樹也不是二叉樹答：以前的標答是B，因為那時樹的定義是n≥1（C）2．二叉樹是非線性數(shù)據結構，所以。（Ａ）它不能用順序存儲結構存儲;（Ｂ）它不能用鏈式存儲結構存儲;（Ｃ）順序存儲結構和鏈式存儲結構都能存儲;（Ｄ）順序存儲結構和鏈式存儲結構都不能使用（C）3.具有n(n>0)個結點的完全二叉樹的深度為。(Ａ)log2(n)(Ｂ)log2(n)(Ｃ)log2(n)+1(Ｄ)log2(n)+1注1：x表示不小于x的最小整數(shù)；x表示不大于x的最大整數(shù)，它們與[]含義不同！(四舍五入)注2：選（A）是錯誤的。例如當n為2的整數(shù)冪時就會少算一層。log2(n+1)是正確的。（A）4．把一棵樹轉換為二叉樹后，這棵二叉樹的形態(tài)是。（Ａ）唯一的（Ｂ）有多種（Ｃ）有多種，但根結點都沒有左孩子（Ｄ）有多種，但根結點都沒有右孩子四、簡答題（每小題4分，共20分）1.一棵度為2的樹與一棵二叉樹有何區(qū)別？答：度為2的樹從形式上看與二叉樹很相似，但它的子樹是無序的，而二叉樹是有序的。即，在一般樹中若某結點只有一個孩子，就無需區(qū)分其左右次序，而在二叉樹中即使是一個孩子也有左右之分。2.給定二叉樹的兩種遍歷序列，分別是：前序遍歷序列：D，A，C，E，B，H，F(xiàn)，G，I；中序遍歷序列：D，C，B，E，H，A，G，I，F(xiàn)，試畫出二叉樹B，并簡述由任意二叉樹B的前序遍歷序列和中序遍歷序列求二叉樹B的思想方法。解：方法是：由前序先確定root，由中序可確定root的左、右子樹。然后由其左子樹的元素集合和右子樹的集合對應前序遍歷序列中的元素集合，可繼續(xù)確定root的左右孩子。將他們分別作為新的root，不斷遞歸，則所有元素都將被唯一確定，問題得解。D ACFEGBHI五、閱讀分析題1.試寫出如圖所示的二叉樹分別按先序、中序、后序遍歷時得到的結點序列。答：DLR：ABDFJGKCEHILMLDR:BFJDGKACHELIMLRD：JFKGDBHLMIECA2.把如圖所示的樹轉化成二叉樹。答：注意全部兄弟之間都要連線（包括度為2的兄弟）,并注意原有連線結點一律歸入左子樹，新添連線結點一律歸入右子樹。ABECKFHDLGIMJ4.畫出和下列二叉樹相應的森林。答：注意根右邊的子樹肯定是森林，而孩子結點的右子樹均為兄弟。5.假設用于通信的電文僅由8個字母組成，字母在電文中出現(xiàn)的頻率分別為0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10。試為這8個字母設計哈夫曼編碼。使用0～7的二進制表示形式是另一種編碼方案。對于上述實例，比較兩種方案的優(yōu)缺點。解：方案1；哈夫曼編碼先將概率放大100倍，以方便構造哈夫曼樹。w={7,19,2,6,32,3,21,10}，按哈夫曼規(guī)則：01010121321010101213210101106123（40）（60）192132(28）(11)7106（5）23方案比較：字母編號對應編碼字母編號對應編碼出現(xiàn)頻率10000.0720010.1930100.0240110.0651000.3261010.0371100.2181110.10字母編號對應編碼出現(xiàn)頻率111000.07