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

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

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

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

姓名: ____________________   日期: ____________

1.简单

哪种记号表示增长的上界？

  1. ABig Theta
  2. BLittle omega
  3. CBig O
  4. DBig Omega
2.简单

一个包含两层嵌套循环、每层都执行 n 次的算法，通常具有哪种复杂度？

  1. AO(log n)
  2. BO(n²)
  3. CO(2n)
  4. DO(n)
3.简单

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

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

在活动选择问题中，哪条贪心规则总能得到数量最多的互不重叠的活动？

  1. A先选择最短的活动
  2. B选择最早开始的活动
  3. C先选择与其他活动重叠最少的活动，然后在与之相容的活动中重复这一步
  4. D选择最早结束的活动，然后在与之相容的活动中重复这一步
5.中等

用标准的三重循环计算两个 n × n 矩阵的乘积，时间复杂度是多少？

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

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

  1. AO(V × E)
  2. BO(E log V)
  3. CO(V³ × E)
  4. DO(V + E)
7.困难

当 n 很大时，n! 与 2ⁿ 相比如何？

  1. A两者以相同的速率增长
  2. B2ⁿ 比 n! 增长得快
  3. Cn! 比 2ⁿ 增长得快
  4. Dn! 是 O(n²)
8.困难

要证明一个判定问题 X 是 NP 完全的，必须证明哪两点？

  1. AX 没有多项式算法，并且 X 是可判定的
  2. BX 能归约到 P 中的某个问题，并且 X 属于 NP
  3. CX 属于 P，并且 X 能归约到 SAT
  4. DX 属于 NP，并且某个已知的 NP 完全问题能在多项式时间内归约到 X

答案

  1. 1. C · Big O
  2. 2. B · O(n²)
  3. 3. B · f 与 g 以相同的速率增长，上下都被 g 的常数倍所界定
  4. 4. D · 选择最早结束的活动，然后在与之相容的活动中重复这一步
  5. 5. A · O(n³)
  6. 6. A · O(V × E)
  7. 7. C · n! 比 2ⁿ 增长得快
  8. 8. D · X 属于 NP，并且某个已知的 NP 完全问题能在多项式时间内归约到 X

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