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

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

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

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

姓名: ____________________   日期: ____________

1.简单

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

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

当 n 变大时，下列哪一项增长最慢？

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

什么是蛮力算法（brute-force algorithm）？

  1. A在多个处理器上运行的算法
  2. B尝试所有可能的候选解的算法
  3. C总是使用递归的算法
  4. D随机猜测答案的算法
4.中等

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

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

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

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

用自底向上的表格计算第 n 个斐波那契数，时间复杂度是多少？

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

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

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

Held–Karp 动态规划算法能精确求解旅行商问题。对 n 个城市，它的运行时间是多少？

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

答案

  1. 1. A · 指数级
  2. 2. C · O(log n)
  3. 3. B · 尝试所有可能的候选解的算法
  4. 4. A · 不同底的对数之间只相差一个常数因子
  5. 5. D · 约 20 次
  6. 6. C · O(n)
  7. 7. C · 属于 NP，且所有 NP 问题都能在多项式时间内归约到它
  8. 8. B · O(n² 2ⁿ)

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