程序一：BST 综合

依次插入 5,2,8,1,3,7,9,6。完成第 1～6 题。

第 1 题

中序遍历是什么？

{{ input(1) }}

---

第 2 题

前序遍历是什么？

{{ input(2) }}

---

第 3 题

查找 6 的路径是什么？

{{ input(3) }}

---

第 4 题

树的深度是多少？

{{ input(4) }}

---

第 5 题

叶子结点共有多少个？

{{ input(5) }}

---

第 6 题

严格递增插入造成的主要问题是（ ）。

{{ select(6) }}

• 树退化成链
• 自动变成堆
• 中序不再有序
• 所有结点成为叶子

---

程序二：大根堆调整

1 下标堆数组为 20,15,18,8,10,12,17。完成第 7～12 题。

第 7 题

该数组是否满足大根堆？

{{ select(7) }}

• 是
• 否

---

第 8 题

删除根并完成下沉后的数组是什么？

{{ input(8) }}

---

第 9 题

向原堆插入 19 并完成上浮后的数组是什么？

{{ input(9) }}

---

第 10 题

编号 6 的父结点编号是多少？

{{ input(10) }}

---

第 11 题

原堆共有多少个叶子结点？

{{ input(11) }}

---

第 12 题

堆数组从左到右是否必须整体有序？

{{ select(12) }}

• 是
• 否

---

情境三：哈夫曼树

权值为 4,5,9,12,13。完成第 13～18 题。

第 13 题

第一次合并后的新权值是多少？

{{ input(13) }}

---

第 14 题

第二次合并后的新权值是多少？

{{ input(14) }}

---

第 15 题

WPL 是多少？

{{ input(15) }}

---

第 16 题

根结点权值是多少？

{{ input(16) }}

---

第 17 题

权值 4 的编码长度是多少？

{{ input(17) }}

---

第 18 题

当候选中出现相同权值时，不同取法可能（ ）。

{{ select(18) }}

• 改变最优 WPL
• 改变具体树形但不改变最优 WPL
• 使编码不再是前缀码
• 使算法死循环

---

情境四：贪心判断

结合活动选择、硬币和哈夫曼完成第 19～24 题。

第 19 题

活动 (1,4),(3,5),(0,6),(5,7),(3,9),(8,11),(12,16) 按结束时间贪心，最多选几个？

{{ input(19) }}

---

第 20 题

第一个选择的活动是哪个？

{{ input(20) }}

---

第 21 题

选择 (5,7) 后，下一个被选择的活动是哪个？

{{ input(21) }}

---

第 22 题

面额 1,3,4 用最大面额贪心凑 6，需要几枚？

{{ input(22) }}

---

第 23 题

上述硬币问题的最优解需要几枚？

{{ input(23) }}

---

第 24 题

下列说法正确的是（ ）。

{{ select(24) }}

• 看到最值就一定能贪心
• 贪心必须有正确性依据，哈夫曼的局部选择经过证明
• 所有排序后扫描都是贪心
• 贪心一定优于动态规划

---