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

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

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

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

姓名: ____________________   日期: ____________

1.简单

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

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

归并排序采用哪种设计策略？

  1. A贪心选择
  2. B分治法（divide and conquer）
  3. C蛮力法
  4. D动态规划
3.简单

什么是算法？

  1. A解决问题的、由有限个明确定义的步骤组成的序列
  2. B一种为书写数学公式而设计的编程语言
  3. C一种存储数字的数据结构
  4. D任何带有图形界面的计算机程序
4.中等

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

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

在有 V 个顶点、E 条边的图上，Bellman–Ford 算法的时间复杂度是多少？

  1. AO(E log V)
  2. BO(V × E)
  3. CO(V + E)
  4. DO(V³ × E)
6.中等

哪种排序算法是稳定的？

  1. A归并排序
  2. B堆排序
  3. C快速排序（常见的原地版本）
  4. D选择排序（常见版本）
7.困难

22n 属于 O(2ⁿ) 吗？

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

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

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

答案

  1. 1. C · 指数级
  2. 2. B · 分治法（divide and conquer）
  3. 3. A · 解决问题的、由有限个明确定义的步骤组成的序列
  4. 4. A · O(n)
  5. 5. B · O(V × E)
  6. 6. A · 归并排序
  7. 7. A · 不属于，因为 22n = 4ⁿ，而 4ⁿ / 2ⁿ = 2ⁿ 无界地增长
  8. 8. D · Θ(n log n)

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