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

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

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

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

姓名: ____________________   日期: ____________

1.简单

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

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

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

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

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

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

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

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

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

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

一个问题具有最优子结构是什么意思？

  1. A该问题恰好有一个最优解，所有子问题共享这个解
  2. B每个子问题的规模都相同
  3. C最优解可以由其子问题的最优解构造出来
  4. D该问题可以在常数时间内求解
7.困难

关于 log(n!)，哪个界是正确的？

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

当 n 很大时，n! 与 2ⁿ 相比如何？

  1. A两者以相同的速率增长
  2. B2ⁿ 比 n! 增长得快
  3. Cn! 比 2ⁿ 增长得快
  4. Dn! 是 O(n²)

答案

  1. 1. A · 指数级
  2. 2. D · 尝试所有可能的候选解的算法
  3. 3. C · O(n³)
  4. 4. A · O(n)
  5. 5. D · 从起始节点出发、按边数计的最短路径
  6. 6. C · 最优解可以由其子问题的最优解构造出来
  7. 7. B · Θ(n log n)
  8. 8. C · n! 比 2ⁿ 增长得快

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