6.3练习题及参考答案
6.3.1 练习题
一．选择题
1．有一“遗传”关系：设x是y的父亲，则x可以把它的属性遗传给y。表示该遗传关系最合适的数据结构为（）。
A．向量  B. 树  C. 图D二叉树
2．树最合适用来表示（）。
A.有序数据元素
B.元素之间具有分支层次关系的数据
C. 无序数据元素
D. 元素之间无联系的数据.
3．树B的层号表示为1a,2b,3d,3e,2c，对应于下面选择的（）。
A.1a(2b(3d,3e),2c)
B.a(b(D.,e),c)
C. a(b(d,e),c)
D.a(b,d(e),c)
4．对二叉树的结点从1开始连续编号，要求每个结点的编号大于其左，右孩子的编号，同一结点的左，右孩子中，其左孩子编号小于其右孩子编号，则可采用（）次序的遍历实现二叉树的结点编号。
A.先序
B. 中序
C. 后序
D. 从根开始按层次遍历
5．假定一棵三叉树的结点为50，则它的最小高度为（）。
A. 3
B. 4    C    5    D 6
6. 在一棵具有K层的满三叉树中，结点总数为（）
A. (3k-1)/2
B. 3k-1
C. (3k-1)/3
D. 3k
7.按照二叉树的定义，具有3个结点的二叉树有（）种。
A. 3
先序中序后序遍历二叉树B. 4
C. 5
D. 6
8.在一棵有n个结点的二叉树中，若度为2的结点数为n2，度为一的结点数为n1，度为0的结点数为n0，则树的最大高度为（），其叶结点数为（）；树的最小高度为（），其叶结点数为（）；若采用链表存储结构，则有（）个空链域。
A. n/2
B. [log2 n+1]    C . log2 n    D. n
E n0 + n1 + n2    F. n1 + n2 G. n2+ 1 H. 1
I. n + 1 J. n1 K. n2 L. n1 + 1
9. 对一个满二叉树，m个树叶，n个结点，深度为h，则（）。
A. n = h + m
B. h + m = 2n
C. m = h -1
D. n = 2h– 1
10. 设高度为h的二叉树中只有度为0和度为2 的结点，则此类二叉树中所包含的结点数至少为（），至多为（）。
A. 2h
B. 2h – 1
C. 2h + 1
D. h +1
E. 2h-1
F.2h– 1
G. 2h+1 +1
H.2h+1
11. 在一棵二叉树上第5层的结点数最多为（）。（假设根结点的层数为0）
A. 8
B. 16
C. 15
D. 32
12. 深度为5 的二叉树至多有（）个结点。
A. 16
B. 32
C. 31
D. 10
13．一棵有124个叶结点的完全二叉树，最多有（）个结点。
A. 247
B. 248
C. 249
D. 250
E. 251
14.含有129个叶结点的完全二叉树，最多有（）个结点。
A. 254
B.255
C.256
D. 257
E. 258
15.假定在一棵二叉树中，双分支结点数为15，单分支结点数为30个，则叶子结点数为（）个。
A. 15
B. 16
C. 17
D. 47
16 用顺序存储的方法将完全二叉树中所有结点逐层存放在数组R[1…n]中，结点R[i]若有左子树，则左子树是结点（）。
A.R[2i+1]
B. R[2i]
C. R[i/2]
D. R[2i -1]
17．在一非空二叉树的中序遍历序列中，根结点的左边（）
A．只有右子树上的所有结点  B. 只有右子树上的部分结点
C．只有左子树上的部分结点  D. 只有左子树上的所有结点
18 . 任何一棵二叉树的叶结点在先序，中序和后序遍历中的相对次序（）。
A．不发生改变  B. 发生改变C.不能确定  D.以上都不对
19．设n,m为一棵树上的两个结点，在中序遍历时，n在m前的条件是（）。
A. n在m右方B。n是m祖先C。n在m左方D。n是m 子孙
20．一棵完全二叉树按层次遍历的序列为ABCDEFGHI，则在先序遍历中结点E 的直接前趋为（），后序遍历中结点B 的直接后继是（）。
（1）B （2）D （3）A（4）I （5）F （6）C
21．已知某二叉树的后序遍历是d a b e c ，中序遍历序列是d e b a c，它的前序遍历序列是（）。
A. acbed
B. decab
C. deabc    D .cedba
22．若二叉树采用二叉链表作存储结构，要交换其所有分支结点左右子树的位置，利用（）遍历方法最合适。
A前序B。中序  C 后序  D 层次
23．欲实现任意二叉树的后序遍历的非递归算法而不必使用栈结构，最佳方案是二叉树采用（）存储结构。
A三叉链表B。广义表C。二叉链表Ｄ。顺序
24．在线索化二叉树中，Ｔ所指结点没有左子树的充要条件是（）。
Ａ.T→left = NULL    B. T→ltag = 1    C. T→ltag =1 且T→left = NULL    D 以上都不对25.线索二叉树是一种（）结构。
Ａ。逻辑Ｂ。逻辑和存储Ｃ。物理D线性
26.将图6-6中的二叉树按中序线索化，结点X的右指针和Y 的左指针分别指向（）。
（1）A，D (2) B,C (3)D,A （4）C，A
A
B    D
C X    E
Y
图6-6
27．在下列三次次序的线索二叉树中（），对查指定结点在该在次序下的后继效果较差。
A．前序线索树B。中序线索树C后序线索树
28．设中序线索二叉树T是按lchild- rchild表示法存储，欲确定T中结点p在前提下的后
继，下述说法不正确的是（）。
A .  若p 有左子女，则该后继为p 的左子女
B ． 若p 无左子女且有右子女，则该后继为p 的右子女
C ． 若p 无左子女且无右子女，则该后继为p 的右线索所指结点
D.  若p 无左子女，从结点p 开始，追综rchild 链，直到rchild 不是线索，则这时rchid （不为NULL 的话）所指结点为该后继。
29．树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先序遍历，中序遍历和后序遍历。这里，把由树转化得到的二叉树叫做这棵树对应得二叉树。下面结论正确的是（）。
A ．树的先根遍历序列与其对应的二叉树的先序遍历序列相同
B ．树的后序遍历序列与其对应的二叉树的后序遍历序列相同
C ．树的先根遍历序列与其对应的二叉树的中序遍历序列相同
D ．以上都不对
30．如果T2 是由有序树T 转换而来的二叉树，那么T 中结点的前序就是T2中结点的（）。
A ． 前序
B 。 中序
C 。 后序
D 层次序
31．如果T2 是由有序树T 转换而来的二叉树，那么T 中结点的后序就是T2中结点的（）。
A ． 前序
B 。 中序
C 。 后序
D 层次序
32．如图6-7所示的t2是由有序树t1转化而来的二叉树，那么树t1有（）个叶结点。
A 4
B  5
C  6
D  7
33．设T 是哈夫曼树，具有5个叶结点，树T 的高度最高可以是（）。
A  1
B 。2
C 。  3
D  4  E. 5  Ｆ  ６
34.由带权为８，２，５，７的四个叶子结点构造一棵哈夫曼树，该树的带权路径长度为（）。
Ａ。23  B. 37    C. 46    D . 43
35. 若只考虑有序树的情形，则具有７个结点的不同形态的树共有（）种。
A .132  B. 154.    C.  429  D.  前三者均不正确
36．树的后根遍历序列等同于该树对应的二叉树的（）
Ａ．先序遍历  Ｂ。中序遍历  Ｃ。 后序遍历  Ｄ。层次遍历
二． 填空题
１．在树形结构中，树根结点没有________结点，其余每个结点有且只有_____个前趋结点；叶子结点没有______结点，其余每个结点的后继结点可以______。
２．有一棵树如图６－８所示，回答下面的问题。
这棵树的根点是______；这棵树的叶子结点是_____; 结点k3的度是_____；这棵树的度a
b    e
c    f h
i 图6-7
g d j
为_____；这棵树的深度为_____；结点k3的子女是_____；结点k3的父结点是____．
３．假定一棵树的广义表表示为A(B(E),C(F(H,I,J),G),D)，则该树的度为_____；树的深度为_____，终端结点的个数为___，单分支结点的  个数为_____，双分支结点的个数为___，三分支结点的个数为_____,C 结点的双亲结点为_____，其孩子结点为____和 _____结点。
4． 设树T 中除叶结点外，任意结点的度数是3，则T 的第i 层结点的个数为_____。 （假设根结点的层数为1）
5．一棵深度为h 的满k 叉树有如下性质：第h 层上的节点都是叶子结点，其余各层上的每个结点都有k 棵非空子树。
如果按层次顺序从1开始对全部结点编号，则第i 层上的结点数目是_____；编号为n 的结点的双亲结点（若存在）的编号是_____；编号为n 的结点的第i 个孩子结点（若存在） 的编号是______，编号为n 的结点有右兄弟的条件是___，其右兄弟的编号是______。
6．在具有n(n ≥1)个结点的k 叉树中，有____个空指针。
7．一棵含有n 个结点的k 叉树，可能达到的最大深度为____，最小深度为______。
8．一棵深度为k 的满二叉树的结点总数为______，一棵深度为k 的完全二叉树的结点总数的最小值是_____，从左到右次序给结点编号（从1 开始）则编号最小的叶子结点的编号为______，最大值是____
__.
9. 由a,b,c 三个结点构成的二叉树，共有______种不同的结构。
10．设根结点的层次数为0，定义树的高度为树中层次最大的结点的层次加 1 ，则高度为k 的二叉树具有的结点数目，最少为_____，最多是_____.
11．N 个结点的完全二叉树， 按从上到下的，从左到右给结点顺序编号，则编号最大的非叶结点编号为_____，编号最小的叶结点为________。
12．在一棵二叉树中，度为0的结点个数为n0，度为2的结点个数为n2，则n0=______.
13．一棵二叉树的第i （i ≥1）层最多有_____个结点 ，一棵树有n(n>0)个结点的 满二叉树共有______个叶子和____非最高非终端结点。
14．一棵完全二叉树的第5层有5个结点，则共有____个结点，其中度为1的结点有____个，度为0的结点有_____个。
15．具有n 个结点的完全二叉树，其叶结点的个数是_____.
16．对一棵具有n 个结点的二叉树，当进行链接存储时，其二叉链表中的指针域的总数为_____个，其中____个用于连接孩子结点，____个空闲着。
17．对于一棵具有 n 个结点的二叉树，当它为一棵______二叉树时具有最小高度，高k1
k2 k4 k3 k5 图6-8
k6
k7
度为____，当它为一棵单支树具有____高度，高度为___。
18．树所对应得二叉树其根结点的______子树一定为空。
19．从概念上讲，树与二叉树是两种不同的数据结构，将树转化成二叉树的基本目标是_____.
20．结点最少的树为______，结点最少的二叉树是______.
21．设根结点的层次数为0 ，定义树的高度为树中层次最大的结点层次加1，则高度为k ，内部结点的度数为1的二叉树有___棵。
22．一棵完全二叉树按层次遍历的序列为ABCDEFGHI，则在先序遍历中结点E 的直接前趋为_____，后序遍历中结点B 的直接后继是_____.。
23．某二叉树的中序遍历序列为ABCDEFG ，后序序列为BDCAFGE ，则该二叉树结点的前序序列为______，该二叉树对应的森林包括_____棵树。
24．用一维数组存放的一棵完全二叉树如图所示。
则后序遍历该二叉树时结点访问的顺序为_______。
25． 在一棵二叉排列树上按______遍历得到的结点序列是一个有序序列。
26．由n 个权值构成的哈夫曼树共有_______个结点。
27．由带权为3，9，6，2，5的5个叶子结点构成一棵哈夫曼树，则带权路径长度为________。
28．设F 是一个森林，B 是由F 转换得到的二叉树，F 中有n 个非终端结点，则B 中右指针域为空的结点有______个。
6.3.2  练习题参考答案
一． 选择题
1．B  2. B  3. C  4. C  5. C  6. A  7. C  8. E,G ,B,G ,I  9. D  10. B ,F 11. B  12. C
13. B  14. D  15. B  16. B  17. A  18.A  19. C  20.  (4)(5)  21. D  22. C  23. A  24. B
25.C  26. (3)  27. C  28. C  29. A  30. A  31. B  32. C  33. D ,E  34. D  35.A  36. B
二．填空
1．前趋 ；1；后继；任意多个。
2．①k1②k2,k5,k7,k4③2④3 ⑤4 ⑥k5, k6 ⑦k1
3. ①3 ②4 ③6 ④1 ⑤ 1 ⑥2 ⑦A ⑧ F ⑨G
4. 3i-1
5.①k i-1  ②⎥⎦
⎥⎢⎣⎢+-k k n 2  ③ (n-1)*k+i+1 ④i ≠nk+1(n=0,1,2,…)⑤n+1 6. n(k-1) +1
7.n , log k (n(k-1)+1)
8. ①2k -1 ② 2k-1  ③2k-2+1 ④2k-1
9.  5
10. k; 2k -1 .
11.⎣⎦2/n ⎣⎦⎡⎤)2/)1((12/++n n 或
12.n2 +1
13. 2i-1, ⎡⎤2/n ;⎣⎦2/n

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。