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

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

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

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

姓名: ____________________   日期: ____________

1.简单

在以邻接表存储的图上进行深度优先搜索，时间复杂度是多少？

  1. AO(E log V)
  2. BO(V × E)
  3. CO(V + E)
  4. DO(V²)
2.简单

哪种记号表示增长的下界？

  1. AO（Big O）
  2. BΘ（Big Theta）
  3. Co（little o）
  4. DΩ（Big Omega）
3.简单

在已经有序的数组上，插入排序的最好情况时间复杂度是多少？

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

快速排序总是使用第一个元素作为基准。它在哪种输入上表现出最坏情况？

  1. A所有元素都不相同的数组
  2. B长度为 2 的数组
  3. C随机顺序的数组
  4. D已经有序的数组
5.中等

在活动选择问题中，哪条贪心规则总能得到数量最多的互不重叠的活动？

  1. A先选择最短的活动
  2. B选择最早结束的活动，然后在与之相容的活动中重复这一步
  3. C先选择与其他活动重叠最少的活动，然后在与之相容的活动中重复这一步
  4. D选择最早开始的活动
6.中等

用标准的三重循环计算两个 n × n 矩阵的乘积，时间复杂度是多少？

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

为什么哈希表的平均查找时间是 O(1)，而最坏情况是 O(n)？

  1. A哈希函数运行很慢
  2. B许多键可能冲突（collision）到同一个桶中
  3. C键必须先排序
  4. D数组的访问时间是 O(n)
8.困难

拓扑排序只适用于：

  1. A带负权重的图
  2. B有向无环图（DAG）
  3. C无向图
  4. D完全图

答案

  1. 1. C · O(V + E)
  2. 2. D · Ω（Big Omega）
  3. 3. A · O(n)
  4. 4. D · 已经有序的数组
  5. 5. B · 选择最早结束的活动，然后在与之相容的活动中重复这一步
  6. 6. D · O(n³)
  7. 7. B · 许多键可能冲突（collision）到同一个桶中
  8. 8. B · 有向无环图（DAG）

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