历年试卷 / 顺序阅读

F，错误。 主定理中 $n^{\log_4 4}=n$，而 $f(n)=n\lg n$，所以 $T(n)=\Theta(n\lg^2 n)$。

F，错误。 快速排序在最坏情况下需要 $\Theta(n^2)$ 次比较，堆排序的最坏时间复杂度为 $\Theta(n\lg n)$。

F，错误。 标准选择排序无论输入初始排列如何，都要进行 $n(n-1)/2$ 次关键字比较，时间复杂度为 $\Theta(n^2)$。

T，正确。 随机化选择每次划分后只递归处理一侧，期望运行时间为 $\Theta(n)$；最坏情况仍可能为 $\Theta(n^2)$。

F，错误。 假设存在这样的算法，则可先用 $O(n)$ 时间将任意数组建堆，再转换为二叉搜索树，最后中序遍历得到排序结果，总时间为 $O(n)$，与比较排序的 $\Omega(n\lg n)$ 最坏下界矛盾。

T，正确。 原树不能有相邻红节点；反色后的树也不能有相邻红节点，因此非根内部节点之间也不能相邻为黑。内部节点颜色必须逐层交替。结合每条根到 NIL 路径黑节点数相同，可得所有 NIL 叶子深度相同，树为完美二叉树，各节点左右子树节点数相等。

由 $\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).$$

依次填入：$p-1$、$r-1$、$A[j]\le x$、$p<r$、$q-1$、$q+1$。

RANDOMIZED-QUICKSORT(A, p, r)
    if p < r
        q = RANDOMIZED-PARTITION(A, p, r)
        RANDOMIZED-QUICKSORT(A, p, q - 1)
        RANDOMIZED-QUICKSORT(A, q + 1, r)

最坏和最好情况下，函数调用总次数均为 $\Theta(n)$。每个非平凡子问题确定一个枢轴，两次递归调用形成一棵总节点数线性的递归树。调用次数不要与总比较次数或递归深度混淆。

采用左右双指针向内搜索。以下按非递减顺序给出伪代码，修正了原答案中的循环边界与变量笔误。

OPPOSITE-PAIR(a, n)
    l = 0
    r = n - 1
    while l < r
        s = a[l] + a[r]
        if s == 0
            return True
        if s > 0
            r = r - 1
        else
            l = l + 1
    return False

若和大于 $0$，则当前右端值不可能与剩余任何值组成零和，应缩小右端；若和小于 $0$，同理增大左端。条件 $l<r$ 保证下标不同。两个指针各最多移动 $n$ 次，时间为 $O(n)$，辅助空间为 $O(1)$。

第 1 问：抽取最小结点。 将最小结点的孩子加入根链表，删除最小结点，再反复合并度数相同的根。合并时较小关键字成为父节点，最后更新最小指针。

第 2 问：降低关键字。 将 $25$ 改为 $3$。若它小于父节点，则切断并加入根链表；对原父节点执行级联切断：未标记的非根结点先置标记，已标记的非根结点继续切断。移到根链表的结点清除标记，再更新最小指针。

上图保留配套答案中的结构示意。根链表顺序及同度根的合并顺序可以不同，应核对堆序、父子关系、度数、标记和最小指针。

(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)$。

(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)

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)

旋转操作应同步维护父子指针和受影响结点的高度。

定义前缀量 $D_0=0$，以及

$$D_k=\sum_{i=1}^{k}s_i-\alpha k.$$

刷题范围为 $(x,y]$ 时，最终得分为 $S+D_y-D_x$。于是问题转为统计

$$0\le x<y\le n,\qquad l-S\le D_y-D_x\le r-S$$

的数对数目。

可用归并排序计数：按原下标将前缀数组分为左右两半，递归统计内部合法对；合并前对已排序的两半，用两个单调指针统计每个左半值在右半中满足差值区间的数量；再完成归并。每层 $O(n)$，共 $O(\lg n)$ 层，总时间 $O(n\lg n)$，辅助空间 $O(n)$。

这里按原解统计非空连续段。若把“不刷任何题”也算一种方案，当 $S\in[l,r]$ 时再加 $1$。

F，错误。 因为 $\log_5 2<1/2$，$\sqrt n$ 多项式级地大于 $n^{\log_5 2}$；且 $2\sqrt{n/5}=(2/\sqrt5)\sqrt n$ 满足正则条件，所以 $T(n)=\Theta(\sqrt n)$。

F，错误。 堆排序通常不稳定，但自底向上的 BUILD-MAX-HEAP 时间复杂度为 $\Theta(n)$。不能把逐次插入建堆的上界当作该算法的复杂度。

T，正确。 例如初始数组为 $[2,3,\ldots,n,1]$。最后一趟开始前，前 $n-1$ 个元素有序但都应向右移动一位，最后的 $1$ 则应移到第一位。

F，错误。 链表归并可以直接重连指针，无须额外的线性合并数组。链表又不支持随机访问，因此题目给出的优势不成立。

T，正确。 在结点标识互异的通常约定下，后序为“左、右、根”，中序为“左、根、右”。若右子树非空，根的位置就不可能相同；对子树递归应用同样结论。

F，错误。 这是 AVL 树的高度平衡要求。红黑树约束黑高相等和红节点不相邻，并不要求左右子树普通高度差至多为 $1$。

