第一章 单元测试

1、单选题：
下列对算法的理解不正确的是（ ）。
选项：
A:算法一般是机械的，有时要进行大量重复的计算，它的优点是一种通法
B:算法要求是一步步执行，每一步都能得到唯一的结果
C:算法有一个共同特点就是对一类问题都有效(而不是个别问题)
D:任何问题都可以用算法来解决
答案: 【任何问题都可以用算法来解决】

2、单选题：
算法渐近时间复杂度的分析主要关注哪一方面？（ ）
选项：
A:实际运行时间的精确测量
B:最高次项的系数
C:低阶项和常系数的精确计算
D:最高次项并忽略常系数
答案: 【最高次项并忽略常系数】

3、单选题：
渐近时间复杂度分析中，通常认为哪种情况对算法选择更重要？（ ）
选项：
A:最坏情况
B:最好情况
C:最佳和最坏情况的平均
D:平均情况
答案: 【最坏情况】

4、判断题：
使用渐近符号的函数通常刻画算法的运行时间，但是渐近符号也可以适用于刻画算法的某个其他方面的函数，甚至可以适用于和算法没有任何关系的函数。（ ）
选项：
A:对
B:错
答案: 【对】

5、单选题：
在算法分析中，常用大O记号限制算法的（ ）。
选项：
A:最坏情况运行时间
B:最好情况运行时间
C:平均情况运行时间
答案: 【最坏情况运行时间】

第二章 单元测试

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

2、单选题：
下面关于NPC问题说法不正确的是（ ）
选项：
A:非确定性多项式时间不可解决
B:如果一个NPC问题在多项式时间可解，则所有NP问题在多项式时间可解
C:所有的NP类问题可归约成该问题
D:所有的NPC问题之间可相互归约
答案: 【非确定性多项式时间不可解决】

3、多选题：
假设存在两个问题X、Y，问题X可以在多项式时间内归约为问题Y，下面说法正确的是（ ）
选项：
A:如果问题X是NP-hard，那么问题Y是NPC
B:如果问题X是NP-hard，那么问题Y也是NP难的
C:如果Y是易处理的（多项式时间可解），那么问题X也是易处理的
D:如果问题X是NPC，那么问题Y是NP-hard的
答案: 【如果问题X是NP-hard，那么问题Y也是NP难的;
如果Y是易处理的（多项式时间可解），那么问题X也是易处理的】

4、单选题：
假设集合I是图G的独立集，集合C是图G的顶点覆盖集，下面说法不正确的是（ ）
选项：
A:对于图G中任意一条边(u,v)，有u∈I或v∈I
B:对于图G中任意一条边(u,v)，有u∈C或v∈C
C:假设V为图G的顶点集合，则有I=V-C
D:对于图G中任意一条边(u,v)，有u∈C且v∈C
答案: 【对于图G中任意一条边(u,v)，有u∈I或v∈I】

5、多选题：
下列关于CNF-SAT问题的说法中，正确的是（ ）
选项：
A:对于任意的CNF都存在使得表达式为真的赋值
B:对于一个CNF-SAT 问题，可以在多项式时间内验证一个解的正确性
C:CNF-SAT是一个P问题
D:3-CNF 可满足性问题可以在多项式时间内被归约到图的独立集问题
答案: 【对于一个CNF-SAT 问题，可以在多项式时间内验证一个解的正确性;
3-CNF 可满足性问题可以在多项式时间内被归约到图的独立集问题】