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

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

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

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

姓名: ____________________   日期: ____________

1.简单

当 n 变大时，下列哪一项增长最慢？

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

O(2ⁿ) 的增长称为什么？

  1. A指数级
  2. B多项式级
  3. C对数级
  4. D线性
3.简单

哪种排序算法选择一个基准，并把数组划分为较小元素和较大元素两部分？

  1. A插入排序
  2. B冒泡排序
  3. C快速排序
  4. D归并排序
4.中等

基于比较的排序在最坏情况下的下界是：

  1. AΩ(log n)
  2. BΩ(n)
  3. CΩ(n²)
  4. DΩ(n log n)
5.中等

一个问题具有最优子结构是什么意思？

  1. A每个子问题的规模都相同
  2. B该问题恰好有一个最优解，所有子问题共享这个解
  3. C该问题可以在常数时间内求解
  4. D最优解可以由其子问题的最优解构造出来
6.中等

Floyd–Warshall 算法计算什么？速度如何？

  1. A以 O(V²) 计算拓扑序
  2. B以 O(V + E) 计算从一个源顶点到所有其他顶点的最短路径
  3. C以 O(E log V) 计算最小生成树
  4. D以 O(V³) 计算所有顶点对之间的最短路径
7.困难

Bellman–Ford 算法如何检测从源点可达的负权环？

  1. A检查是否有边的权重为负
  2. B在 V − 1 轮之后，检查是否还有边可以被松弛
  3. C它运行两次 Dijkstra 算法，并比较两次的距离结果
  4. D用深度优先搜索统计环的数量
8.困难

如果有人为某个 NP 完全问题找到了多项式时间算法，会有什么结果？

  1. A只有那一个问题会进入 P
  2. B所有指数时间算法都会立即变成线性时间
  3. CNP 中的每个问题都能在多项式时间内求解，因此 P = NP
  4. D停机问题将变得可判定

答案

  1. 1. B · O(log n)
  2. 2. A · 指数级
  3. 3. C · 快速排序
  4. 4. D · Ω(n log n)
  5. 5. D · 最优解可以由其子问题的最优解构造出来
  6. 6. D · 以 O(V³) 计算所有顶点对之间的最短路径
  7. 7. B · 在 V − 1 轮之后，检查是否还有边可以被松弛
  8. 8. C · NP 中的每个问题都能在多项式时间内求解，因此 P = NP

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