智慧树知到答案算法分析与设计（山东联盟）最新答案

第一章 单元测试

1、判断题：
一个问题的同一实例可以有不同的表示形式
选项：
A:错
B:对
答案: 【对】

2、判断题：
同一数学模型使用不同的数据结构会有不同的算法，有效性有很大差别。
选项：
A:错
B:对
答案: 【对】

3、判断题：
问题的两个要素是输入和实例。
选项：
A:对
B:错
答案: 【错】

4、单选题：
算法与程序的区别是（）
选项：
A:有穷性
B:确定性
C:输出
D:输入
答案: 【有穷性】

5、单选题：
解决问题的基本步骤是（）。（1）算法设计（2）算法实现（3）数学建模（4）算法分析（5）正确性证明
选项：
A:(3)(1)(5)(4)(2)
B:(1)(2)(3)(4)(5)
C:(3)(4)(1)(5)(2)
D:(3)(1)(4)(5)(2)
答案: 【(3)(1)(5)(4)(2)】

6、单选题：

下面说法关于算法与问题的说法错误的是（）。
选项：
A:同一问题可能有几种不同的算法，解题思路和解题速度也会显著不同。
B:算法是一种计算方法，对问题的每个实例计算都能得到正确答案。
C:证明算法不正确，需要证明对任意实例算法都不能正确处理。
D:如果一个算法能应用于问题的任意实例，并保证得到正确解答，称这个算法解答了该问题。
答案: 【证明算法不正确，需要证明对任意实例算法都不能正确处理。】

7、多选题：
下面关于程序和算法的说法正确的是（）。
选项：
A:算法是一个过程，计算机每次求解是针对问题的一个实例求解。
B:程序是算法用某种程序设计语言的具体实现。
C:程序总是在有穷步的运算后终止。
D:算法的每一步骤必须要有确切的含义，必须是清楚的、无二义的。
答案: 【算法是一个过程，计算机每次求解是针对问题的一个实例求解。;程序是算法用某种程序设计语言的具体实现。;算法的每一步骤必须要有确切的含义，必须是清楚的、无二义的。】

8、多选题：
最大独立集问题和（）问题等价。
选项：
A:稳定匹配问题
B:最小顶点覆盖
C:区间调度问题
D:最大团
答案: 【最小顶点覆盖;最大团】

9、多选题：
给定两张喜欢列表，稳定匹配问题的输出是（  ） 。
选项：
A:完美匹配
B:稳定匹配
C:没有不稳定配对
D:最大匹配
答案: 【完美匹配;稳定匹配;没有不稳定配对;最大匹配】

10、单选题：

问题变换的目的有（）。(1)复杂变简单 (2)未知变已知 (3)隐式变显式 (4)难解变易解 （5）以上都是。
选项：
A:（3）

B:（4）

C:（5）
D:（1）

E:（2）

答案: 【（5）】

11、单选题：

按照霍纳法则，计算p(x) = a_nxⁿ + a_n-1x^n-1 +… + a₁x¹ + a₀   的数量级为____ 。
选项：
A:n^2

B:n

C:logn

D:nlogn

答案: 【n
】

第二章 单元测试

1、判断题：
时间复杂度是指算法最坏情况下的运行时间。
选项：
A:对
B:错
答案: 【对】

2、判断题：
f(n)=3n³+7n²+4nlogn =O（n²）
选项：
A:对
B:错
答案: 【错】

3、判断题：
如果一个算法是多项式时间算法，该算法是有效的,是好算法。
选项：
A:对
B:错
答案: 【对】

4、单选题：
算法复杂度分析的两种基本方法为（  ）和（    ）。
选项：
A:事后统计  事前分析
B:平摊复杂度 平滑复杂度
C:几何复杂度  平均复杂度
D:结构化方法 面向对象方法
答案: 【事后统计  事前分析】

5、单选题：

下面程序的时间复杂度为（）

x=1

for i=1 to n  do

