内容发布更新时间 : 2024/12/22 19:30:33星期一 下面是文章的全部内容请认真阅读。

习 题 六 树 和 二 叉 树

6.1 单项选择题

1. 如图8.7所示的4棵二叉树，_C___不是完全二叉树。

（A）（B）（C）（D）图8.7 4棵二叉树 2. 如图8.8所示的4棵二叉树，__B_是平衡二叉树。 （A）（B）（C）（D）图8.8 4棵二叉树

3. 在线索化二叉树中，t所指结点没有左子树的充要条件是B__。 A. t—＞left=NULL B. t—＞ltag=1 C. t—＞ltag=1且t—＞left=NULL D. 以上都不对

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

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

6. 由于二叉树中每个结点的度最大为2，所以二叉树是一种特殊的树，这种说法___B_。 A. 正确 B. 错误

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

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

8. 如图8.9所示二叉树的中序遍历序列___B_。

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

abcdgef图8.9 一棵二叉树

9. 已知某二叉树的后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是D____。

A. acbed B. decab C. deabc D. cedba

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

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

11. 假定在一棵二叉树中，双分支结点数为15，单分支结点数为30个，则叶子结点数为 个。B

A．15 B．16 C．17 D．47

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

A. bdgcefha B. gdbecfha C. bdgaechf D. gdbehfca

13. 二叉树为二叉排序树的充分必要条件是其任一结点的值均大于其左孩子的值、小于其右孩子的值。这种说法__B__。 A. 正确 B. 错误

14. 按照二叉树的定义，具有3个结点的二叉树有__C__种。 A. 3 B. 4 C. 5 D. 6 15. 一棵二叉树如图8.10所示，其中序遍历的序列为__B__。 A. abdgcefh B. dgbaechf C. gdbehfca D. abcdefgh abcdefg图8.10 一棵二叉树h

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

A. 树的先根遍历序列与其对应的二叉树的先序遍历序列相同