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

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

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

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

姓名: ____________________   日期: ____________

1.简单

对范围在 0 到 k 之间的 n 个整数进行计数排序（counting sort），运行时间是多少？

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

什么是记忆化（memoisation）？

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

插入排序（insertion sort）的最坏情况时间复杂度是多少？

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

为什么在 Big O 中通常省略对数的底，例如写成 O(log n)？

  1. A计算机科学中所有对数的底都是 10，所以可以省略
  2. B对数总是被四舍五入为整数
  3. C不同底的对数之间只相差一个常数因子
  4. D底只在 n 很小时才有影响
5.中等

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

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

在无权图上进行广度优先搜索（BFS）可以求出：

  1. A所有图的拓扑序
  2. B含负权重边的图中的最短路径
  3. C最小生成树
  4. D从起始节点出发、按边数计的最短路径
7.困难

一个问题是 NP 完全（NP-complete）的，当且仅当它：

  1. A属于 NP，且所有 NP 问题都能在多项式时间内归约到它
  2. B不属于 NP，但比所有 NP 问题都难，例如停机问题
  3. C不可能被解决
  4. D可以在多项式时间内解决
8.困难

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

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

答案

  1. 1. B · O(n + k)
  2. 2. D · 存储函数调用的结果，使重复调用能直接从内存中得到答案
  3. 3. C · O(n²)
  4. 4. C · 不同底的对数之间只相差一个常数因子
  5. 5. B · 它的子问题不重叠，因此没有可以复用的结果
  6. 6. D · 从起始节点出发、按边数计的最短路径
  7. 7. A · 属于 NP，且所有 NP 问题都能在多项式时间内归约到它
  8. 8. A · 把一个已知的 NP 难问题在多项式时间内归约到 X

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