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

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

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

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

姓名: ____________________   日期: ____________

1.简单

当 n 很大时，哪个复杂度类增长最快？

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

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

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

归并排序采用哪种设计策略？

  1. A分治法（divide and conquer）
  2. B蛮力法
  3. C贪心选择
  4. D动态规划
4.中等

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

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

朴素递归斐波那契（fib(n) = fib(n−1) + fib(n−2)）的时间复杂度是：

  1. A线性
  2. B常数
  3. C指数级
  4. D对数级
6.中等

下面代码的时间复杂度是多少：for i = 1 to n: for j = 1 to i: 执行 O(1) 的工作？

  1. AO(n²)
  2. BO(n)
  3. CO(n³)
  4. DO(n log n)
7.困难

Cook–Levin 定理确立了什么？

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

为什么在单链表上二分查找不能达到 O(log n) 的时间？

  1. A链表无法排序
  2. B二分查找至少需要两倍的内存
  3. C链表节点上的比较更慢
  4. D由于不能按下标直接访问，到达中间元素需要 O(n) 步

答案

  1. 1. A · O(2ⁿ)
  2. 2. D · O(log n)
  3. 3. A · 分治法（divide and conquer）
  4. 4. A · 已经有序的数组
  5. 5. C · 指数级
  6. 6. A · O(n²)
  7. 7. D · 布尔可满足性问题（SAT）是 NP 完全的
  8. 8. D · 由于不能按下标直接访问，到达中间元素需要 O(n) 步

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