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

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

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

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

姓名: ____________________   日期: ____________

1.简单

log₂ 1024 等于多少？

  1. A10
  2. B512
  3. C12
  4. D32
2.简单

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

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

一个 O(n²) 算法在 n = 1000 时需要 1 秒。n = 2000 时大约需要多长时间？

  1. A8 秒
  2. B1 秒
  3. C2 秒
  4. D4 秒
4.中等

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

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

在一个有序数组中，你从两端各放一个指针向内移动，寻找和为目标值的两个元素。时间复杂度是多少？

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

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

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

要证明一个新问题 X 是 NP 难（NP-hard）的，必须做什么？

  1. A把一个已知的 NP 难问题在多项式时间内归约到 X
  2. B把 X 在多项式时间内归约到一个已知的 NP 难问题
  3. C证明 X 能在多项式时间内被验证
  4. D证明 X 对于小规模输入没有多项式算法
8.困难

一次加一操作可能翻转许多位，那么二进制计数器加一的均摊代价是多少？

  1. A每次加一 O(log n)
  2. B每次加一 O(1)
  3. C每次加一 O(n log n)
  4. D每次加一 O(n)

答案

  1. 1. A · 10
  2. 2. A · 分解、解决、合并
  3. 3. D · 4 秒
  4. 4. B · O(n)
  5. 5. D · O(n)
  6. 6. C · O(n)
  7. 7. A · 把一个已知的 NP 难问题在多项式时间内归约到 X
  8. 8. B · 每次加一 O(1)

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