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

1、第5章樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)19700101第5章樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù)課后習(xí)題講解課后習(xí)題講解1.填空題⑴樹(shù)是n（n≥0）結(jié)點(diǎn)的有限集合，在一棵非空樹(shù)中，有（）個(gè)根結(jié)點(diǎn)，其余的結(jié)點(diǎn)分成m（m＞0）個(gè)（）的集合，每個(gè)集合都是根結(jié)點(diǎn)的子樹(shù)。【解答】有且僅有一個(gè)，互不相交⑵樹(shù)中某結(jié)點(diǎn)的子樹(shù)的個(gè)數(shù)稱(chēng)為該結(jié)點(diǎn)的（），子樹(shù)的根結(jié)點(diǎn)稱(chēng)為該結(jié)點(diǎn)的（），該結(jié)點(diǎn)稱(chēng)為其子樹(shù)根結(jié)點(diǎn)的（）?！窘獯稹慷?，孩子，雙親⑶一棵二叉樹(shù)的第i（i≥1）層最多有（）個(gè)結(jié)點(diǎn)；一棵

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

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

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

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

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