配套答案给出上界 $O((\lg n)^2)$。令 $L=\lg n$，$a=\lg3$，$b=\lg(3/2)$，猜测 $T(n)\le cL^2$。由归纳假设，

$$\begin{aligned} T(n)&\le\frac c2(L-a)^2+\frac c2(L-b)^2+L\\ &=cL^2+[1-c(a+b)]L+\frac c2(a^2+b^2). \end{aligned}$$

选择 $c>1/(a+b)$，则对充分大的 $n$，后两项之和非正。放大常数并处理有限个基例，得 $T(n)=O((\lg n)^2)$。

本题在答案卷中位于“简答题第 3 题”，已按题目内容配对。

按原答案的排序与配对思路，可写成更简洁的双指针实现：

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 题”。

以集合元素为红黑树关键字。在每个结点 $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 题”。

第 1 问：抽取最小结点。 将最小结点的孩子加入根链表，删除最小结点，再反复合并度数相同的根。合并时较小关键字成为父节点，最后更新最小指针。

第 2 问：降低关键字。 将 $35$ 改为 $4$。若它小于父节点，则切断并加入根链表；对原父节点执行级联切断：未标记的非根结点先置标记，已标记的非根结点继续切断。移到根链表的结点清除标记，再更新最小指针。

上图保留配套答案中的结构示意。根链表顺序及同度根的合并顺序可以不同，应核对堆序、父子关系、度数、标记和最小指针。

(a) 只递归处理含目标秩的那一侧。

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$；该结果与它自己的递推在小规模基例处也不一致。这里明确采用题给伪代码的“关键字比较次数”口径，原文仍可在原卷中核对。

(a) 恰有 $1$ 棵。优先级最小的结点必须为根；关键字将其余结点唯一地分到左右子树，再递归应用相同结论。

(b)

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}$$

采用滑动窗口和哈希桶。若价格和 $A$ 是整数，取桶宽 $A+1$，则同桶的两个值一定满足差值要求；还需检查相邻桶。以下把原答案中的窗口变量 k 统一为 W。

VALUE-RANGE(a, W, A)
    if W < 1 or A < 0
        return False
    buckets = empty hash map
    width = A + 1
    for i = 0 to length(a) - 1
        id = floor(a[i] / width)
        if id in buckets
            return True
        if id - 1 in buckets
            if abs(a[i] - buckets[id - 1]) <= A
                return True
        if id + 1 in buckets
            if abs(a[i] - buckets[id + 1]) <= A
                return True
        buckets[id] = a[i]
        if 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))$。一般哈希表不保证最坏线性时间。

F，错误。 主定理给出 $T(n)=\Theta(n^{\log_{3/2}2})$，因为 $\log_{3/2}2>1$，$n\log 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)$。

T，正确。 对标准归并排序，稳定归并保证稳定性，每层合并代价为 $\Theta(n)$，递归层数为 $\Theta(\log n)$。这里采用课程中标准实现的约定。

F，错误。 标准稳定计数排序需要计数数组和输出数组，辅助空间为 $O(n+k)$，其中 $k$ 为关键字范围大小。

F，错误。 即使结点互异，前序和后序也不能唯一确定中序。例如前序为 $[1,2]$、后序为 $[2,1]$ 时，结点 $2$ 可以是根的左孩子，也可以是右孩子。

F，错误。 在课程使用的黑高约定下，黑红逐层交替的满二叉树可有 $2^{2h}-1$ 个内部节点，超过题目给出的界。

这里 $\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$ 这一情形。

用双指针维护窗口 $[\mathrm{left},\mathrm{right}]$，用 counts 记录每种颜色的出现次数，total 记录不同颜色数。右端点扩展到满足要求后，反复收缩左端并更新最小长度。

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$ 约定。

以端点为关键字建立扩张红黑树。左端点权重为 $+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)$。

若为闭区间且坐标相同，必须先处理左端点再处理右端点；同类端点再用唯一编号区分，以正确处理重复端点。

第 1 问：抽取最小结点。 将最小结点的孩子加入根链表，删除最小结点，再反复合并度数相同的根。合并时较小关键字成为父节点，最后更新最小指针。

第 2 问：降低关键字。 将 $30$ 改为 $4$。若它小于父节点，则切断并加入根链表；对原父节点执行级联切断：未标记的非根结点先置标记，已标记的非根结点继续切断。移到根链表的结点清除标记，再更新最小指针。

上图保留配套答案中的结构示意。根链表顺序及同度根的合并顺序可以不同，应核对堆序、父子关系、度数、标记和最小指针。

(a)

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).$$

(a) $x.\mathrm{size}=3+5+1=9$。$x$ 的子树内排名为左子树大小加 $1$，即 $4$，故 OS-Select$(x,4)$ 返回 $x$ 自身。

(b)

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)$。

小规模：$n<4$。 最多 $3!=6$ 个排列状态。以每种允许的交换作为代价 $0$ 或 $1$ 的边，在状态图上做 0–1 BFS，求到有序排列的最短距离。

当 $n\ge4$ 时分情况：

1. $k=1$。 仅能交换相邻的数值，最少代价等于原排列的逆序对数：

$$\mathrm{ans}=\#\{(i,j):1\le i<j\le n,\ t_i>t_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$。