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

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

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

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

姓名: ____________________   日期: ____________

1.简单

一个算法的运行时间是 O(n)。这种增长称为什么？

  1. A平方
  2. B对数
  3. C常数
  4. D线性
2.简单

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

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

哪种记号表示增长的上界？

  1. ABig O
  2. BBig Omega
  3. CBig Theta
  4. DLittle omega
4.中等

一个函数先运行一个 n 次迭代的循环，然后再单独运行另一个 n 次迭代的循环。它的时间复杂度是多少？

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

对 n 个 k 进制、d 位的整数进行 LSD 基数排序（radix sort），运行时间是多少？

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

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

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

Cook–Levin 定理确立了什么？

  1. AP 不等于 NP
  2. B布尔可满足性问题（SAT）是 NP 完全的
  3. C每个 NP 问题都能在指数时间内求解
  4. D停机问题是不可判定的
8.困难

为什么当某些边权为负时，Dijkstra 算法可能给出错误结果？

  1. A每遇到一条负权边它就会陷入无限循环
  2. B优先队列中不能存储负数
  3. C顶点被取出时距离就被确定，但之后的负权边仍可能给它一条更短的路径
  4. D它只适用于无向图

答案

  1. 1. D · 线性
  2. 2. D · O(n)
  3. 3. A · Big O
  4. 4. A · O(n)
  5. 5. B · O(d(n + k))
  6. 6. A · 它会不断调用自身，直到调用栈溢出
  7. 7. B · 布尔可满足性问题（SAT）是 NP 完全的
  8. 8. C · 顶点被取出时距离就被确定，但之后的负权边仍可能给它一条更短的路径

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