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

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

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

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

姓名: ____________________   日期: ____________

1.简单

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

  1. AO(n!)
  2. BO(2ⁿ)
  3. CO(n³)
  4. DO(nⁿ)
2.简单

什么是记忆化（memoisation）？

  1. A自动把递归转换为等价的循环，从而不需要调用栈
  2. B在每行代码旁边写注释
  3. C函数返回后释放内存
  4. D存储函数调用的结果，使重复调用能直接从内存中得到答案
3.简单

二分查找对输入有什么要求？

  1. A数组只能包含正数
  2. B数组元素不能超过 1000 个
  3. C数组长度必须是 2 的幂
  4. D数组必须有序
4.中等

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

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

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

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

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

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

拓扑排序只适用于：

  1. A无向图
  2. B有向无环图（DAG）
  3. C完全图
  4. D带负权重的图
8.困难

关于 little-o 记号，下列哪个说法是正确的？

  1. A2n = o(n)，因为 2n 增长得慢
  2. Bn = o(n²)，但 n 不是 o(n)
  3. Cn = o(n)，因为每个函数都是自身的 little-o
  4. Dn² = o(n)

答案

  1. 1. C · O(n³)
  2. 2. D · 存储函数调用的结果，使重复调用能直接从内存中得到答案
  3. 3. D · 数组必须有序
  4. 4. C · O(n²)
  5. 5. A · 插入排序开销小，在小规模或几乎有序的输入上很快
  6. 6. D · O(log n)
  7. 7. B · 有向无环图（DAG）
  8. 8. B · n = o(n²)，但 n 不是 o(n)

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