for j=1 to i do

for k=1 to j do

x++

选项：
A:O(nlogn)
B:O(n)
C:O(n^3)
D:O(n^2)
答案: 【O(n^3)】

6、单选题：
对近似递增序列的线性表从小到大排序，使用哪种方法好？
选项：
A:插入排序
B:归并排序
C:快速排序
D:堆排序
答案: 【插入排序】

7、多选题：
顺序查找适合的数据结构是（）
选项：
A:散列存储
B:链式存储
C:顺序存储
D:压缩存储
答案: 【链式存储;顺序存储】

8、单选题：
给定n个元素的数组A，n=10^{^3}, 使用折半查找比使用顺序查找大约快___倍。
选项：
A:10

B:1000

C:10^(3/2)

D:100

答案: 【100
】

9、单选题：
则f(n)的渐进性态f(n)=Ω(    )

选项：
A:n^2

B:1

C:n

D:100

答案: 【1
】

10、判断题：
f=O(g) 当且仅当 g =Ω (f)
选项：
A:错
B:对
答案: 【对】

第三章 单元测试

1、判断题：
0-1背包问题的枚举算法的时间复杂度为O（2ⁿ）
选项：
A:对
B:错
答案:

2、判断题：
增量构造法生成子集前需要对集合中元素从小到大排列。
选项：
A:对
B:错
答案:

3、判断题：
分块查找一般设分块的长度是n/2.
选项：
A:对
B:错
答案:

4、判断题：
枚举法适用于问题的小规模实例。
选项：
A:错
B:对
答案:

5、单选题：
便于实现集合操作的子集生成算法是（）
选项：
A:增量构造法
B:位向量法
C:二进制法
答案:

6、单选题：
从所有候选答案中去搜索正确的解，这是 （）算法。
选项：
A:递推
B:枚举
C:蛮力
答案:

7、单选题：
logn²=(  )(logn+5)
选项：
A:o
B:w
C:θ
D:O

答案:

8、单选题：
0-1背包问题的枚举算法，如果在百万次每秒的计算机上运行，1年可以计算的问题规模估计是？
选项：
A:50
B:40
C:30
D:60
答案:

9、多选题：
分数拆分问题的枚举算法通过（）方法进行了优化。
选项：
A:优化数学模型
B:减少枚举变量的值域
C:优化数据结构
D:减少枚举变量
答案:

10、多选题：
下面那些算法的时间复杂度为O（）?
选项：
A:折半插入排序
B:顺序查找
C:折半查找
D:冒泡排序
E:插入排序
答案:

11、单选题：
A公司处理器速度是B公司的100倍。对于复杂度为n^2的算法，B公司的计算机可以在1小时内处理规模为n的问题，A公司的计算机在1小时能处理的问题规模是（）
选项：
A:10n

B:n^2

C:100n

D:n

答案:

12、判断题：
冒泡排序的时间复杂度为Ω(n^2)
选项：
A:错
B:对
答案:

第四章 单元测试

1、判断题：
贪心算法总能找到可行解，但未必是最优解。
选项：
A:对
B:错
答案:

2、判断题：
贪心选择通过一步步选择得到问题的解，每一步的局部最优解都构成全局最优解的一部分。

选项：
A:对
B:错
答案:

3、判断题：
问题的最优子结构性质是该问题可用贪心算法或动态规划算法求解的关键特征。
选项：
A:错
B:对
答案:

4、判断题：
Kruskal算法的贪婪准则是每一次选取不构成环路的最小边。
选项：
A:错
B:对
答案:

5、单选题：
贪心算法基本要素有（   ）和最优子结构性质。
选项：
A:重叠子问题性质
B:独立子问题性质
C:贪心选择性质
D:分解合并性质
答案:

6、单选题：
下面不是证明贪心算法证明方法的有（）。
选项：
A:交换论证
B:领先
C:界
D:优化
答案:

