《算法设计与分析》期末试卷A (精选02)

一、计算复杂性分析（每题 10 分，共 30 分）

1. 若 (f(n)=\log_2(n^2))，(g(n)=\log_2 n+5)，分析并确定 (f(n)=O(g(n))) 或 (f(n)=\Omega(g(n))) 或 (f(n)=\Theta(g(n)))，并简述理由。

查看答案与解析

答案：(f(n)=\Theta(g(n)))。

解析：

• 第一步：化简 (f(n))
  [ f(n)=\log_2(n^2)=2\log_2 n ]

• 第二步：比较增长阶
  (g(n)=\log_2 n+5)，常数 5 不改变对数函数的渐进阶，因此 (g(n)=\Theta(\log n))。而 (f(n)=2\log_2 n=\Theta(\log n))。

• 第三步：用极限作严格比较（可选）
  [ \lim_{n\to\infty}\frac

  \lim_{n\to\infty}\frac{2\log_2 n}{\log_2 n+5}

  2 ] 极限为正常数 (2)，故 (f(n)) 与 (g(n)) 同阶：(f(n)=\Theta(g(n)))。

---

难度: ⭐
考点: #渐进复杂度 #O记号 #Theta #对数函数

💡 学习锦囊

📖 相关公式与知识点

• (\log(n^k)=k\log n)（同一对数底）
• 若 (\lim_{n\to\infty}\frac{f(n)}{g(n)}=c\in(0,\infty))，则 (f(n)=\Theta(g(n)))
• 对任何常数 (C)，有 (\log n + C = \Theta(\log n))

思路分析

先把函数化简到常见的 (\log n)、(n^k)、(a^n) 等形式，再用"常数项不影响渐进阶"和"极限判别同阶"快速判断。

易错点

• 把 (\log(n^2)) 误写成 ((\log n)^2)
• 忽略 (\Theta) 判别条件，误把同阶当作 (O) 或 (\Omega) 的单向关系

🔄 举一反三

1. 比较 (f(n)=\log_2(n^3)) 与 (g(n)=10\log_2 n - 7) 的渐进关系。
   查看练习答案与解析

   答案：(f(n)=\Theta(g(n)))。
   解析：(f(n)=3\log_2 n)，(g(n)=10\log_2 n-7=\Theta(\log n))。两者均为 (\Theta(\log n))，且极限 (\lim \frac{3\log n}{10\log n-7}=\frac{3}{10}\in(0,\infty))，故同阶。

2. 判断 (f(n)=\log(n)) 与 (g(n)=\log(n)+\log\log(n)) 的关系。
   查看练习答案与解析

   答案：(f(n)=\Theta(g(n)))。
   解析：(\log\log n=o(\log n))，因此 (g(n)=\log n(1+o(1)))，同阶。

2. 计算下面 C 程序片段嵌套循环里 laugh++ 语句的执行次数（用 (n) 表示）：

for (i = 1; i <= n; i *= 2)
  for (j = 1; j <= i; j++)
    laugh++;

查看答案与解析

答案：执行次数为 (\sum_{k=0}^{\lfloor\log_2 n\rfloor}2^k=2^{\lfloor\log_2 n\rfloor+1}-1)，渐进为 (\Theta(n))。

解析：

• 第一步：刻画外层循环的 (i) 取值
  外层令 (i) 每次乘 2：(1,2,4,\dots,2^m)，其中 (2^m\le n<2^{m+1})，所以 (m=\lfloor\log_2 n\rfloor)。

• 第二步：内层循环次数
  当外层 (i=2^k) 时，内层 (j) 从 1 到 (i)，执行 (i=2^k) 次。

• 第三步：求总次数
  [ T(n)=\sum_{k=0}^{m}2^k=2^{m+1}-1 ] 因为 (2^m\le n<2^{m+1})，得 [ n \le 2^{m+1} < 2n \Rightarrow n-1 \le T(n) < 2n-1 ] 所以 (T(n)=\Theta(n))。

---

难度: ⭐⭐
考点: #循环复杂度 #等比数列求和 #对数迭代

💡 学习锦囊

📖 相关公式与知识点

• 若 (i) 以倍增方式变化，循环次数约为 (\log n)
• 等比数列求和：(\sum_{k=0}^{m}2^k=2^{m+1}-1)

