第七章和第八章补充练习题(答案).docx

《第七章和第八章补充练习题(答案).docx》由会员分享，可在线阅读，更多相关《第七章和第八章补充练习题(答案).docx（72页珍藏版）》请在优知文库上搜索。

1、73补充练习题及参考答案7 .3.1单项选择题1.对于一棵具有n个结点、度为4的树来说,.A.树的高度最多是n-38 .树的高度最多是是n-4C.第i层上最多有4(iT)个结点D.至少在某一层上正好有4个结点答:这样的树中至少有一个结点而旋为4,也就是说,至少有一层中有4个或以上的结点，因此树的高度最多是展3。本题的答案为A。2.度为4、高度为h的树.A.至少有h+3个结点B.最多有4厂1个结点C.最多有4h个结点D.至少有h+4个结点答：与上小题分析相同,本题的答案为Ao3 .对于一棵具有n个结点、度为4的树来说,树的高度至少是.A. log4(2zz)B. Dog4On-I)C. log4

2、(3nl)D. 11og4(2n+l)答：由树的性质4可知,具有n个结点的m次树的最小高度为log,5(m-l)+l)。这里m=4,因此最小高度为log,。+DIo本题的答案为Co4 .在一棵3次树中度为3的结点数为两个,度为2的结点数为一个,度为1的结点数为两个,则度为0的结点数为个。.4B.5C.6D.7答：H3=2,zl2=i,n=2,n=n3+n2+nx+n0=5+%,n二度之和+1=3%+2%+%+1=11,所以0=11-5=6。本题的答案为配5 .若一棵有n个结点的树,其中所有分支结点的度均为k,该树中的叶子结点个数是oA.n(k-1)/kB.n-kC.(n+l)kD.(nk-n+

3、l)k答:m=k,有人。+3度之和=nT=S,%=ST攵所以11o=n-nk=n-(n-l)k=(nk-n+l)/k.本题的答案为D06 .若3次树中有a个度为1的结点、b个度为2的结点、C个度为3的结点,则该树有个叶子结点。A.l+2b3cB.l+2b+3cC.2b-3cD.l+b+2c:n=w+w1w2+=11+a+b+c,n=度之和+1=%+2%+2%+l=a+2b+3c+l,所以，%=8+2c+l,总结点数n=a+2b+3c+l0本题的答案为D7 .假设每个结点值为单个字符,而一棵树的层次遍历序列为Abcdefghij,则其根结点的值是.A.AB.BC.JD.以上都不对答:树的层次遍历

4、过程中访问的第一个结点是根结点,本题的答案为A8 .用双亲存储结构表示树,其优点之一是比较方便.A.找指定结点的双亲结点9 .找指定结点的孩子结点C.找指定结点的兄弟结点D.判断某结点是不是叶子结点答:A。10 用孩子链存储结构表示树,其优点之一是比较方便。A.判断两个指定结点是不是兄弟B.找指定结点的双亲C.判断指定结点在第几层D.计算指定结点的度数答:在树的孩子链存储结构中,每个结点有指向所有孩子结点的指针,所以很容易计算其孩子结点个数(度数)。本题的答案为D10. 一棵度为10、结点个数为m(n100)的树采用孩子链存储结构时,其中非空指针域数占总指针域数的比例约为.A.5%B.10%C

5、.20%D.50%答:在度为10树的孩子链存储结构中,每个结点的指针域个数为10,共有IOn个指针域,其中非空的指针域个数等于分支数,即n-l,其余为空指针域,所以非空指针域数占总指针域数的比例二(n-l)(10n)10%o本题的答案为B011 .如果在树的孩子兄弟链存储结构中有6个空的左指针域,7个空的右指针域,5个结点数、右指针域都为空,则该树中叶子结点的个数.A.有7个B.有6个C.有5个I).不能确定答:在树的孩子兄弟链存储结构中,左指针域指向第一个孩子结点,右指针域指向右兄弟结点。该树有6个空的左指针域,说明有6个结点没有任何孩子,则为叶子结点。本题的答案为B12 .有一棵3次树,其

