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

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

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

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

姓名: ____________________   日期: ____________

1.简单

插入排序（insertion sort）的最坏情况时间复杂度是多少？

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

什么是蛮力算法（brute-force algorithm）？

  1. A尝试所有可能的候选解的算法
  2. B随机猜测答案的算法
  3. C在多个处理器上运行的算法
  4. D总是使用递归的算法
3.简单

在包含 n 个元素的无序数组中进行线性查找（linear search）的时间复杂度（最坏情况）是多少？

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

简单的递归阶乘函数 fact(n) = n × fact(n − 1) 使用多少栈空间？

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

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

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

在活动选择问题中，哪条贪心规则总能得到数量最多的互不重叠的活动？

  1. A选择最早开始的活动
  2. B先选择最短的活动
  3. C先选择与其他活动重叠最少的活动，然后在与之相容的活动中重复这一步
  4. D选择最早结束的活动，然后在与之相容的活动中重复这一步
7.困难

如果有人为某个 NP 完全问题找到了多项式时间算法，会有什么结果？

  1. A只有那一个问题会进入 P
  2. B所有指数时间算法都会立即变成线性时间
  3. C停机问题将变得可判定
  4. DNP 中的每个问题都能在多项式时间内求解，因此 P = NP
8.困难

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

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

答案

  1. 1. D · O(n²)
  2. 2. A · 尝试所有可能的候选解的算法
  3. 3. A · O(n)
  4. 4. A · O(n)
  5. 5. B · O(2ⁿ)
  6. 6. D · 选择最早结束的活动，然后在与之相容的活动中重复这一步
  7. 7. D · NP 中的每个问题都能在多项式时间内求解，因此 P = NP
  8. 8. A · 由于不能按下标直接访问，到达中间元素需要 O(n) 步

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