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

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

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

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

姓名: ____________________   日期: ____________

1.简单

f(n) = Θ(g(n)) 是什么意思？

  1. Af 的增长严格快于 g
  2. Bf 与 g 以相同的速率增长，上下都被 g 的常数倍所界定
  3. Cf 的增长严格慢于 g
  4. D对每个 n，f 总是小于 g，因此 g 是它的上界，但绝不是下界
2.简单

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

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

二分查找对输入有什么要求？

  1. A数组长度必须是 2 的幂
  2. B数组元素不能超过 1000 个
  3. C数组只能包含正数
  4. D数组必须有序
4.中等

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

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

下面代码的时间复杂度是多少：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)
6.中等

在有 V 个顶点、E 条边的图上，Bellman–Ford 算法的时间复杂度是多少？

  1. AO(E log V)
  2. BO(V + E)
  3. CO(V × E)
  4. DO(V³ × E)
7.困难

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

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

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

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

答案

  1. 1. B · f 与 g 以相同的速率增长，上下都被 g 的常数倍所界定
  2. 2. A · Big O
  3. 3. D · 数组必须有序
  4. 4. D · O(n)
  5. 5. A · O(n²)
  6. 6. C · O(V × E)
  7. 7. B · 能由确定性算法在多项式时间内求解的判定问题
  8. 8. C · O(n log n)

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