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

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

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

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

姓名: ____________________   日期: ____________

1.简单

什么是递归？

  1. A在更小的输入上调用自身的函数
  2. B一种数据结构
  3. C一种排序方法
  4. D永远不会结束的循环
2.简单

哪种排序算法会反复交换顺序错误的相邻元素？

  1. A快速排序（Quicksort）
  2. B堆排序（Heap sort）
  3. C归并排序（Merge sort）
  4. D冒泡排序（Bubble sort）
3.简单

插入排序（insertion sort）的最坏情况时间复杂度是多少？

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

为什么动态规划不能真正加速归并排序？

  1. A它的子问题不重叠，因此没有可以复用的结果
  2. B动态规划只适用于图问题，不适用于数组
  3. C归并排序已经是 O(n)
  4. D归并排序没有递归结构
5.中等

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

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

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

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

用一个只保留最后两个值的循环计算第 n 个斐波那契数，时间和空间代价各是多少？

  1. AO(log n) 时间和 O(n) 空间
  2. BO(2ⁿ) 时间和 O(1) 空间
  3. CO(n) 时间和 O(1) 空间
  4. DO(n) 时间和 O(n) 空间
8.困难

22n 属于 O(2ⁿ) 吗？

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

答案

  1. 1. A · 在更小的输入上调用自身的函数
  2. 2. D · 冒泡排序（Bubble sort）
  3. 3. A · O(n²)
  4. 4. A · 它的子问题不重叠，因此没有可以复用的结果
  5. 5. A · O(log n)
  6. 6. D · O(n)
  7. 7. C · O(n) 时间和 O(1) 空间
  8. 8. A · 不属于，因为 22n = 4ⁿ，而 4ⁿ / 2ⁿ = 2ⁿ 无界地增长

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