6、中%=2,=2,n1=1,当该数采用孩子兄弟链存储结构时，其中非空指针域数占总指针域数的比例约为.A.10%B.45%C,70%D.90%答:m=3,11=w0+w1+n2+n3=n0+5,三n-l=1+22+3=ll,所以非空指针域数占总指针域个数为24.指向孩子或者兄弟的非空指针域个数二n-11,所以非空指针域数占总指针域个数的比例=I1/24=45%.本题的答案为B013 .设森林F中有3棵树,第一、第二和第三课数的结点个数分别为犯、也和巧。与森林F对应的二叉树根结点的右子树上的结点个数是A“tn+m2叫D加2+m3答:对应的二叉树根结点的右子树上的结点均由第二和第三棵树上的结点转换得到

7、本题的答案为D.14 .设F是一个森林,B是由F变换的二叉树。若F中有In个分支结点,则B中右指针域为空的结点有个。A.m-lB.mC.m+1D.m+2答:F中的每个分支结点都有一个最右孩子结点,这个最右孩子结点在B中右指针域为空，同时根结点的右指针域也为空,所以B中共有ml个右指针域为空的结点。本题的答案为C.15.设森林F对应的二叉树为B,它有m个结点,B的根为p,p的右子树结点个数为n,森林F中第一棵树的结点个数是.A.m-nB.m-n-1C.n+1D.条件不足,无法确定答:森林林F中的第一棵树转换成二叉树p及p的左子树。本题的答案为A016 .如果将一棵有序树T转换为二叉树B,那么T中

8、结点的先根遍历序列就是B中结点的序列。A.先序B.中序C.后序D.层次序答:若树T的根为N,它的子树为几百，?其先根序列为NTGF。树T转换成二叉树B的过程如图7.7所示口转换为以），为N的左子树中结点，纥的所有结点都在用根结点的右子树中,T的邛分工序列在B中遍历过程是先根结点、再左子树,对应B的先序序列。本题的答案为A.17 .如果将一棵有序树T转换为二叉树B,那么T中结点的后根遍历序列就是B中结点的序列。A.先序B.中序C.后序D.层次序答:若树T的根为N,它的子树为TKTz、Tln,其后根序列为Trr2TmNo树T转换成二叉树B的过程如图7.7所示（I,转换为Bi）,Bl为N的左子树中结

9、点,B2、Bn的所有结点都在Bl根结点的右子树中,T的T1T2TmN序列在B中遍历过程是先左子树,再根结点。又显然不会是B的后序序列，因为在B的后序遍历中,B2中结点会在Bl根结点之前访问,所以只能是B的中序序列。本题的答案为B18 .如果将一棵有序树T转转换为二叉树B,那么T中结点的层次序列对应B的一序列.A.先序遍历B.中序遍历C.层次遍历D.以上都不对答：由于T中的兄弟变为B中的右孩子,改变为父子关系,所以以T中结点的层次序列与B的先序、中序、后序和层次序列都没有对应关系。本题的答案为D19 .二叉树若用顺序方法存储,则下列4种运算中最容易实现.先序遍历历二叉树B.判判断两个结点值分别为

10、x、y的结点是不是在同一层上C.层次遍历二叉树D.求结点值为X的结点的所有孩子答:直接顺序扫描存储二叉树的数组即得到层次遍历二叉树序列。本题的答案为C20.二叉树和度为2的树的相同之处包括.A.每个结点都有一个或两个孩子结点B.至少有一个根结点C.至少有一个度为2的结点D.每个结点最多只有一个双亲结点答:D。二叉树树和度为2的树都属于树形结构,其中每个结点最多只有一个双亲结点.21 .一棵完全二叉树上有1001个结点,其中叶子结点的个数是.A.250B.501C.254D.505答：由二叉树的性质知%-1,且完全二叉树的尸0或1；己知二叉树的总结点数=%+%+%,即有=2%+%-1；将总结点数

