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

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

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

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

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

递归函数的基本情况是什么？

1. A函数的第一行
2. B无需再进行递归调用就能直接给出答案的情况
3. C输入最大的情况，它在任何递归调用之前就被处理
4. D使用内存最多的那次调用

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

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

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

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

哪种排序算法是稳定的？

1. A归并排序
2. B堆排序
3. C快速排序（常见的原地版本）
4. D选择排序（常见版本）

要证明一个判定问题 X 是 NP 完全的，必须证明哪两点？

1. AX 能归约到 P 中的某个问题，并且 X 属于 NP
2. BX 属于 NP，并且某个已知的 NP 完全问题能在多项式时间内归约到 X
3. CX 属于 P，并且 X 能归约到 SAT
4. DX 没有多项式算法，并且 X 是可判定的

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

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