第6章 树和二叉树 练习题

习题6 树和二叉树

6.1 单项选择题

1. 由于二叉树中每个结点的度最大为2，所以二叉树是一种特殊的树，这种说法____。

A. 正确 B. 错误

2. 假定在一棵二叉树中，双分支结点数为15，单分支结点数为30个，则叶子结点数为 个。 A．15 B．16 C．17 D．47

3. 按照二叉树的定义，具有3个结点的不同形状的二叉树有____种。

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

4. 按照二叉树的定义，具有3个不同数据结点的不同的二叉树有____种。

A. 5 B. 6 C. 30 D. 32

5. 深度为5的二叉树至多有____个结点。

A. 16 B. 32 C. 31 D. 10

6. 设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为_ ___。

A. 2h B. 2h-1 C. 2h+1 D. h+1

7. 对一个满二叉树，m个树叶，n个结点，深度为h，则____ 。

A. n=h+m B. h+m=2n C. m=h-1 D. n=2 h-1

8. 任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序____。

A.不发生改变 B.发生改变 C.不能确定 D.以上都不对

9. 如果某二叉树的前序遍历结果为stuwv，中序遍历为uwtvs，那么该二叉树的后序为____。 A. uwvts B. vwuts C. wuvts D. wutsv

10. 二叉树的前序遍历序列中，任意一个结点均处在其子女结点的前面，这种说法____。 A. 正确 B. 错误

11. 某二叉树的前序遍历结点访问顺序是abdgcefh，中序遍历的结点访问顺序是dgbaechf，则其后序遍历的结点访问顺序是____。

A. bdgcefha B. gdbecfha C. bdgaechf D. gdbehfca 12. 在一非空二叉树的中序遍历序列中，根结点的右边____。

A. 只有右子树上的所有结点 B. 只有右子树上的部分结点 C. 只有左子树上的部分结点 D. 只有左子树上的所有结点 13. 如图6.1所示二叉树的中序遍历序列是____。

A. abcdgef B. dfebagc C. dbaefcg D. defbagc

a a a

b b c c

d d e g f

h g e

f 图6.2

图6.1

14. 一棵二叉树如图6.2所示，其中序遍历的序列为__ __。

A. abdgcefh B. dgbaechf C. gdbehfca D. abcdefgh

15．设a,b为一棵二叉树上的两个结点，在中序遍历时，a在b前的条件是 。

A．a在b的右方 B．a在b的左方 C．a是b的祖先 D．a是b的子孙

16. 已知某二叉树的后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是____。 A. acbed B. decab C. deabc D. cedba

17. 实现任意二叉树的后序遍历的非递归算法而不使用栈结构，最佳方案是二叉树采用____存储结构。

A. 二叉链表 B. 广义表存储结构 C. 三叉链表 D. 顺序存

储结构

18. 如图6.3所示的4棵二叉树，____不是完全二叉树。

(A) (B) (C) (D)

图6.3

19. 在线索化二叉树中，t所指结点没有左子树的充要条件是____。

A. t—＞left=NULL B. t—＞ltag=1 C. t—＞ltag=1且t—＞left=NULL D. 以上都不对

20. 二叉树按某种顺序线索化后，任一结点均有指向其前驱和后续的线索，这种说法____。 A. 正确 B. 错误

21. 树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。这里，我们把由树转化得到的二叉树叫做这棵树对应的二叉树。结论____是正确的。

A.树的先根遍历序列与其对应的二叉树的先序遍历序列相同 B.树的后根遍历序列与其对应的二叉树的后序遍历序列相同 C.树的先根遍历序列与其对应的二叉树的中序遍历序列相同 D.以上都不对

22. 树最适合用来表示____。

A. 有序数据元素 B. 无序数据元素

C. 元素之间具有分支层次关系的数据 D. 元素之间无联系的数据 6.2 填空题（将正确的答案填在相应的空中）

1. 有一棵树如图6.5所示，回答下面的问题：

⑴ 这棵树的根结点是____；

k1 ⑵ 这棵树的叶子结点是____； ⑶ 结点k3的度是____； k 2 k 4 k 3 ⑷ 这棵树的度是____；

k 5 k 6 ⑸ 这棵树的深度是____；

⑹ 结点k3的子女是____；

k 7 ⑺ 结点k3的父结点是____； 图6.5 一棵树

2. 指出树和二叉树的三个主要差别____、____、____。

3. 从概念上讲，树与二叉树是两种不同的数据结构，将树转化为二叉树的基本目的是___ _。

4. 一棵二叉树的结点数据采用顺序存储结构，存储于数组t中，如图6.6所示，则该二叉树的链接表示形式为__ __。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 e a f d g c j l h b 图6.6 一棵二叉树的顺序存储数组t

5. 深度为k的完全二叉树至少有____个结点。至多有____个结点，若按自上而下，从左到右次序给结点编号（从1开始），则编号最小的叶子结点的编号是____。

6. 在一棵二叉树中，度为零的结点的个数为n 0，度为2的结点的个数为 n 2，则有n0=____。

7. 一棵二叉树的第i（i≥1）层最多有____个结点；一棵有n（n>0）个结点的满二叉树共有____个叶子和____个非终端结点。

8. 结点最少的树为____，结点最少的二叉树为____。 9. 现有按中序遍历二叉树的结果为abc，问有____种不同形态的二叉树可以得到这一遍历结果，这些二叉树分别是____。

10. 由如图6.7所示的二叉树，回答以下问题： a ⑴ 其中序遍历序列为____；

b c ⑵ 其前序遍历序列为____；

def ⑶ 其后序遍历序列为____；

h i

图6.7 一棵二叉树

习题答案

6.1 1. B 2. B 3. C 4. C 5. C 6. A 7. D 8. A 9. C 10. A

11. D 2. A 13. B 14. B 15. B 16. D 17. C 18. C 19. B 20. B 21. A 22. C 6.2

1. ⑴ k1 ⑵ k2,k5,k7,k4 ⑶ 2 ⑷ 3 ⑸ 4 ⑹ k5,k6 ⑺ k1

2. 树的结点个数至少为1(不同教材规定不同)，

e 而二叉树的结点个数可以为0；

af 树中结点的最大度数没有限制，而二叉树结

点的最大度数为2； d g 树的结点无左、右之分，而二叉树的结点有

c l h j 左、右之分；

3. 树可采用孩子-兄弟链表（二叉链表）做存储

b 结构，目的并利用二叉树的已有算法解决树的有关

图6.9 问题。

4. 如图6.9所示

5. 2 k-1 、 2 k-1 、 2 k-2+1

6. n2+1

7. 2 i-1 2[log2n+1]-1 2[log2n+1] –1 8. 只有一个结点的树；空的二叉树

9. 5；如图6.10所示

c b a ab c a b c 图6.10 树形5种 b a c a b c 10. dgbaechif 、abdgcefhi 、gd …… 此处隐藏：1634字，全部文档内容请下载后查看。喜欢就下载吧 ……