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

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

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

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

姓名: ____________________   日期: ____________

1.简单

在以邻接表存储的图上进行深度优先搜索，时间复杂度是多少？

  1. AO(V × E)
  2. BO(E log V)
  3. CO(V²)
  4. DO(V + E)
2.简单

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

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

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

  1. ABig Theta
  2. BLittle omega
  3. CBig O
  4. DBig Omega
4.中等

一个问题具有最优子结构是什么意思？

  1. A最优解可以由其子问题的最优解构造出来
  2. B每个子问题的规模都相同
  3. C该问题恰好有一个最优解，所有子问题共享这个解
  4. D该问题可以在常数时间内求解
5.中等

快速排序总是使用第一个元素作为基准。它在哪种输入上表现出最坏情况？

  1. A随机顺序的数组
  2. B所有元素都不相同的数组
  3. C长度为 2 的数组
  4. D已经有序的数组
6.中等

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

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

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

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

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

  1. A给定证书时，其"是"答案能在多项式时间内验证的判定问题
  2. B任何算法都无法求解的问题
  3. C非多项式的问题
  4. D不能在多项式时间内求解的问题

答案

  1. 1. D · O(V + E)
  2. 2. D · O(n)
  3. 3. C · Big O
  4. 4. A · 最优解可以由其子问题的最优解构造出来
  5. 5. D · 已经有序的数组
  6. 6. A · O(2ⁿ)
  7. 7. D · 每次加一 O(1)
  8. 8. A · 给定证书时，其"是"答案能在多项式时间内验证的判定问题

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