樹和二叉樹練習(xí)

1、樹和二叉樹練習(xí)一、選擇題1.有一“遺傳”關(guān)系：設(shè)x是y的父親，則x可以把它的屬性遺傳給y。表示該遺傳關(guān)系最合適的數(shù)據(jù)結(jié)構(gòu)為（）。A 向量 B. 樹 C. 圖 D二叉樹 B2.樹最合適用來表示（）。A.有序數(shù)據(jù)元素 B.元素之間具有分支層次關(guān)系的數(shù)據(jù)C. 無序數(shù)據(jù)元素 D. 元素之間無聯(lián)系的數(shù)據(jù).BB的層號表示為1a,2b,3d,3e,2c,對應(yīng)于下面選擇的（）。A.1a(2b(3d,3e),2c) B.a(b(D.,e),c)C. a(b(d,e),c) D.a(b,d(e),c)c4.對二叉樹的結(jié)點(diǎn)從1開始連續(xù)編號，要求每個結(jié)點(diǎn)的編號大于其左，右孩子的編號，同一結(jié)點(diǎn)的左，右孩子中，其左孩子編

2、號小于其右孩子編號，則可采用（ ）次序的遍歷實現(xiàn)二叉樹的結(jié)點(diǎn)編號。A.先序 B. 中序 C. 后序 D. 從根開始按層次遍歷C5.假定一棵三叉樹的結(jié)點(diǎn)為50，則它的最小高度為（）。A. 3 B. 4 C. 5 D. 6CK層的滿三叉樹中，結(jié)點(diǎn)總數(shù)為（）A. (3k-1)/2 B. 3k-1 C. (3k-1)/3 D. 3kA7.按照二叉樹的定義，具有3個結(jié)點(diǎn)的二叉樹有（）種。A. 3 B. 4 C. 5 D. 6Cn個結(jié)點(diǎn)的二叉樹中，若度為2的結(jié)點(diǎn)數(shù)為n2，度為1的結(jié)點(diǎn)數(shù)為n1,度為0的結(jié)點(diǎn)數(shù)為n0，則樹的最大高度為（ ），其葉結(jié)點(diǎn)數(shù)為（）；樹的最小高度為（），其葉結(jié)點(diǎn)數(shù)為（ ）；若采用鏈表

3、存儲結(jié)構(gòu)，則有（）個空鏈域。 A. n/2 B. log2 n+1 C . log2 n D. nE. n0 + n1 + n2 F. n1 + n2 G. n2+ 1 H. 1I. n + 1 J. n1 K. n2 L. n1 + 1EGBGI9.對一個滿二叉樹，m個樹葉，n個結(jié)點(diǎn)，深度為h,則 （）。n = h + m B. h + m = 2n C. m = h -1 D. n = 2h 1Dh的二叉樹中只有度為0和度為2 的結(jié)點(diǎn)，則此類二叉樹中所包含的結(jié)點(diǎn)數(shù)至少為（），至多為（）。A. 2h B. 2h 1 C. 2h + 1 D. h +1 E. 2h-1 h 1 G. 2h+1h

4、+1 BF11. 在一棵二叉樹上第5層的結(jié)點(diǎn)數(shù)最多為（）。（假設(shè)根結(jié)點(diǎn)的層數(shù)為0） A. 8 B. 16 C. 15 D. 32B12.深度為5 的二叉樹至多有（） 個結(jié)點(diǎn)。A. 16 B. 32 C. 31 D. 10C13.一棵有124個葉結(jié)點(diǎn)的完全二叉樹，最多有（） 個結(jié)點(diǎn)。A. 247 B. 248 C. 249 D. 250 E. 251B14. 含有129個葉結(jié)點(diǎn)的完全二叉樹，最多有（）個結(jié)點(diǎn)。 A. 254 B.255 C.256 D. 257 E. 258D15.假定在一棵二叉樹中，雙分支結(jié)點(diǎn)數(shù)為15，單分支結(jié)點(diǎn)數(shù)為30個，則葉子結(jié)點(diǎn)數(shù)為（）個。A. 15 B. 16 C. 1

