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

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

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

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

姓名: ____________________   日期: ____________

1.简单

一个算法的运行时间是 O(n)。这种增长称为什么？

  1. A常数
  2. B线性
  3. C对数
  4. D平方
2.简单

什么是递归？

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

在有序数组上进行二分查找（binary search）的时间复杂度是多少？

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

你对一个 n 个元素的数组排序一次，然后用二分查找回答 k 次成员查询。总代价是多少？

  1. AO(n log n + k log n)
  2. BO(nk)
  3. CO(n + k)
  4. DO(k 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(2ⁿ)
  2. BO(n)
  3. CO(n²)
  4. DO(n log n)
7.困难

关于类 NP 的哪个定义是正确的？

  1. A非多项式的问题
  2. B不能在多项式时间内求解的问题
  3. C给定证书时，其"是"答案能在多项式时间内验证的判定问题
  4. D任何算法都无法求解的问题
8.困难

用自底向上的方法从 n 个无序元素构建二叉堆的时间复杂度是多少？

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

答案

  1. 1. B · 线性
  2. 2. B · 在更小的输入上调用自身的函数
  3. 3. B · O(log n)
  4. 4. A · O(n log n + k log n)
  5. 5. A · 以 O(V³) 计算所有顶点对之间的最短路径
  6. 6. C · O(n²)
  7. 7. C · 给定证书时，其"是"答案能在多项式时间内验证的判定问题
  8. 8. C · O(n)

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