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

log₂ 1024 等于多少？

1. A10
2. B512
3. C12
4. D32

归并排序采用哪种设计策略？

1. A分治法（divide and conquer）
2. B动态规划
3. C贪心选择
4. D蛮力法

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

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

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

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

一个问题具有最优子结构是什么意思？

1. A最优解可以由其子问题的最优解构造出来
2. B该问题可以在常数时间内求解
3. C该问题恰好有一个最优解，所有子问题共享这个解
4. D每个子问题的规模都相同

为什么在 Big O 中通常省略对数的底，例如写成 O(log n)？

1. A计算机科学中所有对数的底都是 10，所以可以省略
2. B底只在 n 很小时才有影响
3. C对数总是被四舍五入为整数
4. D不同底的对数之间只相差一个常数因子

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

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

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

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