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

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

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

空间复杂度衡量的是：

1. A计算机的物理尺寸
2. B代码的行数
3. C随着输入增大，算法所需的内存量
4. D程序编译后程序文件占用的磁盘空间

当 n 变大时，下列哪一项增长最慢？

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

你对一个 n 个元素的数组排序一次，然后用二分查找回答 k 次成员查询。总代价是多少？

1. AO(n + k)
2. BO(k n log n)
3. CO(n log n + k log n)
4. DO(nk)

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

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

硬币面值为 1、3 和 4，金额为 6，贪心的"先取最大硬币"方法使用多少枚硬币？与最优解相比如何？

1. A贪心用 3 枚；最优解是 2 枚
2. B贪心用 3 枚；最优解是 3 枚
3. C贪心用 4 枚；最优解是 3 枚
4. D贪心用 2 枚；最优解是 2 枚

Karatsuba 乘法满足 T(n) = 3T(n/2) + O(n)。它的解是什么？

1. AΘ(n log n)
2. BΘ(n³)
3. CΘ(n²)
4. DΘ(n^{log₂ 3})，约为 n^1.585

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

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