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

一个算法的运行时间是 O(n)。这种增长称为什么？

1. A对数
2. B线性
3. C常数
4. D平方

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

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

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

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

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

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

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

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

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

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

关于在无序数组中选择第 k 小的元素，下列哪个说法是正确的？

1. A快速选择的最坏情况为 O(log n)，因为它只对枢轴的一侧递归
2. B选择总是需要 Ω(n log n)，因为必须先排序
3. C选择只能在 O(n²) 内完成
4. D快速选择的期望时间为 O(n)，而中位数的中位数法保证最坏情况为 O(n)

要证明一个新问题 X 是 NP 难（NP-hard）的，必须做什么？

1. A把一个已知的 NP 难问题在多项式时间内归约到 X
2. B证明 X 对于小规模输入没有多项式算法
3. C把 X 在多项式时间内归约到一个已知的 NP 难问题
4. D证明 X 能在多项式时间内被验证