數(shù)據(jù)結(jié)構(gòu)第6章二叉樹(shù)答案

1、第6章樹(shù)和二叉樹(shù)一、下面是有關(guān)二叉樹(shù)的敘述，請(qǐng)判斷正誤（每小題1分，共10分）（7）1.若二叉樹(shù)用二叉鏈表作存貯結(jié)構(gòu)，則在n個(gè)結(jié)點(diǎn)的二叉樹(shù)鏈表中 只有n1個(gè)非空指針域。（X ）2.二叉樹(shù)中每個(gè)結(jié)點(diǎn)的兩棵子樹(shù)的高度差等于1。（V ）3.二義樹(shù)中每個(gè)結(jié)點(diǎn)的兩棵子樹(shù)是有序的。（X ）4.二義樹(shù)中每個(gè)結(jié)點(diǎn)有兩棵非空子樹(shù)或有兩棵空子樹(shù)。（X ）5.二叉樹(shù)中每個(gè)結(jié)點(diǎn)的關(guān)鍵字值大于其左非空子樹(shù)（若存在的話(huà)） 所有結(jié)點(diǎn)的關(guān)鍵字值，且小于其右非空子樹(shù)（若存在的話(huà)）所有結(jié)點(diǎn)的關(guān)鍵字 值。（應(yīng)當(dāng)是二叉排序樹(shù)的特點(diǎn)）（X ） 6.二義樹(shù)中所有結(jié)點(diǎn)個(gè)數(shù)是2k-l-l,其中k是樹(shù)的深度。（應(yīng)2i- 1）（X ）7.二叉樹(shù)

2、中所有結(jié)點(diǎn)，如果不存在非空左子樹(shù)，則不存在非空右子 樹(shù)。（X ） 8.對(duì)于一棵非空二叉樹(shù)，它的根結(jié)點(diǎn)作為第一層，則它的第i層上 最多能有2i1個(gè)結(jié)點(diǎn)。（應(yīng)2i-l）（V ） 9.用二叉鏈表法（link-rlink）存儲(chǔ)包含n個(gè)結(jié)點(diǎn)的二叉樹(shù)，結(jié)點(diǎn) 的2n個(gè)指針區(qū)域中有n+1個(gè)為空指針。（正確。用二義鏈表存儲(chǔ)包含n個(gè)結(jié)點(diǎn)的二義樹(shù)，結(jié)點(diǎn)共有2n個(gè)鏈域。山于 二叉樹(shù)中，除根結(jié)點(diǎn)外，每一個(gè)結(jié)點(diǎn)有且僅有一個(gè)雙親，所以只有n-l個(gè)結(jié)點(diǎn)的鏈 域存放指向非空子女結(jié)點(diǎn)的指針，還有n+1個(gè)空指針。）即有后繼鏈接的指針僅 nT個(gè)。（V ） 10.K01年計(jì)算機(jī)系研題）具有12個(gè)結(jié)點(diǎn)的完全二義樹(shù)有5個(gè)度為2的結(jié)點(diǎn)。最快

3、方法：用葉子數(shù)=n/2=6,再求n2=n0-l=5二、填空（每空1分，共15分）1. 由3個(gè)結(jié)點(diǎn)所構(gòu)成的二叉樹(shù)有5種形態(tài)。2. 【計(jì)算機(jī)研2000 一棵深度為6的滿(mǎn)二義樹(shù)有nl+n2二0+ n2= n0-1=31個(gè)分支結(jié)點(diǎn)和26-1 =32 個(gè)葉子。注：滿(mǎn)二叉樹(shù)沒(méi)有度為1的結(jié)點(diǎn)，所以分支結(jié)點(diǎn)數(shù)就是二度結(jié)點(diǎn)數(shù)。3. 一棵具有2 5 7個(gè)結(jié)點(diǎn)的完全二叉樹(shù)，它的深度為9 o（注：用 log2（n） +1二 8. xx +1=94. 【全國(guó)專(zhuān)升本統(tǒng)考題】設(shè)一棵完全二義樹(shù)有700個(gè)結(jié)點(diǎn)，則共有350 個(gè)葉子結(jié)點(diǎn)。答：最快方法：用葉子數(shù)=n/2=3505. 設(shè)一棵完全二義樹(shù)具有1000個(gè)結(jié)點(diǎn)，則此完全二義