7、多选题：
最小生成树问题可以使用的算法有（ ）
选项：
A:Solim
B:Dijkstra
C:Prim
D:Kruskal
答案:

8、多选题：
区间问题包含()
选项：
A:区间划分
B:区间选点
C:区间覆盖
D:区间调度
答案:

9、判断题：
负权的单源最短路问题可以使用Dijkstra算法求解

选项：
A:错
B:对
答案:

10、判断题：
设C是一个环， f 是C中的最大边，那么最小生成树中肯定包含f。

选项：
A:对
B:错
答案:

第五章 单元测试

1、判断题：
正推是从小规模的问题推解出大规模间题的一种方法。
选项：
A:对
B:错
答案:

2、判断题：
一般来说，递归的效率高于递推。
选项：
A:对
B:错
答案:

3、单选题：
从大规模问题逐步化为小规模问题的算法是（）
选项：
A:迭代
B:递归
C:正推
D:倒推
答案:

4、单选题：
求解高阶递推方程一般使用（）迭代方法
选项：
A:直接迭代
B:差消迭代
C:换元迭代
答案:

5、多选题：
递归函数的要素是（）
选项：
A:迭代
B:递归方程
C:输入
D:边界条件
答案:

6、多选题：
递归变为非递归的方法有（）
选项：
A:循环
B:递推
C:模拟栈
D:尾递归
答案:

7、多选题：
T(n) = T(n-1) + n ，T(1)=1，则 T(n) =（）
选项：
A:O(n^2)

B:Ω(n^2)
C:θ(n^2)
D:n(n+1)/2
答案:

8、多选题：
递归一般用于解决问题有（）
选项：
A:数据的定义是按递归定义的
B:问题解法按递归实现
C:数据的结构形式是按递归定义的
D:迭代问题
答案:

9、单选题：

主方法可以求解满足T(n)=aT(n/b) + f (n) 形式的递推方程， 则下列关于方程中的约束中不准确的是？设
选项：
A:对于系数b，必须满足b>1
B:若对于常数e>0，f(n)=O(y)，则T(n)=Θ(x)
C:对于系数a，必须满足a>=1
D:若f(n)=O(x)，则T(n)=Θ(xlogn)
答案:

10、单选题：
，则 T(n) =（）

选项：
A:Θ(n^2)
B:O(n)
C:Ω(n^3)
D:O(nlogn)
答案:

11、判断题：
循环用于重复性的工作。循环体的特点是：“以不变应万变”。
选项：
A:错
B:对
答案:

第六章 单元测试

1、判断题：
分治法分解的子问题与原问题形式相同。
选项：
A:对
B:错
答案:

2、判断题：
N个元素排序的时间复杂度不可能是线性时间。
选项：
A:错
B:对
答案:

3、判断题：
三分法的判定树是三叉树。
选项：
A:对
B:错
答案:

4、判断题：
减治法减一个常量就是每次迭代减去一个相同的常数因子(一般为2)
选项：
A:错
B:对
答案:

5、单选题：
设有5000个无序的元素，希望用最快的速度挑选出其中前10个最大的元素，最好选用(   )法。
选项：
A:合并排序
B:快速排序
C:基数排序
D:冒泡排序
答案:

6、单选题：
堆排序的时间复杂度是O（）。
选项：
A:O（nlogn）
B:O（2ⁿ）
C:O（n）
D:O（n²）
答案:

7、单选题：
改进分治算法的方法有（ ）和改进划分的对称性。
选项：
A:加速原理
B:减少子问题数
C:备忘录
D:拟阵原理
答案:

8、多选题：
通过减少子问题个数，降低分治算法时间复杂度的有（）
选项：
A:Strassen矩阵乘法
B:最接近点对
C:线性时间选择
D:大整数乘法
答案:

9、多选题：
分治法在每一层递归上有三个步骤（）
选项：
A:解决

B:分解
C:选择
D:合并
答案:

10、单选题：