11、m=OOi代入得I(X)I=2%+%-1,因101为奇数,故ni=o,得到no=501o本题的答案为Bo22 .一棵有124个叶子结点的完全二叉树最多有个结点。A.247B.248C.249D.250答：由。二%+1可知n2=123;=2+%+0=247+,在完全二叉树中，口1二0或1,所以n的最大值为247+1=248,故选B23 .在一棵具有n个结点的完全二叉树中，分支结点的最大编号为.A.15+1)/2b.1ST)/?c./21I).1./2答：D.24 .在高度为h的完全二叉树中，A.度为0的结点都在第h层上B.第i(IWiWh)层上结点都是度为2的结点C.第(IWiWhT)层上有N个

12、结点D.不存在度为1的结点答:在高度为h的元全二叉树中，第1层第h-1层构成一个满二叉树,在满二叉树中第i层上有2“个结点。本题的答案为C25.每个结点的度或者为O或者为2的二叉树称为正则二叉树,对于n个结点的正则二叉树来说,它的最大高度是A.睡21B.(n-l)2c.地2(一1)1D.(nl)2答：最大高度的正则二叉树是这样的二叉树,第1层有一个结点,第2层第h层均有两个结点,因此2(hT)+l=n,即h=(n+l)2o本题的答案为Do26 .若一棵二叉树具有10个度为2的结点、5个度为1的结点,则度为0的结点个数是.A.9B.11C.15D.不确定答:n2=10,no=n2+l=ll,本题

13、的答案为B27 .若二叉树的中序序列是abcdef,且c为根结点,则A.结点C有两个孩子B.二叉树有两个度为。的的结点C.二叉树的高度为5D.以上都不对答：中序序列是abcdef,则ab为结点C的左子树的中序序歹I1.def为结点C的右子树的中序序列,说明结点c既有左子树又有右子树。本题的答案为A028 .在任何一棵二叉树中，如果结点a有左孩子b、右孩子c,则在结点的先序序列、中序序列、后序序列中,.A.结点b一定在结点a的前面B.结点b一定在结点C的前面C.结点a一定在结点C的前面D.结点a一定在结点b的前面答:在先序遍历、中序遍历和后序遍历中都是先遍历左子树,再遍历右子树,所以结点b一定在

14、结点C的前面访问。本题的答案为B29 .如果一棵二叉树的先序序列是ab，中序序列是ba，则.A.结点a和结点b分别在某结点的左子树和右子树中B.结点b在结点a的右子树中C.结点b在结点a的左子树中D.结点a和结点b分别在某结点的两棵非空子树中答:先序序列是ab,贝IIb在a的左子树中或者b在a的某个祖先X的右子树中，中序序列是ba，则b不可在a的某个祖先X的右子树中，即b只能在a的左子树中。本题的答案为C30.设a、b为一棵二叉树上的两个结点,在中序序列时,a在b之前的条件是A.a在b的右方B.a是b的祖先C.a在b的左方D.a是b的子孙答:中序遍历时,先遍历左子树,再访问根结点,最后遍历右子

15、树。a在b前,则a在b的左子树中或b在a的右子树中，或者a在某棵子树的左子树中而b在其右子树中,这都表示a在b的左方。本题的答案为C。31.如果在一棵二叉树的先序序列、中序序列和后序序列中，结点a、b的位置都是a在前、b在后（即形如ab），则.A.a、b可能是兄弟B.a可能是b的双亲C.a可能是b的的孩子D.不存在这样的二叉树答：图7.8所示的二叉树中a和b结点就满足本题的条件。本题的答案为A。32 .若二叉树树采用二叉链存储结构,如果要交换其所有分支结点的左、右子树位置,利用遍历方法最合适。A.先序B.中序C.后序D.按层次答:先对根结点的左、右子树进行交换,再交换根结点的左、右指针值,这是后序遍历的思路。本题的答案为C.33 .关于非空二叉树的后序序列以下说法正确的是.后序序列的最后一个结点是根结点B.后序序列的最后一个结点一定是叶子结点C.后序序列的第一个结点