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

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

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

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

姓名: ____________________   日期: ____________

1.简单

哪种记号表示增长的上界？

  1. ABig Omega
  2. BBig O
  3. CBig Theta
  4. DLittle omega
2.简单

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

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

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

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

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

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

为什么许多库排序函数在子数组很小时会改用插入排序？

  1. A插入排序开销小，在小规模或几乎有序的输入上很快
  2. B插入排序在最坏情况下是 O(n log n)
  3. C递归算法无法处理少于 10 个元素的数组
  4. D在大规模输入上，插入排序比任何其他排序算法使用的内存都少
6.中等

你对一个 n 个元素的数组排序一次，然后用二分查找回答 k 次成员查询。总代价是多少？

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

22n 属于 O(2ⁿ) 吗？

  1. A不属于，因为 22n 增长得比 2ⁿ 慢
  2. B属于，因为在 Big O 中指数里的常数因子总是被忽略
  3. C不属于，因为 22n = 4ⁿ，而 4ⁿ / 2ⁿ = 2ⁿ 无界地增长
  4. D属于，因为两者都是指数级的
8.困难

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

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

答案

  1. 1. B · Big O
  2. 2. A · O(n)
  3. 3. D · O(n³)
  4. 4. B · O(n²)
  5. 5. A · 插入排序开销小，在小规模或几乎有序的输入上很快
  6. 6. D · O(n log n + k log n)
  7. 7. C · 不属于，因为 22n = 4ⁿ，而 4ⁿ / 2ⁿ = 2ⁿ 无界地增长
  8. 8. B · 有 n 种可能结果的决策树，其深度至少为 log₂ n

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