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

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

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

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

姓名: ____________________   日期: ____________

1.简单

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

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

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

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

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

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

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

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

均摊分析衡量的是什么？

  1. A在随机输入上的期望代价
  2. B在最坏情况的操作序列上，每个操作的平均代价
  3. C序列中任何位置上单个最昂贵操作的代价
  4. D算法在最好输入上的代价
6.中等

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

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

22n 属于 O(2ⁿ) 吗？

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

关于在无序数组中选择第 k 小的元素，下列哪个说法是正确的？

  1. A选择总是需要 Ω(n log n)，因为必须先排序
  2. B快速选择的期望时间为 O(n)，而中位数的中位数法保证最坏情况为 O(n)
  3. C快速选择的最坏情况为 O(log n)，因为它只对枢轴的一侧递归
  4. D选择只能在 O(n²) 内完成

答案

  1. 1. C · 指数级
  2. 2. A · 分解、解决、合并
  3. 3. B · 冒泡排序（Bubble sort）
  4. 4. A · Dijkstra 算法
  5. 5. B · 在最坏情况的操作序列上，每个操作的平均代价
  6. 6. C · O(n²)
  7. 7. C · 不属于，因为 22n = 4ⁿ，而 4ⁿ / 2ⁿ = 2ⁿ 无界地增长
  8. 8. B · 快速选择的期望时间为 O(n)，而中位数的中位数法保证最坏情况为 O(n)

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