5、7 D. 47BR1n中，結(jié)點(diǎn)Ri若有左子樹，則左子樹是結(jié)點(diǎn)（）。A.R2i+1 B. R2i C. Ri/2 D. R2i -1B17.在一非空二叉樹的中序遍歷序列中，根結(jié)點(diǎn)的左邊（）A.只有右子樹上的所有結(jié)點(diǎn) B. 只有右子樹上的部分結(jié)點(diǎn)C. 只有左子樹上的部分結(jié)點(diǎn) D. 只有左子樹上的所有結(jié)點(diǎn)A18.任何一棵二叉樹的葉結(jié)點(diǎn)在先序，中序和后序遍歷中的相對次序（ ）。A不發(fā)生改變 B. 發(fā)生改變 C.不能確定 D.以上都不對An,m為一棵樹上的兩個結(jié)點(diǎn)，在中序遍歷時，n在m前的條件是（ ）。n在m右方 B. n是m祖先 C. n在m左方 D. n是m 子孫CABCDEFGHI，則在先序遍歷中

6、結(jié)點(diǎn)E 的直接前趨為（），后序遍歷中結(jié)點(diǎn)B 的直接后繼是（）。（1）B （2）D （3）A（4）I （5）F （6）C(4)(5)d a b e c ，中序遍歷序列是d e b a c，它的前序遍歷序列是（）。A. acbed B. decab C. deabc D .cedbaD22.二叉樹采用二叉鏈表作存儲結(jié)構(gòu)，要交換其所有分支結(jié)點(diǎn)左右子樹的位置，利用（）遍歷方法最合適。A.前序 B. 中序 C .后序 D .層次C23.欲實現(xiàn)任意二叉樹的后序遍歷的非遞歸算法而不必使用棧結(jié)構(gòu)，最佳方案是二叉樹采用（）存儲結(jié)構(gòu)。A.三叉鏈表 B. 廣義表 C. 二叉鏈表 .順序A24.在線索化二叉樹中，所指

7、結(jié)點(diǎn)沒有左子樹的充要條件是（）。.Tleft = NULL B. Tltag = 1 C. Tltag =1 且Tleft = NULL D 以上都不對B25.線索二叉樹是一種（）結(jié)構(gòu)。.邏輯 .邏輯和存儲.物理D.線性C26.將圖6-6中的二叉樹按中序線索化，結(jié)點(diǎn)X的右指針和Y 的左指針分別指向（）。（1）A，D (2) B,C (3) D,A （4）C，A(3)ABDCXEY圖6-627.在下列三次序的線索二叉樹中 （），對查找指定結(jié)點(diǎn)在該次序下的后繼效果較差。A.前序線索樹 B.中序線索樹 C.后序線索樹CT是按lchild- rchild表示法存儲，欲確定T中結(jié)點(diǎn)p在前提下的后繼，下述

8、說法不正確的是（）。A . 若p有左子女，則該后繼為p的左子女B 若p無左子女且有右子女，則該后繼為p的右子女C 若p無左子女且無右子女，則該后繼為p的右線索所指結(jié)點(diǎn)D. 若p無左子女，從結(jié)點(diǎn)p開始，追綜rchild鏈，直到rchild不是線索，則這時rchid（若不為NULL）所指結(jié)點(diǎn)為該后繼。C29.樹的基本遍歷策略可分為先根遍歷和后根遍歷；二叉樹的基本遍歷策略可分為先序遍歷，中序遍歷和后序遍歷。這里，把由樹轉(zhuǎn)化得到的二叉樹叫做這棵樹對應(yīng)得二叉樹。下面結(jié)論正確的是（）。A樹的先根遍歷序列與其對應(yīng)的二叉樹的先序遍歷序列相同B樹的后序遍歷序列與其對應(yīng)的二叉樹的后序遍歷序列相同C樹的先根遍歷序列

