选择题

1. （2分）在二叉树中，度为0的节点（叶子节点）数为 $n_0$，度为2的节点数为 $n_2$，则它们之间的关系是：{{ select(1) }}

• $n_0 = n_2 + 1$
• $n_0 = n_2 - 1$
• $n_0 = n_2$
• 无法确定

2. （2分）一棵完全二叉树有100个节点，那么它的深度是：{{ select(2) }}

• 6
• 7
• 8
• 9

3. （2分）二叉树的前序遍历序列为ABCDEFG，中序遍历序列为CBDAEGF，则后序遍历序列为：{{ select(3) }}

• CDBGFEA
• CDBFGEA
• CDBAGFE
• CDBEGFA

4. （2分）若要从一个有 $n$ 个节点的二叉排序树中查找一个元素，最坏情况下的时间复杂度是：{{ select(4) }}

• $O(1)$
• $O(log n)$
• $O(n)$
• $O(n log n)$

5. （2分）在哈夫曼树中，权值最小的两个节点一定是：{{ select(5) }}

• 兄弟节点
• 父子节点
• 叶子节点
• 根节点

6. （2分）树的父亲表示法中，每个节点的存储内容不包括：{{ select(6) }}

• 节点的值
• 父节点的下标
• 子节点的下标
• 节点的层次

7. （2分）对于一棵满二叉树，若其深度为 $h$，则节点总数为：{{ select(7) }}

• $2^h - 1$
• $2^{h - 1}$
• $2^h$
• $2^{h + 1} - 1$

8. （2分）在二叉树的中序遍历中，根节点的位置是：{{ select(8) }}

• 第一个访问的节点
• 最后一个访问的节点
• 中间位置的节点
• 不确定，取决于树的结构

9. （2分）若二叉树的后序遍历序列为DABEC，中序遍历序列为DEBAC，则前序遍历序列为：{{ select(9) }}

• CEDBA
• DECAB
• DEABC
• CDEBA

10. （2分）完全二叉树的数组表示法中，根节点是1,若节点 $i$ 有左孩子，则左孩子的下标为：{{ select(10) }}

• $2i$
• $2i + 1$
• $2i - 1$
• $i + 1$

11. （2分）将森林转换为二叉树时，以下哪个操作是正确的？{{ select(11) }}

• 将各棵树的根节点视为兄弟节点
• 保留树的左孩子右兄弟表示法
• 仅保留第一棵树的结构
• 将所有节点按层次遍历顺序排列

12. （2分）线索二叉树中，线索的主要作用是：{{ select(12) }}

• 标识节点的度
• 指向节点的前驱或后继
• 存储节点的权值
• 区分左右孩子

13. （2分）平衡二叉树（AVL树）的平衡因子是指：{{ select(13) }}

• 左子树深度与右子树深度之差
• 节点的度数
• 树的高度
• 叶子节点的数量

14. （2分）树的深度优先遍历不包括以下哪种方式？{{ select(14) }}

• 前序遍历
• 中序遍历
• 后序遍历
• 层次遍历

15. （2分）构造哈夫曼树时，每次选择的两个节点是：{{ select(15) }}

• 权值最大的两个
• 权值最小的两个
• 度数最大的两个
• 度数最小的两个