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

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

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

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

姓名: ____________________   日期: ____________

1.简单

什么是算法？

  1. A一种为书写数学公式而设计的编程语言
  2. B解决问题的、由有限个明确定义的步骤组成的序列
  3. C任何带有图形界面的计算机程序
  4. D一种存储数字的数据结构
2.简单

一个包含两层嵌套循环、每层都执行 n 次的算法，通常具有哪种复杂度？

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

一个 O(n) 算法在 n = 100 万时需要 3 秒。n = 200 万时大约需要多长时间？

  1. A12 秒
  2. B9 秒
  3. C6 秒
  4. D3 秒
4.中等

说一个 O(n²) 算法也是 O(n³)，这正确吗？

  1. A不正确，因为当 n 很大时 n³ 小于 n²
  2. B正确，但仅当 n 小于 100 时
  3. C正确，因为 Big O 是上界，而 n² 的增长不比 n³ 快
  4. D不正确，因为 Big O 必须始终给出函数的确切增长率
5.中等

对 n 个 k 进制、d 位的整数进行 LSD 基数排序（radix sort），运行时间是多少？

  1. AO(d(n + k))
  2. BO(n log n)
  3. CO(n²)
  4. DO(dn log k)
6.中等

在有 V 个顶点、E 条边的图上，Bellman–Ford 算法的时间复杂度是多少？

  1. AO(V × E)
  2. BO(V + E)
  3. CO(E log V)
  4. DO(V³ × E)
7.困难

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

  1. AKruskal 算法
  2. BDijkstra 算法
  3. C从一个节点出发的 Prim 算法
  4. DFloyd–Warshall
8.困难

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

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

答案

  1. 1. B · 解决问题的、由有限个明确定义的步骤组成的序列
  2. 2. B · O(n²)
  3. 3. C · 6 秒
  4. 4. C · 正确，因为 Big O 是上界，而 n² 的增长不比 n³ 快
  5. 5. A · O(d(n + k))
  6. 6. A · O(V × E)
  7. 7. A · Kruskal 算法
  8. 8. D · 许多键可能冲突（collision）到同一个桶中

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