《智慧树知到《算法分析与设计》章节测试答案》由会员分享，可在线阅读，更多相关《智慧树知到《算法分析与设计》章节测试答案（48页珍藏版）》请在人人文库网上搜索。

1、智慧树知到算法分析与设计章节测试答案第一章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)(

(3)(1)(5)(4)(2)7、下面说法关于算法与问题的说法错误的是（）。A:如果一个算法能应用于问题的任意实例，并保证得到正确解答，称这个算法解答了该问题。B:算法是一种计算方法，对问题的每个实例计算都能得到正确答案。C:同一问题可能有几种不同的算法，解题思路和解题速度也会显著不同。D:证明算法不正确，需要证明对任意实例算法都不能正确处理。答案: 证明算法不正确，需要证明对任意实例算法都不能正确处理。8、下面关于程序和算法的说法正确的是（）。A:算法的每一步骤必须要有确切的含义，必须是清楚的、无二义的。B:程序是算法用某种程序

3、设计语言的具体实现。C:程序总是在有穷步的运算后终止。D:算法是一个过程，计算机每次求解是针对问题的一个实例求解。答案: 算法的每一步骤必须要有确切的含义，必须是清楚的、无二义的。,程序是算法用某种程序设计语言的具体实现。,算法是一个过程，计算机每次求解是针对问题的一个实例求解。9、最大独立集问题和（）问题等价。A: 最大团B:最小顶点覆盖C:区间调度问题D:稳定匹配问题答案:  最大团,最小顶点覆盖10、给定两张喜欢列表，稳定匹配问题的输出是（  ） 。A:完美匹配B:没有不稳定配对C:最大匹配D:稳定匹配答案: 完美匹配,没有不稳定配对,最大匹配,稳

n第十二章1、有多项式时间算法的问题是易解问题A:对B:错答案:2、EXP类是所有指数时间可解的判定问题组成的问题类A:对B:错答案:3、如果对于X的任意实例，通过多项式次的计算步骤，加多项式次调用Y的算法，可解决X，则 X可多项式时间

5、归约到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:SATB:最大独立集C:最小顶点覆盖D:旅行商问题答案:8、以下关于判定问题难易处理的叙述中错误的是A:可以由多项式时间算法求解的问题是难处理的B:需要超过多项式时间算法求解的问题是易处理的C:可以由

6、多项式时间算法求解的问题是易处理的D:需要超过多项式时间算法求解的问题是不能处理的答案:9、下列说法错误的是A:If X多项式时间归约到Y and Y多项式时间归约到Z, then X多项式时间归约到Z.B:P包含于NPC:判定问题可多项式时间变换到优化问题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

7、 错4、如果一个算法是多项式时间算法，该算法是有效的,是好算法。A:对B:错答案: 对5、从资源划分，算法的复杂度分为（ ）和（）。A:时间复杂度  空间复杂度B: 空间复杂度   平均复杂度C:最好复杂度 最坏复杂度D:时间复杂度   平均复杂度答案:

事后统计  事前分析第三章1、0-1背包问题的枚举算法的时间复杂度为O（2n）A:对B:错答案:B2、增量构造法生成子集前需要对集合中元素从小到大排列。A:对B:错答案:A3、分块查找一般设分块的长度是n/2.A:对B:错答案:B4、枚举法适用于问题的小规模实例。A:对B:错答案:A5、便于实现集合操作的子集生成算法是（）A:增量构造法B:位向量法C:二进制法答案:C6、从所有候选答案中去搜索正确的解，这是

9、算法，如果在百万次每秒的计算机上运行，1年可以计算的问题规模估计是？A:40B:60C:30D:50答案:A9、分数拆分问题的枚举算法通过（）方法进行了优化。A:减少枚举变量B:减少枚举变量的值域C:优化数据结构D:优化数学模型答案:ABD10、下面那些算法的时间复杂度为O（）?A:顺序查找B:折半查找C:插入排序D:冒泡排序E:折半插入排序答案:插入排序、折半插入排序、冒泡排序第四章1、贪心算法总能找到可行解，但未必是最优解。A:对B:错答案:A2、贪心选择通过一步步选择得到问题的解，每一步的局部最优解都构成全局最优解的一部分。A:对B:错答案:A3、问题的最优子结构性质是该问题可用贪心算法

10、或动态规划算法求解的关键特征。A:对B:错答案:A4、如果图G中每条边的权重都是互不相同的，图G必定只有一颗最小生成树。A:对B:错答案:A5、Kruskal算法的贪婪准则是每一次选取不构成环路的最小边。A:对B:错答案:A6、贪心算法基本要素有（   ）和最优子结构性质。A:分解合并性质B:独立子问题性质C:贪心选择性质D:重叠子问题性质答案:C7、下面不是证明贪心算法证明方法的有（）。A:领先B:优化C:交换论证D:界答案:B8、未来与过去无关指的是（  ）的性质A:贪心选择B:无后效性C:最优子结构D:重叠子问题答案:B9、最小生成树问题可以使用的

）A:KruskalB:PrimC:SolimD:Dijkstra答案:Kruskal、Prim、Solim10、区间问题包含()A:区间调度B:区间划分C:区间选点D:区间覆盖答案:ABCD第五章1、正推是从小规模的问题推解出大规模间题的一种方法。A:对B:错答案:A2、一般来说，递归的效率高于递推。A:对B:错答案:B3、从大规模问题逐步化为小规模问题的算法是（）A:递归B:正推C:倒推D:迭代答案:A4、求解高阶递推方程一般使用（）迭代方法A:差消迭代B:换元迭代C:直接迭代答案:A5、下面有关递归与迭代的说法错误的是（）A:递归与迭代都是解决“重复操作”的机制。B:递归算法的

12、实现往往要比迭代算法耗费更多的时间。C:每个迭代算法原则上总可以转换成与它等价的递归算法。D:每个递归算法原则上总可以转换成与它等价的迭代算法答案:D6、递归函数的要素是（）A:边界条件B:递归方程C:迭代D:输入答案:AB7、递归变为非递归的方法有（）A:模拟栈B:递推C:尾递归D:循环答案:模拟栈、递推、尾递归8、T(n) = T(n-1) + n，T(1)=1，则 T(n)

(n)形式的递推方程，则下列关于方程中的约束中不准确的是？设A:对于系数a，必须满足a>=1B:对于系数b，必须满足b>1C:若对于常数>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:错答案:A2、N个元素排序的时间复杂度不可能是线性时间。A:对B:错答案:B3、三分法的判定树是三叉树。A:对B:错答案:

14、A4、减治法减一个常量就是每次迭代减去一个相同的常数因子(一般为2)A:对B:错答案:B5、设有5000个无序的元素，希望用最快的速度挑选出其中前10个最大的元素，最好选用(   )法。A:冒泡排序B:快速排序C:合并排序D:基数排序答案:A6、堆排序的时间复杂度是O（）。A: O（n）B:O（2n）C:O（n2）D: O（nlogn）答案:D7、以下不可以使用分治法求解的是（  ）。A:棋盘覆盖问题B:线性选择问题C:归并排序D:0/1背包问题答案:D8、改进分治算法的方法有（ ）和改进划分的对称性。A:减少子问题数B:备忘录C:拟阵原理D:加速原理答

15、案:A9、通过减少子问题个数，降低分治算法时间复杂度的有（）A:大整数乘法B:Strassen矩阵乘法C:线性时间选择D:最接近点对答案:AB10、 分治法在每一层递归上有三个步骤（）A:分解B:解决C:合并D:选择答案:分解、解决、合并第七章1、动态规划算法把原问题分为交叉的子问题，解决子问题，记录子问题的解，合并为原问题的解。A:对B:错答案:A2、0/1背包问题的动态规划算法是多项式时间算法。A:对B:错答案:B3、对于稀疏图，Floyd算法的效率要高于执行n次Dijkstra算法，也要高于执行n次SPFA算法。A:对B:错答案:B4、Dijkstra算法在求解过程中，源点到集合S内各顶

16、点的最短路径一旦求出，则之后不变了，修改的仅仅是源点到还没选择的顶点的最短路径长度。A:对B:错答案:A5、含负权的最短路问题一般使用（）求解。A:动态规划B:贪心算法C:分治算法D:网络流算法答案:A6、动态规划算法的基本要素有（ ）和最优子结构性质。A:分解合并性质B:独立子问题性质C:贪心选择性质D:重叠子问题性质答案:D7、下面不是动态规划的基本方法有（）。A:多重选择B:增加变量C:舍入D:区间变量答案:C8、最短路算法中适用于稀疏图的是（）A:Floyd算法B:SPFA算法C: Bellman算法D:Dijkstra算法答案:SPFA算法、Bellman算法、Dijkstra算法9

17、、动态规划算法的特点（）A:自底向上计算B:自顶向下计算C:从大到小计算D:从小到大计算答案:从小到大计算、自底向上计算10、 备忘录算法的特点（）A:自底向上计算B:自顶向下计算C:从大到小计算D:从小到大计算答案:自顶向下计算、从大到小计算第八章1、回溯法是按广度优先策略搜索解空间树。A:对B:错答案:B2、死结点是正在产生儿子的结点。A:对B:错答案:B3、回溯法的一个显著特征是在搜索过程中动态产生问题的解空间。A:对B:错答案:A第九章1、分支限界法在对问题的解空间树进行搜索的方法中，一个活结点有多次机会成为活结点。A:对B:错答案:B2、分支限界法找出满足约束条件的一个解，或是在满足

18、约束条件的解中找出在某种意义下的最优解。A:对B:错答案:A3、队列式分支限界法以最小耗费优先的方式搜索解空间树。A:对B:错答案:B4、优先队列式分支限界法按照队列先进先出的原则，选取下一个节点为扩展结点。A:对B:错答案:B5、下列算法中不能解决0/1背包问题的是A:贪心法B:动态规划C:回溯法D:分支限界法答案:A6、分支限界法解旅行商问题时的解空间树是A:子集树B:排列树C:深度优先生成树D:广度优先生成树答案:B7、优先队列式分支限界法选取扩展结点的原则是A:先进先出B:后进先出C:结点的优先级D:随机答案:C8、用分支限界法设计算法的步骤是：A:针对所给问题，定义问题的解空间（对解

19、进行编码）B:确定易于搜索的解空间结构（按树或图组织解）C:定义最优子结构D:以广度优先或以最小耗费（最大收益）优先的方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索答案:ABD9、分支限界法与回溯法的不同点是什么？A:求解目标不同B:搜索方式不同C:对扩展结点的扩展方式不同D:存储空间的要求不同答案:ABCD10、FIFO是（  ）的搜索方式。A:回溯算法B:分支限界C:动态规划D:贪心算法答案:B第十章1、网络流满足容量约束，但一般不满足流量守恒约束。A:对B:错答案:B2、设G

BFS遍历得到层次图，如果同一层中的结点无边相连，则G是二分图。A:对B:错答案:A5、有下界的流通问题不一定有可行流。A:对B:错答案:A6、Dinic算法的时间复杂度为（）A: mn2B:mnC:m2nD:  m2logC答案:A7、如果每条边的最大容量为1，则时间复杂度是O（nm）的网络流算法有A:FF算法B:容量缩放算法C:EK算法D:

21、 Dinic算法答案:A8、给定二分图G = <V, E>中无孤立点，|V|=n，其最大流算法求得最大流f,则 G的（）=n-fA:最大独立数B:最大匹配数C:最小顶点覆盖D:最小边覆盖答案:9、改进FF网络流算法，可以通过选择（  ）增广路，降低时间复杂度。A:最大容量B:最短路径C: 最大瓶颈容量D:边数最少答案:ABCD10、带需求的流通必须满足供给和 = 需求和A:对B:错答案:A第十一章1、蒙特卡罗算法的结果肯定是一个正确解。A:对B:错答案:B2、Sherwood算法随机选择一个数组元素作为划分标准求解k小元素问题,保证线性时间的平均性能。A:对B:

22、错答案:A3、借助随机预处理技术，不改变原有的确定性算法，仅对其输入进行随机洗牌，可收到舍伍德算法的效果。A:对B:错答案:A4、随机算法共同点是计算时间越多或运行次数越多,正确性越高.A:对B:错答案:A5、增加拉斯维加斯算法的反复求解次数,可使求解无效的概率任意小。A:对B:错答案:A6、在下列算法中有时找不到问题解的是A:蒙特卡罗算法B:拉斯维加斯算法C:舍伍德算法D:数值随机算法答案:拉斯维加斯算法7、肯定获得可行解，但不一定是正确解的算法是A:蒙特卡罗算法B:拉斯维加斯算法C:舍伍德算法D:数值随机算法答案:A8、在一般输入数据的程序里，输入多少会影响到算法的计算复杂度，为了消除这种影响可用（  ）对输入进行预处理。A:蒙特卡罗算法B:拉斯维加斯算法C:舍伍德算法D:数

第二章 算 法 研究计算复杂性问题主要是针对n很大的情形 Definition 2 多项式时间算法 100多年前，有位美国推销员乘驿站马车 向西旅行 ，从州A (state ,状态) 到州E 如图，需要4个 驿程（stage，阶段）。问题为求从 State A到 State E 走哪条途径使他最安全？ 如果一个问题π 的输出（即答案）为 Yes or No，则称问题π为判定问题 . 2 ； 否则，N(so) :=N(so) - s ; N(so)=ф， 停止; 否则，返回 step 2 . 启发式算法的长处： 4）简单易行，比较直观，易被使用者接受； 三、启发式算法的四个基本策略 so 的 2-opt 邻域是对 so 的任 两个元素对换，如果固定第一个城市1，即 四、启发式算法的性能分析 （2） 概率分析 （3） 大规模计算分析 第二章 算 法 D1 ∈ P， 则 TSP 、IP ∈ NP-c 已证有4000余个问题 §3 P 类、NP 类、NP—完全问题 NP-c 类问题有如下十分有趣的性质： 1、任何 NP-c 问题都不能用任何已知的多项式 时间算法求解； 2、任何一个 NP-c 问题有多项式时间算法，则 一切 NP-c 问题都有多项式时间算法 . 如果 π1 是 NP – c 问题, π2 ∈ NP，且π1 可以多项式时间归约到 π2 ，则 π2 是 NP – c 问题 . Theorem 4 P = NP 当且仅当存在一个 NP – c 问题 有多项式时间算法 . 第二章 算 法 主要证明 NP-c 某 一问题可多项式时 间归约为 E 如果成立，则有如下常用方法： 1、寻找尽可能快的算法求解； (如：分枝定界法、单纯形法) 2、在给定假设下，对具体问题提出解的有效算法； 3、提出启发式算法（最好是近似算法），快速地得到 满意解。 （如：贪婪算法、遗传算法） Definition 5 如果某优化问题 π 的判定问题是 NP – c , 则称 π 是 NP – 难 (hard) 问题 . §3 P 类、NP 类、NP—完全问题 ? 单纯形法是否是有效算法？ 1972年，美国数学家 Klee 和 Minty 构造了一个著名例子，证明了单纯形 算法不是多项式时间算法，而是指数 时间算法. 不是 1979年，苏联数学家 Khachiyan提出了一个多项式 时间算法——椭球算法. 证明 了LP ∈ P . 1984年，美国贝尔实验室28岁 的印度人提出了以他自己名字命名的 Karma