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

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

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

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

姓名: ____________________   日期: ____________

1.简单

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

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

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

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

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

  1. ABig Omega
  2. BLittle omega
  3. CBig O
  4. DBig Theta
4.中等

对 n 个元素的数组进行归并排序，递归共有多少层？

  1. A约 n / 2 层
  2. B约 n 层
  3. C约 log₂ n 层
  4. D约 √n 层
5.中等

当问题具有以下特征时，动态规划（dynamic programming）很有用：

  1. A完全没有子问题，因此一步就能解决
  2. B重叠子问题和最优子结构
  3. C只有随机输入
  4. D只有一个循环
6.中等

在包含 1,000,000 个元素的有序数组上，二分查找在最坏情况下大约需要多少次比较？

  1. A约 1,000 次
  2. B约 100 次
  3. C约 20 次
  4. D约 500,000 次
7.困难

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

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

关于 log(n!)，哪个界是正确的？

  1. AΘ(log n)
  2. BΘ(n)
  3. CΘ(n log n)
  4. DΘ(n²)

答案

  1. 1. C · 反复找出未排序部分的最小值，并把它交换到前面
  2. 2. B · O(n²)
  3. 3. C · Big O
  4. 4. C · 约 log₂ n 层
  5. 5. B · 重叠子问题和最优子结构
  6. 6. C · 约 20 次
  7. 7. B · X 属于 NP，并且某个已知的 NP 完全问题能在多项式时间内归约到 X
  8. 8. C · Θ(n log n)

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