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

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

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

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

姓名: ____________________   日期: ____________

1.简单

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

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

如果一个操作的运行时间是 O(1)，这意味着什么？

  1. A它只能运行一次
  2. B它每秒运行时间恰好处理一个元素
  3. C它的运行时间不随输入规模增长
  4. D它总是恰好花费一秒
3.简单

O(2ⁿ) 的增长称为什么？

  1. A多项式级
  2. B线性
  3. C指数级
  4. D对数级
4.中等

快速排序总是使用第一个元素作为基准。它在哪种输入上表现出最坏情况？

  1. A所有元素都不相同的数组
  2. B随机顺序的数组
  3. C已经有序的数组
  4. D长度为 2 的数组
5.中等

硬币面值为 1、3 和 4，金额为 6，贪心的"先取最大硬币"方法使用多少枚硬币？与最优解相比如何？

  1. A贪心用 2 枚；最优解是 2 枚
  2. B贪心用 3 枚；最优解是 2 枚
  3. C贪心用 4 枚；最优解是 3 枚
  4. D贪心用 3 枚；最优解是 3 枚
6.中等

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

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

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

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

使用主定理，T(n) = 8T(n/2) + O(n²) 的解是：

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

答案

  1. 1. C · f 与 g 以相同的速率增长，上下都被 g 的常数倍所界定
  2. 2. C · 它的运行时间不随输入规模增长
  3. 3. C · 指数级
  4. 4. C · 已经有序的数组
  5. 5. B · 贪心用 3 枚；最优解是 2 枚
  6. 6. B · O(n²)
  7. 7. C · O(n log n)
  8. 8. B · Θ(n³)

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