思路分析

先把"外层取值序列"写成 (2^k) 的形式，再把内层执行次数写成关于 (k) 的表达式，最后做一次求和即可。

易错点

• 把外层循环次数误认为是 (n) 次（忽略倍增）
• 只写 (\Theta(n)) 不写精确求和式（题目要求"执行次数"）

🔄 举一反三

1. 若内层改为 for (j = 1; j <= n; j++)，此时 laugh++ 执行次数是多少？
   查看练习答案与解析

   答案：(\Theta(n\log n))。
   解析：外层约 (\lfloor\log_2 n\rfloor+1) 次，每次内层 (n) 次，总计 (n(\lfloor\log_2 n\rfloor+1))。

2. 若外层改为 for (i = 1; i <= n; i *= 3)，并保留内层 j <= i，总次数渐进为何？
   查看练习答案与解析

   答案：(\Theta(n))。
   解析：总和为 (1+3+3^2+\dots+3^m=\frac{3^{m+1}-1}{2})，且 (3^m\le n<3^{m+1})，同理得 (\Theta(n))。

3. 递归式 (T(n)=3T(n/2)+O(n))（(T(n)) 表示长度为 (n) 位的乘法运算时间），求该递归式的解。

查看答案与解析

答案：(T(n)=\Theta!\left(n^{\log_2 3}\right))。

解析（主定理）：

• 第一步：对齐主定理形式
  [ T(n)=aT(n/b)+f(n) ] 其中 (a=3)，(b=2)，(f(n)=O(n))。

• 第二步：计算临界函数
  [ n^{\log_b a}=n^{\log_2 3}\approx n^{1.585} ]

• 第三步：比较 (f(n)) 与 (n^{\log_b a})
  因为 (f(n)=O(n))，且存在 (\varepsilon=\log_2 3-1>0)，有 [ f(n)=O!\left(n^{\log_2 3-\varepsilon}\right) ] 满足主定理 Case 1。

• 结论
  [ T(n)=\Theta!\left(n^{\log_2 3}\right) ]

---

难度: ⭐⭐
考点: #主定理 #递归式求解 #分治复杂度

💡 学习锦囊

📖 相关公式与知识点

• 主定理：比较 (f(n)) 与 (n^{\log_b a}) 来判别递归阶
• 常见对数：(\log_2 3\approx 1.585)

思路分析

先算 (n^{\log_b a}) 再比 (f(n))。多数题只要识别属于三种 Case 的哪一种即可快速给出渐进解。

易错点

• 把 (\log_b a) 算反（写成 (\log_a b)）
• 忘记写 (\Theta)（只写 (O) 会丢分）

🔄 举一反三

1. 求 (T(n)=2T(n/2)+O(n)) 的解。
   查看练习答案与解析

   答案：(\Theta(n\log n))。
   解析：(a=2,b=2\Rightarrow n^{\log_2 2}=n)，与 (f(n)=\Theta(n)) 相同，属 Case 2。

2. 求 (T(n)=4T(n/2)+O(n^2)) 的解。
   查看练习答案与解析

   答案：(\Theta(n^2\log n))。
   解析：(n^{\log_2 4}=n^2)，与 (f(n)=\Theta(n^2)) 相同，属 Case 2。

---

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

1. 简述算法与程序的差异。

查看答案与解析

答案要点：

• 算法：对求解问题步骤的抽象描述（与语言/平台无关），强调正确性、有限性、确定性、可行性与复杂度。
• 程序：算法在某种语言/环境下的具体实现，包含语法细节、输入输出、数据结构、异常处理、工程组织等。

解析（可展开阐述）：

• 同一算法可用多种语言实现为不同程序；
• 程序除了算法，还包含工程约束（内存管理、库调用、I/O、边界检查、性能调优等）；
• 一个程序可能包含多个算法模块。

---

难度: ⭐
考点: #算法概念 #程序实现 #抽象与实现

💡 学习锦囊

📖 相关公式与知识点

• 算法五要素（常见表述）：输入、输出、确定性、可行性、有限性（以及正确性）

思路分析