9、與其對應(yīng)的二叉樹的中序遍歷序列相同D以上都不對AT2 是由有序樹T轉(zhuǎn)換而來的二叉樹，那么T 中結(jié)點(diǎn)的前序就是T2中結(jié)點(diǎn)的（）。 A前序 B. 中序 C. 后序 D. 層次序 AT2 是由有序樹T轉(zhuǎn)換而來的二叉樹，那么T 中結(jié)點(diǎn)的后序就是T2中結(jié)點(diǎn)的（）。A前序 B. 中序 C.后序 D 層次序Bt2是由有序樹t1轉(zhuǎn)化而來的二叉樹，那么樹t1有（）個葉結(jié)點(diǎn)。A . 4 B. 5 C. 6 D. 7C圖6-7abecfhigdjT是哈夫曼樹，具有5個葉結(jié)點(diǎn)，樹T的高度最高可以是（）。A . 1 B. 2 C. 3D. 4 E. 5 . 6D,E34.由帶權(quán)為，的四個葉子結(jié)點(diǎn)構(gòu)造一棵哈夫曼樹，該樹的

10、帶權(quán)路徑長度為（）。.23 B. 37 C. 46 D . 43D35.若只考慮有序樹的情形，則具有個結(jié)點(diǎn)的不同形態(tài)的樹共有（）種。 A.132 B. 154. C. 429 D. 前三者均不正確A36.樹的后根遍歷序列等同于該樹對應(yīng)的二叉樹的（）先序遍歷.中序遍歷B二、填空題1.在樹形結(jié)構(gòu)中，樹根結(jié)點(diǎn)沒有_結(jié)點(diǎn)，其余每個結(jié)點(diǎn)有且只有_個前趨結(jié)點(diǎn)；葉子結(jié)點(diǎn)沒有_結(jié)點(diǎn)，其余每個結(jié)點(diǎn)的后繼結(jié)點(diǎn)可以_。前趨1后繼任意多個 2.有一棵樹如圖所示，回答下面的問題。這棵樹的根點(diǎn)是_;這棵樹的葉子結(jié)點(diǎn)是_; 結(jié)點(diǎn)k3的度是_;這棵樹的度為_;這棵樹的深度為_;結(jié)點(diǎn)k3的子女是_;結(jié)點(diǎn)k3的父結(jié)點(diǎn)是_k1k2

11、,k5,k7,k4234K5,k6k1 圖6-8k1k2k4k3k5k6k7A(B(E),C(F(H,I,J),G),D),則該樹的度為_;樹的深度為_,終端結(jié)點(diǎn)的個數(shù)為_，單分支結(jié)點(diǎn)的 個數(shù)為_,雙分支結(jié)點(diǎn)的個數(shù)為_,三分支結(jié)點(diǎn)的個數(shù)為_,C結(jié)點(diǎn)的雙親結(jié)點(diǎn)為_,其孩子結(jié)點(diǎn)為_和 _結(jié)點(diǎn)。346112AFGT中除葉結(jié)點(diǎn)外，任意結(jié)點(diǎn)的度數(shù)是3，則T的第i層結(jié)點(diǎn)的個數(shù)為_。（假設(shè)根結(jié)點(diǎn)的層數(shù)為1）3i-1 h的滿k叉樹有如下性質(zhì)：第h層上的節(jié)點(diǎn)都是葉子結(jié)點(diǎn)，其余各層上的每個結(jié)點(diǎn)都有k棵非空子樹。如果按層次順序從1開始對全部結(jié)點(diǎn)編號，則第i層上的結(jié)點(diǎn)數(shù)目是_；編號為n的結(jié)點(diǎn)的雙親結(jié)點(diǎn)（若存在）的編號

