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

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

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

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

姓名: ____________________   日期: ____________

1.简单

在以邻接表存储的图上进行深度优先搜索，时间复杂度是多少？

  1. AO(E log V)
  2. BO(V + E)
  3. CO(V × E)
  4. DO(V²)
2.简单

一个 O(n²) 算法在 n = 1000 时需要 1 秒。n = 2000 时大约需要多长时间？

  1. A8 秒
  2. B2 秒
  3. C4 秒
  4. D1 秒
3.简单

标准的基于数组的归并排序使用多少额外内存？

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

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

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

为什么在 Big O 中通常省略对数的底，例如写成 O(log n)？

  1. A不同底的对数之间只相差一个常数因子
  2. B计算机科学中所有对数的底都是 10，所以可以省略
  3. C底只在 n 很小时才有影响
  4. D对数总是被四舍五入为整数
6.中等

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

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

拓扑排序只适用于：

  1. A带负权重的图
  2. B完全图
  3. C有向无环图（DAG）
  4. D无向图
8.困难

关于 P 和 NP，下列哪个说法是正确的？

  1. A已经证明 P ≠ NP
  2. BP 中的每个问题也都属于 NP
  3. CNP 表示“not polynomial”（非多项式）
  4. DNP 问题无法被快速验证

答案

  1. 1. B · O(V + E)
  2. 2. C · 4 秒
  3. 3. D · O(n)
  4. 4. C · Ω(n log n)
  5. 5. A · 不同底的对数之间只相差一个常数因子
  6. 6. C · O(n log n)
  7. 7. C · 有向无环图（DAG）
  8. 8. B · P 中的每个问题也都属于 NP

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