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

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

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

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

姓名: ____________________   日期: ____________

1.简单

空间复杂度衡量的是：

  1. A随着输入增大，算法所需的内存量
  2. B计算机的物理尺寸
  3. C程序编译后程序文件占用的磁盘空间
  4. D代码的行数
2.简单

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

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

一个 O(n) 算法在 n = 100 万时需要 3 秒。n = 200 万时大约需要多长时间？

  1. A6 秒
  2. B3 秒
  3. C12 秒
  4. D9 秒
4.中等

快速排序的最坏情况时间复杂度是多少？

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

用自底向上的表格计算第 n 个斐波那契数，时间复杂度是多少？

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

在边权非负的图中，哪种算法用于求单源最短路径？

  1. AKruskal 算法
  2. BDijkstra 算法
  3. C深度优先搜索（DFS）
  4. D任何情况下都必须使用 Bellman–Ford
7.困难

插入排序在有序输入上运行时间为 O(n)。这与比较排序的 Ω(n log n) 下界矛盾吗？

  1. A不矛盾，因为插入排序不是比较排序
  2. B矛盾，但仅对长度小于 100 的数组
  3. C矛盾，因此这个下界是错的
  4. D不矛盾，下界针对的是所有输入中的最坏情况，而不是每一个输入
8.困难

要证明一个判定问题 X 是 NP 完全的，必须证明哪两点？

  1. AX 能归约到 P 中的某个问题，并且 X 属于 NP
  2. BX 没有多项式算法，并且 X 是可判定的
  3. CX 属于 NP，并且某个已知的 NP 完全问题能在多项式时间内归约到 X
  4. DX 属于 P，并且 X 能归约到 SAT

答案

  1. 1. A · 随着输入增大，算法所需的内存量
  2. 2. B · O(n²)
  3. 3. A · 6 秒
  4. 4. D · O(n²)
  5. 5. C · O(n)
  6. 6. B · Dijkstra 算法
  7. 7. D · 不矛盾，下界针对的是所有输入中的最坏情况，而不是每一个输入
  8. 8. C · X 属于 NP，并且某个已知的 NP 完全问题能在多项式时间内归约到 X

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