选择题

1. （2分）在一棵二叉树中，若某节点的度为1，则该节点：{{ select(1) }}

• 一定有左孩子
• 一定有右孩子
• 至少有一个孩子
• 没有孩子

2. （2分）二叉树的后序遍历序列为LRN，则其对应的前序遍历序列为：{{ select(2) }}

• NLR
• NRL
• LNR
• RNL

3. （2分）一棵有n个节点的完全二叉树，其高度h为：{{ select(3) }}

• ⌊log₂n⌋
• ⌊log₂n⌋ + 1
• ⌈log₂(n+1)⌉
• ⌈log₂n⌉

4. （2分）以下哪种树结构最适合用于实现优先队列？{{ select(4) }}

• 二叉排序树
• 平衡二叉树
• 哈夫曼树
• 堆

5. （2分）线索二叉树中，若节点没有左孩子，则其左线索指向：{{ select(5) }}

• 前驱节点
• 后继节点
• 根节点
• 空

6. （2分）将一棵二叉树转换为森林时，以下说法正确的是：{{ select(6) }}

• 二叉树的右孩子对应森林中树的根节点
• 二叉树的左孩子对应森林中树的根节点
• 森林中树的数量等于二叉树的右链长度
• 森林中树的数量等于二叉树的左链长度

7. （2分）在二叉排序树中插入一个新节点时，新节点的位置一定是：{{ select(7) }}

• 根节点
• 叶子节点
• 度为1的节点
• 度为2的节点

8. （2分）一棵哈夫曼树共有23个节点，则其叶子节点数为：{{ select(8) }}

• 11
• 12
• 13
• 14

9. （2分）以下哪种遍历方式可以唯一确定一棵二叉树？{{ select(9) }}

• 前序遍历
• 中序遍历
• 后序遍历
• 前序+中序遍历

10. （2分）在树的孩子兄弟表示法中，每个节点存储的指针不包括：{{ select(10) }}

• 第一个孩子
• 下一个兄弟
• 父节点
• 以上都包括

11. （2分）平衡二叉树（AVL树）的平衡因子绝对值不能超过：{{ select(11) }}

• 0
• 1
• 2
• 3

12. （2分）一棵满二叉树的第k层有多少个节点？{{ select(12) }}

• 2^(k-1)
• 2^k - 1
• 2^k
• 2^(k+1) - 1

13. （2分）树的深度是指：{{ select(13) }}

• 树中节点的最大度数
• 树中节点的总数
• 树中叶子节点的数量
• 树中节点的最大层次

14. （2分）以下哪种数据结构不是树？{{ select(14) }}

• 堆
• 红黑树
• 图
• B树

15. （2分）构造哈夫曼树时，若有5个权值，则需要进行多少次合并操作？{{ select(15) }}

• 3
• 4
• 5
• 6