使用分治法求解不需要满足的条件是（ ）。
选项：
A:原问题和子问题使用相同的方法求解
B:子问题必须是一样的
C:子问题的解可以合并
D:子问题不能够重复
答案:

11、判断题：
最小堆中每个元素调整的次数不超过树高。
选项：
A:对
B:错
答案:

12、判断题：
分治算法的思想是将难以直接解决的大问题，分割成一些规模较小的子问题，以便各个击破，分而治之。

选项：
A:对
B:错
答案:

13、判断题：
任何排序算法至少需要O(n log n)次比较。
选项：
A:错
B:对
答案:

14、单选题：
找n个元素的中位数的分治算法的时间复杂度为O().
选项：
A:n

B:n^2
C:nlogn

D:logn
答案:

第七章 单元测试

1、判断题：
动态规划算法把原问题分为交叉的子问题，解决子问题，记录子问题的解，合并为原问题的解。
选项：
A:错
B:对
答案:

2、判断题：
0/1背包问题的动态规划算法是多项式时间算法。
选项：
A:对
B:错
答案:

3、判断题：
对于稀疏图，Floyd算法的效率要高于执行n次Dijkstra算法，也要高于执行n次SPFA算法。
选项：
A:对
B:错
答案:

4、判断题：
Dijkstra算法在求解过程中，源点到集合S内各顶点的最短路径一旦求出，则之后不变了，修改的仅仅是源点到还没选择的顶点的最短路径长度。
选项：
A:对
B:错
答案:

5、单选题：
含负权的最短路问题一般使用（）求解。
选项：
A:贪心算法
B:网络流算法
C:动态规划
D:分治算法
答案:

6、单选题：
动态规划算法的基本要素有（ ）和最优子结构性质。
选项：
A:分解合并性质
B:独立子问题性质
C:贪心选择性质
D:重叠子问题性质
答案:

7、单选题：

下面不是动态规划的基本方法有（）。
选项：
A:舍入
B:增加变量
C:多重选择
D:区间变量
答案:

8、多选题：
最短路算法中适用于稀疏图的是（）
选项：
A:Dijkstra算法
B:SPFA算法
C:Floyd算法
D:Bellman算法
答案:

9、多选题：
分治算法与动态规划算法的相同点是（）
选项：
A:递推关系
B:最优子结构
C:子问题重叠
D:子问题独立

答案:

10、判断题：
DAG上最短路，固定起点和终点没有意义。
选项：
A:错
B:对
答案:

11、判断题：
DAG图最长路的递推函数d(i)表示从某个顶点i出发的最长路长度 。
选项：
A:对
B:错
答案:

12、判断题：
树上最大权独立集不包含u，可能包含儿子结点，也可能不包含儿子结点。
选项：
A:错
B:对
答案:

13、判断题：
SPFA算法的时间复杂度为O（mn）
选项：
A:对
B:错
答案:

第八章 单元测试

1、判断题：
回溯法是按广度优先策略搜索解空间树。
选项：
A:错
B:对
答案:

2、判断题：
死结点是正在产生儿子的结点。
选项：
A:错
B:对
答案:

3、判断题：
回溯法的一个显著特征是在搜索过程中动态产生问题的解空间。
选项：
A:错
B:对
答案:

4、判断题：
回溯法不适用于解一些组合数相当大的问题。
选项：
A:对
B:错
答案:

5、判断题：
好的约束函数能显著地减少所生成的结点数。但这样的约束函数往往计算量较大。因此，在选择约束函数时通常存在生成结点数与约束函数计算量之间的折衷。
选项：
A:错
B:对
答案:

6、单选题：
下列算法中，通常以深度优先方式系统搜索问题解的是（     ）。
选项：
A:贪心法
B:备忘录法
C:动态规划法
D:回溯法
答案:

7、单选题：
装载问题的回溯算法所需的计算时间为
选项：
A:O（2ⁿ）
B:O（n²）
C:O（n）
D:O（nlogn）
答案:

