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

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

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

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

姓名: ____________________   日期: ____________

1.简单

对范围在 0 到 k 之间的 n 个整数进行计数排序（counting sort），运行时间是多少？

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

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

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

在有序数组上进行二分查找（binary search）的时间复杂度是多少？

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

递推式 T(n) = 2T(n/2) + O(1) 的解是什么？

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

快速排序总是使用第一个元素作为基准。它在哪种输入上表现出最坏情况？

  1. A随机顺序的数组
  2. B所有元素都不相同的数组
  3. C长度为 2 的数组
  4. D已经有序的数组
6.中等

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

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

要证明一个新问题 X 是 NP 难（NP-hard）的，必须做什么？

  1. A证明 X 对于小规模输入没有多项式算法
  2. B把一个已知的 NP 难问题在多项式时间内归约到 X
  3. C把 X 在多项式时间内归约到一个已知的 NP 难问题
  4. D证明 X 能在多项式时间内被验证
8.困难

Cook–Levin 定理确立了什么？

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

答案

  1. 1. A · O(n + k)
  2. 2. A · 线性
  3. 3. C · O(log n)
  4. 4. B · O(n)
  5. 5. D · 已经有序的数组
  6. 6. A · O(d(n + k))
  7. 7. B · 把一个已知的 NP 难问题在多项式时间内归约到 X
  8. 8. B · 布尔可满足性问题（SAT）是 NP 完全的

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