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

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

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

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

姓名: ____________________   日期: ____________

1.简单

分治算法的三个步骤是什么？

  1. A读取、计算、写入
  2. B排序、查找、返回
  3. C分解、解决、合并
  4. D猜测、检查、重复
2.简单

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

  1. AO（Big O）
  2. Bo（little o）
  3. CΘ（Big Theta）
  4. DΩ（Big Omega）
3.简单

log₂ 1024 等于多少？

  1. A32
  2. B512
  3. C10
  4. D12
4.中等

简单的递归阶乘函数 fact(n) = n × fact(n − 1) 使用多少栈空间？

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

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

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

对 n 个元素的数组进行归并排序，递归共有多少层？

  1. A约 n 层
  2. B约 log₂ n 层
  3. C约 √n 层
  4. D约 n / 2 层
7.困难

为什么当某些边权为负时，Dijkstra 算法可能给出错误结果？

  1. A它只适用于无向图
  2. B每遇到一条负权边它就会陷入无限循环
  3. C顶点被取出时距离就被确定，但之后的负权边仍可能给它一条更短的路径
  4. D优先队列中不能存储负数
8.困难

对于哪种背包问题变体，贪心规则"按单位重量价值的顺序取物品"总能给出最优解？

  1. A分数背包问题，物品可以分割
  2. B两种变体都可以
  3. C0/1 背包问题，物品必须整个拿取
  4. D两种变体都不可以

答案

  1. 1. C · 分解、解决、合并
  2. 2. D · Ω（Big Omega）
  3. 3. C · 10
  4. 4. D · O(n)
  5. 5. B · O(2ⁿ)
  6. 6. B · 约 log₂ n 层
  7. 7. C · 顶点被取出时距离就被确定，但之后的负权边仍可能给它一条更短的路径
  8. 8. A · 分数背包问题，物品可以分割

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