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

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

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

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

姓名: ____________________   日期: ____________

1.简单

下列哪个运行时间是多项式的？

  1. AO(n³)
  2. BO(nⁿ)
  3. CO(n!)
  4. DO(2ⁿ)
2.简单

当 n 变大时，下列哪一项增长最慢？

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

在包含 n 个元素的无序数组中进行线性查找（linear search）的时间复杂度（最坏情况）是多少？

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

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

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

贪心算法（greedy algorithm）：

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

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

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

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

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

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

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

答案

  1. 1. A · O(n³)
  2. 2. B · O(log n)
  3. 3. D · O(n)
  4. 4. B · O(n)
  5. 5. C · 在每一步都做出局部最优的选择
  6. 6. D · O(n)
  7. 7. D · O(n log n)
  8. 8. B · 不可判定问题没有任何能处理所有输入的算法，而难解问题有算法，但太慢

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