# 前四课闭卷自测题册

答案见讲义第十三章。

# 十 分层自测题

答案见第十三章。

## 1 概念与短题

**D01 渐进关系。** 对以下四对 $(A,B)$ 分别填写五列 $O,o,\Omega,\omega,\Theta$：① $(3n^2+2n,n^2)$；② $(n\lg n,n^{1.1})$；③ $(4^n,2^{2n})$；④ $(n(2+\sin n),n)$。

**D02 指数化简。** 化简 $8^{\lg n}$、$n^{3/\lg n}$、$(\lg n)^{\lg n}$、$2^{\lg\lg n}$，指出哪些与 $n^3$ 同阶。

**D03 函数排序。** 将 $1,\lg\lg n,\sqrt{\lg n},(\lg n)^3,n^{0.01},n,2^n,n!$ 按由慢到快排列，并说明 $(\lg n)^3$ 与 $n^{0.01}$ 的比较理由。

**D04 命题证明。** 若 $f=O(g)$ 且 $g=O(h)$，证明 $f=O(h)$。写出常数与阈值如何合并。

**D05 命题反例。** 否定“$f=\Theta(g)$ 推出 $3^f=\Theta(3^g)$”，并给出一个足以推出该指数结论的更强条件。

**D06 循环计数。** 外层 $i=1,\ldots,n$，内层 $j=1,\ldots,i$，求总次数；若每轮内层从 $j=1$ 开始、执行 `j *= 2` 直到超过 $n$，求总次数的渐近阶。

**D07 稳定性。** 对选择排序 $[2_a,2_b,1]$ 给出反例轨迹；解释插入排序把 `>` 改为 `>=` 后会发生什么。

**D08 作业算法边界。** 分别给出：非空最大子数组 $[-4,-2,-7]$ 的和与端点；两数之和输入 $[5]$、目标 10 的判断结果；多路归并输入为空表集合、或只有一个表 $[1,1,3]$ 时的输出。说明各题最容易误用的初始化或循环条件。

**D09 随机算法。** 判断并说明理由：“随机快排每次划分期望均衡，所以每条实际路径都只有对数层。”

**D10 排序方案选择。** 原题 2.3-7 要求 $\Theta(n\lg n)$ 时间。为什么归并排序加双指针满足要求，而固定末尾枢轴的快排加双指针不能保证？若改用随机快排，必须怎样表述其时间结论？

**D11 堆操作。** 堆内有 $k$ 个候选，查看最小值与删除最小值的时间分别是什么？为什么自底向上建堆是 $O(k)$？

**D12 比较决策树。** 有 20 个必须区分的候选状态，每次比较只有两种结果。最坏至少需要几次比较？为什么叶数容量足够不自动证明存在达到该次数的合法比较算法？

## 2 计算与完整解题

**D13 主定理。** 求下列递推式的紧确界并说明情况：① $3T(n/3)+n$；② $9T(n/3)+n$；③ $T(n/2)+n$；④ $4T(n/2)+n^3$。

**D14 不适用主定理。** 求 $T(n)=T(n-3)+n$ 和 $T(n)=T(\sqrt n)+1$ 的紧确界，给出展开或终止条件。

**D15 对数变式。** 求 $2T(n/2)+n\lg n$ 和 $2T(n/2)+n/\lg n$ 的紧确界。说明基本主定理哪里不能直接用。

**D16 插入过程。** 对 $[4,1,3,2]$ 写出每轮插入后的数组，并给出右移总次数和逆序对清单。

**D17 归并过程。** 合并 $[1,4,6]$ 与 $[2,3,5]$，列出每次键比较和输出，总比较次数是多少？

**D18 两数之和。** 对 $[-5,-2,0,3,7,10]$、目标 8，列出双指针轨迹。再说明目标 20 时为什么不能重复使用值 10。

**D19 最大子数组。** 对 $[2,-5,3,1,-2,4,-6,2]$ 列出每个位置的 $E_j,B_j$，给出一组最优端点。

**D20 前缀和。** 对 $[3,-1,4,-2]$ 建立前缀和，求闭区间 $[1,3]$ 的和；说明一组下标差 1 的常见错误。

**D21 多路归并。** 合并 $[1,4]$、空表、$[1,3,5]$、$[2]$。列出输出序列、初始堆节点数和最大堆节点数。

**D22 快排划分。** 用本讲义的 Lomuto 划分处理 $[9,3,7,1,6]$，末尾 6 为枢轴。写出每次有效交换后的数组及最终枢轴位置。

**D23 混合排序。** 设 $k=4$，第一阶段结果为 $[2,1,3],4,[6,5],7,[9,8]$。剩余逆序对多少？最终插入排序右移几次？若 $k=\sqrt n$，代入总上界。

**D24 混合排序阈值。** 将 $k$ 的四种取值 $2,\Theta(\lg n),\Theta(\sqrt n),n$ 分别代入 $O(nk+n\lg(n/k))$，化简上界。为什么不能推出所有机器通用的最佳整数阈值？

## 3 迁移与证明

**D25 不等规模分治。** 证明 $T(n)=T(n/3)+T(2n/3)+n$ 为 $\Theta(n\lg n)$，不得直接套等规模主定理。

**D26 逆序对算法。** 描述利用归并排序计数逆序对的算法。为什么合并时 $L[i]>R[j]$ 可一次增加 $|L|-i$？

**D27 连续区间优化。** 最大子数组要同时输出左右端点时，只保存 `best` 为什么不够？还需哪些变量，何时更新？

