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

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

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

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

姓名: ____________________   日期: ____________

1.简单

归并排序的最坏情况时间复杂度是多少？

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

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

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

一个 O(n²) 算法在 n = 1000 时需要 1 秒。n = 2000 时大约需要多长时间？

  1. A8 秒
  2. B2 秒
  3. C4 秒
  4. D1 秒
4.中等

贪心算法（greedy algorithm）：

  1. A总能给出最优解
  2. B尝试所有可能的解
  3. C只使用递归
  4. D在每一步都做出局部最优的选择
5.中等

基于比较的排序在最坏情况下的下界是：

  1. AΩ(n log n)
  2. BΩ(log n)
  3. CΩ(n²)
  4. DΩ(n)
6.中等

均摊分析衡量的是什么？

  1. A序列中任何位置上单个最昂贵操作的代价
  2. B算法在最好输入上的代价
  3. C在最坏情况的操作序列上，每个操作的平均代价
  4. D在随机输入上的期望代价
7.困难

Cook–Levin 定理确立了什么？

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

关于 log(n!)，哪个界是正确的？

  1. AΘ(n log n)
  2. BΘ(log n)
  3. CΘ(n)
  4. DΘ(n²)

答案

  1. 1. B · O(n log n)
  2. 2. B · O(1)
  3. 3. C · 4 秒
  4. 4. D · 在每一步都做出局部最优的选择
  5. 5. A · Ω(n log n)
  6. 6. C · 在最坏情况的操作序列上，每个操作的平均代价
  7. 7. C · 布尔可满足性问题（SAT）是 NP 完全的
  8. 8. A · Θ(n log n)

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