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

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

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

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

姓名: ____________________   日期: ____________

1.简单

一个循环从 i = 1 开始，每次迭代将 i 翻倍，直到 i > n。它运行多少次迭代？

  1. A约 n / 2 次
  2. B约 n² 次
  3. C约 log₂ n 次
  4. D约 n 次
2.简单

在已经有序的数组上，插入排序的最好情况时间复杂度是多少？

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

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

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

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

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

下面代码的时间复杂度是多少：for i = 1 to n: (j = 1; while j < n: j = j × 2)？

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

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

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

为什么哈希表的平均查找时间是 O(1)，而最坏情况是 O(n)？

  1. A哈希函数运行很慢
  2. B键必须先排序
  3. C数组的访问时间是 O(n)
  4. D许多键可能冲突（collision）到同一个桶中
8.困难

哪种技术能使快速排序在任意输入上的期望运行时间为 O(n log n)？

  1. A在运行快速排序前先对输入排序
  2. B只对左侧进行递归
  3. C总是选择第一个元素
  4. D均匀随机地选择基准

答案

  1. 1. C · 约 log₂ n 次
  2. 2. A · O(n)
  3. 3. C · f 与 g 以相同的速率增长，上下都被 g 的常数倍所界定
  4. 4. D · Ω(n log n)
  5. 5. B · O(n log n)
  6. 6. D · O(n)
  7. 7. D · 许多键可能冲突（collision）到同一个桶中
  8. 8. D · 均匀随机地选择基准

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