第6章二叉樹答案

1、第6章樹和二叉樹自測卷解答姓名班級題號二三四五總分題分101511202024100得分一、下面是有關二叉樹的敘述，請判斷正誤（每小題1分，共10分）（7）1.若二叉樹用二叉鏈表作存貯結構，則在n個結點的二叉樹鏈表中 只有n1個非空指針域。（X ）2.二叉樹中每個結點的兩棵子樹的高度差等于1。（V ）3.二叉樹中每個結點的兩棵子樹是有序的。（X ）4.二叉樹中每個結點有兩棵非空子樹或有兩棵空子樹。（X ）5.二義樹中每個結點的關鍵字值大于其左非空子樹（若存在的話） 所有結點的關鍵字值，且小于其右非空子樹（若存在的話）所有結點的關鍵字 值。（應當是二叉排序樹的特點）（X ） 6.二義樹中所有結點

2、個數是2k-l-l,其中k是樹的深度。（應2i- 1）X ）7.二叉樹中所有結點，如果不存在非空左子樹，則不存在非空右子樹。（x ） 8.對于一棵非空二叉樹，它的根結點作為第一層，則它的第i層上 最多能有2i1個結點。（應2i-l）（V ） 9.用二叉鏈表法（link-rlink）存儲包含n個結點的二叉樹，結點 的2n個指針區(qū)域中有n+1個為空指針。（正確。用二叉鏈表存儲包含n個結點的二叉樹，結點共有2n個鏈域。由于 二叉樹中，除根結點外，每一個結點有且僅有一個雙親，所以只有n-l個結點的鏈 域存放指向非空子女結點的指針，還有n+1個空指針。）即有后繼鏈接的指針僅 nT個。（V ） 10. K

3、01年計算機系研題具有12個結點的完全二義樹有5個度 為2的結點。最快方法：用葉子數=n/2=6,再求n2=n0-l=5二、填空（每空1分，共15分）1. 由3個結點所構成的二叉樹有5 種形態(tài)。2. 【訃算機研2000 一棵深度為6的滿二義樹有nl+n2二0+ n2二n0- 1=31個分支結點和26-1 =32 個葉子。注：滿二叉樹沒有度為1的結點，所以分支結點數就是二度結點數。3. 一棵具有2 5 7個結點的完全二叉樹，它的深度為9。（注：用 log2（n） +1二 8. xx +1=94. 【全國專升本統(tǒng)考題】設一棵完全二叉樹有700個結點，則共有350 個葉子結點。答：最快方法:用葉子數

4、=n/2=3505. 設一棵完全二叉樹具有1000個結點，則此完全二叉樹有500個葉子結點，有 499 個度為2的結點，有 1個結點只有非空左子樹，有 0個結點只有非空右子樹。答：最快方法：用葉子數=n/2=500 , n2二nO-l二499。另外，最后一結點 為2i屬于左葉子，右葉子是空的，所以有1個非空左子樹。完全二義樹的特點決 定不可能有左空右不空的情況，所以非空右子樹數=06. 【嚴題集6.73】一棵含有n個結點的k義樹，可能達到的最大深度 為 n ,最小深度為2。答：當k=l（單義樹）時應該最深，深度=n （層）；當k二n-l （n-1 X樹）時 應該最淺，深度=2 （層），但不包括

5、n二0或1時的特例情況。教材答案是“完全 k義樹”,未定量。）7.【96程試題1】（R） o因而二義樹的遍歷次序有六種。最常用的是三種：前序法（即按 L R次 序），后序法（即按 L R N 次序）和中序法（也稱對稱序法，即按L NR次序）。這三種方法相互之間有關聯(lián)。若已知一棵二義樹的前序序列是BEFCGDH,中序序列是FEBGCHD,則它的后序序列必是F E G H D CBo解：法1：先由已知條件畫圖，再后序遍歷得到結果；法2：不畫圖也能快速得出后序序列，只要找到根的位置特征。山前序先確 定root,由中序先確定左子樹。例如，前序遍歷BEFCGDH中，根結點在最前面， 是B；則后序遍歷中B

