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

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

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

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

姓名: ____________________   日期: ____________

1.简单

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

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

log₂ 1024 等于多少？

  1. A10
  2. B512
  3. C32
  4. D12
3.简单

当 n 很大时，哪个复杂度类增长最快？

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

为什么动态规划不能真正加速归并排序？

  1. A归并排序已经是 O(n)
  2. B动态规划只适用于图问题，不适用于数组
  3. C归并排序没有递归结构
  4. D它的子问题不重叠，因此没有可以复用的结果
5.中等

在包含 1,000,000 个元素的有序数组上，二分查找在最坏情况下大约需要多少次比较？

  1. A约 500,000 次
  2. B约 100 次
  3. C约 20 次
  4. D约 1,000 次
6.中等

在边权非负的图中，哪种算法用于求单源最短路径？

  1. A深度优先搜索（DFS）
  2. B任何情况下都必须使用 Bellman–Ford
  3. CKruskal 算法
  4. DDijkstra 算法
7.困难

插入排序在有序输入上运行时间为 O(n)。这与比较排序的 Ω(n log n) 下界矛盾吗？

  1. A矛盾，但仅对长度小于 100 的数组
  2. B不矛盾，下界针对的是所有输入中的最坏情况，而不是每一个输入
  3. C矛盾，因此这个下界是错的
  4. D不矛盾，因为插入排序不是比较排序
8.困难

旅行商问题如何分类？

  1. A它属于 P，因为 Dijkstra 算法通过把每个城市访问一次来求解它
  2. B判定版本是 NP 完全的，优化版本是 NP 难的
  3. C判定版本属于 P，但优化版本是 NP 完全的
  4. D它是不可判定的

答案

  1. 1. C · 指数级
  2. 2. A · 10
  3. 3. B · O(2ⁿ)
  4. 4. D · 它的子问题不重叠，因此没有可以复用的结果
  5. 5. C · 约 20 次
  6. 6. D · Dijkstra 算法
  7. 7. B · 不矛盾，下界针对的是所有输入中的最坏情况，而不是每一个输入
  8. 8. B · 判定版本是 NP 完全的，优化版本是 NP 难的

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