2024-2025 第二学期 算法设计与分析

---

一、简答题（每题5分，共20分）

1. 题目内容

简述分治法进行算法设计的三个基本步骤。

答案与深度解析

答案： 分治法（Divide and Conquer）的三个基本步骤为：

1. 分解（Divide）： 将原问题分解为若干个规模较小、相互独立且与原问题形式相同的子问题。
2. 解决（Conquer）： 若子问题规模较小且容易被解决，则直接求解；否则，递归地解决各个子问题。
3. 合并（Combine）： 将各个子问题的解合并为原问题的解。

深度解析：

• 核心驱动力： 面对庞大复杂的问题，计算机处理起来会非常耗时。分治法的底层逻辑是“降维打击”，通过不断缩小问题的规模，直到问题简单到可以直接得出答案（即递归的基线条件）。
• 关键点与风险： 分治法成功的前提是“子问题必须相互独立”。如果子问题之间有重叠（即存在公共子子问题），分治法会进行大量重复计算，此时算法效率极低，应转而考虑动态规划。
• 应用实例： 归并排序、快速排序、二分查找都严格遵循了这三个步骤。

---

2. 题目内容

简述回溯法与分支限界法的异同。

答案与深度解析

答案：

• 相同点： 两者都是在问题的状态空间树（解空间）上进行搜索的算法；都需要通过设计限界函数（剪枝函数）来避免无效搜索，提高算法效率。
• 不同点：
  1. 搜索方式不同： 回溯法采用深度优先搜索（DFS）；分支限界法采用广度优先搜索（BFS）或最小耗费优先（优先队列）搜索。
  2. 求解目标不同： 回溯法的目标通常是找出满足约束条件的所有解或任一解；分支限界法的目标则是找出满足约束条件的一个解，或者是某种意义下的最优解（如最大值或最小值）。

深度解析：

• 形象化理解： * 回溯法就像是在走迷宫，你顺着一条路一直走到黑（深度优先），遇到死胡同就退回上一个岔路口（回溯），尝试另一条路，直到把所有角落都走遍。
  • 分支限界法像是在雷达扫描，你站在起点，先把周围第一圈的岔路口都看一遍（广度优先），然后评估哪条路看起来最有可能通向宝藏（通过代价函数评估），接着优先去展开那条最有希望的路。
• 空间复杂度差异： 回溯法只需要保存当前从根节点到当前节点的路径，空间复杂度通常为 $O(n)$；而分支限界法需要维护一个活结点表（队列），在最坏情况下空间复杂度可能达到指数级。

---

3. 题目内容

简述拉斯维加斯算法与蒙特卡洛算法的异同。

答案与深度解析

答案：

• 相同点： 两者都属于随机化算法，都在算法执行过程中引入了随机数来辅助决策，以期望获得更好的平均性能或绕过最坏情况。
• 不同点：
  • 拉斯维加斯算法（Las Vegas）： 只要算法返回了结果，这个结果就一定正确。但它的执行时间是不确定的，有时可能找不到解并宣告失败。
  • 蒙特卡洛算法（Monte Carlo）： 算法的执行时间是确定且通常较快的，它一定会给出一个答案，但这个答案不一定正确，获得正确解的概率存在一个界限。

深度解析：

• 如何记忆： * 去“拉斯维加斯”赌场，要么赢钱（拿到绝对正确的解），要么输光离场（找不到解），但赌场绝对不会给你假钞（结果绝对正确）。
  • “蒙特卡洛”常用于估算（例如用随机投点法估算圆周率 $\pi$），投的点越多，估算越准确，但它始终是一个近似值（有概率犯错）。
• 性能提升策略： 蒙特卡洛算法可以通过反复多次执行来无限逼近 100% 的正确率；而拉斯维加斯算法如果失败，只能重新运行，期望下一次运气好能找到解。

---

4. 题目内容

简述分支限界法中活结点表的组织方式。

答案与深度解析

答案： 分支限界法中，活结点表（用于存放已经被生成但尚未展开的节点）主要有两种组织方式：

1. 队列式（FIFO）分支限界法： 将活结点表组织成一个先进先出的队列。按照节点生成的顺序依次扩展。
2. 优先队列式分支限界法： 将活结点表组织成一个优先队列（通常用堆来实现）。每个节点都有一个由代价函数计算出的优先级（如成本或价值），算法每次总是从活结点表中选取优先级最高（或代价最小）的节点作为下一个扩展的节点。

深度解析：

• 底层数据结构： 队列式对应简单的数组队列或链式队列；优先队列式对应数据结构中的“大顶堆”或“小顶堆”。
• 策略选择： 在实际解决工程优化问题（如单源最短路径、旅行商问题）时，优先队列式分支限界法应用更广，因为它能更快地引导搜索过程逼近最优解，从而引发更多的“剪枝”，大幅缩减搜索空间。

---

二、选择题（每题1分，共10分）

1. 题目内容

在算法设计中，要求算法对于错误的输入也有相应的处理即要求设计的算法具有（ ）。 A. 确定性
B. 健壮性
C. 可行性
D. 正确性

答案与深度解析

答案：B

• 分析：
  • 确定性： 算法的每一步都必须有明确的定义，无二义性。
  • 健壮性（Robustness）： 也称鲁棒性，指当输入数据非法或出现异常情况时，算法能够适当地做出反应或进行处理，而不会产生莫名其妙的输出或直接崩溃。这正是题干描述的内容。
  • 可行性： 算法中的操作必须足够基本，能够在有限次内完成。
  • 正确性： 算法对合法的输入能产生满足要求的正确输出。

