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

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

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

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

姓名: ____________________   日期: ____________

1.简单

一个问题通常在什么情况下被称为易解的（tractable）？

  1. A没有解
  2. B能在常数时间内求解
  3. C只能通过尝试所有可能来求解
  4. D能在多项式时间内求解
2.简单

归并排序采用哪种设计策略？

  1. A蛮力法
  2. B分治法（divide and conquer）
  3. C动态规划
  4. D贪心选择
3.简单

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

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

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

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

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

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

快速排序总是使用第一个元素作为基准。它在哪种输入上表现出最坏情况？

  1. A已经有序的数组
  2. B随机顺序的数组
  3. C所有元素都不相同的数组
  4. D长度为 2 的数组
7.困难

要证明一个新问题 X 是 NP 难（NP-hard）的，必须做什么？

  1. A把 X 在多项式时间内归约到一个已知的 NP 难问题
  2. B证明 X 能在多项式时间内被验证
  3. C把一个已知的 NP 难问题在多项式时间内归约到 X
  4. D证明 X 对于小规模输入没有多项式算法
8.困难

拓扑排序只适用于：

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

答案

  1. 1. D · 能在多项式时间内求解
  2. 2. B · 分治法（divide and conquer）
  3. 3. C · 指数级
  4. 4. A · Dijkstra 算法
  5. 5. C · 插入排序开销小，在小规模或几乎有序的输入上很快
  6. 6. A · 已经有序的数组
  7. 7. C · 把一个已知的 NP 难问题在多项式时间内归约到 X
  8. 8. B · 有向无环图（DAG）

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