6、定在最后面。法3：遞歸計算。如B在前序序列中第一，中序中在中間(可知左右子樹上 有哪些元素)，則在后序中必為最后。如法對B的左右子樹同樣處理，則問題得 解。8. 【全國專升本統(tǒng)考題】中序遍歷的遞歸算法平均空間復雜度為 0(n)答：即遞歸最大嵌套層數，即棧的占用單元數。精確值應為樹的深度k+1, 包括葉子的空域也遞歸了一次。9. 【計算機研2001用5個權值3, 2, 4, 5, 1構造的哈夫曼(Huffman)樹的帶權路徑長度是33。解：先構造哈夫曼樹，得到各葉子的路徑長度之后便可求出WPL= (4 + 5 + 3) X2+ (1 + 2) X3二33(15)(9)(6)(注：兩個合并值先后不

7、同會導致編碼不同，即哈夫曼編碼不唯一)453(3)(注：合并值應排在葉子值之后)（注：原題為選擇題：A. 32B. 33C.34D. 15)三、單項選擇題（每小題1分，共11分）（C ） 1.不含任何結點的空樹（A）是一棵樹；樹；（C）是一棵樹也是一棵二叉樹；義樹（B）是一棵二叉（D）既不是樹也不是二答：以前的標答是B,因為那時樹的定義是（C ） 2.二叉樹是非線性數據結構，所以（A）它不能用順序存儲結構存儲;儲結構存儲；（B）它不能用鏈式存（C）順序存儲結構和鏈式存儲結構都能存儲；（D）順序存儲結構和鏈式存儲結構都不能使用（C ） 3.K01年計算機研題具有n（n>0）個結點的完全二叉

8、樹的深度為。（A） log2（n）（B） log2（n）（C） log2（n） +1（D） log2（n）+l注1： X表示不小于X的最小整數；X表示不大于X的最大整數，它們與 含義不同！注2：選（A）是錯誤的。例如當n為2的整數幕時就會少算一層。似乎 log2（n） +1 是對的？（A ） 4.把一棵樹轉換為二義樹后，這棵二叉樹的形態(tài)是。（A ）唯一的（B）有多種（C）有多種，但根結點都沒有左孩子（D）有多種，但根結點都沒有右孩子5.【94程P11】 從供選擇的答案中，選出應填入下面敘述？ 內的最確切的解答，把相應編號寫在答卷的對應欄內。樹是結點的有限集合，它A根結點，記為T。其余的結點分成

9、為m （mO） 個 B的集合Tl, T2,，Tm,每個集合又都是樹，此時結點T稱為Ti的父結 點，Ti稱為T的子結點（iWiWm）。一個結點的子結點個數為該結點 的 C 。供選擇的答案A：有0個或1個有0個或多個有且只有1個有1個或1個以上B:互不相交允許相交允許葉結點相交允許樹枝結點相交C：權維數次數（或度）序答案：ABC=1, 1, 36.【95程P13】 從供選擇的答案中，選出應填入下面敘述 ？ 內的 最確切的解答，把相應編號寫在答卷的對應欄內。二叉樹A。在完全的二義樹中，若一個結點沒有 B ,則它必定是葉結 點。每棵樹都能惟一地轉換成與它對應的二義樹。山樹轉換成的二義樹里，一個結 點&

10、#39;的左子女是'在原樹里對應結點的 C ,而'的右子女是它在原樹里對應 結點的 D 。供選擇的答案A：是特殊的樹不是樹的特殊形式是兩棵樹的總稱有是只 有二個根結點的樹形結構B:左子結點 右子結點 左子結點或者沒有右子結點兄弟CD：最左子結點最右子結點 最鄰近的右兄弟最鄰近的左兄弟最左的兄弟 最右的兄弟答案：A二B二C二D答案：ABCDE = 2, 1, 1, 3四、簡答題（每小題4分，共20分）1. 【嚴題集6. 2® 一棵度為2的樹與一棵二義樹有何區(qū)別?答：度為2的樹從形式上看與二義樹很相似，但它的子樹是無序的，而二義 樹是有序的。即，在一般樹中若某結點只有一個

11、孩子，就無需區(qū)分其左右次序，而 在二叉樹中即使是一個孩子也有左右之分。C的結點類型定義如下：struct nodechar data;struct node *lchild, rchild;c算法如下：void traversal(struct node *root)if (root)printf( a%cn , root>datd);traversal(root->lchild);printf ( u%c n , root-datd);traversal(root->rchild);2. KOI年計算機研題II設如下圖所示的二義樹B的存儲結構為二叉鏈表，root為 根指針，結點結構為：(lchild, data, rchild)。其中l(wèi)child, rchild分別為指 向左右孩子的指針，data為字符型