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

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

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

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

姓名: ____________________   日期: ____________

1.简单

log₂ 1024 等于多少？

  1. A32
  2. B10
  3. C12
  4. D512
2.简单

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

  1. ABig Theta
  2. BBig O
  3. CBig Omega
  4. DLittle omega
3.简单

归并排序的最坏情况时间复杂度是多少？

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

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

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

下面代码的时间复杂度是多少：for i = 1 to n: (j = 1; while j < n: j = j × 2)？

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

快速排序的最坏情况时间复杂度是多少？

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

关于类 P 的哪个定义是正确的？

  1. A其解可以被验证、但绝不能在多项式时间内找到的问题
  2. B能由确定性算法在多项式时间内求解的判定问题
  3. C能够并行求解的问题
  4. D在每台计算机上都需要指数时间的问题
8.困难

插入排序在有序输入上运行时间为 O(n)。这与比较排序的 Ω(n log n) 下界矛盾吗？

  1. A矛盾，但仅对长度小于 100 的数组
  2. B不矛盾，下界针对的是所有输入中的最坏情况，而不是每一个输入
  3. C矛盾，因此这个下界是错的
  4. D不矛盾，因为插入排序不是比较排序

答案

  1. 1. B · 10
  2. 2. B · Big O
  3. 3. B · O(n log n)
  4. 4. A · O(log n)
  5. 5. B · O(n log n)
  6. 6. A · O(n²)
  7. 7. B · 能由确定性算法在多项式时间内求解的判定问题
  8. 8. B · 不矛盾，下界针对的是所有输入中的最坏情况，而不是每一个输入

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