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

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

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

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

姓名: ____________________   日期: ____________

1.简单

在包含 n 个元素的无序数组中进行线性查找（linear search）的时间复杂度（最坏情况）是多少？

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

二分查找对输入有什么要求？

  1. A数组只能包含正数
  2. B数组长度必须是 2 的幂
  3. C数组元素不能超过 1000 个
  4. D数组必须有序
3.简单

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

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

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

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

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

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

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

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

插入排序在有序输入上运行时间为 O(n)。这与比较排序的 Ω(n log n) 下界矛盾吗？

  1. A矛盾，但仅对长度小于 100 的数组
  2. B不矛盾，下界针对的是所有输入中的最坏情况，而不是每一个输入
  3. C矛盾，因此这个下界是错的
  4. D不矛盾，因为插入排序不是比较排序
8.困难

使用主定理，T(n) = 8T(n/2) + O(n²) 的解是：

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

答案

  1. 1. D · O(n)
  2. 2. D · 数组必须有序
  3. 3. B · O(log n)
  4. 4. B · O(n²)
  5. 5. D · Dijkstra 算法
  6. 6. D · 从起始节点出发、按边数计的最短路径
  7. 7. B · 不矛盾，下界针对的是所有输入中的最坏情况，而不是每一个输入
  8. 8. A · Θ(n³)

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