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

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

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

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

姓名: ____________________   日期: ____________

1.简单

二分查找对输入有什么要求？

  1. A数组只能包含正数
  2. B数组必须有序
  3. C数组元素不能超过 1000 个
  4. D数组长度必须是 2 的幂
2.简单

log₂ 1024 等于多少？

  1. A12
  2. B512
  3. C10
  4. D32
3.简单

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

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

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

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

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

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

朴素递归斐波那契（fib(n) = fib(n−1) + fib(n−2)）的时间复杂度是：

  1. A对数级
  2. B常数
  3. C指数级
  4. D线性
7.困难

为什么在有序数组中任何基于比较的查找在最坏情况下都需要 Ω(log n) 次比较？

  1. A有 n 种可能结果的决策树，其深度至少为 log₂ n
  2. B每次比较都需要对数时间
  3. C每个元素都必须至少比较一次
  4. D二分查找是唯一可能的算法，它需要 log₂ n 次比较
8.困难

停机问题（halting problem）表明：

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

答案

  1. 1. B · 数组必须有序
  2. 2. C · 10
  3. 3. B · 指数级
  4. 4. D · 选择最早结束的活动，然后在与之相容的活动中重复这一步
  5. 5. D · O(n²)
  6. 6. C · 指数级
  7. 7. A · 有 n 种可能结果的决策树，其深度至少为 log₂ n
  8. 8. A · 不存在一种算法能对所有程序和输入判定其是否会停机

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