12、是_ ；編號為n的結(jié)點(diǎn)的第i個孩子結(jié)點(diǎn)（若存在）的編號是_ ，編號為n的結(jié)點(diǎn)有右兄弟的條件是_,其右兄弟的編號是_。ki-1(n-1)*k+i+1ink+1(n=0,1,2,)n+1 n(n1)個結(jié)點(diǎn)的k叉樹中，有_個空指針。n(k-1)+17.一棵含有n個結(jié)點(diǎn)的k叉樹，可能達(dá)到的最大深度為_，最小深度為_ 。 n logk(n(k-1)+1) k的滿二叉樹的結(jié)點(diǎn)總數(shù)為_,一棵深度為k的完全二叉樹的結(jié)點(diǎn)總數(shù)的最小值是_，從左到右次序給結(jié)點(diǎn)編號（從1 開始）則編號最小的葉子結(jié)點(diǎn)的編號為_，最大值是_.2k-12k-12k-2+12k-1 9.由a,b,c三個結(jié)點(diǎn)構(gòu)成的二叉樹，共有_種不同的結(jié)構(gòu)。

13、 5 0，定義樹的高度為樹中層次最大的結(jié)點(diǎn)的層次加 1 ，則高度為k的二叉樹具有的結(jié)點(diǎn)數(shù)目，最少為_,最多是_. k2k-1 11. N個結(jié)點(diǎn)的完全二叉樹， 按從上到下的，從左到右給結(jié)點(diǎn)順序編號，則編號最大的非葉結(jié)點(diǎn)編號為_，編號最小的葉結(jié)點(diǎn)為_ 。12.在一棵二叉樹中，度為0的結(jié)點(diǎn)個數(shù)為n0,度為2的結(jié)點(diǎn)個數(shù)為n2，則n0=_. n2 +1 i（i1）層最多有_個結(jié)點(diǎn) ，一棵樹有n(n0)個結(jié)點(diǎn)的 滿二叉樹共有_個葉子和_個最高非終端結(jié)點(diǎn)。2i-1; 14.一棵完全二叉樹的第5層有5個結(jié)點(diǎn)，則共有_個結(jié)點(diǎn)，其中度為1的結(jié)點(diǎn)有_個，度為0的結(jié)點(diǎn)有_個。 20110n個結(jié)點(diǎn)的完全二叉樹，其葉結(jié)點(diǎn)

14、的個數(shù)是_.16.對一棵具有n個結(jié)點(diǎn)的二叉樹，當(dāng)進(jìn)行鏈接存儲時，其二叉鏈表中的指針域的總數(shù)為_個，其中_個用于連接孩子結(jié)點(diǎn)， _個空閑著。 2n n-1 n+1 17.對于一棵具有 n個結(jié)點(diǎn)的二叉樹，當(dāng)它為一棵_二叉樹時具有最小高度，高度為_ ，當(dāng)它為一棵單支樹具有_高度，高度為_。完全（或理想平衡） 最大 n 18.樹所對應(yīng)得二叉樹其根結(jié)點(diǎn)的_子樹一定為空。 右 19.從概念上講，樹與二叉樹是兩種不同的數(shù)據(jù)結(jié)構(gòu)，將樹轉(zhuǎn)化成二叉樹的基本目標(biāo)是_.樹可以采用二叉樹的存儲結(jié)構(gòu)并利用二叉樹的已有算法解決樹的有關(guān)問題 20.結(jié)點(diǎn)最少的樹為_ ，結(jié)點(diǎn)最少的二叉樹是_. 只有一個結(jié)點(diǎn)樹 空的二叉樹 21.設(shè)根結(jié)點(diǎn)的層次數(shù)為0 ，定義樹的高度為樹中層次最大的結(jié)點(diǎn)層次加1，則高度為k，內(nèi)部結(jié)點(diǎn)的度數(shù)為1的二叉樹有_棵。 2k-1 22.一棵完全二叉樹按層次遍歷的序列為ABCDEFGHI,則在先序遍歷中結(jié)點(diǎn)E 的直接前趨為_,后序遍歷中結(jié)點(diǎn)B的直接后繼是_。 IF 23.某二叉樹的中序遍歷序列為ABCDEFG，后序序列為BDCAFGE，則該二叉