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

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

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

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

姓名: ____________________   日期: ____________

1.简单

什么是算法？

  1. A一种为书写数学公式而设计的编程语言
  2. B任何带有图形界面的计算机程序
  3. C解决问题的、由有限个明确定义的步骤组成的序列
  4. D一种存储数字的数据结构
2.简单

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

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

标准的基于数组的归并排序使用多少额外内存？

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

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

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

均摊分析衡量的是什么？

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

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

  1. AO(V³ × E)
  2. BO(V × E)
  3. CO(V + E)
  4. DO(E log V)
7.困难

22n 属于 O(2ⁿ) 吗？

  1. A属于，因为在 Big O 中指数里的常数因子总是被忽略
  2. B不属于，因为 22n = 4ⁿ，而 4ⁿ / 2ⁿ = 2ⁿ 无界地增长
  3. C不属于，因为 22n 增长得比 2ⁿ 慢
  4. D属于，因为两者都是指数级的
8.困难

关于 little-o 记号，下列哪个说法是正确的？

  1. An² = o(n)
  2. Bn = o(n²)，但 n 不是 o(n)
  3. Cn = o(n)，因为每个函数都是自身的 little-o
  4. D2n = o(n)，因为 2n 增长得慢

答案

  1. 1. C · 解决问题的、由有限个明确定义的步骤组成的序列
  2. 2. C · 数组必须有序
  3. 3. B · O(n)
  4. 4. B · O(n)
  5. 5. C · 在最坏情况的操作序列上，每个操作的平均代价
  6. 6. B · O(V × E)
  7. 7. B · 不属于，因为 22n = 4ⁿ，而 4ⁿ / 2ⁿ = 2ⁿ 无界地增长
  8. 8. B · n = o(n²)，但 n 不是 o(n)

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