---

2. 题目内容

下述表达不正确的选项是（ ）。 A. $n^2 / 2 + 2^n$ 上界函数是 $O(2^n)$
B. $n^2 / 2 + 2^n$ 的下界函数是 $\Omega(2^n)$
C. $\log_2 n^3$ 上界函数是 $O(\log_2 n)$
D. $\log_2 n^3$ 的下界函数是 $\Omega(n^3)$

答案与深度解析

答案：D

• 分析： 复杂度分析关注的是当问题规模 $n$ 趋于无穷大时，函数的增长量级。我们在多项式相加时，只保留最高阶项。
  • 对于 $n^2 / 2 + 2^n$，指数级 $2^n$ 的增长速度远远快于多项式 $n^2$。因此最高阶项是 $2^n$。它的上界 $O$ 和下界 $\Omega$ 都可以是 $2^n$。A和B表述正确。
  • 对于 $\log_2 n^3$，根据对数运算法则，它等于 $3 \log_2 n$。常数系数 3 在量级分析中被忽略，因此它的确切量级是 $\Theta(\log_2 n)$。这意味着它的上界是 $O(\log_2 n)$，下界是 $\Omega(\log_2 n)$。
  • 选项 D 说下界是 $\Omega(n^3)$，即认为该函数的增长速度大于等于 $n^3$，这是极其荒谬的，对数函数的增长极其缓慢，远小于多项式函数。因此 D 错误。

---

3. 题目内容

某递归算法的时间复杂度公式为：$T(n)=8T(n/3)+n^2\log_2 n$，则该算法的时间复杂度为（ ）。 A. $O(n)$
B. $O(n^2)$
C. $O(n^2 \log_2 n)$
D. $O(n^{8/3})$

答案与深度解析

答案：C

• 分析： 此题考察求解递归式的终极武器——主定理（Master Theorem）。 主定理用于求解形式为 $T(n) = aT(n/b) + f(n)$ 的递归方程。
  1. 提取参数：题干中 $a = 8$（子问题个数），$b = 3$（问题规模缩小的比例），$f(n) = n^2 \log_2 n$（分解和合并的代价）。
  2. 计算参照项：计算 $n^{\log_b a}$，即 $n^{\log_3 8}$。因为 $3^2 = 9 > 8$，所以 $\log_3 8$ 的值略小于 2（约为 1.89）。即参照项约为 $n^{1.89}$。
  3. 比较 $f(n)$ 与参照项：我们将 $f(n) = n^2 \log_2 n$ 与 $n^{1.89}$ 比较。显然 $n^2$ 的多项式阶数 2 大于 1.89。所以 $f(n)$ 在多项式意义上大于 $n^{\log_b a}$。
  4. 匹配主定理情况：这属于主定理的第三种情况（根节点的计算量占主导地位）。算法的时间复杂度由 $f(n)$ 决定。
  5. 结论：$T(n) = \Theta(f(n)) = O(n^2 \log_2 n)$。

---

4. 题目内容

在棋盘覆盖问题中，关于 $2^k \times 2^k$ 的特殊棋盘（有一个特殊方块），所需的L型牌（可以覆盖3个方格）的个数是（ ）。 A. $4^k / 3$
B. $(4^k - 1) / 3$
C. $4^k$
D. $2^k / 3$

答案与深度解析

答案：B

• 分析： 这是一个纯粹的数学逻辑题，不需要死记硬背算法。
  1. 棋盘的边长是 $2^k$，因此总方格数是边长乘边长：$2^k \times 2^k = 4^k$。
  2. 题目说棋盘是“特殊棋盘”，意味着其中有 1 个方格是特殊方格（不需要被覆盖）。
  3. 需要被L型牌覆盖的剩余方格总数为：$4^k - 1$。
  4. 每一块L型骨牌刚好覆盖 3 个方格。
  5. 因此所需骨牌数量为：$(4^k - 1) / 3$。

---

5. 题目内容

在求解 $n$ 个元素中第 $k$ 小元素问题中，假设利用快速排序算法思想对 $n$ 个元素进行划分，应如何选择划分基准（ ）。 A. 随机选择一个元素作为划分基准
B. 取子序列的第一个元素作为划分基准
C. 用中位数的中位数方式寻觅划分基准
D. 以上皆可行，但不同方式，算法复杂度上界可能不同

答案与深度解析

答案：D

• 分析： 求解第 $k$ 小元素的经典算法是“快速选择算法”（Quickselect），它的核心也是划分（Partition）。
  • 取第一个元素（B）或随机取元素（A）： 很容易实现，平均时间复杂度很好，是 $O(n)$。但如果是极端恶劣的数据（例如已经排好序的数组，且每次取第一个），最坏情况下的时间复杂度会退化到 $O(n^2)$。
  • 中位数的中位数（C）： 这是著名的 BFPRT 算法（线性时间选择算法）。它通过复杂的逻辑强制找到一个相对居中的元素作为基准。虽然常数项较大，但它能保证在最坏情况下依然具有 $O(n)$ 的时间复杂度上界。
  • 因此，这三种方法在工程上和理论上都是可行的，只是它们的最坏时间复杂度上界存在差异。选项 D 描述最为客观全面。

---

6. 题目内容

用回溯法求解子集树问题，最坏情形下其解空间的叶结点数量为（ ）。 A. $2^{n-1}$
B. $2^n$
C. $n!$
D. $2^{n+1}-1$

答案与深度解析

答案：B

