一、单选题 8题（每题 5分，共 40分）

第 1 题

以下函数 createTree() 构造的树是什么类型？

{{ select(1) }}

• 满二叉树
• 完全二叉树
• 二叉排序树
• 其他都不对

---

第 2 题

已知二叉树的 中序遍历 是 [D, B, E, A, F, C]，先序遍历 是 [A, B, D, E, C, F]。请问该二叉树的后序遍历结果 是（ ）。

{{ select(2) }}

• [D, E, B, F, C, A]
• [D, B, E, F, C, A]
• [D, E, B, C, F, A]
• [B, D, E, F, C, A]

---

第 3 题

完全二叉树可以用数组连续高效存储，如果节点从 1 开始编号，则对有两个孩子节点的节点 i ，（ ）。

{{ select(3) }}

• 左孩子位于 2i ，右孩子位于 2i+1
• 完全二叉树的叶子节点可以出现在最后一层的任意位置
• 所有节点都有两个孩子
• 左孩子位于 2i+1 ，右孩子位于 2i+2

---

第 4 题

设有字符集 {a, b, c, d, e, f} ，其出现频率分别为 {5, 9, 12, 13, 16, 45} 。哈夫曼算法构造最优前缀编码，以下哪一组可能是对应的哈夫曼编码？（非叶子节点左边分支记作 0，右边分支记作 1，左右互换不影响 正确性）。

{{ select(4) }}

• a: 00；b: 01；c: 10；d: 110；e: 111；f: 0
• a: 1100；b: 1101；c: 100；d: 101；e: 111；f: 0
• a: 000；b: 001；c: 01；d: 10；e: 110；f: 111
• a: 10；b: 01；c: 100；d: 101；e: 111；f: 0

---

第 5 题

在二叉排序树（Binary Search Tree, BST）中查找元素 50 ，从根节点开始：若根值为 60 ，则下一步应去 搜索： {{ select(5) }}

• 左子树
• 右子树
• 随机
• 根节点

---

第 6 题

（ ）只有最底层的节点未被填满，且最底层节点尽量靠左填充。 {{ select(6) }}

• 完美二叉树
• 完全二叉树
• 完满二叉树
• 平衡二叉树

---

第 7 题

在使用数组表示完全二叉树时，如果一个节点的索引为 i（从 0 开始计数），那么其左子节点的索引通常是（ ）。 {{ select(7) }}

• (i-1)/2
• i+1
• i*2
• 2*i+1

---

第 8 题

3位格雷编码中，编码 101 之后的下一个编码不可能是（ ）。 {{ select(8) }}

• 100
• 111
• 110
• 001

---

二、判断题 5 题（每题 5分，共 25分）

第 1 题

哈夫曼编码是最优前缀码，且编码结果唯一。

{{ select(9) }}

• T
• F

---

第 2 题

一个含有100个节点的完全二叉树，高度为8 。

{{ select(10) }}

• T
• F

---

第 3 题

一棵有 n 个节点的二叉树一定有 n-1 条边。

{{ select(11) }}

• T
• F

---

第 4 题

给定一组字符及其出现的频率，构造出的哈夫曼树是唯一的。

{{ select(12) }}

• T
• F

---

第 5 题

对一棵二叉排序树进行中序遍历，可以得到一个递增的有序序列。

{{ select(13) }}

• T
• F

---