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

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

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

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

姓名: ____________________   日期: ____________

1.简单

log₂ 1024 等于多少？

  1. A10
  2. B32
  3. C12
  4. D512
2.简单

一个问题通常在什么情况下被称为易解的（tractable）？

  1. A能在多项式时间内求解
  2. B没有解
  3. C能在常数时间内求解
  4. D只能通过尝试所有可能来求解
3.简单

如果一个操作的运行时间是 O(1)，这意味着什么？

  1. A它的运行时间不随输入规模增长
  2. B它每秒运行时间恰好处理一个元素
  3. C它只能运行一次
  4. D它总是恰好花费一秒
4.中等

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

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

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

  1. AO(V³ × E)
  2. BO(E log V)
  3. CO(V × E)
  4. DO(V + E)
6.中等

均摊分析衡量的是什么？

  1. A在最坏情况的操作序列上，每个操作的平均代价
  2. B在随机输入上的期望代价
  3. C算法在最好输入上的代价
  4. D序列中任何位置上单个最昂贵操作的代价
7.困难

停机问题（halting problem）表明：

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

一个问题是 NP 完全（NP-complete）的，当且仅当它：

  1. A不属于 NP，但比所有 NP 问题都难，例如停机问题
  2. B不可能被解决
  3. C可以在多项式时间内解决
  4. D属于 NP，且所有 NP 问题都能在多项式时间内归约到它

答案

  1. 1. A · 10
  2. 2. A · 能在多项式时间内求解
  3. 3. A · 它的运行时间不随输入规模增长
  4. 4. C · Ω(n log n)
  5. 5. C · O(V × E)
  6. 6. A · 在最坏情况的操作序列上，每个操作的平均代价
  7. 7. D · 不存在一种算法能对所有程序和输入判定其是否会停机
  8. 8. D · 属于 NP，且所有 NP 问题都能在多项式时间内归约到它

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