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

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

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

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

姓名: ____________________   日期: ____________

1.简单

归并排序采用哪种设计策略？

  1. A贪心选择
  2. B动态规划
  3. C蛮力法
  4. D分治法（divide and conquer）
2.简单

什么是算法？

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

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

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

关于一个没有可达基本情况的递归函数，下列哪个说法是正确的？

  1. A它会自动返回 0
  2. B编译器总会把它变成能安全结束的循环
  3. C它会不断调用自身，直到调用栈溢出
  4. D它的运行时间为 O(1)
5.中等

在无权图上进行广度优先搜索（BFS）可以求出：

  1. A含负权重边的图中的最短路径
  2. B所有图的拓扑序
  3. C最小生成树
  4. D从起始节点出发、按边数计的最短路径
6.中等

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

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

为什么哈希表的平均查找时间是 O(1)，而最坏情况是 O(n)？

  1. A许多键可能冲突（collision）到同一个桶中
  2. B键必须先排序
  3. C数组的访问时间是 O(n)
  4. D哈希函数运行很慢
8.困难

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

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

答案

  1. 1. D · 分治法（divide and conquer）
  2. 2. A · 解决问题的、由有限个明确定义的步骤组成的序列
  3. 3. A · 分解、解决、合并
  4. 4. C · 它会不断调用自身，直到调用栈溢出
  5. 5. D · 从起始节点出发、按边数计的最短路径
  6. 6. B · 选择最早结束的活动，然后在与之相容的活动中重复这一步
  7. 7. A · 许多键可能冲突（collision）到同一个桶中
  8. 8. B · 属于 NP，且所有 NP 问题都能在多项式时间内归约到它

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