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

一个问题通常在什么情况下被称为易解的（tractable）？

1. A能在多项式时间内求解
2. B没有解
3. C能在常数时间内求解
4. D只能通过尝试所有可能来求解

平均情况运行时间描述的是什么？

1. A在给定的规模为 n 的输入分布上的期望时间
2. B在最常见的计算机上所需的时间
3. C最好情况与最坏情况运行时间之间的中间值
4. D平均长度的输入所需的时间

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

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

贪心算法（greedy algorithm）：

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

你对一个 n 个元素的数组排序一次，然后用二分查找回答 k 次成员查询。总代价是多少？

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

在包含 1,000,000 个元素的有序数组上，二分查找在最坏情况下大约需要多少次比较？

1. A约 1,000 次
2. B约 500,000 次
3. C约 20 次
4. D约 100 次

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

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

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

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