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

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

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

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

姓名: ____________________   日期: ____________

1.简单

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

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

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

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

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

  1. AO(2ⁿ)
  2. BO(nⁿ)
  3. CO(n³)
  4. DO(n!)
4.中等

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

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

递推式 T(n) = 2T(n − 1) + O(1) 的解是什么？

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

贪心算法（greedy algorithm）：

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

为什么在有序数组中任何基于比较的查找在最坏情况下都需要 Ω(log n) 次比较？

  1. A二分查找是唯一可能的算法，它需要 log₂ n 次比较
  2. B每次比较都需要对数时间
  3. C每个元素都必须至少比较一次
  4. D有 n 种可能结果的决策树，其深度至少为 log₂ n
8.困难

关于类 P 的哪个定义是正确的？

  1. A其解可以被验证、但绝不能在多项式时间内找到的问题
  2. B在每台计算机上都需要指数时间的问题
  3. C能够并行求解的问题
  4. D能由确定性算法在多项式时间内求解的判定问题

答案

  1. 1. D · O(n)
  2. 2. A · O(n²)
  3. 3. C · O(n³)
  4. 4. D · O(n)
  5. 5. A · O(2ⁿ)
  6. 6. A · 在每一步都做出局部最优的选择
  7. 7. D · 有 n 种可能结果的决策树，其深度至少为 log₂ n
  8. 8. D · 能由确定性算法在多项式时间内求解的判定问题

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