2021知到答案 算法分析与设计 智慧树网课章节测试答案

第一章 章节测试

1、选择题:算法是指解决选择题的方法或过程，它包含一系列步骤，用来将输入数据转换成输出结果。
选项：
A:对
B:错
答案: 【对】
2、选择题:使用伪代码描述算法具有（ ）等优点。
选项：
A:易于转化为程序语言代码
B:容易修改
C:简单易懂
D:格式统一规范
答案: 【易于转化为程序语言代码;
容易修改;
简单易懂】
3、选择题:算法通常具有（ ）的性质。
选项：
A:输出：至少有一个输出
B:有限性：算法中每条指令的执行次数有限，执行每条指令的时间也有限
C:确定性：组成算法的每条指令清晰、无歧义
D:输入：有零个或多个输入
答案: 【输出：至少有一个输出;
有限性：算法中每条指令的执行次数有限，执行每条指令的时间也有限;
确定性：组成算法的每条指令清晰、无歧义;
输入：有零个或多个输入】
4、选择题:程序是算法用某种程序设计语言的具体实现，程序需满足算法的所有性质。
选项：
A:错
B:对
答案: 【错】
5、选择题:常用的描述算法的形式有（ ）。
选项：
A:自然语言
B:程序流程图
C:伪代码
D:机器语言
答案: 【自然语言;
程序流程图;
伪代码】
6、选择题:函数f(n)=20log3^n的渐进表达式是（ ）。
选项：
A:O(n)
B:0（n^2）
C:0(log(n))
D:0(1)
答案: 【O(n)】
7、选择题:一个算法的优劣由（ ）决定。
选项：
A:代码长度
B:使用的编程语言
C:时间复杂度
D:空间复杂度
答案: 【时间复杂度;
空间复杂度】
8、选择题:如果存在正的常数C和自然数N0,使得当N≥N0时有f(N)≤Cg(N),则称函数f(N)当N充分大时上有界，且g(N)是它的一个上界，记为f(N)=O(g(N)),即f(N)的阶不高于g(N）的阶。
选项：
A:错
B:对
答案: 【对】
9、选择题:分析以下代码的时间复杂度：
int func(int n)
{
int i=1, k=0;
while(i<=n) {
k++;
i=i*2;
}
return k;
}
选项：
A:O(n)
B:O(n^2)
C:O(n/2)
D:O(logn)
答案: 【O(logn)】
10、选择题:对于f(n)=n，下列说法正确的是（ ）。
选项：
A:f(n)=O(n)
B:f(n)=O(1/n)
C:f(n)=O(n^2)
D:f(n)=O(n^3)
答案: 【f(n)=O(n);
f(n)=O(n^2);
f(n)=O(n^3)】

第二章 章节测试

1、选择题:递归函数是指在一个函数体中出现直接或间接调用该函数自身的函数。
选项：
A:错
B:对
答案: 【对】
2、选择题:已知f(1)=1，f(n)=f(n-1)+n，那么f(50)的作用是( )。
选项：
A:计算1到50的乘积。
B:计算1到50的和。
C:计算50个1的和。
D:计算斐波拉契数列的第50个元素的值。
答案: 【计算1到50的和。】
3、选择题:递归的优点包括( )。
选项：
A:结构清晰
B:容易用数学归纳法来证明算法的正确性
C:可读性强
D:运行效率高
答案: 【结构清晰;
容易用数学归纳法来证明算法的正确性;
可读性强】
4、选择题:在经典的汉诺塔选择题中，如果有5个圆盘需要从A柱移至C柱，最少需要移动( )步。
选项：
A:31
B:41
C:32
D:28
答案: 【31】
5、选择题:分治法能解决的选择题一般具有（ ）等特征。
选项：
A:该选择题缩小到一定程度时可以容易地解决
B:分解出的子选择题的解可以合并为原选择题的解
C:子选择题相互独立
D:最优子结构
答案: 【该选择题缩小到一定程度时可以容易地解决;
分解出的子选择题的解可以合并为原选择题的解;
子选择题相互独立;
最优子结构】
6、选择题:在使用分治法设计算法时，最好使子选择题的规模大致相同，即将一个选择题分成大小相等的多个子选择题的处理方法是行之有效的。
选项：
A:对
B:错
答案: 【对】
7、选择题:给定递归公式T(n)=4T(n/2)+O(n),由主定理可以得知T(n)=( )。
选项：
A:O(logn)
B:O(nlogn)
C:O(n^2)
D:O(n)
答案: 【O(n^2)】
8、选择题:已知某楼房共20层，如果采用二分查找，请问最多猜( )次就能猜出任意一个楼层。
选项：
A:5
B:3
C:6
D:4
答案: 【5】
9、选择题:关于快速排序的时间复杂度，( )是正确的。
选项：
A:在平均情况下时间复杂度为O(nlogn)
B:在最坏情况下时间复杂度为O(n^2)
C:在平均情况下时间复杂度为O(n^2)
D:在最好情况下时间复杂度为O(nlogn)
答案: 【在平均情况下时间复杂度为O(nlogn);
在最坏情况下时间复杂度为O(n^2);
在最好情况下时间复杂度为O(nlogn)】
10、选择题:快速排序是对传统排序算法( )的一种改进。
选项：
A:归并排序
B:冒泡排序
C:插入排序
D:选择排序
答案: 【冒泡排序】

第三章 章节测试

1、选择题:能够使用动态规划算法来求解的选择题通常需要具备两个重要的性质，它们分别是( )。
选项：
A:贪心选择性质
B:最优子结构
C:重叠子选择题
D:递归调用
答案: 【最优子结构;
重叠子选择题】[$]
2、选择题:关于备忘录法，以下说法正确的是( )。
选项：
A:备忘录法又称为记忆化搜索，它采用一种自底向上的方式求解选择题。
B:备忘录法可以避免相同子选择题的重复求解。
C:备忘录法的控制结构与直接使用递归方法的控制结构相同。
D:备忘录法为每个解过的子选择题建立备忘录以备需要时查看，又称查表法。
答案: 【备忘录法可以避免相同子选择题的重复求解。;
备忘录法的控制结构与直接使用递归方法的控制结构相同。;
备忘录法为每个解过的子选择题建立备忘录以备需要时查看，又称查表法。】
3、选择题:字符序列abcde与字符序列abdge的最长公共子序列长度为( )，最长公共子串长度为( )。
选项：
A:4,6
B:3,5
C:4,2
D:4,1
答案: 【4,2】
4、选择题:使用动态规划算法求两条长度分别为m和n的序列的最长公共子序列，其时间复杂度为( )。
选项：
A:O(n^2)
B:O(m^n)
C:O(nlogm)
D:O(n*m)
答案: 【O(n*m)】
5、选择题:输入数组（-1, 0, 1, -2, 3），它的最大子段和是( )。
选项：
A:1
B:4
C:3
D:2
答案: 【3】
6、选择题:序列（1，7，3，4，9，2，3）的最长递增子序列的长度为( )。
选项：
A:1
B:3
C:2
D:4
答案: 【4】
7、选择题:使用穷举法求解最长递增子序列的时间复杂度为( )。
选项：
A:O(n^2)
B:O(n^n)
C:O(n*2^n)
D:O(nlogn)
答案: 【O(n*2^n)】
8、选择题:使用动态规划算法求最大子段和的时间复杂度为( )。
选项：
A:O(n)
B:O(nlogn)
C:O(logn)
D:O(2^n)
答案: 【O(n)】
9、选择题:某工厂预计明年有A,B,C,D四个新建项目，每个项目的投资额分别为15,10,12,8（万元），投资收益分别为12,8,9,5（万元），投资总额为30万元，选择项目( )可以使总收益最大。（不允许部分投资某个项目）
选项：
A:A
B:D
C:C
D:B
答案: 【D;
C;
B】
10、选择题:在使用动态规划算法求解0-1背包选择题时，若m[i][j]=m[i+1][j-w[i]]+v[i]，说明第i个物品在剩余背包容量为j时可以装入，并且装入比不装入的背包总价值更大，装入后，背包剩余容量减少w[i]，价值增加v[i]。
选项：
A:错
B:对
答案: 【对】

第四章 章节测试

1、选择题:能够使用贪心算法求解的选择题需具备的基本要素包括( )。
选项：
A:贪心选择性质
B:最优子结构性质
C:平衡子选择题
D:递归调用
E:重复子选择题
答案: 【贪心选择性质;
最优子结构性质】
2、选择题:下列关于贪心算法与动态规划算法说法正确的是( )。
选项：
A:贪心算法与动态规划算法的主要区别是贪心算法要求选择题具有贪心选择性质
B:贪心算法与动态规划算法求解的选择题都具有重复子选择题性质
C:贪心算法与动态规划算法求解的选择题都具备最优子结构性质
D:贪心算法与动态规划算法的主要区别是动态规划算法要求选择题具有贪心选择性质
答案: 【贪心算法与动态规划算法的主要区别是贪心算法要求选择题具有贪心选择性质;
贪心算法与动态规划算法求解的选择题都具备最优子结构性质】
3、选择题:在解决活动安排选择题时应首先对活动进行排序，排序的依据是( )。
选项：
A:按照活动结束时间降序排列
B:按照活动开始时间降序排列
C:按照活动结束时间升序排列
D:按照活动开始时间升序排列
答案: 【按照活动结束时间升序排列】
4、选择题:使用贪心算法求解最优装载选择题，其时间复杂度为( )。
选项：
A:O(nlogn)
B:O(n3n)
C:O(n5n)
D:O(n2n)
答案: 【O(nlogn)】
5、选择题:( )能够使用贪心算法求解。
选项：
A:最小生成树选择题
B:单源最短路径选择题
C:活动安排选择题
D:0-1背包选择题
E:部分背包选择题
F:最优装载选择题
答案: 【最小生成树选择题;
单源最短路径选择题;
活动安排选择题;
部分背包选择题;
最优装载选择题】
6、选择题:0-1背包选择题与部分背包选择题的区别在于( )。
选项：
A:在0-1背包选择题中，物品只有装入和不装入两种情况，而部分背包选择题允许只装入物品的一部分
B:若用贪心算法解决0-1背包选择题，只能得到近似最优解
C:没有区别，它们的含义相同
D:若用贪心算法解决部分背包选择题，只能得到近似最优解
答案: 【在0-1背包选择题中，物品只有装入和不装入两种情况，而部分背包选择题允许只装入物品的一部分;
若用贪心算法解决0-1背包选择题，只能得到近似最优解】
7、选择题:在求解部分背包选择题时采用的贪心策略是( )。
选项：
A:选择重量最轻的物品
B:选择单位价值下重量最大的物品
C:选择价值最大的物品
D:选择单位重量下价值最大的物品
答案: 【选择单位重量下价值最大的物品】
8、选择题:Dijkstra算法可用于求解( )。
选项：
A:单终点最短路径选择题
B:每对顶点间最短路径选择题
C:单源最短路径选择题
D:单对顶点最短路径选择题
答案: 【单终点最短路径选择题;
每对顶点间最短路径选择题;
单源最短路径选择题;
单对顶点最短路径选择题】
9、选择题:Prim算法适合稀疏图，其时间复杂度只与边的数目有关。
选项：
A:对
B:错
答案: 【错】
10、选择题:在对Dijkstra算法进行初始化时，如果两个顶点之间没有边，则它们之间的距离为( )。
选项：
A:-1
B:0
C:无穷大
D:无穷小
答案: 【无穷大】

第五章 章节测试

1、选择题:回溯法中的剪枝函数包括( )。
选项：
A:递归函数
B:静态函数
C:虚函数
D:随机数生成函数
E:限界函数
F:约束函数
答案: 【限界函数;
约束函数】
2、选择题:回溯法采用的搜索策略是( )。
选项：
A:深度优先搜索
B:启发式搜索
C:层次搜索
D:广度优先搜索
答案: 【深度优先搜索】
3、选择题:回溯法的主要用途包括求选择题的所有解、求选择题的最优解和求选择题的任一解。
选项：
A:对
B:错
答案: 【对】
4、选择题:马的遍历选择题能否有可行解，与( )有关。
选项：
A:马的初始位置
B:马的遍历顺序
C:马的遍历深度
D:棋盘大小
答案: 【马的初始位置;
棋盘大小】
5、选择题:在N皇后选择题中，需要将棋盘当做一个二维数组来分析，对于该二维数组，以下说法正确的是( )。
选项：
A:对于任意一条左斜线上的两个点，它们的横坐标和纵坐标相减的值相同。
B:对于任意一条左斜线上的两个点，它们的横坐标和纵坐标相加的值相同。
C:对于任意一条右斜线上的两个点，它们的横坐标和纵坐标相加的值相同。
D:对于任意一条右斜线上的两个点，它们的横坐标和纵坐标相减的值相同。
答案: 【对于任意一条左斜线上的两个点，它们的横坐标和纵坐标相加的值相同。;
对于任意一条右斜线上的两个点，它们的横坐标和纵坐标相减的值相同。】
6、选择题:四皇后选择题一共有2个可行解，八皇后选择题一共有76个可行解。
选项：
A:对
B:错
答案: 【错】
7、选择题:用m种颜色给n个顶点着色、且使一条边的两个顶点颜色不同，则对应的解空间树是一棵( )。
选项：
A:高为n的m叉树
B:高为m的m叉树
C:高为n的n叉树
D:高为m的n叉树
答案: 【高为n的m叉树】
8、选择题:任何一张地图只用( )种颜色就能使具有共同边界的国家着上不同的颜色。
选项：
A:6
B:2
C:3
D:4
答案: 【4】
9、选择题:使用回溯法求解0-1背包选择题时，计算右子树上界的方法是通过贪心策略求得上界，即将剩余物品依其单位重量价值排序，然后依次装入物品，直至装不下时，再装入该物品的一部分而装满背包，此时得到的价值就是右子树中解的上界。
选项：
A:错
B:对
答案: 【对】
10、选择题:关于使用回溯法求解0-1背包选择题，以下说法正确的是( )。
选项：
A:使用限界函数剪去得不到更优解的左子树（装该物品）。
B:使用约束函数剪去不合理的右子树（不装该物品）。
C:使用限界函数剪去得不到更优解的右子树（不装该物品）。
D:使用约束函数剪去不合理的左子树（装该物品）。
答案: 【使用限界函数剪去得不到更优解的右子树（不装该物品）。;
使用约束函数剪去不合理的左子树（装该物品）。】

第六章 章节测试

1、选择题:分支限界法采用的搜索策略是( )。
选项：
A:广度优先搜索
B:递归搜索
C:深度优先搜索
D:启发式搜索
答案: 【广度优先搜索】
2、选择题:根据活结点表的组织方式不同，分支限界法包括( )等形式。
选项：
A:栈式分支限界法
B:队列式分支限界法
C:单调队列式分支限界法
D:二叉树式分支限界法
E:优先队列式分支限界法
答案: 【队列式分支限界法;
优先队列式分支限界法】
3、选择题:关于回溯法和分支限界法，以下说法正确的是( )。
选项：
A:在回溯法中，活结点的所有可行子结点均被遍历后才从栈中弹出
B:分支限界法通常用于求满足约束条件的一个解或特定意义下的最优解
C:在分支限界法中，每个结点只有一次成为扩展结点的机会
D:回溯法通常用于求满足约束条件的所有解
答案: 【在回溯法中，活结点的所有可行子结点均被遍历后才从栈中弹出;
分支限界法通常用于求满足约束条件的一个解或特定意义下的最优解;
在分支限界法中，每个结点只有一次成为扩展结点的机会;
回溯法通常用于求满足约束条件的所有解】
4、选择题:应用分支限界法的三个关键选择题包括( )。
选项：
A:如何设计合适的剪枝函数
B:如何组织活结点表
C:如何限制搜索的层次
D:如何确定最优解的解向量
答案: 【如何设计合适的剪枝函数;
如何组织活结点表;
如何确定最优解的解向量】
5、选择题:关于分支限界法的基本思想，下列描述正确的是( )。
选项：
A:从活结点表中取下一结点成为当前扩展结点，并重复结点扩展过程
B:那些导致不可行解或导致非最优解的子结点被舍弃，其余子结点被加入活结点表中
C:每一个活结点只有一次机会成为扩展结点
D:一直持续到找到所求的解或活结点表为空时为止
E:活结点一旦成为扩展结点，就一次性产生其所有子结点
答案: 【从活结点表中取下一结点成为当前扩展结点，并重复结点扩展过程;
那些导致不可行解或导致非最优解的子结点被舍弃，其余子结点被加入活结点表中;
每一个活结点只有一次机会成为扩展结点;
一直持续到找到所求的解或活结点表为空时为止;
活结点一旦成为扩展结点，就一次性产生其所有子结点】
6、选择题:优先队列式分支限界法将活结点表组织成一个优先队列，按优先队列中规定的结点优先级选取优先级最高的下一个结点成为当前扩展结点。
选项：
A:对
B:错
答案: 【对】
7、选择题:队列具有( )的性质。
选项：
A:先进后出
B:进出无序
C:先进先出
D:仅进不出
答案: 【先进先出】
8、选择题:使用队列式分支限界法求解装载选择题时，每次从队列Q中取出队首元素作为当前扩展结点。取队首元素后，判断当前Q是否为空。如Q非空，则将尾部标记-1加入Q，算法开始处理下一层的活结点。
选项：
A:错
B:对
答案: 【错】
9、选择题:如果一个给定装载选择题有解，则采用的装载策略为：首先将第一艘轮船尽可能装满；再将剩余的集装箱装上第二艘轮船。
选项：
A:对
B:错
答案: 【对】
10、选择题:在装载选择题中，如果右子树表示不将此集装箱装上船。设bestw是当前最优解；ew是当前扩展结点所相应的重量；r是剩余集装箱的重量，则当( )时，可将其右子树剪去。
选项：
A:ew+r>bestw
B:r<bestw< span=””></bestw<>
C:r>=bestw
D:ew+r<=bestw
答案: 【ew+r<=bestw】

第七章 章节测试

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:Floyd算法
 
B:SPFA算法
 
C: Bellman算法
 
D:Dijkstra算法
 
答案: 【SPFA算法
 
;
 Bellman算法
 
;
Dijkstra算法
 
】
9、选择题:动态规划算法的特点（）
选项：
A:自底向上计算
 
B:自顶向下计算
 
C:从大到小计算
 
D:从小到大计算
 
答案: 【自底向上计算
 
;
从小到大计算
 
】
10、选择题:备忘录算法的特点（）
选项：
A:自底向上计算
B:自顶向下计算
C:从大到小计算
D:从小到大计算
答案: 【自顶向下计算;
从大到小计算 】

第八章 章节测试

1、选择题:回溯法是按广度优先策略搜索解空间树。
选项：
A:对
B:错
答案: 【错】
2、选择题:死结点是正在产生儿子的结点。
选项：
A:对
B:错
答案: 【错】
3、选择题:回溯法的一个显著特征是在搜索过程中动态产生选择题的解空间。
选项：
A:对
B:错
答案: 【对】

第九章 章节测试

1、选择题:分支限界法在对选择题的解空间树进行搜索的方法中，一个活结点有多次机会成为活结点。
选项：
A:对
B:错
答案: 【错】
2、选择题:分支限界法找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。
选项：
A:对
B:错
答案: 【对】
3、选择题:队列式分支限界法以最小耗费优先的方式搜索解空间树。
选项：
A:对
B:错
答案: 【错】
4、选择题:

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

5、选择题:下列算法中不能解决0/1背包选择题的是
选项：
A:贪心法
 
B:动态规划
 
C:回溯法
 
D:分支限界法
 
答案: 【贪心法
 
】
6、选择题:分支限界法解旅行商选择题时的解空间树是
选项：
A:子集树
 
B:排列树
 
C:深度优先生成树
 
D:广度优先生成树
 
答案: 【排列树
 
】
7、选择题:优先队列式分支限界法选取扩展结点的原则是
选项：
A:先进先出
 
B:后进先出
 
C:结点的优先级
 
D:随机
 
答案: 【结点的优先级
 
】
8、选择题:用分支限界法设计算法的步骤是：
选项：
A:针对所给选择题，定义选择题的解空间（对解进行编码）
B:确定易于搜索的解空间结构（按树或图组织解）
 
C:定义最优子结构
 
D:以广度优先或以最小耗费（最大收益）优先的方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索
 
答案: 【针对所给选择题，定义选择题的解空间（对解进行编码）;
确定易于搜索的解空间结构（按树或图组织解）
 
;
以广度优先或以最小耗费（最大收益）优先的方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索
 
】
9、选择题:分支限界法与回溯法的不同点是什么？
选项：
A:求解目标不同
 
B:搜索方式不同
 
C:对扩展结点的扩展方式不同
 
D:存储空间的要求不同
 
答案: 【求解目标不同
 
;
搜索方式不同
 
;
对扩展结点的扩展方式不同
 
;
存储空间的要求不同
 
】
10、选择题:

FIFO是（  ）的搜索方式。
选项：
A:回溯算法
B:分支限界
C:动态规划
D:贪心算法
答案: 【分支限界
】

第十章 章节测试

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:mn
 
C:m²n
 
D:  m²logC
 
答案: 【 mn²
 
】
7、选择题:如果每条边的最大容量为1，则时间复杂度是O（nm）的网络流算法有
选项：
A:FF算法
 
B:容量缩放算法
 
C:EK算法
 
D: Dinic算法
 
答案: 【FF算法
 
】
8、选择题:给定二分图G = <V, E>中无孤立点，|V|=n，其最大流算法求得最大流f, 则 G的（）=n-f
选项：
A:最大独立数
 
B:最大匹配数
 
C:最小顶点覆盖
 
D:最小边覆盖
 
答案: 【最大独立数
 
;
最小边覆盖
 
】
9、选择题:改进FF网络流算法，可以通过选择（  ）增广路，降低时间复杂度。
选项：
A:最大容量
 
B:最短路径
 
C: 最大瓶颈容量
 
D:边数最少
 
答案: 【最大容量
 
;
最短路径
 
;
 最大瓶颈容量
 
;
边数最少
 
】
10、选择题:带需求的流通必须满足供给和 = 需求和
选项：
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:舍伍德算法的精髓不是避免最坏的情况，而是设法消除最坏情况和特定实例的关联性。
 
答案: 【现实计算机上无法产生真正的随机数
 
;
求解同一实例用同一随机化算法求解两次，所用时间和所得结果可能完全不同。
 
;
蒙特卡罗算法总是能提供选择题的一个解,但可能给出错误解。
 
;
舍伍德算法的精髓不是避免最坏的情况，而是设法消除最坏情况和特定实例的关联性。
 
】

第十二章 章节测试

1、选择题:有多项式时间算法的选择题是易解选择题
选项：
A:对
B:错
答案: 【对】
2、选择题:EXP类是所有指数时间可解的判定选择题组成的选择题类
选项：
A:对
B:错
答案: 【对】
3、选择题:如果对于X的任意实例，通过多项式次的计算步骤，加多项式次调用Y的算法，可解决X，则 X可多项式时间归约到Y。
选项：
A:对
B:错
答案: 【对】
4、选择题:如果X选择题 Y 且 Y不能多项式时间解决, 那么X也不能多项式时间解决。
选项：
A:对
B:错
答案: 【错】
5、选择题:下面关于NP选择题说法正确的是（ ）
选项：
A:NP选择题都是不可能解决的选择题
 
B:P类选择题包含在NP类选择题中
 
C:NP完全选择题是P类选择题的子集
 
D:NP类选择题包含在P类选择题中
 
答案: 【P类选择题包含在NP类选择题中
 
】
6、选择题:P类选择题可以（ ）。
选项：
A:多项式时间计算
 
B:指数时间计算
 
C:指数时间验证
 
答案: 【多项式时间计算
 
】
7、选择题:下面属于NP完全选择题的是（）
选项：
A:SAT
 
B:最大独立集
 
C:最小顶点覆盖
 
D:旅行商选择题
 
答案: 【SAT
 
;
最大独立集
 
;
最小顶点覆盖
 
;
旅行商选择题
 
】
8、选择题:以下关于判定选择题难易处理的叙述中错误的是
选项：
A:可以由多项式时间算法求解的选择题是难处理的
 
B:需要超过多项式时间算法求解的选择题是易处理的
 
C:可以由多项式时间算法求解的选择题是易处理的
 
D:需要超过多项式时间算法求解的选择题是不能处理的
 
答案: 【可以由多项式时间算法求解的选择题是难处理的
 
;
需要超过多项式时间算法求解的选择题是易处理的
 
;
需要超过多项式时间算法求解的选择题是不能处理的
 
】
9、选择题:

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

第十三章 章节测试

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:近似性能比不可能小于1
B:完全多项式时间近似方案的近似性能比是1+p，p>0
C:NP-hard 与NPC 区别是否属于NP

NP-hard 与NPC 区别是否属于NP
D:旅行商选择题的近似性能比不会小于2
答案: 【旅行商选择题的近似性能比不会小于2】[/$]