# 算法设计与分析前四课月考试卷（训练版）

> 满分 100 分；建议用时 90 分钟；下标从 0 开始。除特别说明外，渐近分析默认一次比较、数组访问和机器字范围内算术运算均为常数时间。

## 一、合并重叠区间（25 分）

给定 $n$ 个闭区间 $[l_1,r_1],[l_2,r_2],\ldots,[l_n,r_n]$，其中 $l_i\le r_i$。请设计一个时间复杂度尽可能低的算法，合并所有相交的区间（含端点相接），使输出区间互不相交，并按左端点递增排列。

例如：

$$
[[15,18],[1,3],[8,10],[3,6]]\longrightarrow [[1,6],[8,10],[15,18]].
$$

要求：

1. 写出算法或伪代码，并说明排序关键字。（10 分）
2. 对上述样例写出排序后的序列和扫描过程。（6 分）
3. 证明算法正确，并给出时间、空间复杂度。（9 分）

## 二、旋转升序数组中的二分查找（25 分）

给定一个严格递增数组在某个未知位置旋转后的结果 $A=[a_0,a_1,\ldots,a_{n-1}]$。例如 $[0,1,2,4,5,6,7]$ 旋转后可得到 $[4,5,6,7,0,1,2]$。给定目标值 $s$，要求在 $O(\log n)$ 时间内返回其下标；若不存在，返回 $-1$。

要求：

1. 写出算法或伪代码。（10 分）
2. 对 $A=[4,5,6,7,0,1,2]$，分别说明查找 $s=0$ 和 $s=3$ 时每轮的 $l,m,r$ 及保留区间。（7 分）
3. 证明每轮可以安全丢弃一半区间，并分析复杂度。（8 分）

## 三、递推式紧确渐近界（25 分）

设 $T(n)=\Theta(1)$（当 $n$ 不超过常数时）。分别求下列递推式的紧确渐近界，并写出所用方法或关键展开步骤：

1. $T(n)=2T(n/2)+n^4$；
2. $T(n)=T(7n/10)+n$；
3. $T(n)=16T(n/4)+n^2$；
4. $T(n)=7T(n/3)+n^2$；
5. $T(n)=7T(n/2)+n^2$；
6. $T(n)=2T(n/4)+\sqrt n$；
7. $T(n)=T(n-2)+n^2$。

每小题约 3--4 分，共 25 分。不得只写答案，至少写出 $a,b,f(n)$ 的比较或展开求和。

## 四、快速排序与插入排序混合算法（25 分）

修改随机快速排序：当递归处理的子数组长度 **少于** $k$ 时直接停止，不再排序；整个快速排序阶段结束后，对整个数组执行一次标准插入排序。假设元素互异，每次从当前子数组均匀随机选择枢轴，且 $2\le k\le n$。

1. 写出算法流程，并解释为什么第一阶段结束后，不同终止小块之间不会产生逆序对。（8 分）
2. 设第一阶段结束后剩余逆序对数为 $I$，证明插入排序阶段时间为 $\Theta(n+I)$，并证明 $I=O(nk)$。（7 分）
3. 证明第一阶段期望时间为 $O(n\lg(n/k))$（允许保留一个 $O(n)$ 的线性项），从而得到总期望时间
   $$O\left(nk+n\lg\frac nk\right).$$
   （7 分）
4. 将 $k=2,\Theta(\lg n),\Theta(\sqrt n),n$ 代入总上界并比较；说明理论阈值与实践阈值为什么不是同一个问题。（3 分）
