智慧树知到《算法分析与设计》章节测试答案

智慧树知到《算法分析与设计》章节测试答案
第一章
1、给定一个实例，如果一个算法能得到正确解答，称这个算法解答了该问题。
A:对
B:错
答案: 错
2、一个问题的同一实例可以有不同的表示形式
A:对
B:错
答案: 对
3、同一数学模型使用不同的数据结构会有不同的算法，有效性有很大差别。
A:对
B:错
答案: 对
4、问题的两个要素是输入和实例。
A:对
B:错
答案: 错
5、算法与程序的区别是（）
A:输入
B:输出
C:确定性
D:有穷性
答案: 有穷性
6、解决问题的基本步骤是（）。（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)
答案: (3)(1)(5)(4)(2)
7、下面说法关于算法与问题的说法错误的是（）。
A:如果一个算法能应用于问题的任意实例，并保证得到正确解答，称这个算法解答了该问题。
B:算法是一种计算方法，对问题的每个实例计算都能得到正确答案。
C:同一问题可能有几种不同的算法，解题思路和解题速度也会显著不同。
D:证明算法不正确，需要证明对任意实例算法都不能正确处理。
答案: 证明算法不正确，需要证明对任意实例算法都不能正确处理。
8、下面关于程序和算法的说法正确的是（）。
A:算法的每一步骤必须要有确切的含义，必须是清楚的、无二义的。
B:程序是算法用某种程序设计语言的具体实现。
C:程序总是在有穷步的运算后终止。
D:算法是一个过程，计算机每次求解是针对问题的一个实例求解。
答案: 算法的每一步骤必须要有确切的含义，必须是清楚的、无二义的。
,程序是算法用某种程序设计语言的具体实现。
,算法是一个过程，计算机每次求解是针对问题的一个实例求解。
9、最大独立集问题和（）问题等价。
A: 最大团
B:最小顶点覆盖
C:区间调度问题
D:稳定匹配问题
答案:  最大团
,最小顶点覆盖
10、给定两张喜欢列表，稳定匹配问题的输出是（  ） 。
A:完美匹配
B:没有不稳定配对
C:最大匹配
D:稳定匹配
答案: 完美匹配
,没有不稳定配对
,最大匹配
,稳定匹配
11、问题变换的目的有（）。(1)复杂变简单 (2)未知变已知 (3)隐式变显式 (4)难解变易解 （5）以上都是。
A:（1）
B:（2）
C:（3）
D:（4）
E:（5）
答案: （5）
12、按照霍纳法则，计算p(x) = anxn + an-1xn-1+… +a1x1+ a0  的数量级为____ 。
A:n^2
B:n
C:nlogn
D:logn
答案: n
第十二章
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类问题中
答案:
6、P类问题可以（ ）。
A:多项式时间计算
B:指数时间计算
C:指数时间验证
答案:
7、下面属于NP完全问题的是（）
A:SAT
B:最大独立集
C:最小顶点覆盖
D:旅行商问题
答案:
8、以下关于判定问题难易处理的叙述中错误的是
A:可以由多项式时间算法求解的问题是难处理的
B:需要超过多项式时间算法求解的问题是易处理的
C:可以由多项式时间算法求解的问题是易处理的
D:需要超过多项式时间算法求解的问题是不能处理的
答案:
9、下列说法错误的是
A:If X多项式时间归约到Y and Y多项式时间归约到Z, then X多项式时间归约到Z.
B:P包含于NP
C:判定问题可多项式时间变换到优化问题
D:如果一个NP完全问题有多项式时间算法，那么NP中的每一个问题都可以有多项式时间算法
答案:
第二章
1、时间复杂度是指算法最坏情况下的运行时间。
A:对
B:错
答案: 对
2、f(n)=O(g(n))  则 f(n)2=O(g(n)2)
A:对
B:错
答案: 对
3、f(n)=3n3+7n2+4nlogn =O（n2）
A:对
B:错
答案: 错
4、如果一个算法是多项式时间算法，该算法是有效的,是好算法。
A:对
B:错
答案: 对
5、从资源划分，算法的复杂度分为（ ）和（）。
A:时间复杂度  空间复杂度
B: 空间复杂度   平均复杂度
C:最好复杂度 最坏复杂度
D:时间复杂度   平均复杂度
答案: 时间复杂度  空间复杂度
6、算法复杂度分析的两种基本方法为（  ）和（    ）。
A:结构化方法 面向对象方法
B:事后统计  事前分析
C:几何复杂度  平均复杂度
D:平摊复杂度 平滑复杂度
答案: 事后统计  事前分析
第三章
1、0-1背包问题的枚举算法的时间复杂度为O（2n）
A:对
B:错
答案:B
2、增量构造法生成子集前需要对集合中元素从小到大排列。
A:对
B:错
答案:A
3、分块查找一般设分块的长度是n/2.
A:对
B:错
答案:B
4、枚举法适用于问题的小规模实例。
A:对
B:错
答案:A
5、便于实现集合操作的子集生成算法是（）
A:增量构造法
B:位向量法
C:二进制法
答案:C
6、从所有候选答案中去搜索正确的解，这是 （）算法。
A:蛮力
B:枚举
C:递推
答案:B
7、logn2=(  )(logn+5)
A:θ
B:O
C:W
D:o
答案:A
8、0-1背包问题的枚举算法，如果在百万次每秒的计算机上运行，1年可以计算的问题规模估计是？
A:40
B:60
C:30
D:50
答案:A
9、分数拆分问题的枚举算法通过（）方法进行了优化。
A:减少枚举变量
B:减少枚举变量的值域
C:优化数据结构
D:优化数学模型
答案:ABD
10、下面那些算法的时间复杂度为O（）?
A:顺序查找
B:折半查找
C:插入排序
D:冒泡排序
E:折半插入排序
答案:插入排序、折半插入排序、冒泡排序
第四章
1、贪心算法总能找到可行解，但未必是最优解。
A:对
B:错
答案:A
2、贪心选择通过一步步选择得到问题的解，每一步的局部最优解都构成全局最优解的一部分。
A:对
B:错
答案:A
3、问题的最优子结构性质是该问题可用贪心算法或动态规划算法求解的关键特征。
A:对
B:错
答案:A
4、如果图G中每条边的权重都是互不相同的，图G必定只有一颗最小生成树。
A:对
B:错
答案:A
5、Kruskal算法的贪婪准则是每一次选取不构成环路的最小边。
A:对
B:错
答案:A
6、贪心算法基本要素有（   ）和最优子结构性质。
A:分解合并性质
B:独立子问题性质
C:贪心选择性质
D:重叠子问题性质
答案:C
7、下面不是证明贪心算法证明方法的有（）。
A:领先
B:优化
C:交换论证
D:界
答案:B
8、未来与过去无关指的是（  ）的性质
A:贪心选择
B:无后效性
C:最优子结构
D:重叠子问题
答案:B
9、最小生成树问题可以使用的算法有（ ）
A:Kruskal
B:Prim
C:Solim
D:Dijkstra
答案:Kruskal、Prim、Solim
10、区间问题包含()
A:区间调度
B:区间划分
C:区间选点
D:区间覆盖
答案:ABCD
第五章
1、正推是从小规模的问题推解出大规模间题的一种方法。
A:对
B:错
答案:A
2、一般来说，递归的效率高于递推。
A:对
B:错
答案:B
3、从大规模问题逐步化为小规模问题的算法是（）
A:递归
B:正推
C:倒推
D:迭代
答案:A
4、求解高阶递推方程一般使用（）迭代方法
A:差消迭代
B:换元迭代
C:直接迭代
答案:A
5、下面有关递归与迭代的说法错误的是（）
A:递归与迭代都是解决“重复操作”的机制。
B:递归算法的实现往往要比迭代算法耗费更多的时间。
C:每个迭代算法原则上总可以转换成与它等价的递归算法。
D:每个递归算法原则上总可以转换成与它等价的迭代算法
答案:D
6、递归函数的要素是（）
A:边界条件
B:递归方程
C:迭代
D:输入
答案:AB
7、递归变为非递归的方法有（）
A:模拟栈
B:递推
C:尾递归
D:循环
答案:模拟栈、递推、尾递归
8、T(n) = T(n-1) + n，T(1)=1，则 T(n) =（）
A:Ω(n^2)
B:n(n+1)/2
C:O(n^2)
D:θ(n^2)
答案:Ω(n^2)、n(n+1)/2、O(n^2)、θ(n^2)
9、 递归一般用于解决问题有（）
A:数据的定义是按递归定义的
B:问题解法按递归实现
C:数据的结构形式是按递归定义的
D:迭代问题
答案:ABC
10、主方法可以求解满足T(n)=aT(n/b) + f (n)形式的递推方程，则下列关于方程中的约束中不准确的是？
设ε
A:对于系数a，必须满足a>=1
B:对于系数b，必须满足b>1
C:若对于常数ε>0，f(n)=O(y)，则T(n)=Θ(x)
D:若f(n)=O(x)，则T(n)=Θ(xlogn)
答案:若f(n)=O(nlogba)，则T(n)=Θ(nlogbalogn)
第六章
1、分治法分解的子问题与原问题形式相同。
A:对
B:错
答案:A
2、N个元素排序的时间复杂度不可能是线性时间。
A:对
B:错
答案:B
3、三分法的判定树是三叉树。
A:对
B:错
答案:A
4、减治法减一个常量就是每次迭代减去一个相同的常数因子(一般为2)
A:对
B:错
答案:B
5、设有5000个无序的元素，希望用最快的速度挑选出其中前10个最大的元素，最好选用(   )法。
A:冒泡排序
B:快速排序
C:合并排序
D:基数排序
答案:A
6、堆排序的时间复杂度是O（）。
A: O（n）
B:O（2n）
C:O（n2）
D: O（nlogn）
答案:D
7、以下不可以使用分治法求解的是（  ）。
A:棋盘覆盖问题
B:线性选择问题
C:归并排序
D:0/1背包问题
答案:D
8、改进分治算法的方法有（ ）和改进划分的对称性。
A:减少子问题数
B:备忘录
C:拟阵原理
D:加速原理
答案:A
9、通过减少子问题个数，降低分治算法时间复杂度的有（）
A:大整数乘法
B:Strassen矩阵乘法
C:线性时间选择
D:最接近点对
答案:AB
10、 分治法在每一层递归上有三个步骤（）
A:分解
B:解决
C:合并
D:选择
答案:分解、解决、合并
第七章
1、动态规划算法把原问题分为交叉的子问题，解决子问题，记录子问题的解，合并为原问题的解。
A:对
B:错
答案:A
2、0/1背包问题的动态规划算法是多项式时间算法。
A:对
B:错
答案:B
3、对于稀疏图，Floyd算法的效率要高于执行n次Dijkstra算法，也要高于执行n次SPFA算法。
A:对
B:错
答案:B
4、Dijkstra算法在求解过程中，源点到集合S内各顶点的最短路径一旦求出，则之后不变了，修改的仅仅是源点到还没选择的顶点的最短路径长度。
A:对
B:错
答案:A
5、含负权的最短路问题一般使用（）求解。
A:动态规划
B:贪心算法
C:分治算法
D:网络流算法
答案:A
6、动态规划算法的基本要素有（ ）和最优子结构性质。
A:分解合并性质
B:独立子问题性质
C:贪心选择性质
D:重叠子问题性质
答案:D
7、下面不是动态规划的基本方法有（）。
A:多重选择
B:增加变量
C:舍入
D:区间变量
答案:C
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:错
答案:B
2、死结点是正在产生儿子的结点。
A:对
B:错
答案:B
3、回溯法的一个显著特征是在搜索过程中动态产生问题的解空间。
A:对
B:错
答案:A
第九章
1、分支限界法在对问题的解空间树进行搜索的方法中，一个活结点有多次机会成为活结点。
A:对
B:错
答案:B
2、分支限界法找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。
A:对
B:错
答案:A
3、队列式分支限界法以最小耗费优先的方式搜索解空间树。
A:对
B:错
答案:B
4、优先队列式分支限界法按照队列先进先出的原则，选取下一个节点为扩展结点。
A:对
B:错
答案:B
5、下列算法中不能解决0/1背包问题的是
A:贪心法
B:动态规划
C:回溯法
D:分支限界法
答案:A
6、分支限界法解旅行商问题时的解空间树是
A:子集树
B:排列树
C:深度优先生成树
D:广度优先生成树
答案:B
7、优先队列式分支限界法选取扩展结点的原则是
A:先进先出
B:后进先出
C:结点的优先级
D:随机
答案:C
8、用分支限界法设计算法的步骤是：
A:针对所给问题，定义问题的解空间（对解进行编码）
B:确定易于搜索的解空间结构（按树或图组织解）
C:定义最优子结构
D:以广度优先或以最小耗费（最大收益）优先的方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索
答案:ABD
9、分支限界法与回溯法的不同点是什么？
A:求解目标不同
B:搜索方式不同
C:对扩展结点的扩展方式不同
D:存储空间的要求不同
答案:ABCD
10、FIFO是（  ）的搜索方式。
A:回溯算法
B:分支限界
C:动态规划
D:贪心算法
答案:B
第十章
1、网络流满足容量约束，但一般不满足流量守恒约束。
A:对
B:错
答案:B
2、设G = <V1, V2, E>为二分图, |V1|≤|V2|, M为G中一个最大匹配, 且|M| = |V1|, 则称M为G的完备匹配，也是最大匹配。
A:对
B:错
答案:A
3、存在割 (A, B) 使流值 v(f) = 割的容量cap(A, B).，则割 (A, B)是最小割。
A:对
B:错
答案:A
4、给定连通图G, BFS遍历得到层次图，如果同一层中的结点无边相连，则G是二分图。
A:对
B:错
答案:A
5、有下界的流通问题不一定有可行流。
A:对
B:错
答案:A
6、Dinic算法的时间复杂度为（）
A: mn2
B:mn
C:m2n
D:  m2logC
答案:A
7、如果每条边的最大容量为1，则时间复杂度是O（nm）的网络流算法有
A:FF算法
B:容量缩放算法
C:EK算法
D: Dinic算法
答案:A
8、给定二分图G = <V, E>中无孤立点，|V|=n，其最大流算法求得最大流f,则 G的（）=n-f
A:最大独立数
B:最大匹配数
C:最小顶点覆盖
D:最小边覆盖
答案:
9、改进FF网络流算法，可以通过选择（  ）增广路，降低时间复杂度。
A:最大容量
B:最短路径
C: 最大瓶颈容量
D:边数最少
答案:ABCD
10、带需求的流通必须满足供给和 = 需求和
A:对
B:错
答案:A
第十一章
1、蒙特卡罗算法的结果肯定是一个正确解。
A:对
B:错
答案:B
2、Sherwood算法随机选择一个数组元素作为划分标准求解k小元素问题,保证线性时间的平均性能。
A:对
B:错
答案:A
3、借助随机预处理技术，不改变原有的确定性算法，仅对其输入进行随机洗牌，可收到舍伍德算法的效果。
A:对
B:错
答案:A
4、随机算法共同点是计算时间越多或运行次数越多,正确性越高.
A:对
B:错
答案:A
5、增加拉斯维加斯算法的反复求解次数,可使求解无效的概率任意小。
A:对
B:错
答案:A
6、在下列算法中有时找不到问题解的是
A:蒙特卡罗算法
B:拉斯维加斯算法
C:舍伍德算法
D:数值随机算法
答案:拉斯维加斯算法
7、肯定获得可行解，但不一定是正确解的算法是
A:蒙特卡罗算法
B:拉斯维加斯算法
C:舍伍德算法
D:数值随机算法
答案:A
8、在一般输入数据的程序里，输入多少会影响到算法的计算复杂度，为了消除这种影响可用（  ）对输入进行预处理。
A:蒙特卡罗算法
B:拉斯维加斯算法
C:舍伍德算法
D:数值随机化算法
答案:C
9、（ ）肯定获得最优解。
A:分支限界
B:贪心算法
C:随机算法
D:动态规划算法
答案:AD
10、下面说法正确的是
A:现实计算机上无法产生真正的随机数
B:求解同一实例用同一随机化算法求解两次，所用时间和所得结果可能完全不同。
C:蒙特卡罗算法总是能提供问题的一个解,但可能给出错误解。
D:舍伍德算法的精髓不是避免最坏的情况，而是设法消除最坏情况和特定实例的关联性。
答案:
第十三章
1、给定问题p，若有算法A，存在一个常数K>=0，使得问题p的所有实例I，总有：|A(I)-OPT(I)|<=K,则称算法A为解答问题p的绝对近似算法。
A:对
B:错
答案:A
2、NP-hard 问题属于NP
A:对
B:错
答案:B
3、当P不等于NP时，NP-hard优化问题存在多项式时间绝对近似算法。
A:对
B:错
答案:B
4、绝大多数NP-hard问题存在多项式时间绝对近似算法
A:对
B:错
答案:B
5、若P不等于NP，则最大独立集问题存在多项式时间绝对近似算法。
A:对
B:错
答案:B
6、最大优化问题的近似性能比小于1，越接近1越说明算法好
A:对
B:错
答案:B
7、多项式时间近似方案的近似性能比是1 + q，q>0.
A:对
B:错
答案:A
8、多项式时间近似方案的时间复杂度是P(n, 1/ q)， P是多项式函数, q>0。
A:对
B:错
答案:B
9、近似算法的设计方法有（）
A:贪心
B:组合技术
C:定价法
D:线性规划和舍入
答案:ABCD
10、下面说法错误的是（）
A:近似性能比不可能小于1
B:完全多项式时间近似方案的近似性能比是1+p，p>0
C:NP-hard 与NPC区别是否属于NP
NP-hard 与NPC区别是否属于NP
D:旅行商问题的近似性能比不会小于2
答案: