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

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

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

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

姓名: ____________________   日期: ____________

1.简单

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

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

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

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

标准的基于数组的归并排序使用多少额外内存？

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

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

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

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

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

在边权非负的图中，哪种算法用于求单源最短路径？

  1. ADijkstra 算法
  2. B深度优先搜索（DFS）
  3. C任何情况下都必须使用 Bellman–Ford
  4. DKruskal 算法
7.困难

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

  1. A2ⁿ 比 n! 增长得快
  2. Bn! 是 O(n²)
  3. Cn! 比 2ⁿ 增长得快
  4. D两者以相同的速率增长
8.困难

22n 属于 O(2ⁿ) 吗？

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

答案

  1. 1. A · 冒泡排序（Bubble sort）
  2. 2. D · O(n + k)
  3. 3. C · O(n)
  4. 4. B · O(n)
  5. 5. A · 插入排序开销小，在小规模或几乎有序的输入上很快
  6. 6. A · Dijkstra 算法
  7. 7. C · n! 比 2ⁿ 增长得快
  8. 8. D · 不属于，因为 22n = 4ⁿ，而 4ⁿ / 2ⁿ = 2ⁿ 无界地增长

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