算法分析与设计答案2023

第十二章测试

1.

有多项式时间算法的问题是易解问题

A:对 B:错
答案:A
2.

EXP类是所有指数时间可解的判定问题组成的问题类

A:对 B:错 3.

如果对于X的任意实例，通过多项式次的计算步骤，加多项式次调用Y的算法，可解决X，则X可多项式时间归约到Y。

A:错 B:对 4.

下面关于NP问题说法正确的是（ ）

A:NP问题都是不可能解决的问题 B:NP完全问题是P类问题的子集 C:P类问题包含在NP类问题中 D:NP类问题包含在P类问题中 5.

下面属于NP完全问题的是（）

A:最小顶点覆盖 B:SAT C:最大独立集 D:旅行商问题 6.

以下关于判定问题难易处理的叙述中错误的是

A:可以由多项式时间算法求解的问题是难处理的 B:需要超过多项式时间算法求解的问题是易处理的 C:可以由多项式时间算法求解的问题是易处理的 D:需要超过多项式时间算法求解的问题是不能处理的 7.

下列说法错误的是

A:如果一个NP完全问题有多项式时间算法，那么NP中的每一个问题都可以有多项式时间算法 B:If X 多项式时间归约到Y and Y 多项式时间归约到Z, then X多项式时间归约到Z.
C:判定问题可多项式时间变换到优化问题 D:P 包含于 NP 8.

问题Y NP，对于任意的NP类问题X， XY,则Y NP完全问题。

A:对 B:错 9.

NP完全问题的证明方法有（）

A:局部替换 B:分支设计 C:限制技术 D:定义法 10.

在一个平面或球面的任何地图能够只用4种颜色着色，使相邻国家在地图上着不同颜色。

A:对 B:错 11.

任何图的二着色问题都是NPC问题

A:错 B:对 12.

如果 k 为小常数, 最小顶点覆盖问题存在多项式时间算法。

A:错 B:对 13.

如果一个NP完全问题能在多项式时间内得到解决，那么NP中的每一个问题都可以在多项式时间内求解。

A:错 B:对