# 算法基础期中题库 · 文字与 LaTeX 公式 题目按原卷转写，答案依据配套答案整理并注明修正。 ## 2023 年 · 判断题 第 1 题 出处：2023 年秋季学期算法基础期中考试，试卷第 1 页；答案卷第 1 页起。 ### 题目 递归式 $T(n)=4T(n/4)+n\lg n$ 的解满足 $T(n)=\Theta(n^2\lg n)$。 ### 参考答案（整理版） **F，错误。** 主定理中 $n^{\log_4 4}=n$，而 $f(n)=n\lg n$，所以 $T(n)=\Theta(n\lg^2 n)$。 --- ## 2023 年 · 判断题 第 2 题 出处：2023 年秋季学期算法基础期中考试，试卷第 1 页；答案卷第 1 页起。 ### 题目 堆排序和快速排序都是渐近最优的比较排序算法，它们在最坏情况下都需要做 $O(n\lg n)$ 次比较。 ### 参考答案（整理版） **F，错误。** 快速排序在最坏情况下需要 $\Theta(n^2)$ 次比较，堆排序的最坏时间复杂度为 $\Theta(n\lg n)$。 --- ## 2023 年 · 判断题 第 3 题 出处：2023 年秋季学期算法基础期中考试，试卷第 1 页；答案卷第 1 页起。 ### 题目 选择排序的时间复杂度与输入数据的初始排列有关。 ### 参考答案（整理版） **F，错误。** 标准选择排序无论输入初始排列如何，都要进行 $n(n-1)/2$ 次关键字比较，时间复杂度为 $\Theta(n^2)$。 --- ## 2023 年 · 判断题 第 4 题 出处：2023 年秋季学期算法基础期中考试，试卷第 2 页；答案卷第 1 页起。 ### 题目 在使用 RANDOMIZED-SELECT 算法选择第 $k$ 大的元素时，算法的期望运行时间是线性的。 ### 参考答案（整理版） **T，正确。** 随机化选择每次划分后只递归处理一侧，期望运行时间为 $\Theta(n)$；最坏情况仍可能为 $\Theta(n^2)$。 --- ## 2023 年 · 判断题 第 5 题 出处：2023 年秋季学期算法基础期中考试，试卷第 2 页；答案卷第 1 页起。 ### 题目 可以使用基于比较的算法，以 $O(n)$ 的最坏时间复杂度将二叉堆转换为二叉搜索树。 ### 参考答案（整理版） **F，错误。** 假设存在这样的算法，则可先用 $O(n)$ 时间将任意数组建堆，再转换为二叉搜索树，最后中序遍历得到排序结果，总时间为 $O(n)$，与比较排序的 $\Omega(n\lg n)$ 最坏下界矛盾。 --- ## 2023 年 · 判断题 第 6 题 出处：2023 年秋季学期算法基础期中考试，试卷第 2 页；答案卷第 1 页起。 ### 题目 如果把一棵红黑树除根节点和叶子节点外所有节点的颜色反转后，所得到的仍是合法的红黑树，那么任意一个节点的左右子树节点数相等。 ### 参考答案（整理版） **T，正确。** 原树不能有相邻红节点；反色后的树也不能有相邻红节点，因此非根内部节点之间也不能相邻为黑。内部节点颜色必须逐层交替。结合每条根到 NIL 路径黑节点数相同，可得所有 NIL 叶子深度相同，树为完美二叉树，各节点左右子树节点数相等。 --- ## 2023 年 · 简答题 第 1 题 出处：2023 年秋季学期算法基础期中考试，试卷第 2 页；答案卷第 2 页起。 ### 题目 对于递归式 $$T(n)=T(2n/3)+2^{\lceil\lg n\rceil},$$ 给出 $T(n)$ 的一个渐近紧确界。 注：$2^{\lg n}=n$。 ### 参考答案（整理版） 由 $\lg n\le\lceil\lg n\rceil<\lg n+1$ 可得 $$n\le 2^{\lceil\lg n\rceil}<2n.$$ 因此非递归代价为 $\Theta(n)$。用 $F(n)=F(2n/3)+n$ 和 $G(n)=G(2n/3)+2n$ 夹逼，二者均为 $\Theta(n)$，所以 $$T(n)=\Theta(n).$$ --- ## 2023 年 · 简答题 第 2 题 出处：2023 年秋季学期算法基础期中考试，试卷第 3 页；答案卷第 2 页起。 ### 题目 补全算法 Randomized-Quicksort（$A$ 为数组）的伪代码，并分析 Randomized-Quicksort$(A,1,n)$（$n=A.\mathrm{length}$）运行过程中，在最坏和最好情况下，Randomized-Quicksort 分别被调用了多少次？以 $\Theta$ 符号形式给出答案。 ```text PARTITION(A, p, r) x = A[r] i = ____ for j = p to ____ if ____ i = i + 1 swap(A[i], A[j]) swap(A[i + 1], A[r]) return i + 1 RANDOMIZED-PARTITION(A, p, r) i = RANDOM(p, r) swap(A[r], A[i]) return PARTITION(A, p, r) RANDOMIZED-QUICKSORT(A, p, r) if ____ q = RANDOMIZED-PARTITION(A, p, r) RANDOMIZED-QUICKSORT(A, p, ____) RANDOMIZED-QUICKSORT(A, ____, r) ``` ### 参考答案（整理版） 依次填入：$p-1$、$r-1$、$A[j]\le x$、$p 0 r = r - 1 else l = l + 1 return False ``` 若和大于 $0$，则当前右端值不可能与剩余任何值组成零和，应缩小右端；若和小于 $0$，同理增大左端。条件 $lm$）的数列 $Z$，其每个元素由 $Z_i=X_i+Y_i$ 生成，其中 $$X_i\in\left\{0,\frac1m,\frac2m,\ldots,\frac{m-1}{m}\right\}$$ 离散均匀取值，$Y_i$ 在 $(0,1/n)$ 上连续均匀取值，所有 $X_i,Y_i$ 均独立。 请设计一个桶排序算法，以 $O(n)$ 的期望时间复杂度对 $Z$ 排序。只需简述算法流程，不需要证明时间复杂度。 提示：应设计 $\Theta(n)$ 个桶，尽可能均匀地分配元素。 ### 参考答案（整理版） **(a)** 以 $n$ 为基做稳定基数排序。关键字最大为 $n^2=(100)_n$，因此至多 $3$ 位，每一位用计数排序，代价为 $\Theta(n+n)$。总时间为 $\Theta(3n)=\Theta(n)$。 **(b)** 由于 $Y_i<1/n<1/m$，可还原 $$x=\lfloor mZ_i\rfloor,\qquad Y_i=Z_i-\frac{x}{m}.$$ 建立 $m$ 个大桶，每个大桶再分 $n$ 个小桶。将 $Z_i$ 放入编号为 $(x,y)$ 的桶，其中 $$y=\left\lfloor n^2\left(Z_i-\frac{x}{m}\right)\right\rfloor.$$ 桶 $(x,y)$ 对应半开区间 $[x/m+y/n^2,\ x/m+(y+1)/n^2)$；小桶边界用半开区间实现以覆盖所有值。总桶数 $mn=\Theta(n)$，因为 $m$ 是常数。每桶内部用插入排序，最后按大桶、小桶顺序串联。各桶等概率，故期望总时间为 $O(n)$。 --- ## 2023 年 · 综合题 第 2 题 出处：2023 年秋季学期算法基础期中考试，试卷第 6 页；答案卷第 8 页起。 ### 题目 二叉搜索树在最坏情况下仍需 $O(n)$ 时间完成一次搜索，因此需要引入平衡二叉搜索树。AVL 树要求每个结点左右子树的高度差不超过 $1$。 维护 `height[x]` 表示结点高度，平衡因子 `BF[x]` 为左子树高度减右子树高度；取 $0,1,-1$ 时，分别表示等高、左高、右高。 **(a)** 已知某结点 $x'$ 满足 $\mathrm{BF}[\mathrm{left}[x']]=0$，$\mathrm{BF}[\mathrm{right}[x']]=1$，求 $\mathrm{BF}[x']$ 的可能值。 **(b)** 证明：有 $n$ 个结点的 AVL 树高度为 $O(\lg n)$。 **(c)** 插入结点后，某些结点的平衡因子可能为 $2$ 或 $-2$。补全 AVL-Balance$(x)$：输入以 $x$ 为根且左右子树都高度平衡的子树，将其恢复平衡并返回调整后的根；无需调整则返回 $x$。 ```text AVL-BALANCE(x) if |BF[x]| <= 1 return x else if ____ y = ____ if ____ LEFT-ROTATE(y) return ____ else ____ if ____ ____ return ____ ``` ### 参考答案（整理版） **(a)** 可能为 $-1,0,1$。仅知道两个孩子自身的平衡因子，不能确定两个孩子的绝对高度。 **(b)** 令 $N(h)$ 为高度 $h$ 的 AVL 树的最少结点数，取空树高度为 $-1$。有 $$N(-1)=0,\quad N(0)=1,$$ $$N(h)=1+N(h-1)+N(h-2).$$ 该递推按斐波那契速度增长，即 $N(h)=\Omega(\varphi^h)$，$\varphi=(1+\sqrt5)/2$。因此 $n\ge N(h)$ 蕴含 $h=O(\lg n)$。 **(c)** ```text AVL-BALANCE(x) if |BF[x]| <= 1 return x else if BF[x] == 2 y = left[x] if height[left[y]] < height[right[y]] LEFT-ROTATE(y) return RIGHT-ROTATE(x) else y = right[x] if height[left[y]] > height[right[y]] RIGHT-ROTATE(y) return LEFT-ROTATE(x) ``` 旋转操作应同步维护父子指针和受影响结点的高度。 --- ## 2023 年 · 附加题 第 1 题 出处：2023 年秋季学期算法基础期中考试，试卷第 7 页；答案卷第 9 页起。 ### 题目 小花不刷题时能够考 $S$ 分。《算法导论》共有 $n$ 道题，刷第 $i$ 题能使分数提升 $s_i$（$s_i\ge0$）。若一共刷了 $k$ 道题，则因疲劳损失 $\alpha k$ 分（$\alpha\ge0$）。 她只会从某一题开始，按顺序刷连续的若干题，不跳题、不倒序、不重复。若希望最终分数落入 $[l,r]$，有多少种刷题方案？ 设计一个最坏时间复杂度为 $O(n\lg n)$ 的算法。分数不一定是 $0\sim100$ 的整数，因此不能使用计数排序等限制数据范围的方法。 ### 参考答案（整理版） 定义前缀量 $D_0=0$，以及 $$D_k=\sum_{i=1}^{k}s_i-\alpha k.$$ 刷题范围为 $(x,y]$ 时，最终得分为 $S+D_y-D_x$。于是问题转为统计 $$0\le x1/(a+b)$，则对充分大的 $n$，后两项之和非正。放大常数并处理有限个基例，得 $T(n)=O((\lg n)^2)$。 本题在答案卷中位于“简答题第 3 题”，已按题目内容配对。 --- ## 2024 年 · 简答题 第 2 题 出处：2024 年秋季学期算法基础期中考试，试卷第 3 页；答案卷第 2 页起。 ### 题目 有 $n$ 个木块，大小为 $a_1,\ldots,a_n$；另有 $m$ 个大小为 $V$ 的容器。一个容器“被填满”当且仅当其中放入两个木块 $a_i,a_j$，且 $a_i+a_j\le V$。每个木块只能使用一次。 请给出 $O(n\log n)$ 时间的算法，判断是否存在分配方案，使得这 $m$ 个容器都被填满。给出伪代码，说明原理；只输出是或否，不需要输出方案。 ### 参考答案（整理版） 按原答案的排序与配对思路，可写成更简洁的双指针实现： ```text CAN-FILL(a, n, m, V) sort a in nondecreasing order l = 1 r = n pairs = 0 while l < r if a[l] + a[r] <= V pairs = pairs + 1 l = l + 1 r = r - 1 else r = r - 1 return pairs >= m ``` 若最小与最大木块之和大于 $V$，最大木块与任何剩余木块都不兼容，可舍弃。否则将它们配成一对不会降低最优配对数：在任意最优解中，通过交换伙伴可使这两个木块配对，而其余被替换的较小木块仍然兼容。 排序为 $O(n\log n)$，扫描为 $O(n)$，总时间 $O(n\log n)$。对应答案卷“简答题第 1 题”。 --- ## 2024 年 · 简答题 第 3 题 出处：2024 年秋季学期算法基础期中考试，试卷第 3 页；答案卷第 2 页起。 ### 题目 扩张红黑树，使其能以 $O(1)$ 时间给出动态数集 $Q$ 中两个最接近的数之间的差值 MIN-GAP。 例如 $Q=\{1,5,9,15,18,22\}$ 时，返回 $18-15=3$。写出数据结构，并说明 MIN-GAP 如何计算。 ### 参考答案（整理版） 以集合元素为红黑树关键字。在每个结点 $x$ 维护：子树最小值 $x.\mathrm{min}$、最大值 $x.\mathrm{max}$、最小相邻差 $x.\mathrm{gap}$。 设左右孩子分别为 $L,R$，则 $x.\mathrm{gap}$ 为以下有效候选的最小值： - $L.\mathrm{gap}$，$R.\mathrm{gap}$； - 当 $L$ 非空时，$x.\mathrm{key}-L.\mathrm{max}$； - 当 $R$ 非空时，$R.\mathrm{min}-x.\mathrm{key}$。 空子树及不足两个元素的子树，其最小差取 $+\infty$。最小值、最大值也可由左右子树在 $O(1)$ 时间合并得到。 插入、删除和旋转后维护这些属性，更新仍为 $O(\log n)$。根结点的 `gap` 就是全局最小差，查询为 $O(1)$。对应答案卷“简答题第 2 题”。 --- ## 2024 年 · 简答题 第 4 题 出处：2024 年秋季学期算法基础期中考试，试卷第 4 页；答案卷第 3 页起。 ### 题目 对于下图所给的斐波那契堆，黑色节点表示结点的 `mark` 属性为 `true`： 1. 抽取最小结点，画出操作后的最终结果，需要考虑 CONSOLIDATE（合并）操作。 2. 在第 1 问的基础上，把关键字 $35$ 减为 $4$，画出操作后的最终结果，需要考虑 CASCADING-CUT（级联切断）操作。 ![原卷结构图](../assets/2024-heap-question.webp) ### 参考答案（整理版） **第 1 问：抽取最小结点。** 将最小结点的孩子加入根链表，删除最小结点，再反复合并度数相同的根。合并时较小关键字成为父节点，最后更新最小指针。 ![抽取最小结点](../assets/2024-heap-answer1.webp) **第 2 问：降低关键字。** 将 $35$ 改为 $4$。若它小于父节点，则切断并加入根链表；对原父节点执行级联切断：未标记的非根结点先置标记，已标记的非根结点继续切断。移到根链表的结点清除标记，再更新最小指针。 ![降低关键字](../assets/2024-heap-answer2.webp) 上图保留配套答案中的结构示意。根链表顺序及同度根的合并顺序可以不同，应核对堆序、父子关系、度数、标记和最小指针。 --- ## 2024 年 · 综合题 第 1 题 出处：2024 年秋季学期算法基础期中考试，试卷第 5 页；答案卷第 6 页起。 ### 题目 **快速排序** **(a)** 不对整个数组排序，而只确定一个含 $n$ 个元素的数列的第 $m$ 小元素。修改快速排序，避免完整排序的额外操作。根据下面的 QUICKSORT 和 PARTITION，填写 QuickSelect$(\mathrm{arr},\mathrm{low},\mathrm{high},m)$。 ```text QUICKSORT(arr, low, high) if low < high pivotIndex = PARTITION(arr, low, high) QUICKSORT(arr, low, pivotIndex - 1) QUICKSORT(arr, pivotIndex + 1, high) PARTITION(arr, low, high) pivot = arr[high] i = low - 1 for j = low to high - 1 if arr[j] <= pivot i = i + 1 SWAP(arr[i], arr[j]) SWAP(arr[i + 1], arr[high]) return i + 1 QuickSelect(arr, low, high, m) // 在此补全算法 ``` **(b)** 给出 QuickSelect 平均键码比较次数 $C_{n,m}$ 的递推表达式。 **(c)** 当 $m=1$ 时，计算 $C_{n,1}$。 ### 参考答案（整理版） **(a)** 只递归处理含目标秩的那一侧。 ```text QUICKSELECT(arr, low, high, m) if low == high return arr[low] pivotIndex = PARTITION(arr, low, high) k = pivotIndex - low + 1 if m == k return arr[pivotIndex] else if m < k return QUICKSELECT(arr, low, pivotIndex - 1, m) else return QUICKSELECT(arr, pivotIndex + 1, high, m - k) ``` **(b)** 假设枢轴的秩等概率分布。按题给 PARTITION，每次划分做 $n-1$ 次关键字比较，因此 $C_{1,1}=0$，且 $$\begin{aligned} C_{n,m}=n-1+\frac1n\Bigg(&\sum_{s=1}^{m-1}C_{n-s,m-s}\\ &+\sum_{s=m+1}^{n}C_{s-1,m}\Bigg). \end{aligned}$$ **(c)** 令 $C_n=C_{n,1}$，则 $$C_n=n-1+\frac1n\sum_{s=1}^{n-1}C_s.$$ 将 $nC_n$ 与 $(n-1)C_{n-1}$ 相减，得到 $C_n-C_{n-1}=2-2/n$。从 $C_1=0$ 累加可得 $$C_{n,1}=2n-2H_n,$$ 其中 $H_n=\sum_{j=1}^{n}1/j$。 **原答案差异：** 原答案写了划分代价 $n+1$，并给出 $2n-2$；该结果与它自己的递推在小规模基例处也不一致。这里明确采用题给伪代码的“关键字比较次数”口径，原文仍可在原卷中核对。 --- ## 2024 年 · 综合题 第 2 题 出处：2024 年秋季学期算法基础期中考试，试卷第 6 页；答案卷第 8 页起。 ### 题目 二叉搜索树在最坏情况下仍需 $O(n)$ 时间搜索。Treap 是二叉搜索树（tree）与最小堆（heap）的组合：每个结点 $x$ 有互异的关键字 $x.\mathrm{key}$ 和互异的优先级 $x.\mathrm{priority}$，满足： - 若 $v$ 是 $u$ 的左孩子，则 $v.\mathrm{key}u.\mathrm{key}$； - 若 $v$ 是 $u$ 的孩子，则 $v.\mathrm{priority}>u.\mathrm{priority}$。 **(a)** 给定结点集合 $\{(x_i.\mathrm{key},x_i.\mathrm{priority})\mid1\le i\le n\}$，有多少棵不同的 Treap 能表示这个集合？ **(b)** 给出 Treap-Insert$(T,x)$ 的伪代码，可调用 Left-Rotate 和 Right-Rotate。 **(c)** 假设优先级独立且均匀分布，求 $n$ 结点 Treap 中叶子结点数的期望 $E(n)$。 ### 参考答案（整理版） **(a)** 恰有 $1$ 棵。优先级最小的结点必须为根；关键字将其余结点唯一地分到左右子树，再递归应用相同结论。 **(b)** ```text TREAP-INSERT(T, x) if T == NIL return x // x 的左右孩子初始化为 NIL if x.key < T.key T.left = TREAP-INSERT(T.left, x) if T.left.priority < T.priority T = RIGHT-ROTATE(T) else T.right = TREAP-INSERT(T.right, x) if T.right.priority < T.priority T = LEFT-ROTATE(T) return T ``` **(c)** 根的关键字秩均匀分布。对 $n\ge2$，有 $$E(n)=\frac1n\sum_{k=0}^{n-1}[E(k)+E(n-1-k)].$$ 基例 $E(0)=0$、$E(1)=1$。代入并归纳可得 $$E(n)=\begin{cases}0,&n=0,\\1,&n=1,\\(n+1)/3,&n\ge2.\end{cases}$$ --- ## 2024 年 · 附加题 第 1 题 出处：2024 年秋季学期算法基础期中考试，试卷第 7 页；答案卷第 9 页起。 ### 题目 小迪提出股票“价值区间”分析法。给定价格序列 $a=[a_0,a_1,\ldots,a_{n-1}]$（$a_i>0$），区间大小 $W$ 和价值差 $A$；若存在 $0\le i= W erase buckets[floor(a[i - W] / width)] return False ``` 处理当前值前，桶中包含前面距离不超过 $W$ 的值。若尚未找到合法对，一个桶至多保存一个候选值，因此移除过期值不会覆盖仍需保留的同桶值。 **实数价格的条件：** 题干未规定整数。若 $A>0$ 为实数，可把桶宽改为 $A$，同桶差严格小于 $A$，相邻桶仍逐个检查；若 $A=0$，改用窗口内精确值的哈希判重。 假设哈希操作期望为 $O(1)$，总期望时间 $O(n)$，空间 $O(\min(n,W))$。一般哈希表不保证最坏线性时间。 --- ## 2025 年 · 判断题 第 1 题 出处：2025 年秋季学期算法基础期中考试，试卷第 1 页；答案卷第 1 页起。 ### 题目 递归式 $T(n)=2T(2n/3)+n\log n$ 的解满足 $T(n)=\Theta(n^2)$。 ### 参考答案（整理版） **F，错误。** 主定理给出 $T(n)=\Theta(n^{\log_{3/2}2})$，因为 $\log_{3/2}2>1$，$n\log n$ 比该幂函数多项式级地小。 --- ## 2025 年 · 判断题 第 2 题 出处：2025 年秋季学期算法基础期中考试，试卷第 1 页；答案卷第 1 页起。 ### 题目 记 $\sigma(n)$ 表示数字 $n$ 的因子个数，例如 $\sigma(6)=4$，因为 $1,2,3,6$ 都是 $6$ 的因子。那么 $\sum_{i=1}^{n}\sigma(i)$ 是 $\Theta(n\sqrt n)$ 的。 ### 参考答案（整理版） **F，错误。** 按因子计数可得 $\sum_{i=1}^{n}\sigma(i)=\sum_{d=1}^{n}\lfloor n/d\rfloor$。利用调和级数，上下界分别为 $nH_n-n$ 和 $nH_n$，所以结果是 $\Theta(n\log n)$。 --- ## 2025 年 · 判断题 第 3 题 出处：2025 年秋季学期算法基础期中考试，试卷第 1 页；答案卷第 1 页起。 ### 题目 归并排序是稳定的，其时间复杂度在任何情况下都一定是 $\Theta(n\log n)$。 ### 参考答案（整理版） **T，正确。** 对标准归并排序，稳定归并保证稳定性，每层合并代价为 $\Theta(n)$，递归层数为 $\Theta(\log n)$。这里采用课程中标准实现的约定。 --- ## 2025 年 · 判断题 第 4 题 出处：2025 年秋季学期算法基础期中考试，试卷第 2 页；答案卷第 1 页起。 ### 题目 计数排序（Counting Sort）的空间复杂度是 $O(1)$。 ### 参考答案（整理版） **F，错误。** 标准稳定计数排序需要计数数组和输出数组，辅助空间为 $O(n+k)$，其中 $k$ 为关键字范围大小。 --- ## 2025 年 · 判断题 第 5 题 出处：2025 年秋季学期算法基础期中考试，试卷第 2 页；答案卷第 1 页起。 ### 题目 某二叉树的前序、中序、后序遍历中，任意给定两项，都可以唯一确定第三项。 ### 参考答案（整理版） **F，错误。** 即使结点互异，前序和后序也不能唯一确定中序。例如前序为 $[1,2]$、后序为 $[2,1]$ 时，结点 $2$ 可以是根的左孩子，也可以是右孩子。 --- ## 2025 年 · 判断题 第 6 题 出处：2025 年秋季学期算法基础期中考试，试卷第 2 页；答案卷第 1 页起。 ### 题目 对于一棵黑高为 $h$ 的红黑树，其内部节点（也就是有键值的点）的数量至多是 $2^{h+1}-1$。 ### 参考答案（整理版） **F，错误。** 在课程使用的黑高约定下，黑红逐层交替的满二叉树可有 $2^{2h}-1$ 个内部节点，超过题目给出的界。 --- ## 2025 年 · 简答题 第 1 题 出处：2025 年秋季学期算法基础期中考试，试卷第 2 页；答案卷第 2 页起。 ### 题目 对于递归式 $$T(n)=2T\!\left(\frac n2\right)+\frac{n}{\log_2 n},$$ 请给出渐近确界。 ### 参考答案（整理版） 这里 $\log_2 n$ 表示以 $2$ 为底的对数。令 $n=2^k$，并令常数规模的递归终止代价为 $\Theta(1)$。 递归树第 $i$ 层的总非递归代价为 $n/(k-i)$，所以 $$\begin{aligned} T(n)&=\Theta(n)+n\sum_{i=0}^{k-1}\frac1{k-i}\\ &=\Theta(n)+nH_k\\ &=\Theta(n\log\log n). \end{aligned}$$ 其中 $H_k=\Theta(\log k)$。一般 $n$ 的上下界可用相邻的 $2$ 的幂夹逼。课程给出的主定理版本不能直接覆盖 $f(n)=n/\log n$ 这一情形。 --- ## 2025 年 · 简答题 第 2 题 出处：2025 年秋季学期算法基础期中考试，试卷第 3 页；答案卷第 2 页起。 ### 题目 有一排共 $n$ 桶染料，每桶颜色用 $[1,n]$ 之间的一个数字表示。画家小 S 想至少使用 $k$ 种颜色，但只能使用连续的若干桶染料。 求满足至少 $k$ 种颜色要求时，最少需要使用多少桶。给出伪代码并说明原理，时间复杂度要求为 $O(n)$。不需要考虑无解情况。 ### 参考答案（整理版） 用双指针维护窗口 $[\mathrm{left},\mathrm{right}]$，用 `counts` 记录每种颜色的出现次数，`total` 记录不同颜色数。右端点扩展到满足要求后，反复收缩左端并更新最小长度。 ```text SHORTEST-K-COLORS(colors, k) n = length(colors) counts[1..n] = 0 left = 1 total = 0 answer = n for right = 1 to n c = colors[right] if counts[c] == 0 total = total + 1 counts[c] = counts[c] + 1 while total >= k answer = min(answer, right - left + 1) c = colors[left] counts[c] = counts[c] - 1 if counts[c] == 0 total = total - 1 left = left + 1 return answer ``` 每个元素最多进入和离开窗口各一次，时间复杂度为 $O(n)$，计数数组空间为 $O(n)$。该写法与原解的“先扩右端，再移左端”窗口思路等价，采用通常的 $1\le k\le n$ 约定。 --- ## 2025 年 · 简答题 第 3 题 出处：2025 年秋季学期算法基础期中考试，试卷第 3 页；答案卷第 3 页起。 ### 题目 在一个区间集合中，被最多数量区间覆盖的点称为最大重叠点，且它一定可以是某个区间的端点。 简述一种数据结构，使其支持对动态区间集合查询最大重叠点（返回任意符合要求的端点即可），并分析各操作的时间复杂度。 提示：可将左端点关联 $+1$ 值，右端点关联 $-1$ 值。 ### 参考答案（整理版） 以端点为关键字建立扩张红黑树。左端点权重为 $+1$，右端点权重为 $-1$；扫描前缀权重和就是覆盖数。 每个结点维护子树权重和 `sum`、最大非空前缀和 `max_prefix` 及其位置 `argmax`。设左右孩子为 $L,R$，当前权重为 $w$，则 $$\mathrm{sum}(x)=\mathrm{sum}(L)+w+\mathrm{sum}(R).$$ 最大前缀和取以下有效候选的最大值： 1. $\mathrm{max\_prefix}(L)$； 2. $\mathrm{sum}(L)+w$； 3. $\mathrm{sum}(L)+w+\mathrm{max\_prefix}(R)$。 同时保存最大值对应的端点。空子树的 `sum` 设为 $0$，其非空前缀候选忽略。 插入或删除一个区间，需插入或删除两个端点，沿路径及旋转时每结点用 $O(1)$ 时间重算属性，总时间 $O(\log n)$；查询根的 `argmax`，时间 $O(1)$。 若为闭区间且坐标相同，必须先处理左端点再处理右端点；同类端点再用唯一编号区分，以正确处理重复端点。 --- ## 2025 年 · 简答题 第 4 题 出处：2025 年秋季学期算法基础期中考试，试卷第 4 页；答案卷第 4 页起。 ### 题目 对于下图所给的斐波那契堆，黑色节点表示结点的 `mark` 属性为 `true`： 1. 抽取最小结点，画出操作后的最终结果，需要考虑 CONSOLIDATE（合并）操作。 2. 在第 1 问的基础上，把关键字 $30$ 减为 $4$，画出操作后的最终结果，需要考虑 CASCADING-CUT（级联切断）操作。 ![原卷结构图](../assets/2025-heap-question.webp) ### 参考答案（整理版） **第 1 问：抽取最小结点。** 将最小结点的孩子加入根链表，删除最小结点，再反复合并度数相同的根。合并时较小关键字成为父节点，最后更新最小指针。 ![抽取最小结点](../assets/2025-heap-answer1.webp) **第 2 问：降低关键字。** 将 $30$ 改为 $4$。若它小于父节点，则切断并加入根链表；对原父节点执行级联切断：未标记的非根结点先置标记，已标记的非根结点继续切断。移到根链表的结点清除标记，再更新最小指针。 ![降低关键字](../assets/2025-heap-answer2.webp) 上图保留配套答案中的结构示意。根链表顺序及同度根的合并顺序可以不同，应核对堆序、父子关系、度数、标记和最小指针。 --- ## 2025 年 · 综合题 第 1 题 出处：2025 年秋季学期算法基础期中考试，试卷第 5 页；答案卷第 5 页起。 ### 题目 **线性排序算法** **(a)** 基数排序（Radix Sort）的正确性依赖稳定的子排序算法。使用计数排序（Counting Sort）作为稳定子排序算法，写出 COUNTING-SORT$(A,m)$ 的伪代码，对数组 $A$ 中的 $n$ 个元素排序，每个元素均为不大于 $m$ 的非负整数。 原题文字处写作 COUNTING-SORT$(A,d)$，其后算法标题及关键字范围使用 $m$；这里按算法标题统一参数。 **(b)** 待排序的 $n$ 个元素各有 $d$ 位数字，每一位可取 $0$ 至 $k-1$ 中任一值，推导 RADIX-SORT 总时间复杂度。 **(c)** 对 $b$ 位二进制数，不按单比特排序，而将其分成 $d=\lceil b/r\rceil$ 组，每组至多 $r$ 位（$r\le b$），逐组用计数排序。总时间复杂度 $T(n,b,r)$ 是多少？ ### 参考答案（整理版） **(a)** ```text COUNTING-SORT(A, m) n = length(A) let B[1..n] be a new array let C[0..m] be a new array for i = 0 to m C[i] = 0 for j = 1 to n C[A[j]] = C[A[j]] + 1 for i = 1 to m C[i] = C[i] + C[i - 1] for j = n downto 1 B[C[A[j]]] = A[j] C[A[j]] = C[A[j]] - 1 return B ``` 逆序遍历输入数组写入输出，保证相同关键字的相对次序不变，因此稳定。 **(b)** 每一位的计数排序为 $\Theta(n+k)$，共 $d$ 位，故 $$T=\Theta\bigl(d(n+k)\bigr).$$ **(c)** 每组最多 $r$ 位，关键字范围大小为 $2^r$，组数为 $\lceil b/r\rceil$，所以 $$T(n,b,r)=\Theta\!\left(\left\lceil\frac br\right\rceil(n+2^r)\right).$$ --- ## 2025 年 · 综合题 第 2 题 出处：2025 年秋季学期算法基础期中考试，试卷第 6 页；答案卷第 6 页起。 ### 题目 标准二叉搜索树可支持 Search、Insert 和 Delete，但无法高效回答“第 $i$ 小的关键字是什么”或“关键字 $x$ 的排名是多少”。 顺序统计树（Order-Statistic Tree，OST）在每个结点 $x$ 中维护 $x.\mathrm{size}$，表示以 $x$ 为根的子树结点总数，包含 $x$ 自身。NIL 的 `size` 为 $0$。OS-Select$(x,i)$ 返回该子树中第 $i$ 小的结点。 **(a)** 某结点满足 $x.\mathrm{left}.\mathrm{size}=3$，$x.\mathrm{right}.\mathrm{size}=5$： 1. 计算 $x.\mathrm{size}$。 2. OS-Select$(x,4)$ 返回哪个结点？说明理由。 **(b)** 写出 OS-Select$(x,i)$ 的伪代码。若 $1\le i\le x.\mathrm{size}$，返回对应结点，否则返回 NIL。 **(c)** 关键字 $1,2,\ldots,n$ 按均匀随机排列依次插入，构造 OST。令 $D_i$ 为第 $i$ 小关键字结点的深度，根深度为 $0$。 1. 证明 $$\mathbb E[D_i]=H_i+H_{n-i+1}-2.$$ 提示：$H_k=\sum_{j=1}^{k}1/j$，且 $\ln(k+1)\le H_k\le1+\ln k$。 2. 利用上式，推导 OS-Select$(T.\mathrm{root},i)$ 的时间复杂度。 ### 参考答案（整理版） **(a)** $x.\mathrm{size}=3+5+1=9$。$x$ 的子树内排名为左子树大小加 $1$，即 $4$，故 OS-Select$(x,4)$ 返回 $x$ 自身。 **(b)** ```text OS-SELECT(x, i) if x == NIL return NIL if i < 1 or i > x.size return NIL r = x.left.size + 1 // NIL.size = 0 if i == r return x else if i < r return OS-SELECT(x.left, i) else return OS-SELECT(x.right, i - r) ``` **(c.1)** 对 $j\ne i$，结点 $j$ 是 $i$ 的祖先，当且仅当在关键字区间 $[\min(i,j),\max(i,j)]$ 内，$j$ 最早插入。因此 $$\Pr[j\text{ 是 }i\text{ 的祖先}]=\frac1{|i-j|+1}.$$ 利用期望的线性性， $$\begin{aligned} \mathbb E[D_i]&=\sum_{j=1}^{i-1}\frac1{i-j+1}\\ &\quad+\sum_{j=i+1}^{n}\frac1{j-i+1}\\ &=(H_i-1)+(H_{n-i+1}-1). \end{aligned}$$ **(c.2)** 查找访问 $D_i+1$ 个结点，故 $$\mathbb E[\mathrm{time}]=\Theta(H_i+H_{n-i+1}-1)=\Theta(\log n)$$ （$n\ge2$）。这是随机构建假设下的期望复杂度，单棵退化树的最坏情况仍为 $O(n)$。 --- ## 2025 年 · 附加题 第 1 题 出处：2025 年秋季学期算法基础期中考试，试卷第 7 页；答案卷第 7 页起。 ### 题目 有 $n$ 块按顺序排成一排的“记忆碎片”，第 $i$ 块记录时间为 $t_i$，$t_1,\ldots,t_n$ 是 $1\sim n$ 的一个排列。你希望通过交换恢复顺序： $$(t_1,t_2,\ldots,t_n)\longrightarrow(1,2,\ldots,n).$$ “回忆能力值”为 $k$。一次操作可选两块碎片，其时间为 $x,y$；当且仅当 $|x-y|\le k$ 时，可以交换它们**当前所在的位置**。 - 若 $|x-y|=1$，消耗 $1$ 点精力； - 若 $2\le|x-y|\le k$，代价为 $0$。 可做任意多次合法交换，求恢复严格递增顺序所需的最小精力。设计时间复杂度尽可能小的算法。输入为 $n,[t_1,\ldots,t_n],k$，输出最小代价。 ### 参考答案（整理版） **小规模：$n<4$。** 最多 $3!=6$ 个排列状态。以每种允许的交换作为代价 $0$ 或 $1$ 的边，在状态图上做 0–1 BFS，求到有序排列的最短距离。 **当 $n\ge4$ 时分情况：** **1. $k=1$。** 仅能交换相邻的数值，最少代价等于原排列的逆序对数： $$\mathrm{ans}=\#\{(i,j):1\le it_j\}.$$ 可将操作视为在逆排列中交换相邻位置，而排列及其逆排列的逆序数相同。用归并排序统计，时间 $O(n\log n)$。 **2. $k=2$。** 差为 $2$ 的免费交换连通所有奇数，也连通所有偶数，因此可在每一类内部免费任意重排。设 $$\mathrm{mism}=\#\{i:(t_i\bmod2)\ne(i\bmod2)\}.$$ 每次付费交换最多修正两个奇偶错位；通过类内免费重排可让一对相邻数值处于需要交换的位置，因此该下界可达： $$\mathrm{ans}=\mathrm{mism}/2.$$ 时间为 $O(n)$。 **3. $k\ge3$。** 免费交换允许数值差为 $2$ 或 $3$。当 $n\ge4$ 时，这些边连通全部数值（$1,2,3,4$ 已连通，其余可用差 $2$ 连入），连通图边交换可生成任意排列，因此答案为 $0$。 **边界：** 若允许 $k=0$，没有合法交换；已排序时为 $0$，否则无法完成。原解默认 $k\ge1$。 ---