• 分析：
  • 子集树（Subset Tree）： 当问题是从 $n$ 个元素的集合中找出满足某种性质的子集时（例如 0/1 背包问题、装载问题），每个元素只有两种状态：选（1）或不选（0）。
  • 这相当于做了 $n$ 次决策，每次决策有 2 个分支。
  • 画出一棵完整的状态树，第 1 层有 2 个节点，第 2 层有 4 个……到了第 $n$ 层结束时，底部的叶子节点数量正好是所有可能的子集数量，即 $2^n$。
  • 补充知识：如果题目问的是排列树（例如旅行商问题、N皇后问题），所有可能的排列方式有 $n!$ 种，此时叶节点数量为 $n!$。

---

7. 题目内容

以深度优先方式对解空间进行搜索的算法是（ ）。 A. 分支限界
B. 贪心算法
C. 动态规划
D. 回溯法

答案与深度解析

答案：D

• 分析： 这是一道概念识记题。正如简答题第 2 题所分析的：回溯法的核心引擎就是深度优先搜索（DFS），再辅以剪枝函数。分支限界法是广度优先或优先队列。贪心和动态规划通常不直接描述为对树结构的穷举搜索。

---

8. 题目内容

备忘录算法是（ ）的变形。 A. 分治法
B. 贪心算法
C. 动态规划法
D. 分支限界法

答案与深度解析

答案：C

• 分析：
  • 动态规划的核心痛点是“重叠子问题”，如果用普通递归，会引发指数级的重复计算。
  • 解决重复计算有两种路线：
    1. 自底向上： 也就是狭义上的动态规划。先从最小的子问题开始算，用表格存起来，慢慢推导到大问题。
    2. 自顶向下： 依然保持自然的递归写法，但是准备一个“备忘录”（通常是一个数组或哈希表）。每次递归计算出一个子问题的答案时，把它记在备忘录里；下次再遇到完全相同的子问题，直接查备忘录拿答案，不用再算一遍。这就是备忘录算法（Memoization）。
  • 因此，备忘录算法本质上是动态规划思想的“自顶向下”实现方式。

---

9. 题目内容

利用贪心算法求解 $n$ 个集装箱最优装载问题（已知轮船载重量为 $W$，有 $n$ 个集装箱重量分别为 $w_i$，设计使得轮船上能装载更多的集装箱）时间复杂度的是（ ）。 A. $O(n)$
B. $O(n^2)$
C. $O(n\log_2 n)$
D. $O(\sqrt{n})$

答案与深度解析

答案：C

• 分析： 1. 贪心策略： 要想装载“最多”数量的集装箱，最直观且正确的策略就是：优先挑最轻的装。轻的占用的载重量少，留给后面集装箱的额度就多。 2. 算法执行步骤： 第一步，必须对 $n$ 个集装箱的重量进行从小到大排序。第二步，从轻到重依次遍历，只要没超重就装进去。 3. 时间复杂度分析： 最优的比较排序算法（如快速排序、归并排序）的时间复杂度为 $O(n\log_2 n)$。第二步的遍历只需扫描一次，复杂度为 $O(n)$。两者相加，排序步骤主导了整体时间耗费，因此总时间复杂度为 $O(n\log_2 n)$。

---

10. 题目内容

调用一次下列随机算法进行问题求解时，可能成功也可能失败的是（ ）。 A. 蒙特卡洛算法
B. 拉斯维加斯算法
C. 舍伍德算法
D. 数值概率算法

答案与深度解析

答案：B

• 分析： 结合简答题第 3 题的知识：
  • 拉斯维加斯算法最大的特征就是：一旦它输出结果，结果绝对正确（100%）。但它不能保证在限定时间内一定能找到解，如果运气不好走入死胡同，它会返回“失败”（无解）。这完全契合题目描述的“可能成功也可能失败”。
  • 蒙特卡洛算法必定会返回一个答案（一定成功运行），只是答案可能是错的。
  • 舍伍德算法是为了消除最坏情况而引入随机性（例如随机选择快速排序的基准元素），它总能求得正确解，且必定成功。

---

三、填空题（每空2分，共20分）

1. 题目内容

求解 0/1 背包问题可采用动态规划法、回溯法和分支限界法，其中需要按照单位重量价值比进行排序以提高算法效率的是 _____，不需要进行排序的是 _____ 。

答案与深度解析

答案： 第一空：回溯法和分支限界法 第二空：动态规划法

• 深度解析： * 为什么回溯和分支限界需要排序？因为这两种方法本质是在枚举所有组合。为了能尽早剪去不可能产生最优解的枝丫，我们需要一个强有力的“上界函数”。将物品按性价比（价值/重量）降序排列，可以让我们用贪心思想迅速估算出一个“理想状态下的最大可能收益”，如果这个理想收益都比不过当前已经找到的解，直接砍掉这个搜索分支，大幅提升效率。
  • 为什么动态规划不需要？动态规划是基于状态转移方程 dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])，它通过穷尽表格所有容量状态来获得绝对最优解，物品出现的先后顺序不影响最终表格右下角的答案，因此排序纯属多此一举。

---

2. 题目内容

标识主元素的蒙特卡洛算法，获得正确解的概率为 0.5，则调用该算法 3 次可以将获得正确解的概率提高到 _____ 。

答案与深度解析

答案：0.875 （或 87.5%、7/8）

