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

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

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

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

姓名: ____________________   日期: ____________

1.简单

一个算法的运行时间是 O(n)。这种增长称为什么？

  1. A对数
  2. B常数
  3. C平方
  4. D线性
2.简单

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

  1. ALittle omega
  2. BBig Omega
  3. CBig O
  4. DBig Theta
3.简单

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

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

Prim 算法如何构建最小生成树？

  1. A从一个起始顶点开始扩展一棵树，每次加入离开该树的最便宜的边
  2. B不断删除最贵的边，直到没有环为止
  3. C运行广度优先搜索并保留 BFS 树
  4. D把所有边按权重排序，逐条加入，除非会在森林中形成环
5.中等

对于在满时将容量翻倍的动态数组，追加元素的均摊（amortised）时间复杂度是多少？

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

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

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

停机问题（halting problem）表明：

  1. A有些程序在更快的计算机上运行得更快，所以是否停机取决于硬件
  2. B不存在一种算法能对所有程序和输入判定其是否会停机
  3. C每个程序最终都会停机
  4. D应当避免使用循环
8.困难

关于 log(n!)，哪个界是正确的？

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

答案

  1. 1. D · 线性
  2. 2. C · Big O
  3. 3. A · 指数级
  4. 4. A · 从一个起始顶点开始扩展一棵树，每次加入离开该树的最便宜的边
  5. 5. A · O(1)
  6. 6. A · O(log n)
  7. 7. B · 不存在一种算法能对所有程序和输入判定其是否会停机
  8. 8. C · Θ(n log n)

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