算法分析与设计答案2023秋

第十二章测试

1.

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

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

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

A:错 B:对 3.

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

A:对 B:错 4.

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

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

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

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

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

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

下列说法错误的是

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