智慧树知到《算法分析与设计》章节测试答案
智慧树知到《算法分析与设计》章节测试答案
第一章单元测试
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.rC.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.mn2
B.mn
C.m2n
D.m2logC
正确答案：mn2
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
第一章单元测试
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.rC.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.mn2
B.mn
C.m2n
D.m2logC
正确答案：mn2
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