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

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

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

什么是蛮力算法（brute-force algorithm）？

1. A在多个处理器上运行的算法
2. B总是使用递归的算法
3. C随机猜测答案的算法
4. D尝试所有可能的候选解的算法

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

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

在有 V 个顶点、E 条边的图上，Bellman–Ford 算法的时间复杂度是多少？

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

关于一个没有可达基本情况的递归函数，下列哪个说法是正确的？

1. A它的运行时间为 O(1)
2. B它会不断调用自身，直到调用栈溢出
3. C它会自动返回 0
4. D编译器总会把它变成能安全结束的循环

在无权图上进行广度优先搜索（BFS）可以求出：

1. A最小生成树
2. B含负权重边的图中的最短路径
3. C从起始节点出发、按边数计的最短路径
4. D所有图的拓扑序

为什么在单链表上二分查找不能达到 O(log n) 的时间？

1. A由于不能按下标直接访问，到达中间元素需要 O(n) 步
2. B二分查找至少需要两倍的内存
3. C链表节点上的比较更慢
4. D链表无法排序

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

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