• 深度解析： 这是一个基础概率论计算题，需要逆向思维。
  • 算法运行 1 次，正确的概率是 0.5，错误的概率是 1 - 0.5 = 0.5。
  • “调用 3 次且最终拿到正确解”的含义是：只要这 3 次中有任意一次是正确的，我们就成功了。它的反面是：3 次全部都算错了。
  • 3 次全部算错的概率是：$0.5 \times 0.5 \times 0.5 = 0.125$。
  • 那么至少有一次算对（即最终获得正确解）的概率就是：$1 - 0.125 = 0.875$。

---

3. 题目内容

$n$ 皇后问题的满 $n$ 叉树的求解算法的框架如下，补充完整该算法：

int sum = 0; // sum 用于记录可行解个数
void queen(int t) // 放第 t 个皇后
{
    if (t > n)
        _____(1)_____;
    else
        for (int j = 1; ____(2)____; j++)
        {
            ____(3)_____; 
            if (place(t))
                ____(4)_____; 
        }
}

答案与深度解析

答案： (1) sum++ (2) j <= n (3) x[t] = j （这里假设用于记录第 t 个皇后所在的列号的全局数组名为 x，这是极其通用的约定写法） (4) queen(t + 1)

• 深度解析： 这是经典的回溯法框架。我们一行一行从零梳理逻辑：
  • 函数 queen(t) 的意义是：去决定第 t 行的皇后应该放在哪一列。
  • 第(1)空： 递归的终止条件。题目说一共有 $n$ 个皇后，如果此时传入的 $t > n$，说明第 1 到第 $n$ 个皇后都已经成功放置在棋盘上了，这意味着我们找到了一个合法的可行解。此时当然要让解的计数器增加：sum++。
  • 第(2)空： else 块表示还在放置前 $n$ 个皇后。要在第 t 行放皇后，她能放在哪里呢？棋盘的列数是从第 1 列到第 $n$ 列。所以我们要遍历所有的列尝试放置：for (int j = 1; j <= n; j++)。
  • 第(3)空： 我们尝试把第 t 个皇后放在第 j 列。必须有一个数组把这个尝试记录下来，系统后面的 place(t) 函数才知道去哪里检查冲突。通常这个数组叫 x[]。记录动作是 x[t] = j。
  • 第(4)空： place(t) 是检查函数，如果刚才放的位置（不和前面几行的皇后同列、同对角线）是安全的（返回 true），那该怎么办？当然是继续去放下一行的皇后了，即递归调用：queen(t + 1)。

---

4. 题目内容

利用分治法求解正整数的划分数问题时，$f(n,m)$ 表示将正整数 $n$ 划分成最大正整数不超过 $m$ 的划分数，当 $n>m$ 时（$n>0, m>0$），$f(n, m)=$ _____

答案与深度解析

答案：$f(n, m-1) + f(n-m, m)$

• 深度解析： 这是一个非常经典的递归数学模型。所谓划分，比如数字 5 划分且最大数不超过 3，可以是 3+2, 3+1+1, 2+2+1, 2+1+1+1, 1+1+1+1+1。 当要划分数字 $n$，且允许使用的最大数字是 $m$ 时（前提 $n > m$），我们可以把所有可能的情况强制分为互不重叠的两大类：
  • 类别一：我们划分的过程中，打死都不用数字 $m$。 既然不用 $m$，那我们能用的最大数字就降级成了 $m-1$。这种情况下，划分方式的数目等价于 $f(n, m-1)$。
  • 类别二：我们划分的过程中，至少使用了一个数字 $m$。 既然确定至少包含一个 $m$，那么把这个 $m$ 先剥离出来，我们要面临的新问题就是如何把剩下的总数 $(n-m)$ 继续进行划分。此时允许使用的最大数字依然是 $m$。这种情况下，划分数目等价于 $f(n-m, m)$。
  • 由于这两类覆盖了所有情况且互斥，运用加法原理，总数就是 $f(n, m-1) + f(n-m, m)$。

---

5. 题目内容

利用动态规划法求解最长公共子序列问题时，设计动态规划数组 $dp[m][n]$。其中 $dp[i][j]$ 为：长度为 $i$ 的 $X$ 子序列 $(x_0, x_1, \dots, x_i)$ 和长度为 $j$ 的 $Y$ 子序列 $(y_0, y_1, \dots, y_j)$ 的最长公共子序列的长度。若 $x[i-1] = y[j-1]$（当前两个字符相同）则 $dp[i][j]=$ _____ ；若 $x[i-1] \neq y[j-1]$ 则 $dp[i][j]=$ _____

答案与深度解析

答案： 第一空：dp[i-1][j-1] + 1 第二空：max(dp[i-1][j], dp[i][j-1])

• 深度解析： 动态规划的核心在于推导“状态转移方程”。我们用白话进行逻辑推演：
  • dp[i][j] 就像是两个指针，分别指着字符串 X 的第 i 个字符，和字符串 Y 的第 j 个字符（注意题目给的暗示：C语言数组下标通常从0开始，所以第 i 个字符对应 x[i-1]）。
  • 情景一：两边的末尾字符竟然一模一样（$x[i-1] == y[j-1]$）！ 这简直是天上掉馅饼，这两个字符必定能成为公共子序列的最后一个字符。那么现在的长度，等于把这两个字符都扔掉后，前面剩余部分的公共长度再加上这1个字符。前面剩余部分的长度就是 dp[i-1][j-1]。所以是 dp[i-1][j-1] + 1。
  • 情景二：两边的末尾字符不一样（$x[i-1] \neq y[j-1]$）。 既然不一样，这两个字符绝对不可能同时出现在最长公共子序列的末尾。我们只能做取舍：
    • 要么抛弃 X 的末尾字符，看 X 的前 i-1 个字符和 Y 的前 j 个字符能凑出多长：dp[i-1][j]。
    • 要么抛弃 Y 的末尾字符，看 X 的前 i 个字符和 Y 的前 j-1 个字符能凑出多长：dp[i][j-1]。 既然要求“最长”，我们就取这两种取舍方案中的较大值：max(dp[i-1][j], dp[i][j-1])。

