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

哪种排序算法选择一个基准，并把数组划分为较小元素和较大元素两部分？

1. A冒泡排序
2. B插入排序
3. C快速排序
4. D归并排序

标准的基于数组的归并排序使用多少额外内存？

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

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

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

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

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

对长度为 m 和 n 的两个字符串求最长公共子序列，标准动态规划算法的时间复杂度是多少？

1. AO(mn)
2. BO(m + n)
3. CO(2^m+n)
4. DO(mn log n)

在一个有序数组中，你从两端各放一个指针向内移动，寻找和为目标值的两个元素。时间复杂度是多少？

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

拓扑排序只适用于：

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

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

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