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

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

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

一个 O(n) 算法在 n = 100 万时需要 3 秒。n = 200 万时大约需要多长时间？

1. A6 秒
2. B12 秒
3. C9 秒
4. D3 秒

在有序数组上进行二分查找（binary search）的时间复杂度是多少？

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

Floyd–Warshall 算法计算什么？速度如何？

1. A以 O(E log V) 计算最小生成树
2. B以 O(V²) 计算拓扑序
3. C以 O(V³) 计算所有顶点对之间的最短路径
4. D以 O(V + E) 计算从一个源顶点到所有其他顶点的最短路径

为什么动态规划不能真正加速归并排序？

1. A归并排序没有递归结构
2. B动态规划只适用于图问题，不适用于数组
3. C归并排序已经是 O(n)
4. D它的子问题不重叠，因此没有可以复用的结果

简单的递归阶乘函数 fact(n) = n × fact(n − 1) 使用多少栈空间？

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

拓扑排序只适用于：

1. A有向无环图（DAG）
2. B完全图
3. C带负权重的图
4. D无向图

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

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