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

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

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

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

姓名: ____________________   日期: ____________

1.简单

递归函数的基本情况是什么？

  1. A无需再进行递归调用就能直接给出答案的情况
  2. B输入最大的情况，它在任何递归调用之前就被处理
  3. C使用内存最多的那次调用
  4. D函数的第一行
2.简单

什么是递归？

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

下列哪个运行时间是多项式的？

  1. AO(2ⁿ)
  2. BO(n!)
  3. CO(n³)
  4. DO(nⁿ)
4.中等

贪心算法（greedy algorithm）：

  1. A总能给出最优解
  2. B只使用递归
  3. C尝试所有可能的解
  4. D在每一步都做出局部最优的选择
5.中等

Prim 算法如何构建最小生成树？

  1. A从一个起始顶点开始扩展一棵树，每次加入离开该树的最便宜的边
  2. B不断删除最贵的边，直到没有环为止
  3. C运行广度优先搜索并保留 BFS 树
  4. D把所有边按权重排序，逐条加入，除非会在森林中形成环
6.中等

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

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

在有 V 个顶点、E 条边的图上，使用二叉堆的 Dijkstra 算法运行时间是多少？

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

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

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

答案

  1. 1. A · 无需再进行递归调用就能直接给出答案的情况
  2. 2. D · 在更小的输入上调用自身的函数
  3. 3. C · O(n³)
  4. 4. D · 在每一步都做出局部最优的选择
  5. 5. A · 从一个起始顶点开始扩展一棵树，每次加入离开该树的最便宜的边
  6. 6. C · O(n)
  7. 7. D · O((V + E) log V)
  8. 8. B · 属于 NP，且所有 NP 问题都能在多项式时间内归约到它

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