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

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

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

如果一个操作的运行时间是 O(1)，这意味着什么？

1. A它每秒运行时间恰好处理一个元素
2. B它总是恰好花费一秒
3. C它的运行时间不随输入规模增长
4. D它只能运行一次

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

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

贪心算法（greedy algorithm）：

1. A只使用递归
2. B尝试所有可能的解
3. C在每一步都做出局部最优的选择
4. D总能给出最优解

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

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

当问题具有以下特征时，动态规划（dynamic programming）很有用：

1. A只有一个循环
2. B只有随机输入
3. C重叠子问题和最优子结构
4. D完全没有子问题，因此一步就能解决

用自底向上的方法从 n 个无序元素构建二叉堆的时间复杂度是多少？

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

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

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