**D28 块间顺序反例。** 设 $n=2m,k=3$，数组为 $[2m-1,2m],[2m-3,2m-2],\ldots,[1,2]$，每块内部升序。求跨块逆序对数；为何“小块短于 $k$”不足以推出 $O(nk)$？截断快排还保证什么？

**D29 归并代价比较。** 合并 $k=\Theta(\sqrt n)$ 个非空有序表，总元素数 $n$。比较扫描表头与最小堆的总时间上界，说明堆初始化成本，以及堆顶查询 $O(1)$ 为什么不代表总时间 $O(n)$。

**D30 比较下界。** 对 6 个互异元素，求任意比较排序的最坏比较次数下界，再证明一般 $n$ 的界。说明为何此下界不保证存在恰好达到该次数的算法。

# 十一 模拟卷 A

自拟题，满分 100 分。

**A01 渐进关系 12 分。** 三对函数分别填 $O,o,\Omega,\omega,\Theta$ 并说明理由，每对 4 分：① $((\lg n)^4,\sqrt n)$；② $(n^{\lg5},5^{\lg n})$；③ $(2^{n+3},2^n)$。

**A02 函数排序 8 分。** 将 $1,\lg n,n^{1/\lg n},\sqrt n,n\lg n,3^n,n!,2^{2^n}$ 按由慢到快排序并同阶分组。

**A03 证明与反例 10 分。** 每问 5 分：① 证明最终为正的 $f,g$ 满足 $f+g=\Theta(\max(f,g))$；② 否定“$f=O(g)\Rightarrow2^f=O(2^g)$”。

**A04 选择排序 12 分。** 对 $[4,1,3,2]$ 使用每轮选最大放末尾的版本：写前两轮数组 4 分；写外层不变式及终止结论 4 分；给出键比较总数、最好和最坏时间 4 分。

**A05 递推式 16 分。** 各求紧确界并说明方法，每问 4 分：① $3T(n/3)+n$；② $9T(n/3)+n$；③ $T(n-3)+n$；④ $T(n/2)+n$。

**A06 两数之和 14 分。** 对 $S=\{-3,0,2,4,7,11\}$、目标 9，设计 $\Theta(n\lg n)$ 判定算法：算法与样例轨迹 6 分；证明指针移动不漏解 5 分；时间与空间 3 分。

**A07 最大子数组 16 分。** 对 $[-1,4,-2,3,-5,2]$：写线性非递归算法或状态递推 6 分；列 $E_j,B_j$ 与答案区间 6 分；说明全负边界、时间与空间 4 分。

**A08 比较排序下界 12 分。** 从决策树证明 $\Omega(n\lg n)$：候选状态与叶数 4 分；树高不等式 4 分；$\lg(n!)$ 的界与适用范围 4 分。

# 十二 模拟卷 B

自拟题，满分 100 分。

**B01 五项辨析 10 分。** 每项 2 分，判断并简要说明：① 选择排序有序输入时为 $\Theta(n)$；② 比值无极限就不可能 $\Theta$；③ 普通随机快排最坏为 $\Theta(n^2)$；④ 堆归并中每次取出并补入候选总能按 $O(1)$ 计算；⑤ 截断快排停止后，不同终止小块之间没有逆序对。

**B02 递推进阶 12 分。** 每问 4 分，求紧确界并说明推导：① $2T(n/2)+n\lg n$；② $T(\sqrt n)+1$；③ $T(n/3)+T(2n/3)+n$。

**B03 堆归并 16 分。** 合并 $[0,5,9]$、$[1,3]$、空表、$[2,4,8]$：算法与节点设计 5 分；不变式 4 分；前四个输出及堆中代表 3 分；时间、空表成本、工作空间与输出空间 4 分。

**B04 快排分析 14 分。** 对 $[8,2,5,1,7,3]$ 取末尾 3 为枢轴，执行本讲义划分：最终数组与枢轴位置 4 分；写互异元素、均匀随机枢轴下的期望比较次数递推 4 分；说明期望 $\Theta(n\lg n)$ 与最坏 $\Theta(n^2)$ 为什么可以同时成立，不能把随机划分直接当成每次均分，6 分。

**B05 混合排序 20 分。** 证明原题 $O(nk+n\lg(n/k))$ 期望界：块间有序 4 分；逆序对与插入代价 6 分；截断快排期望成本 6 分；理论阈值与实践阈值 4 分。必须说明元素、随机枢轴与截止条件。

**B06 最大子数组状态 12 分。** 对 $[3,-4,2,-1,6,-5]$：列出每个位置的结尾最优 $E_j$ 与全局最优 $B_j$，4 分；给出最大和、端点与全负输入的初始化，4 分；解释为什么不能用 $B_{j-1}+A[j]$ 代替 $E_{j-1}+A[j]$，并用本数组指出该错误会虚构什么结果，4 分。

**B07 振荡函数 8 分。** 对原题中的 $A=\sqrt n,B=n^{\sin n}$ 判断 $A=O(B),o(B),\Omega(B),\omega(B),\Theta(B)$ 是否成立。写出比值，并说明怎样用两条子序列排除最终上界和最终正下界；不能只用“振荡”二字作答。

**B08 反例与定义证明 8 分。** 每问 4 分：① 证明 $(n+1)!$ 与 $n!$ 不同阶；② 在 $f=O(g)$ 且足够大时 $\lg g\ge1,f\ge1$ 的条件下，证明 $\lg f=O(\lg g)$，明确所取常数及两个附加条件的作用。
