本书籍提供了丰富的树和二叉树相关习题,并附有详细的参考答案,特别适合学生自我检测和巩固数据结构知识。
树是一种特殊的数据结构,用于描述具有层次关系的集合数据。二叉树是每个节点最多有两个子节点的一种特殊的树形结构。
以下是关于树和二叉树的相关练习题及答案:
一、选择题
1. 由于在二叉树中每一个结点的最大度数为2,所以它是一种特殊类型的树。
答案:正确
2. 假设在一棵二叉树里双分支节点的数量是15个,单分支的节点数量有30个,则叶子节点的数量应该是16个。
答案:16
3. 根据定义,具有三个结点的不同形状的二叉树共有五种形式。
答案:5
4. 按照二叉树的规定,含有三个不同数据值的不同的结构有三十种。
答案:30
5. 一棵深度为5的完全二叉树至多包含31个节点。
答案:31
6. 对于高度为h且仅含度数为0或2结点的二叉树,其最少节点数量应是(2^h)-1。
答案:正确
7. 先序、中序和后序遍历序列中的叶子节点顺序不会改变。
答案:不发生改变
二、填空题
9. 若某二叉树的先根次序为 stuvw,中序遍历结果是 uwtvs,则此二叉树的后续访问顺序应为 wutsv。
10. 任何一棵非空完全二叉树在前序遍历时,每个结点总是出现在其子节点之前。
答案:正确
11. 某个二叉树的先根次序和中根次序分别为 abdgcefh 和 dgbaechf,则该树的后续访问顺序是 gdbehfca。
答案:gdbehfca
12. 在非空完全二叉树的中间遍历序列里,所有右子节点都位于其父结点之后。
答案:正确
13. 如图所示二叉树中序遍历时的结果为 dbaefcg。
答案:dbaefcg
14. 对于如题6.2展示的二叉树,其中序遍历顺序是 dgbaechf。
答案:dgbaechf
15.设 a,b 为一棵二叉树上的两个节点,在中根次序下 a 在 b 前面的前提条件是 a 是 b 的祖先。
答案:a 是 b 的祖先
16. 已知某棵二叉树的后续遍历序列是 dabec,中间顺序为 debac,则它的先序访问方式应为 decab。
答案:decab
17. 要实现任意一棵二叉树后根次序遍历而不使用栈结构的最佳策略是采用三重链表存储此树。
答案:正确
18. 如图6.3所示的4棵二叉树中,(D)不是完全二叉树。
19. 对于如题6.4展示的四棵树而言,只有(B)是一颗平衡二叉树。
20. 在线索化后的一棵二叉树里,结点t无左子节点时满足条件 t—>ltag=1 且 t—>left=NULL。
答案:正确
21. 经过适当的方法对任意一棵二叉树进行线索处理之后,每个节点都有指向其前驱和后继的指针。
答案:正确
22. 当一个二叉树满足任一结点值大于左子节点且小于右子节点时,则此结构被称为排序二叉树。
答案:正确