先用一句话分别下定义，再用"语言无关 vs 语言相关""抽象步骤 vs 工程实现"给出 2-3 个对比点即可。

易错点

• 把算法和程序混为一谈，忽略"抽象描述"与"具体实现"的本质区别
• 忘记提及算法的"有限性"特征

🔄 举一反三

1. 请举例说明"同一算法的不同程序实现"。
   查看练习答案与解析

   答案示例：快速排序算法可分别用 C/C++、Java、Python 实现。
   解析：算法核心（分区与递归）不变，但语言层面的数组/列表操作、递归栈限制、随机化策略与性能优化不同，形成不同程序实现。

2. 简述贪心算法与动态规划算法的区别与联系。

查看答案与解析

答案要点：

• 联系：都用于求最优化问题；都依赖"问题结构"（最优子结构等）。
• 贪心：每步做当前看起来最优的局部选择，不回头；要求"贪心选择性质"成立才能保证全局最优。
• 动态规划：把问题拆成重叠子问题，保存子问题最优解并组合成整体最优；通常要求"最优子结构 + 重叠子问题"，可通过转移方程与边界条件保证正确性。

解析（常见对比维度）：

• 正确性：贪心要证明"局部最优 ⇒ 全局最优"；DP 用状态定义与转移证明覆盖所有方案。
• 复杂度：贪心常为 (O(n\log n)) 或 (O(n))；DP 常为多项式但可能更大（如 (O(n^2))、(O(n^3))）。
• 例子：活动选择（贪心）；0-1 背包（DP）。

---

难度: ⭐⭐
考点: #贪心 #动态规划 #最优子结构 #重叠子问题

💡 学习锦囊

📖 相关公式与知识点

• 贪心选择性质：存在最优解以某一步的贪心选择开头
• DP 三要素：状态、转移、边界（初始化）

思路分析

先给出"能否保证最优"的判别条件，再用一两个经典反例（如 0-1 背包贪心不一定最优）强化区别。

易错点

• 混淆"最优子结构"（两者都需要）与"贪心选择性质"（仅贪心需要）
• 忘记说明贪心"不回头"的特点

🔄 举一反三

1. 为什么"分数背包"适合贪心而"0-1 背包"通常不适合？
   查看练习答案与解析

   答案：分数背包允许拆分物品，按单位价值贪心可逐步构造最优；0-1 背包不可拆分，局部按单位价值选取可能导致后续空间浪费，不能保证全局最优。
   解析：关键差别在于可分性改变了可行解空间的结构，使贪心选择性质成立与否发生变化。

3. 以棋盘覆盖为例简述分治法基本思想。

查看答案与解析

答案要点（以经典"缺一格棋盘覆盖"为例）：

• 分：把 (2^k\times 2^k) 棋盘划分为 4 个 (2^{k-1}\times 2^{k-1}) 子棋盘；缺失格只落在其中一个子棋盘。
• 治：在棋盘中心放置一个 L 形骨牌，使另外 3 个子棋盘各"人为制造"一个缺格。
• 递归：对 4 个子棋盘分别递归覆盖；当子棋盘规模为 (2\times 2) 时直接放置骨牌作为基本情形。
• 合：递归完成后整体覆盖完成。

---

难度: ⭐⭐
考点: #分治法 #递归 #棋盘覆盖

💡 学习锦囊

📖 相关公式与知识点

• 分治三步：Divide（分解）/Conquer（解决子问题）/Combine（合并）
• 递归设计算法：明确"规模参数""基本情形""递归调用""合并策略"

思路分析

用"中心放一块 L 形骨牌"这一步作为核心记忆点：它把一个缺格问题转成 4 个同类子问题，从而递归成立。

易错点

• 忘记说明"人为制造缺格"这一关键步骤
• 未明确基本情形（(2\times 2) 棋盘）

🔄 举一反三

1. 若棋盘规模为 (8\times 8)（即 (k=3)），分治递归深度是多少？
   查看练习答案与解析

   答案：3 层（从 (8\to 4\to 2)）。
   解析：每次规模减半，直到 (2\times 2) 作为基本情形，共 (k) 层。

4. 简述回溯法与分支限界法的差异。

查看答案与解析

答案要点：

