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

什么是递归？

1. A永远不会结束的循环
2. B一种数据结构
3. C一种排序方法
4. D在更小的输入上调用自身的函数

在 n 个数的无序数组中找出最大值的时间复杂度是多少？

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

算法的最坏情况运行时间描述的是什么？

1. A在最小输入上所需的时间
2. B在慢速计算机上所需的时间
3. C在规模为 n 的随机输入上所需的期望时间
4. D在所有规模为 n 的输入上所需的最长时间

在无权图上进行广度优先搜索（BFS）可以求出：

1. A从起始节点出发、按边数计的最短路径
2. B最小生成树
3. C所有图的拓扑序
4. D含负权重边的图中的最短路径

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

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

均摊分析衡量的是什么？

1. A在最坏情况的操作序列上，每个操作的平均代价
2. B序列中任何位置上单个最昂贵操作的代价
3. C在随机输入上的期望代价
4. D算法在最好输入上的代价

使用主定理，T(n) = 8T(n/2) + O(n²) 的解是：

1. AΘ(n³)
2. BΘ(n²)
3. CΘ(n² log n)
4. DΘ(n log n)

为什么哈希表的平均查找时间是 O(1)，而最坏情况是 O(n)？

1. A键必须先排序
2. B哈希函数运行很慢
3. C数组的访问时间是 O(n)
4. D许多键可能冲突（collision）到同一个桶中