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

选择排序（selection sort）是如何工作的？

1. A把数组对半分开再合并
2. B反复交换顺序错误的相邻元素
3. C反复找出未排序部分的最小值，并把它交换到前面
4. D通过移动元素，把每个元素插入到不断增长的有序部分中

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

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

一个问题通常在什么情况下被称为易解的（tractable）？

1. A没有解
2. B只能通过尝试所有可能来求解
3. C能在多项式时间内求解
4. D能在常数时间内求解

对 n 个元素的数组进行归并排序，递归共有多少层？

1. A约 √n 层
2. B约 log₂ n 层
3. C约 n / 2 层
4. D约 n 层

用自底向上的表格计算第 n 个斐波那契数，时间复杂度是多少？

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

朴素递归斐波那契（fib(n) = fib(n−1) + fib(n−2)）的时间复杂度是：

1. A常数
2. B对数级
3. C指数级
4. D线性

哪种技术能使快速排序在任意输入上的期望运行时间为 O(n log n)？

1. A均匀随机地选择基准
2. B在运行快速排序前先对输入排序
3. C总是选择第一个元素
4. D只对左侧进行递归

2²ⁿ 属于 O(2ⁿ) 吗？

1. A不属于，因为 2²ⁿ = 4ⁿ，而 4ⁿ / 2ⁿ = 2ⁿ 无界地增长
2. B属于，因为在 Big O 中指数里的常数因子总是被忽略
3. C属于，因为两者都是指数级的
4. D不属于，因为 2²ⁿ 增长得比 2ⁿ 慢