算法与复杂度练习卷（附答案）

免费可打印的算法与复杂度练习卷：8 道题，从简单到考试水平，附答案。可打印或另存为 PDF。

新练习卷在线练习，附提示

教师请注意： 可免费打印、复印并在课堂上使用。每份新练习题都有新的数值和独立的答案。欢迎在课程页面添加指向 ExamProblems 的链接。

姓名: ____________________   日期: ____________

1.简单

平均情况运行时间描述的是什么？

  1. A平均长度的输入所需的时间
  2. B在最常见的计算机上所需的时间
  3. C在给定的规模为 n 的输入分布上的期望时间
  4. D最好情况与最坏情况运行时间之间的中间值
2.简单

O(2ⁿ) 的增长称为什么？

  1. A线性
  2. B多项式级
  3. C对数级
  4. D指数级
3.简单

通过下标访问数组中的元素需要：

  1. AO(n)
  2. BO(1)
  3. CO(n²)
  4. DO(log n)
4.中等

递推式 T(n) = 2T(n/2) + O(1) 的解是什么？

  1. AO(n log n)
  2. BO(log n)
  3. CO(n²)
  4. DO(n)
5.中等

硬币面值为 1、3 和 4，金额为 6，贪心的"先取最大硬币"方法使用多少枚硬币？与最优解相比如何？

  1. A贪心用 3 枚；最优解是 2 枚
  2. B贪心用 3 枚；最优解是 3 枚
  3. C贪心用 4 枚；最优解是 3 枚
  4. D贪心用 2 枚；最优解是 2 枚
6.中等

Floyd–Warshall 算法计算什么？速度如何？

  1. A以 O(E log V) 计算最小生成树
  2. B以 O(V + E) 计算从一个源顶点到所有其他顶点的最短路径
  3. C以 O(V³) 计算所有顶点对之间的最短路径
  4. D以 O(V²) 计算拓扑序
7.困难

Cook–Levin 定理确立了什么？

  1. A每个 NP 问题都能在指数时间内求解
  2. BP 不等于 NP
  3. C停机问题是不可判定的
  4. D布尔可满足性问题（SAT）是 NP 完全的
8.困难

对于哪种背包问题变体，贪心规则"按单位重量价值的顺序取物品"总能给出最优解？

  1. A两种变体都可以
  2. B0/1 背包问题，物品必须整个拿取
  3. C两种变体都不可以
  4. D分数背包问题，物品可以分割

答案

  1. 1. C · 在给定的规模为 n 的输入分布上的期望时间
  2. 2. D · 指数级
  3. 3. B · O(1)
  4. 4. D · O(n)
  5. 5. A · 贪心用 3 枚；最优解是 2 枚
  6. 6. C · 以 O(V³) 计算所有顶点对之间的最短路径
  7. 7. D · 布尔可满足性问题（SAT）是 NP 完全的
  8. 8. D · 分数背包问题，物品可以分割

完整分步解答：请在 examproblems.com 上练习本主题。