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

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

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

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

姓名: ____________________   日期: ____________

1.简单

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

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

什么是记忆化（memoisation）？

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

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

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

均摊分析衡量的是什么？

  1. A算法在最好输入上的代价
  2. B序列中任何位置上单个最昂贵操作的代价
  3. C在最坏情况的操作序列上，每个操作的平均代价
  4. D在随机输入上的期望代价
5.中等

下面代码的时间复杂度是多少：for i = 1 to n: for j = 1 to i: 执行 O(1) 的工作？

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

简单的递归阶乘函数 fact(n) = n × fact(n − 1) 使用多少栈空间？

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

使用主定理，T(n) = 8T(n/2) + O(n²) 的解是：

  1. AΘ(n log n)
  2. BΘ(n³)
  3. CΘ(n² log n)
  4. DΘ(n²)
8.困难

如果有人为某个 NP 完全问题找到了多项式时间算法，会有什么结果？

  1. A所有指数时间算法都会立即变成线性时间
  2. BNP 中的每个问题都能在多项式时间内求解，因此 P = NP
  3. C停机问题将变得可判定
  4. D只有那一个问题会进入 P

答案

  1. 1. C · O(n³)
  2. 2. A · 存储函数调用的结果，使重复调用能直接从内存中得到答案
  3. 3. A · O(log n)
  4. 4. C · 在最坏情况的操作序列上，每个操作的平均代价
  5. 5. A · O(n²)
  6. 6. D · O(n)
  7. 7. B · Θ(n³)
  8. 8. B · NP 中的每个问题都能在多项式时间内求解，因此 P = NP

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