2023-2024-2期中卷

一	二	三	四	五	六	七	八	总分	阅卷人签名

---

一、简答题（本题 15 分，每小题各 5 分）

1. 循环不变式有三个性质：初始化、保持和终止。请问分别是什么含义？
2. 快速排序在不同的数据布局下表现如何？分析快速排序在最佳、平均和最坏情况下的时间复杂度，并讨论为什么快速排序在实际应用中通常优于其他 \(O(n \log n)\) 排序算法。
3. 基数排序和桶排序都是非比较型排序算法。比较这两种算法的工作原理，并讨论它们各自的适用情况、时间复杂度和是否具有稳定性。

二、算法复杂度分析（本题 5 分）

1. 解释为什么“算法 A 的运行时间至少是 \(O(n^2)\)”这一表述是无意义的。

三、排序与顺序统计量（本题 25 分，每小题各 5 分）

1. 在你所学的排序方法中，哪些排序方法是不稳定的？
2. 在算法 SELECT 中，输入元素被分为每组 5 个。如果被分为每组 3 个元素，SELECT 算法是否是线性的？请给出证明过程。
3. 对元素 \(\langle 62, 34, 53, 12, 8, 46, 22 \rangle\) 进行堆排序，输出一个最小的元素之后，剩下的堆是什么？请给出调整过程。
4. 说明在数组 \(B = \langle 20, 15, 30, 5, 10, 25, 40, 35, 12 \rangle\) 上执行 PARTITION 操作的过程，假定基准元素为最后一个元素。画出数组的变化情况。
5. 说明在数组 \(C = \langle 22, 15, 19, 1, 17, 13, 16, 5, 6 \rangle\) 上执行创建大顶堆的过程，并画出数组的变化情况。

四、数据结构（本题 25 分，每小题各 5 分）

1. 序列 \(\langle 17, 1, 18, 9, 25, 6 \rangle\)，画图表示该序列多数组、单数组表示的双向链表。
2. 按照 \(\{40, 72, 38, 35, 67, 51, 90, 8\}\) 建立一棵二叉搜索树，并给出插入过程。
3. 用开放寻址法将关键字 \(12, 27, 35, 19, 26, 44, 17, 16\) 插入到一个长度为 10 的散列表中。辅助散列函数为 \(h(k) = k \bmod 10\)。请用二次探查方法进行操作。
4. 假设一棵二叉搜索树的节点在 1 到 1000 之间，现在想要查找数值为 527 的节点，下面序列中哪些不是查找过的序列？

(1) \(501 \rightarrow 750 \rightarrow 600 \rightarrow 525 \rightarrow 530 \rightarrow 527\)

(2) \(1000 \rightarrow 900 \rightarrow 700 \rightarrow 550 \rightarrow 549 \rightarrow 527\)

(3) \(927 \rightarrow 202 \rightarrow 711 \rightarrow 298 \rightarrow 823 \rightarrow 527\)

(4) \(1000 \rightarrow 500 \rightarrow 750 \rightarrow 600 \rightarrow 530 \rightarrow 527\)

(5) \(500 \rightarrow 750 \rightarrow 1000 \rightarrow 800 \rightarrow 512 \rightarrow 527\)

1. 将关键字 \(42, 39, 29, 13, 28, 19, 8\) 连续插入一颗初始为空的红黑树之后，试着画出该红黑树。

五、动态规划（本题 15 分，每小题各 5 分）

1. 求 \(\langle 1, 0, 0, 1, 0, 1, 0, 1 \rangle\) 和 \(\langle 0, 1, 0, 1, 1, 0, 1, 1, 0 \rangle\) 的一个 LCS。
2. 对维数为序列 \(\langle 5, 10, 8, 20, 4 \rangle\) 的各矩阵，请用动态规划方法找出其矩阵乘积的一个最优加全部括号。
3. 假设有三种不同面额的硬币，分别为 1 元、3 元和 5 元，求组成总金额 10 元的所有可能的硬币组合数量。每种硬币的数量不限。

六、贪心算法（本题 15 分，每小题各 5 分）

1. 某本小说由全部 26 个字母（包括大小写）以及常用的 10 个标点符号写成。现采用固定长度方式进行编码，请问这种编码方式是否有可能空间最优的？请给出理由。
2. 假设某个字符串由 a-h 总共 8 个字母进行编码，其频率为：(a,100), (b, 50), (c, 10), (d, 80), (e, 20), (f, 30), (g, 15), (h, 40)。请构建赫夫曼树进行编码。
3. 假设某棵赫夫曼树如下所示。请说明各字母的编码分别是什么，再对二进制串 0000101011011110101011010100011 进行解码，如果末尾不充分，可以裁剪。