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

1、最新资料欢迎阅读最新资料欢迎阅读 PAGE 27 PAGE 272020测试完整答案智慧树知到算法分析与设计章节测试答案第一章1、给定一个实例，如果一个算法能得到正确解答，称这个算法解答了该问题。23有很大差别。45、算法与程序的区别是() A:输入B: 输 出 C:确定性D:有穷性答案: 有穷性6、解决问题的基本步骤是()。(1)算法设计(2)算法实现(3)数学建模(4(5A:(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

2、:如果一个算法能应用于问题的任意实例，并保证得到正确解答，称这个算法解答了该问题。B:算法是一种计算方法，对问题的每个实例计算都能得到正确答案。C著不同。D:证明算法不正确，需要证明对任意实例算法都不能正确处理。答案: 证明算法不正确，需要证明对任意实例算法都不能正确处理。8、下面关于程序和算法的说法正确的是()。A:算法的每一步骤必须要有确切的含义，必须是清楚的、无二义的。B:程序是算法用某种程序设计语言的具体实现。C:程序总是在有穷步的运算后终止。D:算法是一个过程，计算机每次求解是针对问题的一个实例求解。二义的。,程序是算法用某种程序设计语言的具体实现。9A: 最大团B:最小顶点覆盖C:

3、区间调度问题D:稳定匹配问题答案: 最大团,最小顶点覆盖10A:完美匹配BC:最大匹配答案: 完美匹配,没有不稳定配对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:nB:n C:nlogn D:logn n 1、有多项式时间算法的问题是易解问题答案:2、EXP 类是所有指数时间可解的判定问题组成的问题类答案:3X式次调用YX，则 XY。答案:4XYYX式时间解

4、决。答案:5、下面关于NP 问题说法正确的是( ) A:NP 问题都是不可能解决的问题B:PNPPD:NPP6、PA:多项式时间计算BC7、下面属于NPA:SATB:最大独立集 CD:旅行商问题答案:8、以下关于判定问题难易处理的叙述中错误的是A:可以由多项式时间算法求解的问题是难处理的 BC:可以由多项式时间算法求解的问题是易处理的D:需要超过多项式时间算法求解的问题是不能处理的答案:9、下列说法错误的是A:If X 多项式时间归约到Y and Y多项式时间归约到Z, then X 多项式时间归约到Z.B:P 包含于NPC:判定问题可多项式时间变换到优化问题D:如果一个NPNP问题都可以有多

5、项式时间算法答案:第二章12、f(n)=O(g(n)f(n)2=O(g(n)2) 3、f(n)=3n3+7n2+4nlogn =O(n2)45AB:C答案: 时间复杂度 空间复杂度6、算法复杂度分析的两种基本方法为( )和( )。A:结构化方法 面向对象方法B:事后统计 事前分析C:几何复杂度 平均复杂度D:平摊复杂度 平滑复杂度第三章1、0-1:B2、增量构造法生成子集前需要对集合中元素从小到大排列。:A3、分块查找一般设分块的长度是:B4:A5、便于实现集合操作的子集生成算法是() A:增量构造法BC:C6A:蛮力BC7、logn2=( )(logn+5) A:B:OC:WD:o 8、0-

6、1 背包问题的枚举算法，如果在百万次每秒的计算机上运行，1 年可以计算的问题规模估计是?A:40 B:60 C:30 D:50答案:A9A:减少枚举变量BC:优化数据结构D:优化数学模型答案:ABD10、下面那些算法的时间复杂度为A:顺序查找BCE:折半插入排序第四章1:A2、贪心选择通过一步步选择得到问题的解，每一步的局部最优解都构成全局最优解的一部分。答案:A3、问题的最优子结构性质是该问题可用贪心算法或动态规划算法求解的关键特征。答案:A4GG颗最小生成树。:A5Kruskal:A6、贪心算法基本要素有( )和最优子结构性质。A:分解合并性质BC:贪心选择性质 D:C7A:领先C:交换论

7、证D: 界 答案:B8、未来与过去无关指的是( )的性质A:贪心选择B:无后效性 CD:B9、最小生成树问题可以使用的算法有( ) A:KruskalB:Prim C:Solim D:Dijkstra答案:Kruskal、Prim、Solim 10、区间问题包含()A:区间调度B:区间划分C:区间选点D:区间覆盖答案:ABCD第五章1:A2:B3A:递归BCD4、求解高阶递推方程一般使用()迭代方法A:差消迭代B:换元迭代C:直接迭代答案:A5、下面有关递归与迭代的说法错误的是()A:递归与迭代都是解决“重复操作”的机制。B:递归算法的实现往往要比迭代算法耗费更多的时间。C:每个迭代算法原则上

8、总可以转换成与它等价的递归算法。D:每个递归算法原则上总可以转换成与它等价的迭代算法答案:D6、递归函数的要素是() A:边界条件B:递归方程C:迭代D:输入答案:AB7、递归变为非递归的方法有() A:模拟栈B: 递 推 C:尾递归D:循环答案:模拟栈、递推、尾递归8、T(n) = T(n-1) + n，T(1)=1，则 T(n) =()A:(n ) B:n(n+1)/2 C:O(n )D:(n )答案:(n )、n(n+1)/2、O(n )、(n ) 9、 递归一般用于解决问题有()A:数据的定义是按递归定义的B:问题解法按递归实现C:数据的结构形式是按递归定义的D:迭代问题答案:ABC1

9、0、主方法可以求解满足 T(n)=aT(n/b) + f (n)形式的递推方程，则下列关于方程中的约束中不准确的是?设A:对于系数a，必须满足a=1 B:对于系数b，必须满足b1CT(n)=(x) D:若f(n)=O(x)，则T(n)=(xlogn)答案:若f(n)=O(nlogba)，则T(n)=(nlogbalogn) 第六章1:A2、N:B3:A42)答案:B5、设有 5000 个无序的元素，希望用最快的速度挑选出其中前10 个最大的元素，最好选用( )法。A:冒泡排序B:快速排序C:合并排序D:基数排序答案:A6、堆排序的时间复杂度是O(A: O(n)B:O(2n)C:O(n2)D:

10、O(nlogn) 答案:D7、以下不可以使用分治法求解的是( )。A:棋盘覆盖问题B:线性选择问题C:归并排序D:0/1 背包问题答案:D8、改进分治算法的方法有( )和改进划分的对称性。A:减少子问题数B:备忘录C:拟阵原理D:加速原理答案:A9、通过减少子问题个数，降低分治算法时间复杂度的有() A:大整数乘法B:StrassenC:线性时间选择D:最接近点对答案:AB10A:分解BC第七章1、动态规划算法把原问题分为交叉的子问题，解决子问题，记录子问题的解，合并为原问题的解。答案:A2、0/1 背包问题的动态规划算法是多项式时间算法。答案:B3n 次Dijkstra法，也要高于执行n 次

11、SPFA答案:B4DijkstraS的最短路径长度。答案:A5、含负权的最短路问题一般使用()求解。A:动态规划B:贪心算法 C:分治算法 D:A6、动态规划算法的基本要素有( )和最优子结构性质。A:分解合并性质BC:贪心选择性质 D:D7、下面不是动态规划的基本方法有()。A:多重选择BC:舍入D:C8、最短路算法中适用于稀疏图的是() A:Floyd 算法B:SPFA 算法C: BellmanD:Dijkstra:SPFABellmanDijkstra9A:自底向上计算B:自顶向下计算C:从大到小计算D:从小到大计算答案:从小到大计算、自底向上计算10、 备忘录算法的特点()A:自底向上

12、计算B:自顶向下计算C:从大到小计算D:从小到大计算答案:自顶向下计算、从大到小计算第八章1、回溯法是按广度优先策略搜索解空间树。:B2:B3、回溯法的一个显著特征是在搜索过程中动态产生问题的解空间。答案:A 第九章1、分支限界法在对问题的解空间树进行搜索的方法中，一个活结点有多次机会成为活结点。答案:B2、分支限界法找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。:A3:B4、优先队列式分支限界法按照队列先进先出的原则，选取下一个节点为扩展结点。答案:B50/1A:贪心法BC:回溯法D:分支限界法答案:A6A:子集树C:深度优先生成树D:广度优先生成树答案:B7A

13、:先进先出CD:随机:C8、用分支限界法设计算法的步骤是：A:针对所给问题，定义问题的解空间(对解进行编码) B:确定易于搜索的解空间结构(按树或图组织解)C:定义最优子结构D:以广度优先或以最小耗费(最大收益)优先的方式搜索解空间， 并在搜索过程中用剪枝函数避免无效搜索答案:ABD9A:求解目标不同C:对扩展结点的扩展方式不同D:存储空间的要求不同答案:ABCD10FIFOA:回溯算法BCD:B第十章1:B2、设G|V1|V2|,M 为G|M| = |V1|, 则称M 为G 的完备匹配，也是最大匹配。答案:A3、存在割 (A, B) 使流值 v(f) = 割的容量cap(A, B).，则割(

14、A, B)是最小割。答案:A4、给定连通图G,BFS边相连，则G:A5:A6、Dinic 算法的时间复杂度为()A: B:mn C:m2nD: :A7O(nm算法有A:FFBC:EKD: Dinic:A8、给定二分图 G = 中无孤立点，|V|=n大流f,G()=n-fA:最大独立数 B:最大匹配数 CD:最小边覆盖 9FF杂度。AC:D:边数最少答案:ABCD10、带需求的流通必须满足供给和 = 需求和答案:A第十一章1、蒙特卡罗算法的结果肯定是一个正确解。答案:B2Sherwoodk元素问题,保证线性时间的平均性能。答案:A3、借助随机预处理技术，不改变原有的确定性算法，仅对其输入进行随机洗牌，可收到舍伍德算法的效果。答案:A4、随机算法共同点是计算时间越多或运行次数越多 ,正确性越高.答案:A5意小。答案:A6、在下列算法中有时找不到问题解的是A:蒙特卡罗算法B:拉斯维加斯算法C:舍伍德算法D:数值随机算法答案:拉斯维加斯算法7、肯定获得可行解，但不一定是正确解的算法是A:蒙特卡罗算法B:拉斯维加斯算法C:舍伍德算法D:数值随机算法答案:A8、在一般输入数据的程序里，输入多少会影响到算法的计算复杂度，为了消除这种影响可用( )对输入进行预处理。A:蒙特卡罗算法 BC:舍伍德算法D:数值随机化算法答案:C9A:分支限界BD:动态规划算法