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

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

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

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

姓名: ____________________   日期: ____________

1.简单

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

  1. ABig Omega
  2. BBig Theta
  3. CBig O
  4. DLittle omega
2.简单

什么是递归？

  1. A在更小的输入上调用自身的函数
  2. B永远不会结束的循环
  3. C一种数据结构
  4. D一种排序方法
3.简单

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

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

基于比较的排序在最坏情况下的下界是：

  1. AΩ(log n)
  2. BΩ(n)
  3. CΩ(n²)
  4. DΩ(n log n)
5.中等

Floyd–Warshall 算法计算什么？速度如何？

  1. A以 O(V²) 计算拓扑序
  2. B以 O(V³) 计算所有顶点对之间的最短路径
  3. C以 O(E log V) 计算最小生成树
  4. D以 O(V + E) 计算从一个源顶点到所有其他顶点的最短路径
6.中等

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

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

停机问题（halting problem）表明：

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

关于 P 和 NP，下列哪个说法是正确的？

  1. AP 中的每个问题也都属于 NP
  2. BNP 表示“not polynomial”（非多项式）
  3. C已经证明 P ≠ NP
  4. DNP 问题无法被快速验证

答案

  1. 1. C · Big O
  2. 2. A · 在更小的输入上调用自身的函数
  3. 3. D · 指数级
  4. 4. D · Ω(n log n)
  5. 5. B · 以 O(V³) 计算所有顶点对之间的最短路径
  6. 6. D · O(n²)
  7. 7. B · 不存在一种算法能对所有程序和输入判定其是否会停机
  8. 8. A · P 中的每个问题也都属于 NP

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