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

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

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

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

姓名: ____________________   日期: ____________

1.简单

标准的基于数组的归并排序使用多少额外内存？

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

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

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

空间复杂度衡量的是：

  1. A计算机的物理尺寸
  2. B程序编译后程序文件占用的磁盘空间
  3. C代码的行数
  4. D随着输入增大，算法所需的内存量
4.中等

在活动选择问题中，哪条贪心规则总能得到数量最多的互不重叠的活动？

  1. A先选择最短的活动
  2. B选择最早结束的活动，然后在与之相容的活动中重复这一步
  3. C选择最早开始的活动
  4. D先选择与其他活动重叠最少的活动，然后在与之相容的活动中重复这一步
5.中等

说一个 O(n²) 算法也是 O(n³)，这正确吗？

  1. A不正确，因为当 n 很大时 n³ 小于 n²
  2. B正确，因为 Big O 是上界，而 n² 的增长不比 n³ 快
  3. C正确，但仅当 n 小于 100 时
  4. D不正确，因为 Big O 必须始终给出函数的确切增长率
6.中等

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

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

22n 属于 O(2ⁿ) 吗？

  1. A不属于，因为 22n 增长得比 2ⁿ 慢
  2. B属于，因为两者都是指数级的
  3. C属于，因为在 Big O 中指数里的常数因子总是被忽略
  4. D不属于，因为 22n = 4ⁿ，而 4ⁿ / 2ⁿ = 2ⁿ 无界地增长
8.困难

停机问题（halting problem）表明：

  1. A每个程序最终都会停机
  2. B应当避免使用循环
  3. C有些程序在更快的计算机上运行得更快，所以是否停机取决于硬件
  4. D不存在一种算法能对所有程序和输入判定其是否会停机

答案

  1. 1. D · O(n)
  2. 2. D · O(n³)
  3. 3. D · 随着输入增大，算法所需的内存量
  4. 4. B · 选择最早结束的活动，然后在与之相容的活动中重复这一步
  5. 5. B · 正确，因为 Big O 是上界，而 n² 的增长不比 n³ 快
  6. 6. C · O(n)
  7. 7. D · 不属于，因为 22n = 4ⁿ，而 4ⁿ / 2ⁿ = 2ⁿ 无界地增长
  8. 8. D · 不存在一种算法能对所有程序和输入判定其是否会停机

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