4、樹(shù)有500 個(gè)葉子結(jié)點(diǎn)，有 499 個(gè)度為2的結(jié)點(diǎn)，有 1個(gè)結(jié)點(diǎn)只有非空左子樹(shù)，個(gè)結(jié)點(diǎn)只有非空右子樹(shù)。答：最快方法：用葉子數(shù)=n/2=500 , n2=n0-l=499o另外，最后一結(jié)點(diǎn) 為2i屬于左葉子，右葉子是空的，所以有1個(gè)非空左子樹(shù)。完全二義樹(shù)的特點(diǎn)決 定不可能有左空右不空的情況，所以非空右子樹(shù)數(shù)=0.6. 【嚴(yán)題集6.73】一棵含有n個(gè)結(jié)點(diǎn)的k義樹(shù)，可能達(dá)到的最大深度 為 n ,最小深度為2。答：當(dāng)01（單義樹(shù)）時(shí)應(yīng)該最深，深度=n （層）；當(dāng)k二n-l （n-1 X樹(shù)）時(shí) 應(yīng)該最淺，深度=2 （層），但不包括n二0或1時(shí)的特例情況。教材答案是“完全 k叉樹(shù)”,未定量。）7. 【96

5、程試題1】二義樹(shù)的基本組成部分是：根（N）、左子樹(shù)（L）和右子樹(shù)（R） o因而二義樹(shù)的遍歷次序有六種。最常用的是三種：前序法（即按 L R次 序），后序法（即按 L R N 次序）和中序法（也稱(chēng)對(duì)稱(chēng)序法，即按L NR次序）。這三種方法相互之間有關(guān)聯(lián)。若已知一棵二義樹(shù)的前序序列是 BEFCGDH,中序序列是FEBGCHD.則它的后序序列必是F E G H D CBo解：法1：先由已知條件畫(huà)圖，再后序遍歷得到結(jié)果；法2：不畫(huà)圖也能快速得出后序序列，只要找到根的位置特征。山前序先確 定root,山中序先確定左子樹(shù)。例如，前序遍歷BEFCGDH中，根結(jié)點(diǎn)在最前面， 是B；則后序遍歷中B-定在最后面。法

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

7、53(3)之后)1 2(注：原題為選擇題：A. 3234D. 15)(注：兩個(gè)合并值先后不同會(huì)導(dǎo)(注：合并值應(yīng)排在葉子值B. 33C.三、單項(xiàng)選擇題(每小題1分，共11分)(C ) 1.不含任何結(jié)點(diǎn)的空樹(shù)(A)是一棵樹(shù);(B)是一棵二義樹(shù);(C)是一棵樹(shù)也是一棵二義樹(shù);(D)既不是樹(shù)也不是二義樹(shù)答：以前的標(biāo)答是B,因?yàn)槟菚r(shí)樹(shù)的定義是nNl(C ) 2.二叉樹(shù)是非線(xiàn)性數(shù)據(jù)結(jié)構(gòu)，所以。(A)它不能用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)；(B)它不能用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)存儲(chǔ)；(C)順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)都能存儲(chǔ)；(D)順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)都不能使用(C ) 3.K01年計(jì)算機(jī)研題具有n(n>0)個(gè)結(jié)點(diǎn)的完全二

8、叉樹(shù)的深度為。(A) log2(n)( B) log2(n) (C) log2(n) +1(D) log2(n)+l注1： x表示不小于x的最小整數(shù)；x表示不大于x的最大整數(shù)，它們與 含義不同！注2：選(A)是錯(cuò)誤的。例如當(dāng)n為2的整數(shù)幕時(shí)就會(huì)少算一層。似乎 log2(n) +1 是對(duì)的？(A )4.把一棵樹(shù)轉(zhuǎn)換為二義樹(shù)后，這棵二叉樹(shù)的形態(tài)是。(A)唯一的(B)有多種(C)有多種，但根結(jié)點(diǎn)都沒(méi)有左孩子(D)有多種，但根結(jié)點(diǎn)都沒(méi)有右孩子最確切的解答，把相應(yīng)編號(hào)寫(xiě)在答卷的對(duì)應(yīng)欄內(nèi)。樹(shù)是結(jié)點(diǎn)的有限集合，它A根結(jié)點(diǎn)，記為T(mén)。其余的結(jié)點(diǎn)分成為m （mO） 個(gè) B的集合Tl, T2,，Tm,每個(gè)集合乂都是

