數(shù)據(jù)結(jié)構(gòu)答案第5章

1、第5章樹和二叉樹樹和二叉樹19700101第5章樹和二叉樹樹和二叉樹課后習(xí)題講解課后習(xí)題講解1.填空題⑴樹是n（n≥0）結(jié)點的有限集合，在一棵非空樹中，有（）個根結(jié)點，其余的結(jié)點分成m（m＞0）個（）的集合，每個集合都是根結(jié)點的子樹?！窘獯稹坑星覂H有一個，互不相交⑵樹中某結(jié)點的子樹的個數(shù)稱為該結(jié)點的（），子樹的根結(jié)點稱為該結(jié)點的（），該結(jié)點稱為其子樹根結(jié)點的（）?！窘獯稹慷龋⒆?，雙親⑶一棵二叉樹的第i（i≥1）層最多有（）個結(jié)點；一棵

2、有n（n0）個結(jié)點的滿二叉樹共有（）個葉子結(jié)點和（）個非終端結(jié)點?！窘獯稹?i1，(n1)2，(n1)2【分析】設(shè)滿二叉樹中葉子結(jié)點的個數(shù)為n0，度為2的結(jié)點個數(shù)為n2，由于滿二叉樹中不存在度為1的結(jié)點，所以n=n0n2；由二叉樹的性質(zhì)n0=n21，得n0=(n1)2，n2=(n1)2。⑷設(shè)高度為h的二叉樹上只有度為0和度為2的結(jié)點，該二叉樹的結(jié)點數(shù)可能達到的最大值是（），最小值是（）?！窘獯稹?h1，2h1【分析】最小結(jié)點個數(shù)的情況是

3、第1層有1個結(jié)點，其他層上都只有2個結(jié)點。⑸深度為k的二叉樹中，所含葉子的個數(shù)最多為（）?！窘獯稹?k1【分析】在滿二叉樹中葉子結(jié)點的個數(shù)達到最多。⑹具有100個結(jié)點的完全二叉樹的葉子結(jié)點數(shù)為（）?！窘獯稹?0【分析】100個結(jié)點的完全二叉樹中最后一個結(jié)點的編號為100，其雙親即最后一個分支結(jié)點的編號為【分析】此題注意是序列正好相反，則左斜樹和右斜樹均滿足條件。⑷線索二叉樹中某結(jié)點R沒有左孩子的充要條件是（）。AR.lchild=NUL

4、LBR.ltag=0CR.ltag=1DR.rchild=NULL【解答】C【分析】線索二叉樹中某結(jié)點是否有左孩子，不能通過左指針域是否為空來判斷，而要判斷左標志是否為1。⑸深度為k的完全二叉樹至少有（）個結(jié)點，至多有（）個結(jié)點，具有n個結(jié)點的完全二叉樹按層序從1開始編號，則編號最小的葉子的序號是（）。A2k21B2k1C2k1D2k–11E2k1F2k11G2k11H2k【解答】B，C，A【分析】深度為k的完全二叉樹最少結(jié)點數(shù)的情況應(yīng)

5、是第k層上只有1個結(jié)點，最多的情況是滿二叉樹，編號最小的葉子應(yīng)該是在結(jié)點數(shù)最少的情況下，葉子結(jié)點的編號。⑹一個高度為h的滿二叉樹共有n個結(jié)點，其中有m個葉子結(jié)點，則有（）成立。An=hmBhm=2nCm=h1Dn=2m1【解答】D【分析】滿二叉樹中沒有度為1的結(jié)點，所以有m個葉子結(jié)點，則度為2的結(jié)點個數(shù)為m1。⑺任何一棵二叉樹的葉子結(jié)點在前序、中序、后序遍歷序列中的相對次序（）。A肯定不發(fā)生改變B肯定發(fā)生改變C不能確定D有時發(fā)生變化【解

6、答】A【分析】三種遍歷次序均是先左子樹后右子樹。⑻如果T是由有序樹T轉(zhuǎn)換而來的二叉樹，那么T中結(jié)點的前序序列就是T中結(jié)點的（）序列，T中結(jié)點的后序序列就是T中結(jié)點的（）序列。A前序B中序C后序D層序【解答】A，B⑼設(shè)森林中有4棵樹，樹中結(jié)點的個數(shù)依次為n1、n2、n3、n4，則把森林轉(zhuǎn)換成二叉樹后，其根結(jié)點的右子樹上有（）個結(jié)點，根結(jié)點的左子樹上有（）個結(jié)點。An11Bn1Cn1n2n3Dn2n3n4【解答】D，A【分析】由森林轉(zhuǎn)換的二