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

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

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

在包含 n 个元素的无序数组中进行线性查找（linear search）的时间复杂度（最坏情况）是多少？

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

在以邻接表存储的图上进行深度优先搜索，时间复杂度是多少？

1. AO(V × E)
2. BO(V²)
3. CO(E log V)
4. DO(V + E)

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

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

对于在满时将容量翻倍的动态数组，追加元素的均摊（amortised）时间复杂度是多少？

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

快速排序总是使用第一个元素作为基准。它在哪种输入上表现出最坏情况？

1. A长度为 2 的数组
2. B随机顺序的数组
3. C所有元素都不相同的数组
4. D已经有序的数组

对于哪种背包问题变体，贪心规则"按单位重量价值的顺序取物品"总能给出最优解？

1. A0/1 背包问题，物品必须整个拿取
2. B分数背包问题，物品可以分割
3. C两种变体都不可以
4. D两种变体都可以

用动态规划求解 0/1 背包问题需要 O(nW) 时间。为什么称之为伪多项式（pseudo-polynomial）？

1. AW 是一个数值，因此运行时间相对于表示 W 所需的位数是指数级的
2. B因为它只适用于 W = 0
3. C因为该算法是随机化的，其运行时间随每个输入而变化
4. D因为 n 总是很小