9、樹(shù)，此時(shí)結(jié)點(diǎn)T稱(chēng)為T(mén)i的父結(jié) 點(diǎn)，Ti稱(chēng)為T(mén)的子結(jié)點(diǎn)（iWiWm）。一個(gè)結(jié)點(diǎn)的子結(jié)點(diǎn)個(gè)數(shù)為該結(jié)點(diǎn) 的 C 。供選擇的答案A：有0個(gè)或1個(gè)有0個(gè)或多個(gè)有且只有1個(gè)有1個(gè)或1個(gè)以上B:互不相交允許相交允許葉結(jié)點(diǎn)相交允許樹(shù)枝結(jié)點(diǎn)相交C：權(quán)維數(shù)次數(shù)（或度）序答案：ABC=1, 1, 36.【95程P13】從供選擇的答案中，選出應(yīng)填入下面敘述 ？ 內(nèi)的最確切的解答，把相應(yīng)編號(hào)寫(xiě)在答卷的對(duì)應(yīng)欄內(nèi)。二叉樹(shù)A。在完全的二義樹(shù)中，若一個(gè)結(jié)點(diǎn)沒(méi)有 B ，則它必定是葉結(jié) 點(diǎn)。每棵樹(shù)都能惟一地轉(zhuǎn)換成與它對(duì)應(yīng)的二義樹(shù)。由樹(shù)轉(zhuǎn)換成的二義樹(shù)里，一個(gè)結(jié) 點(diǎn)'的左子女是'在原樹(shù)里對(duì)應(yīng)結(jié)點(diǎn)的 C ,而'的

10、右子女是它在原樹(shù)里對(duì)應(yīng) 結(jié)點(diǎn)的 D 。供選擇的答案A：是特殊的樹(shù) 不是樹(shù)的特殊形式 是兩棵樹(shù)的總稱(chēng) 有是只 有二個(gè)根結(jié)點(diǎn)的樹(shù)形結(jié)構(gòu)B: 左子結(jié)點(diǎn) 右子結(jié)點(diǎn) 左子結(jié)點(diǎn)或者沒(méi)有右子結(jié)點(diǎn)兄弟CD：最左子結(jié)點(diǎn)最右子結(jié)點(diǎn)最鄰近的右兄弟最鄰近的左兄弟最左的兄弟 最右的兄弟答案：A二B二C二D答案：ABCDE = 2, 1, 1, 3四、簡(jiǎn)答題（每小題4分，共20分）1. 【嚴(yán)題集6. 2】一棵度為2的樹(shù)與一棵二義樹(shù)有何區(qū)別？答：度為2的樹(shù)從形式上看與二義樹(shù)很相似，但它的子樹(shù)是無(wú)序的，而二義 樹(shù)是有序的。即，在一般樹(shù)中若某結(jié)點(diǎn)只有一個(gè)孩子，就無(wú)需區(qū)分其左右次序，而 在二叉樹(shù)中即使是一個(gè)孩子也有左右之分。C的

11、結(jié)點(diǎn)類(lèi)型定義如下：struct nodechar data;struct node *lchild, rchild;；c算法如下：void traversal(struct node *root)if (root)printf( c” , root->datd);traversal(root->lchild);printf (c” , root->datd);traversal(root->rch訂d);2. KOI年計(jì)算機(jī)研題II設(shè)如下圖所示的二義樹(shù)B的存儲(chǔ)結(jié)構(gòu)為二叉鏈表，root為 根指針,結(jié)點(diǎn)結(jié)構(gòu)為:(lchild, data, rchild)。其中l(wèi)child, rchild分別為指 向左右孩子的指針，da