• 共同点：都是在解空间树上搜索，利用剪枝减少搜索量。
• 回溯法：深度优先（DFS）为主，通常用于找可行解/全部解或最优解；剪枝依据可行性（约束）与部分最优性。
• 分支限界法：广度优先或按"最有希望结点"（优先队列）搜索，用上下界（bound）剪枝，主要用于最优化问题，倾向于尽快找到最优解并证明最优。

---

难度: ⭐⭐
考点: #回溯法 #分支限界 #剪枝 #解空间树

💡 学习锦囊

📖 相关公式与知识点

• 回溯：可行性剪枝（不满足约束则回退）
• 分支限界：界函数（上界/下界）+ 结点选择策略（FIFO/LIFO/最小代价优先）

思路分析

抓住一句话：回溯"先走到底再回头"（DFS），分支限界"按界最优先扩展"（Best-first），两者剪枝依据也不同。

易错点

• 混淆两者的搜索策略（回溯=DFS，分支限界=Best-first/BFS）
• 忘记说明分支限界主要用于"最优化问题"

🔄 举一反三

1. 0-1 背包问题用分支限界法时，"界"常如何构造？
   查看练习答案与解析

   答案：常用"分数背包上界"作为界。
   解析：对当前部分装包的结点，允许把剩余容量用单位价值最高的物品按"可分"方式装满，得到一个不低于真实最优值的上界，用于剪枝。

---

三、程序设计题（每小题 10 分，共 20 分）

1. 设 a[0..n-1] 是已排好序的数组。改写二分搜索算法：当搜索元素 (x) 不在数组中时，返回小于 (x) 的最大元素位置 (i) 和大于 (x) 的最小元素位置 (j)；当 (x) 在数组中时，(i=j) 均为 (x) 在数组中的位置。给出简要源码。

查看答案与解析

答案（示例实现，C 语言）：

// 若存在 x，则 *i = *j = 其下标
// 若不存在 x，则 *i 为前驱下标（可能为 -1），*j 为后继下标（可能为 n）
void binary_search_neighbors(const int *a, int n, int x, int *i, int *j) {
  int l = 0, r = n;              // 在 [l, r) 上找 lower_bound
  while (l < r) {
    int m = l + (r - l) / 2;
    if (a[m] < x) l = m + 1;
    else r = m;
  }

  // 此时 l 为第一个满足 a[l] >= x 的位置（或 l == n）
  if (l < n && a[l] == x) {
    *i = l;
    *j = l;
    return;
  }

  *j = l;        // 后继：第一个 >= x 的位置（可能为 n 表示不存在）
  *i = l - 1;    // 前驱：最后一个 < x 的位置（可能为 -1 表示不存在）
}

解析：

• 第一步：把问题转为 lower_bound
  找到数组中第一个满足 (a[pos]\ge x) 的位置 pos。
• 第二步：分类讨论
  • 若 pos<n && a[pos]==x，说明命中，返回 i=j=pos。
  • 否则 pos 是后继下标（第一个大于 (x) 的位置），前驱下标为 pos-1。
• 第三步：边界处理
  • 若 (x) 小于所有元素，则 pos=0，前驱为 (-1)。
  • 若 (x) 大于所有元素，则 pos=n，后继为 (n)（可用作"不存在"的哨兵）。

---

难度: ⭐⭐
考点: #二分查找 #lower_bound #边界处理

💡 学习锦囊

📖 相关公式与知识点

• lower_bound：返回第一个满足 (a[pos]\ge x) 的位置
• 上下界常用半开区间 ([l,r)) 表示，边界更稳健

思路分析

将问题转化为寻找 lower_bound（第一个大于等于 (x) 的位置），然后根据是否命中 (x) 分类讨论。

易错点

• 返回"值"而非"下标"
• 忘记处理 (x) 比最小值还小/比最大值还大时的前驱或后继

🔄 举一反三

1. 若要返回"严格大于 (x)" 的最小元素（upper_bound），应如何修改判断条件？
   查看练习答案与解析

   答案：在二分中把条件改为 if (a[m] <= x) l = m + 1; else r = m;，最终 l 即第一个 (a[pos] > x) 的位置。
   解析：upper_bound 与 lower_bound 的唯一区别是比较符号把 < 换成 <=。