8、多选题：
问题的状态生成法有（）
选项：
A:子集树生成法
B:排列树生成法
C:深度优先生成法
D:宽度优先生成法
答案:

9、多选题：
回溯法解题步骤
选项：
A:确定易于搜索的解空间结构
B:确定最优子结构的性质
C:针对所给问题，定义问题的解空间
D:以深度优先方式搜索解空间，在搜索过程中用剪枝函数避免无效搜索。
答案:

10、多选题：
回溯法的效率依赖于下列哪些因素（       ）
选项：
A:计算约束函数的时间
B:计算限界函数的时间
C:满足显约束的值的个数
D:确定解空间的时间
答案:

11、单选题：
剪枝函数包括（ ）和约束函数

选项：
A:启发式函数

B: 限界函数

C:最优函数
D:估计函数
答案:

12、判断题：

回溯法搜索解空间时，在搜索试探时选取x[i]的值顺序是任意的，顺序对于计算量没有差别。
选项：
A:错
B:对
答案:

13、判断题：
回溯法中，如果解空间树是排列树，所给问题的规模为n时，遍历排列树需 O( n! ) 计算时间.
选项：
A:错
B:对
答案:

14、多选题：
回溯法的两种解空间树为（）
选项：
A:排列树

B:递归树
C:子集树
D:祖先树
答案:

第九章 单元测试

1、判断题：
分支限界法在对问题的解空间树进行搜索的方法中，一个活结点有多次机会成为活结点。
选项：
A:错
B:对
答案:

2、判断题：
分支限界法找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。
选项：
A:错
B:对
答案:

3、判断题：
队列式分支限界法以最小耗费优先的方式搜索解空间树。
选项：
A:错
B:对
答案:

4、判断题：

优先队列式分支限界法按照队列先进先出的原则，选取下一个节点为扩展结点。
选项：
A:错
B:对
答案:

5、单选题：
分支限界法解旅行商问题时的解空间树是
选项：
A:深度优先生成树
B:排列树
C:广度优先生成树
D:子集树
答案:

6、单选题：
优先队列式分支限界法选取扩展结点的原则是
选项：
A:先进先出
B:后进先出
C:随机
D:结点的优先级
答案:

7、多选题：
用分支限界法设计算法的步骤是：
选项：
A:确定易于搜索的解空间结构（按树或图组织解）
B:以广度优先或以最小耗费（最大收益）优先的方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索
C:定义最优子结构
D:针对所给问题，定义问题的解空间（对解进行编码）
答案:

8、多选题：
分支限界法与回溯法的不同点是什么？
选项：
A:存储空间的要求不同
B:对扩展结点的扩展方式不同
C:求解目标不同
D:搜索方式不同
答案:

9、单选题：

FIFO是（  ）的搜索方式。
选项：
A:动态规划
B:分支限界

C:贪心算法

D:回溯算法
答案:

10、单选题：

下面说法不正确的是（）
选项：
A:用限界函数剪去得不到最优解的子树
B: 用约束函数在扩展结点处剪去不满足约束的子树
C:使用限界函数作优先级, 第一个加入队列的叶子就是最优解
D:回溯和分支限界都是动态生成解空间树
答案:

11、单选题：

在对问题的解空间树进行搜索的方法中，一个活结点最多有一次机会成为活结点的是（    ）。

选项：
A:分支限界

B:回溯求解子集树问题

C:回溯和分支限界

D:回溯

答案:

12、判断题：
使用限界函数作优先级, 第一个扩展的叶子就是最优解
选项：
A:错
B:对
答案:

13、判断题：
分支限界法不能解决0/1背包问题
选项：
A:错
B:对
答案:

第十章 单元测试

1、判断题：
网络流满足容量约束，但一般不满足流量守恒约束。
选项：
A:错
B:对
答案:

