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

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

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

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

姓名: ____________________   日期: ____________

1.简单

一个包含两层嵌套循环、每层都执行 n 次的算法，通常具有哪种复杂度？

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

哪种排序算法会反复交换顺序错误的相邻元素？

  1. A归并排序（Merge sort）
  2. B冒泡排序（Bubble sort）
  3. C快速排序（Quicksort）
  4. D堆排序（Heap sort）
3.简单

一个循环从 i = 1 开始，每次迭代将 i 翻倍，直到 i > n。它运行多少次迭代？

  1. A约 log₂ n 次
  2. B约 n / 2 次
  3. C约 n² 次
  4. D约 n 次
4.中等

下面代码的时间复杂度是多少：for i = 1 to n: (j = 1; while j < n: j = j × 2)？

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

对于在满时将容量翻倍的动态数组，追加元素的均摊（amortised）时间复杂度是多少？

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

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

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

下面代码的时间复杂度是多少：for i = 1 to n: for (j = i; j ≤ n; j = j + i) 执行 O(1) 的工作？

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

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

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

答案

  1. 1. D · O(n²)
  2. 2. B · 冒泡排序（Bubble sort）
  3. 3. A · 约 log₂ n 次
  4. 4. C · O(n log n)
  5. 5. A · O(1)
  6. 6. C · 以 O(V³) 计算所有顶点对之间的最短路径
  7. 7. D · O(n log n)
  8. 8. C · 属于 NP，且所有 NP 问题都能在多项式时间内归约到它

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