---

四、分析与构造题（每题10分，共30分）

1. 题目内容

根据如下算法，回答问题。

void fun(int a[], int i, int n) // 首次调用时: i为1
{
    int j, k;
    if (i == n) return;
    else
    {
        k = i;
        for (j = i + 1; j <= n; j++)
            if (a[j] < a[k]) k = j;
        if (k != i)
            swap(a[i], a[k]);
        fun(a, i + 1, n);
    }
}

1. 若 $a$ 数组中元素依次为 4, 9, 1, 3, 5, 6，分析并写出调用 fun(a,1,6) 后 $a$ 数组中元素值，并回答该算法完成的功能。（5分）
2. 给出该算法时间复杂度递归方程（仅针对元素比较次数分析即可）并分析该算法的最坏时间复杂度。（5分）

答案与深度解析

1) 数组变化及功能分析：

• 模拟推理（从零推演）： 题目明确 a 的元素是 4, 9, 1, 3, 5, 6。从代码的界限 i 到 n（从 1 到 6），说明该题目将数组视为从索引 1 开始存数据的（即 a[1]=4, a[2]=9, ... a[6]=6）。
  • 第一次调用 fun(a, 1, 6)： i=1。内层循环从 j=2 到 6，寻找其中最小的元素。找到了 a[3]=1 是最小的，因此记录下标 k=3。将 a[1] 和 a[3] 交换。
    • 数组变为：1, 9, 4, 3, 5, 6。随后递归调用 fun(a, 2, 6)。
  • 第二次调用 fun(a, 2, 6)： i=2。此时数组有效区域是索引 2 到 6。寻找这部分最小元素。发现 a[4]=3 最小，记录 k=4。将 a[2] 和 a[4] 交换。
    • 数组变为：1, 3, 4, 9, 5, 6。递归调用 fun(a, 3, 6)。
  • 第三次调用 fun(a, 3, 6)： i=3。寻找到 3..6 中最小的是 a[3]=4 本身，k=3，不交换。
    • 数组保持：1, 3, 4, 9, 5, 6。递归调用 fun(a, 4, 6)。
  • 第四次调用 fun(a, 4, 6)： i=4。寻找 4..6 中最小元素，发现 a[5]=5 最小，交换 a[4] 和 a[5]。
    • 数组变为：1, 3, 4, 5, 9, 6。递归调用 fun(a, 5, 6)。
  • 第五次调用 fun(a, 5, 6)： i=5。寻找 5..6 最小元素，发现 a[6]=6 最小，交换 a[5] 和 a[6]。
    • 数组变为：1, 3, 4, 5, 6, 9。递归调用 fun(a, 6, 6)。
  • 第六次调用 fun(a, 6, 6)： i=n 满足界限条件，直接 return，递归终止。
• 最终结果： 经过算法处理，数组变为：1, 3, 4, 5, 6, 9。
• 算法功能结论： 这是一个递归实现的选择排序（从小到大排序）。

2) 时间复杂度分析：

• 建立递归方程： 设 $T(n)$ 为处理规模为 $n$ 的数组（这里 $n$ 代表待排序的剩余元素个数）所需要的比较次数。
  • 当剩余 1 个元素时（即 i == n），比较次数为 0，即 $T(1) = 0$。
  • 对于规模为 $n$ 的问题，我们要用 for 循环寻找当前 $n$ 个元素中的最小值，需要进行 $(n-1)$ 次比较。然后针对剩下的 $n-1$ 个元素进行递归。
  • 由此得出严谨的递归方程：

    $$T(n) = T(n-1) + (n-1)$$

    $$T(1) = 0$$

• 求解与渐进复杂度： 不断展开这个方程： $T(n) = T(n-2) + (n-2) + (n-1)$$T(n) = T(n-3) + (n-3) + (n-2) + (n-1)$ ... $T(n) = T(1) + 1 + 2 + \dots + (n-2) + (n-1)$ 根据等差数列求和公式，总比较次数为 $\frac{n(n-1)}{2}$。
• 最坏时间复杂度： 无论数组原本是否有序，这套寻找最小值的循环必须雷打不动地执行完。因此，最坏时间复杂度（实际上也是最好和平均情况）均为 $O(n^2)$。

---

2. 题目内容

给定 $n$ 个矩阵 $A_1, A_2, \dots, A_n$，其中 $A_i$ 与 $A_{i+1}$ 保证是可乘的。不同的计算次序需要的乘法次数不同。用动态规划算法求解最小乘法次数，动态转移方程如下：

$$dp[i][j] = \begin{cases} 0 & i=j \\ \displaystyle\min_{i \le k < j}\{dp[i][k]+dp[k+1][j]+ p_{i-1} \cdot p_{k} \cdot p_{j}\} & i<j \end{cases}$$

(注：题目印刷中公式符号可能因版本有细微区别，但实质均为分段相乘代价)。给定矩阵规格对应 $p_0=5, p_1=10, p_2=3, p_3=12, p_4=5, p_5=50, p_6=6$：

1. 给出动态规划数组 $dp$ 及矩阵连乘的断点数组 $s$。（8分）
2. 写出最优的矩阵乘法运算顺序。（2分）

