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

7.3补充练习题及参考答案

7.3.1单项选择题

1.对于一棵具有n个结点、度为4的树来说,_____________.

A.树的高度最多是n-3

B.树的高度最多是是n-4

C.第i层上最多有4(i-1)个结点

D.至少在某一层上正好有4个结点

答:这样的树中至少有一个结点的度为4,也就是说,至少有一层中有4个或以上的结点,因此树的高度最多是n-3。本题的答案为A。

2.度为4、高度为h的树_____________.

A.至少有h+3个结点

B.最多有4h-1个结点

C.最多有4h个结点

D.至少有h+4个结点

答:与上小题分析相同,本题的答案为A。

3.对于一棵具有n个结点、度为4的树来说,树的高度至少是_____________.

A.

B.

C.

D.

答:由树的性质4可知,具有n个结点的m次树的最小高度为。这里m=4,因此最小高度为。本题的答案为C。

4.在一棵3次树中度为3的结点数为两个,度为2的结点数为一个,度为1的结点数为两个,则度为0的结点数为_____________个。

A.4 B.5 C.6 D.7

答：=2，=1，=2，，n=度之和+1=+++1=11，

所以。本题的答案为C。

5.若一棵有n个结点的树,其中所有分支结点的度均为k,该树中的叶子结点个数

是_____________。

A.n(k一1)/k B.n-k C.(n+1)/k D.(nk一n+1)/k

答:m=k,有,度之和=n-1=,,所以=n-=n-(n-1)/k=(nk-n+1)/k.本题的答案为D。

6.若3次树中有a个度为1的结点、b个度为2的结点、C个度为3的结点,则该树有_____________个叶子结点。

A.1+2b+3c B.1+2b+3c C.2b-3c D.1+b+2c

答:n=+++=+a+b+c,n=度之和+1=+++1=a+2b+3c+1,所以,,总结点数n=a+2b+3c+1。本题的答案为D

7.假设每个结点值为单个字符,而一棵树的层次遍历序列为ABCDEFGHIJ,则其根结点的值是____________.

A.A B.B C.J D.以上都不对

答:树的层次遍历过程中访问的第一个结点是根结点,本题的答案为A

8.用双亲存储结构表示树,其优点之一是比较方便____________.

A.找指定结点的双亲结点

B.找指定结点的孩子结点

C.找指定结点的兄弟结点

D.判断某结点是不是叶子结点

答:A。

9.用孩子链存储结构表示树,其优点之一是_________比较方便。

A.判断两个指定结点是不是兄弟

B.找指定结点的双亲

C.判断指定结点在第几层

D.计算指定结点的度数

答:在树的孩子链存储结构中,每个结点有指向所有孩子结点的指针,所以很容易计算其孩子结点个数(度数)。本题的答案为D

10.一棵度为10、结点个数为m(n100)的树采用孩子链存储结构时,其中非空指针域数占总指针域数的比例约为_________.

A.5% B.10% C.20% D.50%

答:在度为10树的孩子链存储结构中,每个结点的指针域个数为10,共有10n个指针域,其中非空的指针域个数等于分支数,即n-1,其余为空指针域,所以非空指针域数占总指针域数的比例=(n-1)/(10n)≈10%。本题的答案为B。

11.如果在树的孩子兄弟链存储结构中有6个空的左指针域,7个空的右指针域,5

个结点数、右指针域都为空,则该树中叶子结点的个数___________.

A.有7个 B.有6个 C.有5个 D.不能确定

答:在树的孩子兄弟链存储结构中,左指针域指向第一个孩子结点,右指针域指向右兄弟结点。该树有6个空的左指针域,说明有6个结点没有任何孩子,则为叶子结点。本题的答案为B

12.有一棵3次树,其中，，，当该数采用孩子兄弟链存储结构时，其中非空指针域数占总指针域数的比例约为___________.

A.10% B.45% C.70% D.90%

答:m=3,=,而,所以非空指针域数占总指针域个数为24.指向孩子或者兄弟的非空指针域个数=n-1=11，所以非空指针域数占总指针域个数的比例=11/24≈45%.本题的答案为B。

13.设森林F中有3棵树,第一、第二和第三课数的结点个数分别为、和。与森林F对应的二叉树根结点的右子树上的结点个数是___________.

A. B. C. D.

答:对应的二叉树根结点的右子树上的结点均由第二和第三棵树上的结点转换得到本题的答案为D.

14.设F是一个森林,B是由F变换的二叉树。若F中有m个分支结点,则B中右指针域为空的结点有__________个。

A.m-1 B.m C.m+l D.m+2

答:F中的每个分支结点都有一个最右孩子结点,这