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

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

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

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

姓名: ____________________   日期: ____________

1.简单

选择排序（selection sort）是如何工作的？

  1. A通过移动元素，把每个元素插入到不断增长的有序部分中
  2. B把数组对半分开再合并
  3. C反复交换顺序错误的相邻元素
  4. D反复找出未排序部分的最小值，并把它交换到前面
2.简单

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

  1. AΩ（Big Omega）
  2. BΘ（Big Theta）
  3. Co（little o）
  4. DO（Big O）
3.简单

如果一个操作的运行时间是 O(1)，这意味着什么？

  1. A它的运行时间不随输入规模增长
  2. B它只能运行一次
  3. C它总是恰好花费一秒
  4. D它每秒运行时间恰好处理一个元素
4.中等

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

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

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

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

说一个 O(n²) 算法也是 O(n³)，这正确吗？

  1. A不正确，因为当 n 很大时 n³ 小于 n²
  2. B正确，因为 Big O 是上界，而 n² 的增长不比 n³ 快
  3. C不正确，因为 Big O 必须始终给出函数的确切增长率
  4. D正确，但仅当 n 小于 100 时
7.困难

下列哪个可满足性问题已知可以在多项式时间内求解？

  1. A电路可满足性问题
  2. B3-SAT，每个子句恰好有三个文字
  3. C合取范式公式上的一般 SAT
  4. D2-SAT，每个子句至多有两个文字
8.困难

不可判定问题与难解问题有什么区别？

  1. A难解问题无法被任何算法求解，而不可判定问题只需要指数时间
  2. B两者都意味着该问题根本没有算法
  3. C不可判定问题属于 NP，而难解问题属于 P
  4. D不可判定问题没有任何能处理所有输入的算法，而难解问题有算法，但太慢

答案

  1. 1. D · 反复找出未排序部分的最小值，并把它交换到前面
  2. 2. A · Ω（Big Omega）
  3. 3. A · 它的运行时间不随输入规模增长
  4. 4. C · O(d(n + k))
  5. 5. A · O(n)
  6. 6. B · 正确，因为 Big O 是上界，而 n² 的增长不比 n³ 快
  7. 7. D · 2-SAT，每个子句至多有两个文字
  8. 8. D · 不可判定问题没有任何能处理所有输入的算法，而难解问题有算法，但太慢

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