答案与深度解析

这道题是动态规划中经典的“矩阵连乘问题”，计算量大，我们需要严谨地列表步步为营。$n=6$，即 6 个矩阵连乘。维度向量 $p = [5, 10, 3, 12, 5, 50, 6]$。矩阵 $A_i$ 的维度是 $p_{i-1} \times p_i$。

1) 计算动态规划数组 $dp$ 和断点数组 $s$： 填表的顺序是按照链长（长度为 L）从小到大进行填写，这样我们在计算较长的链时，它所依赖的短链数据已经算好了。

• 长度 L = 1： 即单一矩阵，不需要乘法。对角线全部为 0。 $dp[1][1] = dp[2][2] = \dots = dp[6][6] = 0$

• 长度 L = 2： 两个相邻矩阵相乘，公式为 $p_{i-1} p_i p_{i+1}$，没有别的断点选择，断点 $s$ 即为左矩阵下标。

  • $dp[1][2] = p_0 \cdot p_1 \cdot p_2 = 5 \times 10 \times 3 = 150$，断点 $s[1][2]=1$
  • $dp[2][3] = p_1 \cdot p_2 \cdot p_3 = 10 \times 3 \times 12 = 360$，$s[2][3]=2$
  • $dp[3][4] = p_2 \cdot p_3 \cdot p_4 = 3 \times 12 \times 5 = 180$，$s[3][4]=3$
  • $dp[4][5] = p_3 \cdot p_4 \cdot p_5 = 12 \times 5 \times 50 = 3000$，$s[4][5]=4$
  • $dp[5][6] = p_4 \cdot p_5 \cdot p_6 = 5 \times 50 \times 6 = 1500$，$s[5][6]=5$

• 长度 L = 3： 试探断点 $k$ 取哪一边使得代价最小。

  • $dp[1][3] = \min \begin{cases} k=1: dp[1][1] + dp[2][3] + 5\times 10\times 12 = 0 + 360 + 600 = 960 \\ k=2: dp[1][2] + dp[3][3] + 5\times 3\times 12 = 150 + 0 + 180 = 330 \end{cases}$。最小值 330，$s[1][3]=2$。
  • $dp[2][4] = \min \begin{cases} k=2: 0 + 180 + 10\times 3\times 5 = 330 \\ k=3: 360 + 0 + 10\times 12\times 5 = 960 \end{cases}$。最小值 330，$s[2][4]=2$。
  • $dp[3][5] = \min \begin{cases} k=3: 0 + 3000 + 3\times 12\times 50 = 4800 \\ k=4: 180 + 0 + 3\times 5\times 50 = 930 \end{cases}$。最小值 930，$s[3][5]=4$。
  • $dp[4][6] = \min \begin{cases} k=4: 0 + 1500 + 12\times 5\times 6 = 1860 \\ k=5: 3000 + 0 + 12\times 50\times 6 = 6600 \end{cases}$。最小值 1860，$s[4][6]=4$。

• 长度 L = 4：

  • $dp[1][4] = \min \begin{cases} k=1: 0 + 330 + 5\times 10\times 5 = 580 \\ k=2: 150 + 180 + 5\times 3\times 5 = 405 \\ k=3: 330 + 0 + 5\times 12\times 5 = 630 \end{cases}$。最小值 405，$s[1][4]=2$。
  • $dp[2][5] = \min \begin{cases} k=2: 0 + 930 + 10\times 3\times 50 = 2430 \\ k=3: 360 + 3000 + 10\times 12\times 50 = 9360 \\ k=4: 330 + 0 + 10\times 5\times 50 = 2830 \end{cases}$。最小值 2430，$s[2][5]=2$。
  • $dp[3][6] = \min \begin{cases} k=3: 0 + 1860 + 3\times 12\times 6 = 2076 \\ k=4: 180 + 1500 + 3\times 5\times 6 = 1770 \\ k=5: 930 + 0 + 3\times 50\times 6 = 1830 \end{cases}$。最小值 1770，$s[3][6]=4$。

• 长度 L = 5：

  • $dp[1][5] = \min \begin{cases} k=1: 0 + 2430 + 2500 = 4930 \\ k=2: 150 + 930 + 750 = 1830 \\ k=3: 330 + 3000 + 3000 = 6330 \\ k=4: 405 + 0 + 1250 = 1655 \end{cases}$。最小值 1655，$s[1][5]=4$。
  • $dp[2][6] = \min \begin{cases} k=2: 0 + 1770 + 180 = 1950 \\ k=3: 360 + 1860 + 720 = 2940 \\ k=4: 330 + 1500 + 300 = 2130 \\ k=5: 2430 + 0 + 3000 = 5430 \end{cases}$。最小值 1950，$s[2][6]=2$。

• 长度 L = 6（全局最终解）：

  • $dp[1][6] = \min \begin{cases} k=1: 0 + 1950 + 5\times 10\times 6 = 2250 \\ k=2: 150 + 1770 + 5\times 3\times 6 = 2010 \\ k=3: 330 + 1860 + 5\times 12\times 6 = 2550 \\ k=4: 405 + 1500 + 5\times 5\times 6 = 2055 \\ k=5: 1655 + 0 + 5\times 50\times 6 = 3155 \end{cases}$。最小值 2010，$s[1][6]=2$。

填表结果如下：（此处为确保你能直观阅览，梳理为简表形式，行代表起点 $i$，列代表终点 $j$）

