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

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

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

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

姓名: ____________________   日期: ____________

1.简单

分治算法的三个步骤是什么？

  1. A分解、解决、合并
  2. B猜测、检查、重复
  3. C排序、查找、返回
  4. D读取、计算、写入
2.简单

3n² + 5n + 2 的 Big O 是什么？

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

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

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

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

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

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

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

为什么在 Big O 中通常省略对数的底，例如写成 O(log n)？

  1. A不同底的对数之间只相差一个常数因子
  2. B对数总是被四舍五入为整数
  3. C底只在 n 很小时才有影响
  4. D计算机科学中所有对数的底都是 10，所以可以省略
7.困难

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

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

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

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

答案

  1. 1. A · 分解、解决、合并
  2. 2. D · O(n²)
  3. 3. B · 分治法（divide and conquer）
  4. 4. C · O(2ⁿ)
  5. 5. A · O(log n)
  6. 6. A · 不同底的对数之间只相差一个常数因子
  7. 7. C · X 属于 NP，并且某个已知的 NP 完全问题能在多项式时间内归约到 X
  8. 8. D · 由于不能按下标直接访问，到达中间元素需要 O(n) 步

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