2、判断题：
设G = <V1, V2, E>为二分图, |V1|≤|V2|, M为G中一个最大匹配, 且|M| = |V1|, 则称M为G的完备匹配，也是最大匹配。
选项：
A:对
B:错
答案:

3、判断题：
存在割 (A, B) 使流值 v(f) = 割的容量cap(A, B)，则割 (A, B)是最小割。
选项：
A:错
B:对
答案:

4、判断题：

给定连通图G, BFS遍历得到层次图，如果同一层中的结点无边相连，则G是二分图。
选项：
A:错
B:对
答案:

5、判断题：
有下界的流通问题不一定有可行流。
选项：
A:对
B:错
答案:

6、单选题：
Dinic算法的时间复杂度为（）
选项：
A:mn²
B:m²logC
C:mn
D:m²n
答案:

7、单选题：
如果每条边的最大容量为1，则时间复杂度是O(nm)的网络流算法有
选项：
A:EK算法
B:容量缩放算法
C:Dinic算法
D:FF算法
答案:

8、多选题：
改进FF网络流算法，可以通过选择（  ）增广路，降低时间复杂度。
选项：
A:边数最少
B:最短路径
C:最大容量
D:最大瓶颈容量
答案:

9、判断题：
带需求的流通必须满足供给和 = 需求和
选项：
A:错
B:对
答案:

10、判断题：

匈牙利算法中起点和终点都是未匹配点的交错路径称为可增广路径，可增广路径有奇数条边。
选项：
A:错
B:对
答案:

11、判断题：
给定二分图G = <V, E>中无孤立点，其最大流算法求得最大流f, 则 G的最大匹配数=f.
选项：
A:对
B:错
答案:

12、判断题：
设G = <V, E>中无孤立点。W为G的最小边覆盖, 若G中存在相邻边就移去其中一条。设移去的边集为N，则W-N是G的最大匹配。
选项：
A:错
B:对
答案:

13、判断题：
设 f是网络N的任意流，(A, B) 是N的任意 s-t 割，则流值f至多等于割的容量。
选项：
A:错
B:对
答案:

第十一章 单元测试

1、判断题：
蒙特卡罗算法的结果肯定是一个正确解。
选项：
A:错
B:对
答案:

2、判断题：
Sherwood算法随机选择一个数组元素作为划分标准求解k小元素问题,保证线性时间的平均性能。
选项：
A:错
B:对
答案:

3、判断题：
借助随机预处理技术，不改变原有的确定性算法，仅对其输入进行随机洗牌，可收到舍伍德算法的效果。
选项：
A:对
B:错
答案:

4、判断题：

随机算法共同点是计算时间越多或运行次数越多,正确性越高.
选项：
A:对
B:错
答案:

5、判断题：
增加拉斯维加斯算法的反复求解次数, 可使求解无效的概率任意小。
选项：
A:错
B:对
答案:

6、单选题：
在下列算法中有时找不到问题解的是
选项：
A:蒙特卡罗算法
B:拉斯维加斯算法
C:舍伍德算法
D:数值随机算法
答案:

7、单选题：
肯定获得可行解，但不一定是正确解的算法是
选项：
A:舍伍德算法
B:数值随机算法
C:拉斯维加斯算法
D:蒙特卡罗算法
答案:

8、单选题：
在一般输入数据的程序里，输入多少会影响到算法的计算复杂度，为了消除这种影响可用（  ）对输入进行预处理。
选项：
A:蒙特卡罗算法
B:舍伍德算法
C:数值随机化算法
D:拉斯维加斯算法
答案:

9、多选题：
下面说法正确的是
选项：
A:蒙特卡罗算法总是能提供问题的一个解,但可能给出错误解。
B:舍伍德算法的精髓不是避免最坏的情况，而是设法消除最坏情况和特定实例的关联性。
C:求解同一实例用同一随机化算法求解两次，所用时间和所得结果可能完全不同。
D:现实计算机上无法产生真正的随机数
答案:

