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

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

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

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

姓名: ____________________   日期: ____________

1.简单

平均情况运行时间描述的是什么？

  1. A在最常见的计算机上所需的时间
  2. B在给定的规模为 n 的输入分布上的期望时间
  3. C平均长度的输入所需的时间
  4. D最好情况与最坏情况运行时间之间的中间值
2.简单

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

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

一个 O(n²) 算法在 n = 1000 时需要 1 秒。n = 2000 时大约需要多长时间？

  1. A1 秒
  2. B2 秒
  3. C4 秒
  4. D8 秒
4.中等

在无权图上进行广度优先搜索（BFS）可以求出：

  1. A含负权重边的图中的最短路径
  2. B最小生成树
  3. C从起始节点出发、按边数计的最短路径
  4. D所有图的拓扑序
5.中等

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

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

在包含 1,000,000 个元素的有序数组上，二分查找在最坏情况下大约需要多少次比较？

  1. A约 1,000 次
  2. B约 500,000 次
  3. C约 20 次
  4. D约 100 次
7.困难

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

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

为什么在单链表上二分查找不能达到 O(log n) 的时间？

  1. A链表节点上的比较更慢
  2. B二分查找至少需要两倍的内存
  3. C链表无法排序
  4. D由于不能按下标直接访问，到达中间元素需要 O(n) 步

答案

  1. 1. B · 在给定的规模为 n 的输入分布上的期望时间
  2. 2. B · 分治法（divide and conquer）
  3. 3. C · 4 秒
  4. 4. C · 从起始节点出发、按边数计的最短路径
  5. 5. B · 指数级
  6. 6. C · 约 20 次
  7. 7. B · Kruskal 算法
  8. 8. D · 由于不能按下标直接访问，到达中间元素需要 O(n) 步

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