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

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

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

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

姓名: ____________________   日期: ____________

1.简单

在以邻接表存储的图上进行深度优先搜索，时间复杂度是多少？

  1. AO(V × E)
  2. BO(E log V)
  3. CO(V²)
  4. DO(V + E)
2.简单

分治算法的三个步骤是什么？

  1. A排序、查找、返回
  2. B猜测、检查、重复
  3. C读取、计算、写入
  4. D分解、解决、合并
3.简单

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

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

说一个 O(n²) 算法也是 O(n³)，这正确吗？

  1. A不正确，因为 Big O 必须始终给出函数的确切增长率
  2. B正确，但仅当 n 小于 100 时
  3. C正确，因为 Big O 是上界，而 n² 的增长不比 n³ 快
  4. D不正确，因为当 n 很大时 n³ 小于 n²
5.中等

均摊分析衡量的是什么？

  1. A在最坏情况的操作序列上，每个操作的平均代价
  2. B算法在最好输入上的代价
  3. C在随机输入上的期望代价
  4. D序列中任何位置上单个最昂贵操作的代价
6.中等

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

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

关于 log(n!)，哪个界是正确的？

  1. AΘ(log n)
  2. BΘ(n log n)
  3. CΘ(n)
  4. DΘ(n²)
8.困难

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

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

答案

  1. 1. D · O(V + E)
  2. 2. D · 分解、解决、合并
  3. 3. A · O(n)
  4. 4. C · 正确，因为 Big O 是上界，而 n² 的增长不比 n³ 快
  5. 5. A · 在最坏情况的操作序列上，每个操作的平均代价
  6. 6. B · O(n²)
  7. 7. B · Θ(n log n)
  8. 8. D · 有 n 种可能结果的决策树，其深度至少为 log₂ n

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