$i \backslash j$	1	2	3	4	5	6
1	0	150 (s=1)	330 (s=2)	405 (s=2)	1655 (s=4)	2010 (s=2)
2	-	0	360 (s=2)	330 (s=2)	2430 (s=2)	1950 (s=2)
3	-	-	0	180 (s=3)	930 (s=4)	1770 (s=4)
4	-	-	-	0	3000 (s=4)	1860 (s=4)
5	-	-	-	-	0	1500 (s=5)
6	-	-	-	-	-	0

2) 最优的矩阵乘法运算顺序： 我们利用求出的断点数组 $s$，从大范围不断往里拆解。

• 全局范围是 1 到 6，查表得知 $s[1][6] = 2$。说明第一刀切在第2个矩阵后。整体结构分为 $(A_1 A_2)$ 和 $(A_3 A_4 A_5 A_6)$。
• 对于左半边 $(A_1 A_2)$，毫无疑问就是直接相乘。
• 对于右半边范围 3 到 6，查表得知 $s[3][6] = 4$。说明这一刀切在第4个矩阵后。结构变为 $(A_3 A_4)$ 和 $(A_5 A_6)$。
• 合并所有括号。最终的最优运算顺序（加括号方式）为： $(A_1 A_2)((A_3 A_4)(A_5 A_6))$

---

3. 题目内容

在操作系统的单机作业调度问题中，$n$ 个作业同时提交给系统，每个作业需要 CPU 处理的时间分别为 $t_i$（$1 \le i \le n$）。

1. 请设计一种贪心策略对作业进行调度，使得所有作业的平均等待时间最短。（5分）
2. 证明该贪心策略满足贪心选择和最优子结构性质。（5分）

答案与深度解析

1) 贪心策略设计：

• 策略（短作业优先，SJF）： 将这 $n$ 个作业按照它们所需 CPU 处理时间 $t_i$ 进行**从小到大（升序）**排序，然后依次调度执行。
• 零基础理解： 想象去银行排队办业务，如果你办业务只需要 1 分钟，而前面站了一个需要办 1 小时的人，你是不是会觉得极其绝望（等待时间巨长）？为了让大家的总体体验最好（平均等待时间最短），银行正确的做法是让办事快的人先办。

2) 数学严格证明： 在进行证明之前，我们要先梳理一个公式： 假设调度顺序已经是 $1, 2, \dots, n$。 第 1 个作业无需等待，等待时间为 0。 第 2 个作业需等待第 1 个作业执行完毕，等待时间为 $t_1$。 第 3 个作业需等待前两个作业执行完，等待时间为 $t_1 + t_2$。 ... 总等待时间 $T = 0 + t_1 + (t_1 + t_2) + \dots + (t_1 + t_2 + \dots + t_{n-1})$。 稍微整理一下同类项，我们发现 $t_1$ 累加了 $n-1$ 次，$t_2$ 累加了 $n-2$ 次…… 所以，总等待时间 $T = (n-1)t_1 + (n-2)t_2 + \dots + 1 \cdot t_{n-1}$。 要使得“平均等待时间最短”，就等同于使得“总等待时间 $T$ 最小”。

• 贪心选择性质证明（运用交换论证法）： 假设我们的短作业优先策略产生的升序排列不是最优的。这意味着存在某个最优调度方案，在这个方案中，必定存在“逆序对”——也就是说，存在排在前面的某个作业 $i$，其处理时间比排在后面的作业 $j$ 更长（即存在某个排列次序使得靠前的位置 $x$ 和靠后的位置 $y$ 满足 $t_x > t_y$）。 在刚才推导的公式 $T$ 中，越排在前面的作业，它乘以的权重系数越大（$(n-x)$ 大于 $(n-y)$）。 如果我们将这个耗时较长的作业 $x$ 与耗时较短的作业 $y$ 交换位置。 新的总耗时相比旧的总耗时，变化量为：$\Delta T = (n-x)t_y + (n-y)t_x - [ (n-x)t_x + (n-y)t_y ] = (y-x)(t_x - t_y)$。 因为 $y > x$ 且 $t_x > t_y$，所以 $(y-x)(t_x - t_y) > 0$。 这意味着交换后总等待时间减小了。这与它原本是“最优方案”相矛盾。 因此，按照时间升序排列（贪心选择）必定包含在最优解中。
• 最优子结构性质证明： 假设我们按照贪心策略选出了耗时最短的作业 1。剩下的问题变成了：如何调度余下的 $n-1$ 个作业使得总等待时间最小。 根据公式推导 $T = (n-1)t_1 + [ (n-2)t_2 + (n-3)t_3 + \dots + 1 \cdot t_n ]$。 方括号内的部分，恰恰就是完全等价于剩下的 $n-1$ 个作业独立调度的总等待时间模型（只是常数项权重集体偏移）。 如果这剩下的 $n-1$ 个作业没有按照使方括号内总和最小的方式去排列，那么必定存在另一个排列能让方括号内的值更小，进而导致整体 $T$ 更小，这与原问题的最优性矛盾。 因此，原问题的最优解包含了子问题的最优解，满足最优子结构性质。

---

五、算法设计（每题10分，共20分）

1. 题目内容

设计递归算法求一个不带头节点的单链表长度。

1. 编写该算法。（5分）
2. 分析所涉及的算法的时间和空间复杂度。（5分）

答案与深度解析

1) 算法代码（C/C++语言表示）：

// 假设链表节点结构体定义如下：
// struct Node {
//     int data;
//     struct Node* next;
// };

