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

一个包含两层嵌套循环、每层都执行 n 次的算法，通常具有哪种复杂度？

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

递归函数的基本情况是什么？

1. A无需再进行递归调用就能直接给出答案的情况
2. B函数的第一行
3. C使用内存最多的那次调用
4. D输入最大的情况，它在任何递归调用之前就被处理

哪种排序算法会反复交换顺序错误的相邻元素？

1. A堆排序（Heap sort）
2. B冒泡排序（Bubble sort）
3. C快速排序（Quicksort）
4. D归并排序（Merge sort）

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

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

说一个 O(n²) 算法也是 O(n³)，这正确吗？

1. A正确，因为 Big O 是上界，而 n² 的增长不比 n³ 快
2. B正确，但仅当 n 小于 100 时
3. C不正确，因为 Big O 必须始终给出函数的确切增长率
4. D不正确，因为当 n 很大时 n³ 小于 n²

Prim 算法如何构建最小生成树？

1. A运行广度优先搜索并保留 BFS 树
2. B不断删除最贵的边，直到没有环为止
3. C把所有边按权重排序，逐条加入，除非会在森林中形成环
4. D从一个起始顶点开始扩展一棵树，每次加入离开该树的最便宜的边

用动态规划求解 0/1 背包问题需要 O(nW) 时间。为什么称之为伪多项式（pseudo-polynomial）？

1. AW 是一个数值，因此运行时间相对于表示 W 所需的位数是指数级的
2. B因为它只适用于 W = 0
3. C因为该算法是随机化的，其运行时间随每个输入而变化
4. D因为 n 总是很小

对于哪种背包问题变体，贪心规则"按单位重量价值的顺序取物品"总能给出最优解？

1. A0/1 背包问题，物品必须整个拿取
2. B两种变体都可以
3. C分数背包问题，物品可以分割
4. D两种变体都不可以