2. 分析如何使用动态规划法解决最长公共子序列（LCS）问题，并给出简要源码。

查看答案与解析

答案（核心思路 + 示例实现）：

解析（DP 建模）：

• 状态定义：令 (dp[i][j]) 表示字符串 (X) 的前 (i) 个字符与字符串 (Y) 的前 (j) 个字符的 LCS 长度。
• 转移方程：
  • 若 (X[i-1]=Y[j-1])，则 [ dp[i][j]=dp[i-1][j-1]+1 ]
  • 否则 [ dp[i][j]=\max(dp[i-1][j],dp[i][j-1]) ]
• 边界条件：(dp[0][j]=dp[i][0]=0)。
• 答案：(dp[m][n])。

源码（C 语言，返回长度；如需输出序列可用 parent 指针回溯）：

#include <stdlib.h>
#include <string.h>

int lcs_len(const char *x, const char *y) {
  int m = (int)strlen(x);
  int n = (int)strlen(y);
  int *dp = (int *)calloc((m + 1) * (n + 1), sizeof(int));
  if (!dp) return -1;

  for (int i = 1; i <= m; i++) {
    for (int j = 1; j <= n; j++) {
      int *cell = &dp[i * (n + 1) + j];
      int up = dp[(i - 1) * (n + 1) + j];
      int left = dp[i * (n + 1) + (j - 1)];
      int diag = dp[(i - 1) * (n + 1) + (j - 1)];

      if (x[i - 1] == y[j - 1]) *cell = diag + 1;
      else *cell = (up > left) ? up : left;
    }
  }

  int ans = dp[m * (n + 1) + n];
  free(dp);
  return ans;
}

---

难度: ⭐⭐
考点: #动态规划 #最长公共子序列 #状态转移

💡 学习锦囊

📖 相关公式与知识点

• 典型二维 DP：行列分别代表两个前缀
• 时间复杂度：(O(mn))，空间复杂度：(O(mn))（可优化到 (O(\min(m,n)))）

思路分析

先想"比较两个前缀"的自然递推：末字符相等就继承对角线并 +1；不相等就从"丢掉一个末字符"的两种情况取最大。

易错点

• 状态定义时忘记处理下标偏移（(X[i-1]) 对应 (dp[i])）
• 边界条件未初始化为 0

🔄 举一反三

1. 如何把 LCS 的空间从 (O(mn)) 优化到 (O(n))？
   查看练习答案与解析

   答案：用滚动数组只保留上一行与当前行（或一维数组配合保存对角线旧值）。
   解析：(dp[i][j]) 只依赖 (dp[i-1][j])、(dp[i][j-1])、(dp[i-1][j-1])，因此无需保留全部二维表。

---

四、程序分析题（每小题 15 分，共 30 分）

1. 有 7 个独立作业 ({1,2,3,4,5,6,7}) 由三台机器 (M_1,M_2,M_3) 加工处理。各作业处理时间分别为 ({2,14,4,16,6,5,3})。使用贪心算法策略给出作业调度安排过程，并计算所需加工时间。

查看答案与解析

答案（采用 LPT：按处理时间从大到小，依次分配给当前负载最小的机器）：

将作业按时间降序排序：
((4:16),(2:14),(5:6),(6:5),(3:4),(7:3),(1:2))（括号中"作业号:时间"）

分配过程：

• 初始：(M_1=0,M_2=0,M_3=0)
• 分配 (16)：(M_1\leftarrow{4})，负载 (16)
• 分配 (14)：(M_2\leftarrow{2})，负载 (14)
• 分配 (6)：(M_3\leftarrow{5})，负载 (6)
• 分配 (5)：给最小负载 (M_3)：(M_3\leftarrow{5,6})，负载 (11)
• 分配 (4)：给最小负载 (M_3)：(M_3\leftarrow{5,6,3})，负载 (15)
• 分配 (3)：给最小负载 (M_2)：(M_2\leftarrow{2,7})，负载 (17)
• 分配 (2)：给最小负载 (M_3)：(M_3\leftarrow{5,6,3,1})，负载 (17)

最终调度：

• (M_1)：作业 ({4})，总时长 (16)
• (M_2)：作业 ({2,7})，总时长 (14+3=17)
• (M_3)：作业 ({5,6,3,1})，总时长 (6+5+4+2=17)