int getListLength(struct Node* head) {
    // 基线条件：如果指针为空，说明走到了链表尽头（或本身是空链表），长度为0
    if (head == NULL) {
        return 0;
    }
    // 递归思想：当前链表的总长度 = 当前这 1 个节点 + 后续链表的长度
    return 1 + getListLength(head->next);
}

2) 复杂度分析：

• 时间复杂度分析： 该递归算法会从链表的首节点依次一直走到链表的末尾 NULL。如果链表长度为 $n$，函数就会被调用执行 $n+1$ 次。每一次函数调用内部只做了简单的指针判空与加法运算，耗时为 $O(1)$。因此总时间复杂度为 $O(n)$。
• 空间复杂度分析： 这一点极其容易被忽略。虽然代码里没有动态分配数组，但是系统执行递归是需要开辟“调用栈”的。每次函数调用，系统要保存局部变量、返回地址等信息到栈帧中。链表长度为 $n$，递归就会深入 $n+1$ 层，栈的最大深度就是 $n+1$。因此，空间复杂度同样为 $O(n)$。

---

2. 题目内容

利用动态规划法设计算法求两个字符串 $A$ 和 $B$ 的编辑距离。设 $A$ 和 $B$ 是两个字符串。所谓的编辑距离即将字符串 $A$ 转换成字符串 $B$ 所经历的最少编辑操作次数。编辑操作共有 3 种：(1) 删除一个字符 delete；(2) 插入一个字符 insert；(3) 将一个字符替换另一个字符 replace。

1. 设计动态规划数组 $dp[i][j]$（将长度为 $i$ 的字符串 $A$ 转换成长度为 $j$ 的字符串 $B$ 的最少编辑操作次数）并给出其动态转移方程。（5分）
2. 编写该算法。（5分）

答案与深度解析

这是一道经典的“莱文斯坦距离（Levenshtein Distance）”算法设计题。我们一步步从基础进行设计：

1) DP 数组设计与动态转移方程推导：

• 数组定义： dp[i][j] 表示将字符串 $A$ 的前 $i$ 个字符转换成字符串 $B$ 的前 $j$ 个字符所需的最少编辑次数。
• 核心逻辑（从零理解为什么这么转移）： 比较 $A$ 的第 $i$ 个字符（A[i-1]）和 $B$ 的第 $j$ 个字符（B[j-1]）：
  • 情况一：两者相等（A[i-1] == B[j-1]）。运气好，最后一个字符不用作任何处理。当前所需的编辑距离与它们都不包含各自最后一个字符时的距离一模一样。 即：dp[i][j] = dp[i-1][j-1]
  • 情况二：两者不等（A[i-1] != B[j-1]）。既然最后一个字符匹配不上，我们就必须得动手实施三种操作之一，实施任意一次操作代价都为 1：
    • 如果执行“替换”： 我们把 $A$ 的最后一个字符强制替换成 $B$ 的最后一个字符。替换完成后，这两者的末尾对齐了。那么之前的任务就是把 $A$ 的前 $i-1$ 变成 $B$ 的前 $j-1$。此时代价为：dp[i-1][j-1] + 1。
    • 如果执行“删除”： 我们把 $A$ 的最后一个字符删掉。这就指望 $A$ 的前 $i-1$ 个字符自己能够变幻成 $B$ 的前 $j$ 个字符。此时代价为：dp[i-1][j] + 1。
    • 如果执行“插入”： 我们在 $A$ 的末尾无中生有地插入一个与 $B$ 末尾一样的字符。末尾对齐后，我们需要将 $A$ 的前 $i$ 个字符变幻成 $B$ 的前 $j-1$ 个字符。此时代价为：dp[i][j-1] + 1。 我们需要从中选择花费最小的一条路径：min(替换代价, 删除代价, 插入代价)。
• 边界条件： 如果 $A$ 长度为 0，$B$ 长度为 $j$，要想转变过去，只能无脑插入 $j$ 次。dp[0][j] = j。 如果 $B$ 长度为 0，$A$ 长度为 $i$，要想转变过去，只能无脑删除 $i$ 次。dp[i][0] = i。
• 严谨的动态转移方程：

  $$dp[i][j] = \begin{cases} i & j = 0 \\ j & i = 0 \\ dp[i-1][j-1] & A[i-1] = B[j-1] \\ \min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1 & A[i-1] \neq B[j-1] \end{cases}$$

2) 算法代码（C/C++实现）：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

// 获取三个数中最小值的辅助函数
int getMin(int a, int b, int c) {
    return min(min(a, b), c);
}

int minDistance(string A, string B) {
    int m = A.length();
    int n = B.length();
    
    // 创建二维动态规划数组，并初始化全为 0
    // 注意数组维度是 (m+1) x (n+1)，因为我们要容纳前缀长度为0（空串）的情况
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
    
    // 初始化边界条件
    for (int i = 0; i <= m; i++) {
        dp[i][0] = i; // B为空串，A必须不断执行删除
    }
    for (int j = 0; j <= n; j++) {
        dp[0][j] = j; // A为空串，A必须不断执行插入
    }
    
    // 使用状态转移方程逐行填表
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            // 注意：第 i 个字符在字符串中的索引是 i-1
            if (A[i - 1] == B[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1]; // 字符相同，无需操作代价
            } else {
                dp[i][j] = 1 + getMin(
                    dp[i - 1][j - 1], // 替换 (Replace)
                    dp[i - 1][j],     // 删除 (Delete)
                    dp[i][j - 1]      // 插入 (Insert)
                );
            }
        }
    }
    
    // 表格右下角的值即为全局最小操作次数
    return dp[m][n];
}