1.4第一单元 章节测验1、【单选题】解决问题的基本步骤是（）。（1）算法设计（2）算法实现（3）数学建模（4）算法分析（5）正确性证明
a、(3)(1)(4)(5)(2)
b、(3)(4)(1)(5)(2)
c、(3)(1)(5)(4)(2)
d、(1)(2)(3)(4)(5)
2、【单选题】下面说法关于算法与问题的说法错误的是（）。
a、如果一个算法能应用于问题的任意实例，并保证得到正确解答，称这个算法解答了该问题。
b、算法是一种计算方法，对问题的每个实例计算都能得到正确答案。
c、同一问题可能有几种不同的算法，解题思路和解题速度也会显著不同。
d、证明算法不正确，需要证明对任意实例算法都不能正确处理。
3、【单选题】算法与程序的区别是（）
a、输入
b、输出
c、确定性
d、有穷性
4、【单选题】问题变换的目的有（）。(1)复杂变简单 (2)未知变已知 (3)隐式变显式 (4)难解变易解 （5）以上都是。
a、(1)
b、(2)
c、(3)
d、(4)
e、(5)
5、【多选题】下面关于程序和算法的说法正确的是（）。
a、算法的每一步骤必须要有确切的含义，必须是清楚的、无二义的。
b、程序是算法用某种程序设计语言的具体实现。
c、程序总是在有穷步的运算后终止。
d、算法是一个过程，计算机每次求解是针对问题的一个实例求解。
6、【多选题】问题变换的方法有（ ）
a、实例简单化
b、问题约简
c、表达变换
d、分支
7、【多选题】最大独立集问题和（）问题等价。
a、最大团
b、最小顶点覆盖
c、区间调度问题
d、稳定匹配问题
8、【多选题】给定两张喜欢列表，稳定匹配问题的输出是（ ） 。
a、完美匹配
b、没有不稳定配对
c、最大匹配
d、稳定匹配
9、【填空题】传教士和野人问题转换的图是____。
10、【填空题】按照霍纳法则，计算p(x) = anxn an-1xn-1 … a1x1 a0 的数量级为____ 。
11、【判断题】同一数学模型使用不同的数据结构会有不同的算法，有效性有很大差别。
12、【判断题】证明算法不正确，只需给出一个反例，算法不能正确处理即可。
13、【判断题】算法是一个语句集合，按照顺序执行语句，处理实例，得到正确答案。
14、【判断题】同一算法只有一种形式描述。
15、【判断题】一个问题的同一实例可以有不同的表示形式。
16、【判断题】算法必须在有穷时间终止。
17、【判断题】问题的两个要素是输入和实例。
18、【判断题】给定一个实例，如果一个算法能得到正确解答，称这个算法解答了该问题
19、【判断题】计算机每次求解是针对问题的每个实例求解。
20、【判断题】一个问题的算法必须在有穷时间终止，并且对一切合法的输入都能得出满足要求的结果。
2.6第二单元 章节测验1、【单选题】从资源划分，算法的复杂度分为（ ）和（）。
a、时间复杂度 空间复杂度
b、空间复杂度 平均复杂度
c、最好复杂度 最坏复杂度
d、时间复杂度 平均复杂度
e、间间复杂度 平均复杂度
2、【单选题】算法复杂度分析的两种基本方法为（ ）和（ ）。
a、结构化方法 面向对象方法
b、事后统计 事前分析
c、几何复杂度 平均复杂度
d、平摊复杂度 平滑复杂度
3、【单选题】对近似递增序列的线性表从小到大排序，使用哪种方法好？
a、堆排序
b、快速排序
c、插入排序
d、归并排序
4、【单选题】f(n)=100 n为奇数 f(n)=5n2 3n n为偶数 则f(n)的下界为
a、n
b、n2
c、2n
d、1
5、【单选题】下面程序的时间复杂度为（） x=1 for i=1 to n do for j=1 to i do for k=1 to j do x
a、o(n)
b、o(n3)
c、o(n2)
d、o(nlogn)
6、【单选题】
a、不高于
b、不低于
c、等价于
d、逼近
7、【多选题】提高事后统计方法准确度的有（）
a、重复测试
b、加大n
c、典型实例测试
d、优化算法
8、【多选题】顺序查找适合的数据结构是（）
a、散列存储
b、顺序存储
c、链式存储
d、压缩存储
9、【填空题】
10、【填空题】
11、【判断题】时间复杂度是指算法最坏情况下的运行时间。
12、【判断题】
13、【判断题】
14、【判断题】
15、【判断题】如果一个算法是多项式时间算法，该算法是有效的,是好算法。
16、【判断题】
17、【判断题】
18、【判断题】
19、【判断题】
20、【判断题】
3.3第三单元 章节测验1、【单选题】便于实现集合操作的子集生成算法是（ ）
a、位向量法
b、二进制法
c、增量构造法
2、【单选题】从所有候选答案中去搜索正确的解，这是 （）算法。
a、蛮力
b、枚举
c、递推
3、【单选题】
a、θ
b、o
c、w
d、o
4、【单选题】0-1背包问题的枚举算法，如果在百万次每秒的计算机上运行，1年可以计算的问题规模估计是？
a、40
b、60
c、30
d、50
5、【多选题】分数拆分问题的枚举算法通过（）方法进行了优化。
a、减少枚举变量
b、减少枚举变量的值域
c、优化数据结构
d、优化数学模型
6、【多选题】下面那些算法的时间复杂度为o（n2）
a、顺序查找
b、折半查找
c、插入排序
d、冒泡排序
e、折半插入排序
7、【填空题】
8、【填空题】折半插入排序的时间复杂度是θ（____）。
9、【填空题】冒泡排序的时间复杂度是o（____）
10、【填空题】选择排序的时间复杂度是o（____）
11、【判断题】
12、【判断题】
13、【判断题】增量构造法生成子集前需要对集合中元素从小到大排列。
14、【判断题】
15、【判断题】二进制法生成子集，子集与运算可以生成并集
16、【判断题】枚举法适用于问题的小规模实例。
17、【判断题】减少枚举变量可以减少枚举算法的时间复杂度。
18、【判断题】增量构造法生成子集，不直接构造子集本身。
19、【判断题】位向量法生成子集，子集或运算可以生成差集
20、【判断题】分块查找一般设分块的长度是n/2.
4.6第四单元 章节测验1、【单选题】贪心算法基本要素有（ ）和最优子结构性质。
a、分解合并性质
b、独立子问题性质
c、贪心选择性质
d、叠子问题性质
2、【单选题】下面不是证明贪心算法证明方法的有（）。
a、领先
b、优化
c、交换论证
d、界
3、【单选题】未来与过去无关指的是（ ）的性质
a、贪心选择
b、无后效性
c、最优子结构
d、重叠子问题
4、【单选题】使目标函数最大（小）的解是问题的（）
a、最优解
b、可行解
5、【单选题】对于稠密图，使用（）算法计算mst更适合
a、kruskal
b、prim
6、【多选题】最小生成树问题可以使用的算法有（ ）
a、kruskal
b、prim
c、solim
d、dijkstra
7、【多选题】区间问题包含()
a、区间调度
b、区间划分
c、区间选点
d、区间覆盖
8、【填空题】把任意一个解逐渐变为贪心算法的解，不会影响其最优性。这种证明方法是____.
9、【填空题】贪心算法一般____后再进行最优化选择。
10、【填空题】逆删除算法利用了使用____的特性
11、【判断题】贪心选择通过一步步选择得到问题的解，每一步的局部最优解都构成全局最优解的一部分。
12、【判断题】问题的最优子结构性质是该问题可用贪心算法或动态规划算法求解的关键特征。
13、【判断题】mst中若在树中任意增加一条边，将出现一个回路；若去掉一条边，将变成非连通图。
14、【判断题】设c是一个环， f 是c中的最大边，那么最小生成树中肯定包含f.
15、【判断题】kruskal算法的贪婪准则是每一次选取不构成环路的最小边。
16、【判断题】哈夫曼编码的平均码长最小
17、【判断题】负权的单源最短路问题可以使用dijkstra算法求解。
18、【判断题】如果e是图g中权重最小的边，它至少是g的一颗最小生成树的边。
19、【判断题】如果图g中每条边的权重都是互不相同的，图g必定只有一颗最小生成树。
20、【判断题】贪心算法总能找到可行解，但未必是最优解
5.4第五单元 章节测验1、【单选题】从大规模问题逐步化为小规模问题的算法是（）
a、递归
b、正推
c、倒推
d、迭代
2、【单选题】下面有关递归与迭代的说法错误的是（）
a、递归与迭代都是解决“重复操作”的机制。
b、递归算法的实现往往要比迭代算法耗费更多的时间。
c、每个迭代算法原则上总可以转换成与它等价的递归算法。
d、每个递归算法原则上总可以转换成与它等价的迭代算法
3、【单选题】主方法可以求解满足t(n)=at(n/b) f (n) 形式的递推方程， 则下列关于方程中的约束中不准确的是？
a、对于系数a，必须满足a>=1
b、对于系数b，必须满足b>1
c、若对于常数ε>0，f(n)=o(nlogba-ε)，则t(n)=θ(nlogba)
d、若f(n)=o(nlogba)，则t(n)=θ(nlogbalogn)
4、【单选题】求解高阶递推方程一般使用（）迭代方法
a、差消迭代
b、换元迭代
c、直接迭代
5、【单选题】t(n) = 2t(n/2) n2 ，t(1)=1，则 t(n) =（）
a、ω(n3)
b、o(nlogn)
c、o(n)
d、o(n2)
6、【多选题】递归函数的要素是（）
a、边界条件
b、递归方程
c、输入
d、迭代
7、【多选题】递归变为非递归的方法有（）
a、模拟栈
b、递推
c、尾递归
d、循环
8、【多选题】递归一般用于解决问题有（）：
a、数据的定义是按递归定义的。
b、问题解法按递归实现。（回溯）
c、数据的结构形式是按递归定义的。
d、迭代问题
9、【多选题】求解递推方程的迭代法分为（ ）
a、直接迭代
b、差消迭代
c、换元迭代
d、主定理
10、【多选题】t(n) = t(n-1) n ，t(1)=1，则 t(n) =（）
a、θ(n2)
b、n(n 1)/2
c、o(n2)
d、ω(n2)
11、【填空题】由结果倒过来推解前提条件，需要使用（ ）算法。
12、【填空题】快速排序的时间复杂度是o（ ）
13、【判断题】正推是从小规模的问题推解出大规模间题的一种方法
14、【判断题】循环用于重复性的工作。循环体的特点是：“以不变应万变”。
15、【判断题】递归算法是直接或间接地调用自身的算法。
16、【判断题】尾递归中的递归调用是整个函数体中最后执行的语句且它的返回值不属于表达式的一部分。
17、【判断题】一般来说，递归的效率高于递推,
18、【判断题】递归表现为自己调用自己，递推则没有这样的形式。
19、【判断题】有些问题采用倒推法，容易理解和解决。
20、【判断题】递推是从问题的最终目标出发，逐渐将复杂问题化为简单问题，最终求得问题。
6.6第六单元 章节测验1、【单选题】设有5000个无序的元素，希望用最快的速度挑选出其中前10个最大的元素，最好选用( )法。
a、冒泡排序
b、快速排序
c、合并排序
d、基数排序
2、【单选题】堆排序的时间复杂度是o（）。
a、o（n）
b、2n
c、n2
d、nlogn
3、【单选题】快速排序的时间复杂度是o（）。
a、n
b、2n
c、n2
d、nlogn
4、【单选题】以下不可以使用分治法求解的是（ ）。
a、线性选择问题
b、归并排序
c、0/1背包问题
d、棋盘覆盖问题
5、【单选题】改进分治算法的方法有（ ）和改进划分的对称性。
a、减少子问题数
b、备忘录
c、拟阵原理
d、加速原理
6、【单选题】使用分治法求解不需要满足的条件是（ ）。
a、子问题不能够重复
b、子问题的解可以合并
c、原问题和子问题使用相同的方法求解
d、子问题必须是一样的
7、【多选题】通过减少子问题个数，降低分治算法时间复杂度的有（）
a、大整数乘法
b、strassen矩阵乘法
c、线性时间选择
d、最接近点对
8、【多选题】分治法在每一层递归上有三个步骤（）
a、分解
b、解决
c、合并
d、选择
9、【填空题】找n个元素的中位数的分治算法的时间复杂度为o(___).
10、【填空题】插入排序最好情况下的时间复杂度为o(___),最坏情况下的复杂度为o（___）
11、【判断题】n个元素排序的时间复杂度不可能是线性时间。
12、【判断题】三分法的判定树是三叉树
13、【判断题】减治法减一个常量就是每次迭代减去一个相同的常数因子(一般为2)
14、【判断题】减治法减可变规模就是每次迭代规模减少的模式不同。
15、【判断题】最小堆中每个元素调整的次数不超过树高 q(logn)。
16、【判断题】分治算法的思想是将难以直接解决的大问题，分割成一些规模较小的子问题，以便各个击破，分而治之。
17、【判断题】任何排序算法至少需要o(n log n)次比较。
18、【判断题】改进子问题合并的时间复杂度可以减少分治算法的时间。
19、【判断题】分治与递归都是从大规模问题逐步化为小规模问题，因此分治算法经常使用递归实现。
20、【判断题】分治法分解的子问题与原问题形式相同。
7.9第七单元 章节测验1、【单选题】含负权的最短路问题一般使用（）求解。
a、动态规划
b、贪心算法
c、分治算法
d、网络流算法
2、【单选题】动态规划算法的基本要素有（ ）和最优子结构性质。
a、分解合并性质
b、独立子问题性质
c、贪心选择性质
d、重叠子问题性质
3、【单选题】下面不是动态规划的基本方法有（）。
a、多重选择
b、增加变量
c、舍入
d、区间变量
4、【单选题】动态规划方法使用（ ）计算方式。
a、自顶向下
b、自高到低
c、自低到高
d、自底向上
5、【单选题】下面不是动态规划算法的基本要素的是（ ）。
a、无后效性
b、独立子问题性质
c、最优子结构性质
d、重叠子问题性质
6、【单选题】spfa算法的时间复杂度为o（）
a、mn
b、m nlgn
c、mlogn
d、n2
7、【多选题】最短路算法中适用于稀疏图的是（）
a、floyd算法
b、spfa算法
c、bellman算法
d、dijkstra算法
8、【多选题】动态规划算法的特点（）
a、自底向上计算
b、自顶向下计算
c、从大到小计算
d、从小到大计算
9、【多选题】分治算法与动态规划算法的相同点是（）
a、递推关系
b、子问题独立
c、子问题重叠
d、最优子结构
10、【多选题】备忘录算法的特点（）
a、自底向上计算
b、自顶向下计算
c、从大到小计算
d、从小到大计算
11、【填空题】备忘录方法是____算法的变形。
12、【填空题】动态规划方程m[i，j]= min(m[i-1,j] m[i-1,j-1] wij), 1≤i≤k≤j≤n, 则算法的则算法的时间复杂度为o（____）.
13、【判断题】0/1背包问题的动态规划算法是多项式时间算法。
14、【判断题】只有顶点i邻接的顶点j对i的影响独立时，才可用刷表法。
15、【判断题】对于稀疏图，floyd算法的效率要高于执行n次dijkstra算法，也要高于执行n次spfa算法
16、【判断题】dijkstra算法在求解过程中，源点到集合s内各顶点的最短路径一旦求出，则之后不变了，修改的仅仅是源点到还没选择的顶点的最短路径长度。
17、【判断题】dag上最短路，固定起点和终点没有意义。
18、【判断题】dag图最长路的递推函数d(i)表示从某个顶点i出发的最长路长度 。
19、【判断题】最大权独立集不包含u，可能包含儿子结点，也可能不包含儿子结点
20、【判断题】动态规划算法把原问题分为交叉的子问题，解决子问题，记录子问题的解，合并为原问题的解。
8.4第八单元 章节测验1、【单选题】下列算法中，通常以深度优先方式系统搜索问题解的是（ ）。
a、备忘录法
b、动态规划法
c、贪心法
d、回溯法
2、【单选题】下面哪种函数是回溯法中为避免无效搜索采取的策略（ ）
a、递归函数
b、剪枝函数
c、随机数函数
d、搜索函数
3、【单选题】装载问题的回溯算法所需的计算时间为（ ）
a、2n
b、nlogn
c、n2
d、n
4、【单选题】剪枝函数包括（ ）和约束函数。
a、启发式函数
b、限界函数
c、估计函数
d、最优函数
5、【多选题】回溯法的效率依赖于下列哪些因素（ ）
a、满足显约束的值的个数
b、计算约束函数的时间
c、计算限界函数的时间
d、确定解空间的时间
6、【多选题】下列哪个结点属于回溯法的结点类型？（ ）
a、扩展结点
b、活结点
c、根结点
d、死结点
7、【多选题】问题的状态生成法有（）
a、子集树生成法
b、深度优先生成法
c、宽度优先生成法
d、排列树生成法
8、【多选题】回溯法解题步骤：
a、针对所给问题，定义问题的解空间
b、确定易于搜索的解空间结构
c、确定最优子结构的性质
d、以深度优先方式搜索解空间，在搜索过程中用剪枝函数避免无效搜索
9、【填空题】回溯法搜索解空间树时，常用的两种剪枝函数为 、 。
10、【填空题】回溯法的两种解空间树为 、 。
11、【填空题】使用回溯法进行状态空间树裁剪分支时一般有两个标准：可行性约束函数和限界函数，装载问题和旅行商问题正好是两种不同的类型，其中同时使用可行性约束函数和限界函数的进行裁剪的是 ，只使用限界函数进行裁剪的是 。
12、【填空题】回溯法中，如果解空间树是排列树，所给的问题规模为n时，通常有__个叶结点，遍历子集树需 o( ) 计算时间 。
13、【判断题】死结点是正在产生儿子的结点
14、【判断题】回溯法中，如果解空间树是子集树，当所给的问题规模为n时，通常有2n个叶结点，遍历子集树需o(2n)计算时间 。
15、【判断题】回溯法不适用于解一些组合数相当大的问题。
16、【判断题】好的约束函数能显著地减少所生成的结点数。但这样的约束函数往往计算量较大。因此，在选择约束函数时通常存在生成结点数与约束函数计算量之间的折衷。
17、【判断题】回溯法搜索解空间时，在搜索试探时选取x[i]的值顺序是任意的，顺序对于计算量没有差别。
18、【判断题】回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但是，当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术，称为回溯法。
19、【判断题】回溯法的一个显著特征是在搜索过程中动态产生问题的解空间。
20、【判断题】回溯法是按广度优先策略搜索解空间树。
9.4第九单元 章节测验1、【单选题】下列算法中不能解决0/1背包问题的是（）
a、贪心法
b、动态规划
c、回溯法
d、分支限界法
2、【单选题】分支限界法解旅行商问题时的解空间树是（ ）。
a、子集树
b、排列树
c、深度优先生成树
d、广度优先生成树
3、【单选题】优先队列式分支限界法选取扩展结点的原则是（ ）
a、先进先出
b、后进先出
c、结点的优先级
d、随机
4、【单选题】在对问题的解空间树进行搜索的方法中，一个活结点最多有一次机会成为活结点的是（ ）。
a、回溯法
b、分支限界法
c、回溯法和分支限界法
d、回溯法求解子集树问题
5、【单选题】fifo是（ ）的搜索方式。
a、回溯
b、分支限界
c、动态规划
d、贪心
6、【多选题】用分支限界法设计算法的步骤是：
a、针对所给问题，定义问题的解空间（对解进行编码）；
b、确定易于搜索的解空间结构（按树或图组织解） ；
c、定义最优子结构
d、以广度优先或以最小耗费（最大收益）优先的方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。
7、【多选题】分支限界法与回溯法的不同点是什么？
a、求解目标不同
b、搜索方式不同
c、对扩展结点的扩展方式不同
d、存储空间的要求不同
8、【多选题】下面说法正确的是（）
a、使用限界函数作优先级, 第一个加入队列的叶子就是最优解
b、用约束函数在扩展结点处剪去不满足约束的子树；
c、用限界函数剪去得不到最优解的子树。
d、回溯和分支限界都是动态生成解空间树。
9、【填空题】队列式分支限界法使用 的搜索方式。
10、【填空题】常见的两种分支限界法为 分支限界法和 分支限界法。
11、【判断题】分支限界法在对问题的解空间树进行搜索的方法中，一个活结点有多次机会成为活结点。
12、【判断题】分支限界法找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。
13、【判断题】队列式分支限界法以最小耗费优先的方式搜索解空间树。
14、【判断题】优先队列式分支限界法按照优先队列中规定的优先级，选取优先级最高的结点，成为当前扩展结点。
15、【判断题】优先队列式分支限界法按照队列先进先出的原则，选取下一个节点为扩展结点。
16、【判断题】分支限界法与回溯法，都是在问题的解空间树上搜索问题解。
17、【判断题】使用限界函数作优先级, 第一个扩展的叶子就是最优解
18、【判断题】分支限界法与回溯法都是在问题的解空间树t上搜索问题的解，二者搜索方式不同，但求解目标相同。
19、【判断题】回溯法和分支限界法的主要区别在于，回溯法求取问题的一个解或所有解。
20、【判断题】分支限界法不能解决0/1背包问题
10.8第十单元 章节测验1、【单选题】dinic算法的时间复杂度为（）
a、mn2
b、mn
c、m2n
d、m2logc
2、【单选题】如果每条边的最大容量为1，则时间复杂度是o（nm）的网络流算法有（）
a、ff算法
b、容量缩放算法
c、ek算法
d、dinic算法
3、【多选题】
a、最大独立数
b、最大匹配数
c、最小顶点覆盖
d、最小边覆盖
4、【多选题】改进ff网络流算法，可以通过选择（ ）增广路，降低时间复杂度。
a、最大容量
b、最短路径
c、最大瓶颈容量
d、边数最少
5、【填空题】设g =
中无孤立点，|v|=n，边覆盖数 匹配数 = ___
6、【填空题】无向图g = (v, e).m í e ，如果任意一个顶点至多出现在m中的一条边中，m是一个___。
7、【判断题】设f任意流,(a, b)是任意 s-t割.则流值至多等于割的容量.
8、【判断题】存在割(a, b) 使流值v(f)=割的容量cap(a, b).，则割 (a, b)是最小割。
9、【判断题】对于简单网络，最短增广路算法时间复杂度o(nm)
10、【判断题】有下界的流通问题不一定有可行流。
11、【判断题】带需求的流通必须满足供给和 = 需求和.
12、【判断题】重标号操作使它的标号上升到比周围最低的结点高度 1,使他的赢余能流出去
13、【判断题】最短增广路算法可以设计出在o（logn）的平均时间内找到一条最短增广路，算法复杂度为o（mnlogn）
14、【判断题】设g是n阶无孤立点的图，则v*是g的顶点覆盖，当且仅当v-v*是g的独立集。
15、【判断题】
16、【判断题】
17、【判断题】匈牙利算法中起点和终点都是未匹配点的交错路径称为可增广路径，可增广路径有奇数条边。
18、【判断题】给定连通图g, bfs遍历得到层次图，如果同一层中的结点无边相连，则g是二分图。
19、【判断题】
20、【判断题】网络流满足容量约束，但一般不满足流量守恒约束。
11.3第十一单元 章节测验
1、【单选题】在下列算法中有时找不到问题解的是（ ）。
a、蒙特卡罗算法
b、拉斯维加斯算法
c、舍伍德算法
d、数值随机算法
2、【单选题】肯定获得可行解，但不一定是正确解的算法是（）。
a、蒙特卡罗算法
b、拉斯维加斯算法舍伍德算法
c、舍伍德算法
d、数值随机算法
3、【单选题】在一般输入数据的程序里，输入多少会影响到算法的计算复杂度，为了消除这种影响可用（ ）对输入进行预处理。
a、蒙特卡罗算法
b、拉斯维加斯算法
c、舍伍德算法
d、数值随机化算法
4、【多选题】（ ）肯定获得最优解。
a、分支限界
b、贪心算法
c、随机算法
d、动态规划算法
5、【多选题】下面说法正确的是（）
a、现实计算机上无法产生真正的随机数
b、求解同一实例用同一随机化算法求解两次，所用时间和所得结果可能完全不同。
c、蒙特卡罗算法总是能提供问题的一个解,但可能给出错误解。
d、舍伍德算法的精髓不是避免最坏的情况，而是设法消除最坏情况和特定实例的关联性。
6、【多选题】下面说法正确的是（）
a、随机算法是一种使用概率和统计方法在其执行过程中对于下一计算步骤作出随机选择的算法.
b、当最坏和平均情况差别较大时, 舍伍德算法可以消除好坏实例的差别，达到平均实例的性能.
c、线性同余法是产生伪随机数的最常用的方法
d、增加蒙特卡罗算法的求解次数, 可使求解错误的概率任意小。
7、【填空题】现实计算机上的随机算法中使用的随机数都是____。
8、【填空题】如果对于同一实例，蒙特卡罗算法不会给出2个不同的正确解答，则称该蒙特卡罗算法是____的。
9、【判断题】sherwood算法随机选择一个数组元素作为划分标准求解k小元素问题,保证线性时间的平均性能。
10、【判断题】借助随机预处理技术，不改变原有的确定性算法，仅对其输入进行随机洗牌，可收到舍伍德算法的效果。
11、【判断题】
12、【判断题】确定性算法的每一计算步骤都确定,求解同一实例用同一算法求解两次，所得结果完全相同。
13、【判断题】增加拉斯维加斯算法的反复求解次数, 可使求解无效的概率任意小。
14、【判断题】蒙特卡罗算法的结果肯定是一个正确解。
15、【判断题】随机算法共同点是计算时间越多或运行次数越多,正确性越高.
16、【判断题】舍伍德算法总是有解, 且解总是正确的，但最坏性能未改变。
17、【判断题】拉斯维加斯算法肯定得到一个正确解。
18、【判断题】随机抽取数组元素k次,从最接近搜索元素x 的位置顺序搜索,顺序搜索的平均比较次数为o(n/(k 1)).
19、【判断题】
20、【判断题】对于给定的正整数n，判定n是一个素数的充要条件是(n-1)!≡1(mod n)。
12.4第十二单元 章节测验
1、【单选题】下列说法错误的是
a、
b、
c、判定问题可多项式时间变换到优化问题
d、如果一个np完全问题有多项式时间算法，那么np中的每一个问题都可以有多项式时间算法
2、【单选题】以下是np完全问题的（）
a、0-1背包
b、顶点覆盖
c、最短路
d、最大公因子
3、【单选题】下面关于np问题说法正确的是（ ）
a、np问题都是不可能解决的问题
b、p类问题包含在np类问题中
c、np完全问题是p类问题的子集
d、np类问题包含在p类问题中
4、【单选题】p类问题可以（ ）
a、多项式时间计算
b、指数时间计算
c、指数时间验证
5、【多选题】下面属于np完全问题的是（）
a、sat
b、最大独立集
c、最小顶点覆盖
d、旅行商问题
6、【多选题】以下关于判定问题难易处理的叙述中错误的是（ ）。
a、可以由多项式时间算法求解的问题是难处理的
b、需要超过多项式时间算法求解的问题是易处理的
c、可以由多项式时间算法求解的问题是易处理的
d、需要超过多项式时间算法求解的问题是不能处理的
7、【多选题】np完全问题的证明方法有（）
a、局部替换
b、分支设计
c、限制技术
d、定义法
8、【填空题】回答是与否的问题是___问题。
9、【填空题】多选式时间可验证问题是____问题。
10、【填空题】构造一个解使目标函数最大或最小的问题是__问题。
11、【填空题】p ___ np
12、【判断题】exp类是所有指数时间可解的判定问题组成的问题类
13、【判断题】
14、【判断题】如果对于x的任意实例，通过多项式次的计算步骤，加多项式次调用y的算法，可解决x，则 x可多项式时间归约到y。
15、【判断题】
16、【判断题】
17、【判断题】
18、【判断题】
19、【判断题】
20、【判断题】如果一个np完全问题能在多项式时间内得到解决，那么np中的每一个问题都可以在多项式时间内求解。
21、【判断题】有多项式时间算法的问题是易解问题
22、【判断题】在一个平面或球面的任何地图能够只用4种颜色着色，使相邻国家在地图上着不同颜色。
23、【判断题】任何图的二着色问题都是npc问题。
24、【判断题】如果 k 为小常数, 最小顶点覆盖问题存在多项式时间算法。
13.5第十三单元 章节测验
1、【单选题】下面说法错误的是（）
a、近似性能比不可能小于1.
b、完全多项式时间近似方案的近似性能比是1 e，e>0.
c、np-hard 与npc 区别是否属于np。
d、旅行商问题的近似性能比不会小于2.
2、【多选题】近似算法的设计方法有（）
a、贪心
b、组合技术
c、定价法
d、线性规划和舍入
3、【判断题】给定问题p，若有算法a，存在一个常数k³0，使得所有实例iîdp，总有：|a(i)-opt(i)|£k则称算法a为解答问题p的绝对近似算法。
4、【判断题】np-hard 问题属于np
5、【判断题】已知当p¹np时，np-hard优化问题存在多项式时间绝对近似算法。
6、【判断题】绝大多数np-hard问题存在多项式时间绝对近似算法
7、【判断题】若p¹np，则最大独立集问题存在多项式时间绝对近似算法。
8、【判断题】最大优化问题的近似性能比小于1，越接近1越说明算法好
9、【判断题】多项式时间近似方案的近似性能比是1 e，e>0.
10、【判断题】多项式时间近似方案的时间复杂度是p(n, 1/ e) ， p是多项式函数。
猜你喜欢
- 2023-10-22 22:49
- 2023-10-22 22:47
- 2023-10-22 22:37
- 2023-10-22 22:32鄂尔多斯市消防救援支队“条令纲要题目答案搜题软件
- 2023-10-22 22:24
- 2023-10-22 22:17
- 2023-10-22 22:00
- 2023-10-22 21:30
- 2023-10-22 21:14
- 2023-10-22 20:45