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

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

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

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

姓名: ____________________   日期: ____________

1.简单

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

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

对范围在 0 到 k 之间的 n 个整数进行计数排序（counting sort），运行时间是多少？

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

分治算法的三个步骤是什么？

  1. A排序、查找、返回
  2. B读取、计算、写入
  3. C分解、解决、合并
  4. D猜测、检查、重复
4.中等

朴素递归斐波那契（fib(n) = fib(n−1) + fib(n−2)）的时间复杂度是：

  1. A对数级
  2. B指数级
  3. C线性
  4. D常数
5.中等

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

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

为什么许多库排序函数在子数组很小时会改用插入排序？

  1. A递归算法无法处理少于 10 个元素的数组
  2. B插入排序开销小，在小规模或几乎有序的输入上很快
  3. C插入排序在最坏情况下是 O(n log n)
  4. D在大规模输入上，插入排序比任何其他排序算法使用的内存都少
7.困难

哪种算法通过反复加入不会形成环的最便宜的边来求最小生成树？

  1. AFloyd–Warshall
  2. BKruskal 算法
  3. C从一个节点出发的 Prim 算法
  4. DDijkstra 算法
8.困难

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

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

答案

  1. 1. C · O(log n)
  2. 2. A · O(n + k)
  3. 3. C · 分解、解决、合并
  4. 4. B · 指数级
  5. 5. C · O(log n)
  6. 6. B · 插入排序开销小，在小规模或几乎有序的输入上很快
  7. 7. B · Kruskal 算法
  8. 8. D · Θ(n log n)

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