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

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

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

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

姓名: ____________________   日期: ____________

1.简单

标准的基于数组的归并排序使用多少额外内存？

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

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

  1. A4 秒
  2. B2 秒
  3. C1 秒
  4. D8 秒
3.简单

3n² + 5n + 2 的 Big O 是什么？

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

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

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

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

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

说一个 O(n²) 算法也是 O(n³)，这正确吗？

  1. A不正确，因为当 n 很大时 n³ 小于 n²
  2. B不正确，因为 Big O 必须始终给出函数的确切增长率
  3. C正确，因为 Big O 是上界，而 n² 的增长不比 n³ 快
  4. D正确，但仅当 n 小于 100 时
7.困难

不可判定问题与难解问题有什么区别？

  1. A难解问题无法被任何算法求解，而不可判定问题只需要指数时间
  2. B两者都意味着该问题根本没有算法
  3. C不可判定问题属于 NP，而难解问题属于 P
  4. D不可判定问题没有任何能处理所有输入的算法，而难解问题有算法，但太慢
8.困难

下面代码的时间复杂度是多少：for i = 1 to n: for (j = i; j ≤ n; j = j + i) 执行 O(1) 的工作？

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

答案

  1. 1. A · O(n)
  2. 2. A · 4 秒
  3. 3. C · O(n²)
  4. 4. D · Ω(n log n)
  5. 5. D · O(n²)
  6. 6. C · 正确，因为 Big O 是上界，而 n² 的增长不比 n³ 快
  7. 7. D · 不可判定问题没有任何能处理所有输入的算法，而难解问题有算法，但太慢
  8. 8. A · O(n log n)

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