所需加工时间（完工时间/工期 makespan）：(\max(16,17,17)=17)。

---

难度: ⭐⭐
考点: #贪心调度 #并行机调度 #LPT #makespan

💡 学习锦囊

📖 相关公式与知识点

• List Scheduling：按某种顺序把任务依次丢给当前最空闲机器
• LPT（Longest Processing Time first）通常比随机顺序更稳健

思路分析

先排序再依次分配到当前负载最小的机器，是贪心调度的典型应用。

易错点

• 不排序直接分配导致过程不清晰
• 最终只给答案不写分配过程（题目要求"安排过程"）

🔄 举一反三

1. 若改用"SPT（短作业优先）"顺序进行同样的 list scheduling，makespan 可能变大吗？
   查看练习答案与解析

   答案：可能变大。
   解析：SPT 可能把大作业推迟到后面，导致某台机器尾部出现大作业拖尾，从而增大最大完工时间；LPT 通过先放大作业通常能减少拖尾风险。

2. 给定带权有向图 (G=(V,E)) 如下图，源点为 (A)。使用分支限界法求从 (A) 到其他各点的最短路径长度（路径长度为边权之和）。

查看答案与解析

答案（最短距离与一条对应最短路径）：

• (d(A)=0)
• (d(B)=4)，路径 (A\to B)
• (d(C)=2)，路径 (A\to C)
• (d(D)=5)，路径 (A\to D)
• (d(E)=7)，路径 (A\to D\to E)
• (d(F)=9)，路径 (A\to B\to F)
• (d(G)=12)，路径 (A\to D\to G)
• (d(H)=11)，路径 (A\to D\to E\to H)
• (d(I)=15)，路径 (A\to D\to G\to I)
• (d(J)=15)，路径 (A\to B\to F\to J)

解析（用"界最小优先"扩展结点，等价于按当前最小代价扩展的最短路过程）：

• 从 (A) 出发初始化：
  (d(B)=4, d(C)=2, d(D)=5)，其他为 (\infty)
• 扩展当前最小的 (C(2))：
  由 (C\to F(9))，得候选 (d(F)=2+9=11)
• 扩展 (B(4))：
  (B\to E(7)\Rightarrow d(E)\le 4+7=11)；(B\to F(5)\Rightarrow d(F)\le 4+5=9)（更新为 9）
• 扩展 (D(5))：
  (D\to E(2)\Rightarrow d(E)\le 5+2=7)（更新为 7）；(D\to G(7)\Rightarrow d(G)=12)
• 扩展 (E(7))：
  (E\to H(4)\Rightarrow d(H)=11)
• 扩展 (F(9))：
  (F\to H(3)\Rightarrow) 候选 (12)（不优于 11）；(F\to J(6)\Rightarrow d(J)=15)
• 扩展 (H(11))：
  (H\to J(7)\Rightarrow) 候选 (18)（不优于 15）
• 扩展 (G(12))：
  (G\to I(3)\Rightarrow d(I)=15)
• 扩展 (I(15))：
  (I\to J(8)\Rightarrow) 候选 (23)（不优于 15）

最终得到上述最短距离。

---

难度: ⭐⭐⭐
考点: #分支限界 #最短路径 #图算法 #界函数

💡 学习锦囊

📖 相关公式与知识点

• 当以"当前路径代价"作为下界并优先扩展最小下界结点时，过程与 Dijkstra 的"最小距离优先"一致
• 松弛（relax）：若 (d(u)+w(u,v)<d(v)) 则更新 (d(v))

思路分析

把"分支限界"理解为：每次扩展当前代价（下界）最小的部分路径；当某结点的最小代价已确定，就不可能再被更小的路径改写。

易错点

• 忘记方向（有向边）导致路径误用
• 混淆边权与结点代价，更新时漏加权值

🔄 举一反三

1. 若把边权都加上同一个常数 (+c)，最短路径的"路径条数（边数）偏好"会发生什么变化？
   查看练习答案与解析

   答案：会更偏向于边数更少的路径。
   解析：每条边都会额外增加 (c)，两条原本权和接近的路径中，边数少的增加得更少，更可能成为最短。