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

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

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

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

姓名: ____________________   日期: ____________

1.简单

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

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

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

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

一个算法的运行时间是 O(n)。这种增长称为什么？

  1. A对数
  2. B线性
  3. C常数
  4. D平方
4.中等

哪种排序算法是稳定的？

  1. A堆排序
  2. B选择排序（常见版本）
  3. C快速排序（常见的原地版本）
  4. D归并排序
5.中等

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

  1. A任何情况下都必须使用 Bellman–Ford
  2. BKruskal 算法
  3. CDijkstra 算法
  4. D深度优先搜索（DFS）
6.中等

硬币面值为 1、3 和 4，金额为 6，贪心的"先取最大硬币"方法使用多少枚硬币？与最优解相比如何？

  1. A贪心用 4 枚；最优解是 3 枚
  2. B贪心用 3 枚；最优解是 2 枚
  3. C贪心用 2 枚；最优解是 2 枚
  4. D贪心用 3 枚；最优解是 3 枚
7.困难

最短简单路径可以在多项式时间内求出。在一般图中求两个顶点之间的最长简单路径，已知情况如何？

  1. A它是不可判定的
  2. B它是 NP 难的
  3. C总能在 O(V + E) 内求解
  4. D可以把权重取反后用 Dijkstra 算法求解
8.困难

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

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

答案

  1. 1. C · 指数级
  2. 2. A · O(n)
  3. 3. B · 线性
  4. 4. D · 归并排序
  5. 5. C · Dijkstra 算法
  6. 6. B · 贪心用 3 枚；最优解是 2 枚
  7. 7. B · 它是 NP 难的
  8. 8. D · Θ(n log n)

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