10、多选题：
下面说法正确的是（）
选项：
A:增加蒙特卡罗算法的求解次数, 可使求解错误的概率任意小。
B:线性同余法是产生伪随机数的最常用的方法
C:随机算法是一种使用概率和统计方法在其执行过程中对于下一计算步骤作出随机选择的算法
D:当最坏和平均情况差别较大时, 舍伍德算法可以消除好坏实例的差别，达到平均实例的性能
答案:

11、判断题：

确定性算法的每一计算步骤都确定,求解同一实例用同一算法求解两次，所得结果完全相同。
选项：
A:对
B:错
答案:

12、判断题：
舍伍德算法总是有解, 且解总是正确的，但最坏性能未改变。
选项：
A:对
B:错
答案:

13、判断题：
拉斯维加斯算法肯定得到一个正确解。
选项：
A:对
B:错
答案:

14、判断题：
随机抽取数组元素k次,从最接近搜索元素x 的位置顺序搜索,  顺序搜索的平均比较次数为O(n/(k+1)).
选项：
A:错
B:对
答案:

第十二章 单元测试

1、判断题：
有多项式时间算法的问题是易解问题
选项：
A:错
B:对
答案:

2、判断题：
EXP类是所有指数时间可解的判定问题组成的问题类
选项：
A:错
B:对
答案:

3、判断题：
如果对于X的任意实例，通过多项式次的计算步骤，加多项式次调用Y的算法，可解决X，则X可多项式时间归约到Y。
选项：
A:错
B:对
答案:

4、单选题：
下面关于NP问题说法正确的是（ ）
选项：
A:NP问题都是不可能解决的问题
B:P类问题包含在NP类问题中
C:NP类问题包含在P类问题中
D:NP完全问题是P类问题的子集
答案:

5、多选题：
下面属于NP完全问题的是（）
选项：
A:SAT
B:旅行商问题
C:最大独立集
D:最小顶点覆盖
答案:

6、多选题：
以下关于判定问题难易处理的叙述中错误的是
选项：
A:需要超过多项式时间算法求解的问题是易处理的
B:可以由多项式时间算法求解的问题是难处理的
C:需要超过多项式时间算法求解的问题是不能处理的
D:可以由多项式时间算法求解的问题是易处理的
答案:

7、单选题：

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

答案:

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:对
答案:

第十三章 单元测试

1、判断题：
给定问题p，若有算法A，存在一个常数K>=0，使得问题p的所有实例I，总有：|A(I)-OPT(I)|<=K,则称算法A为解答问题p的绝对近似算法。
选项：
A:对
B:错
答案:

2、判断题：

NP-hard 问题属于NP
选项：
A:错
B:对
答案:

3、判断题：

当P不等于NP时，NP-hard优化问题存在多项式时间绝对近似算法。
选项：
A:错
B:对
答案:

4、判断题：

绝大多数NP-hard问题存在多项式时间绝对近似算法
选项：
A:对
B:错
答案:

5、判断题：

若P不等于NP，则最大独立集问题存在多项式时间绝对近似算法。
选项：
A:对
B:错
答案:

6、判断题：

最大优化问题的近似性能比小于1，越接近1越说明算法好
选项：
A:对
B:错
答案:

7、判断题：
多项式时间近似方案的近似性能比是1 + q，q>0.
选项：
A:对
B:错
答案:

8、判断题：

多项式时间近似方案的时间复杂度是P(n, 1/ q) ， P是多项式函数, q>0。
选项：
A:错
B:对
答案:

9、多选题：

近似算法的设计方法有（）
选项：
A:组合技术
B:贪心
C:线性规划和舍入
D:定价法
答案:

10、单选题：

下面说法错误的是（）
选项：
A:NP-hard与NPC区别在于是否属于NP
B:近似性能比不可能小于1
C:完全多项式时间近似方案的近似性能比是1+p，p>0
D:旅行商问题的近似性能比不会小于2
答案: