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

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

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

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

姓名: ____________________   日期: ____________

1.简单

f(n) = Θ(g(n)) 是什么意思？

  1. Af 的增长严格慢于 g
  2. B对每个 n，f 总是小于 g，因此 g 是它的上界，但绝不是下界
  3. Cf 的增长严格快于 g
  4. Df 与 g 以相同的速率增长，上下都被 g 的常数倍所界定
2.简单

什么是记忆化（memoisation）？

  1. A自动把递归转换为等价的循环，从而不需要调用栈
  2. B存储函数调用的结果，使重复调用能直接从内存中得到答案
  3. C在每行代码旁边写注释
  4. D函数返回后释放内存
3.简单

在以邻接表存储的图上进行深度优先搜索，时间复杂度是多少？

  1. AO(E log V)
  2. BO(V²)
  3. CO(V + E)
  4. DO(V × E)
4.中等

在有 V 个顶点、E 条边的图上，Bellman–Ford 算法的时间复杂度是多少？

  1. AO(V³ × E)
  2. BO(V + E)
  3. CO(V × E)
  4. DO(E log V)
5.中等

用自底向上的表格计算第 n 个斐波那契数，时间复杂度是多少？

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

在一个有序数组中，你从两端各放一个指针向内移动，寻找和为目标值的两个元素。时间复杂度是多少？

  1. AO(n)
  2. BO(n²)
  3. CO(log n)
  4. DO(n log n)
7.困难

下列哪个可满足性问题已知可以在多项式时间内求解？

  1. A电路可满足性问题
  2. B2-SAT，每个子句至多有两个文字
  3. C合取范式公式上的一般 SAT
  4. D3-SAT，每个子句恰好有三个文字
8.困难

一个问题是 NP 完全（NP-complete）的，当且仅当它：

  1. A不可能被解决
  2. B可以在多项式时间内解决
  3. C属于 NP，且所有 NP 问题都能在多项式时间内归约到它
  4. D不属于 NP，但比所有 NP 问题都难，例如停机问题

答案

  1. 1. D · f 与 g 以相同的速率增长，上下都被 g 的常数倍所界定
  2. 2. B · 存储函数调用的结果，使重复调用能直接从内存中得到答案
  3. 3. C · O(V + E)
  4. 4. C · O(V × E)
  5. 5. B · O(n)
  6. 6. A · O(n)
  7. 7. B · 2-SAT，每个子句至多有两个文字
  8. 8. C · 属于 NP，且所有 NP 问题都能在多项式时间内归约到它

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