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

答案：错答案：对答案：对答案：错5、算法与程序的区别是()B:输出C:确定性D:有穷性A:如果一个算法能应用于问题的任意实例，并保证得到正确解D:算法是一个过程，计算机每次求解是针对问题的一个实例求A:最大团10、给定两张喜欢列表，稳定匹配问题的输出是()。C:最大匹配11、问题变换的目的有()。(1)复杂变隐式变显式(4)难解变易解(5)以上都是。12、按照霍纳法则，计算p(x)=anxn+3、如果对于X的任意实例，通过多项式次的计算步骤，加多项式次调用Y的算法，可解决X,则X可多项式时间归约到Y。5、下面关于NP问题说法正确的是()B:P类问题包含在NP类问题中6、P类问题可以()。A:多项式时间计算7、下面属于NP完全问题的是()D:旅行商问题A:IfX多项式时间归约到YandY多项式时间归约到Z,thenX多项式时间归约到Z.5、从资源划分，算法的复杂度分为()和()。A:时间复杂度空间复杂度B:空间复杂度平均复杂度C:最好复杂度最坏复杂度D:时间复杂度平均复杂度答案：时间复杂度空间复杂度6、算法复杂度分析的两种基本方法为()和()。A:结构化方法面向对象方法B:事后统计事前分析C:几何复杂度平均复杂度D:平摊复杂度平滑复杂度答案：事后统计事前分析第三章1、0-1背包问题的枚举算法的时间复杂度为0(2n)3、分块查找一般设分块的长度是n/2.C:二进制法6、从所有候选答案中去搜索正确的解，这是()算法。A:蛮力B:枚举C:递推行，1年可以计算的问题规模估计是?C:优化数据结构10、下面那些算法的时间复杂度为0()?D:冒泡排序2、贪心选择通过一步步选择得到问题的解3、问题的最优子结构性质是该问题可用贪心4、如果图G中每条边的权重都是互不相同的，图G必定只有一6、贪心算法基本要素有()和最优子结构性质。A:分解合并性质B:独立子问题性质A:领先B:优化C:交换论证第五章B:正推C:倒推D:迭代A:差消迭代C:直接迭代A:边界条件B:递归方程C:迭代D:输入B:递推C:尾递归D:循环D:迭代问题10、主方法可以求解满足T(n)=aT(n/b)+f(n)形式的递推方B:对于系数b,必须满足b>1C:若对于常数ε>0,f(n)=0(y),则T(n)=Θ(x)般为2)5、设有5000个无序的元素，希望用最快的速度挑选出其中前10个最大的元素，最好选用()法。B:快速排序6、堆排序的时间复杂度是0()。7、以下不可以使用分治法求解的是()。8、改进分治算法的方法有()和改进划分的对称性。A:减少子问题数B:备忘录C:拟阵原理A:分解B:解决C:合并D:选择1、动态规划算法把原问题分为交叉的子问题2、0/1背包问题的动态规划算法是多项式时间算3、对于稀疏图，Floyd算法的效率要高于执行n次DijksA:动态规划B:贪心算法C:分治算法6、动态规划算法的基本要素有()和最优子结构性质。A:多重选择B:增加变量3、回溯法的一个显著特征是在搜索过程中动态产生问题的解空2、分支限界法找出满足约束条件的一个解，或是在满足约束条4、优先队列式分支限界法按照队列先进先出的原则，选取下一5、下列算法中不能解决0/1背包问题的是B:动态规划C:回溯法B:排列树A:先进先出B:后进先出C:结点的优先级D:随机C:对扩展结点的扩展方式不同D:存储空间的要求不同B:分支限界C:动态规划D:贪心算法3、存在割(A,B)使流值v(f)=割的容量cap(A,B).,则割4、给定连通图G,BFS遍历得到层次图，边相连，则G是二分图。7、如果每条边的最大容量为1,则时间复杂度是0(nm)的网络流A:FF算法B:容量缩放算法A:最大独立数9、改进FF网络流算法，可以通过选择()增广路，降低时间复A:最大容量D:边数最少10、带需求的流通必须满足供给和=需求和3、借助随机预处理技术，不改变原有的确定性算法，仅对其输4、随机算法共同点是计算时间越多或运行次数越多，正确性越高.B:拉斯维加斯算法C:舍伍德算法B:拉斯维加斯算法8、在一般输入数据的程序里，输入多少会影响到算法的计算复杂度，为了消除这种影响可用()对输入进行预处理。B:拉斯维加斯算法9、()肯定获得最优解。B:贪心算法C:随机算法1、给定问题p,若有算法A,存在一个常数K>=0,使得问题4、绝大多数NP-hard问题存在多项式时间绝对近似算法5、若P不等于NP,则最大独立集问题存在多项式时间绝6、最大优化问题的近似性能比小于1,越接近1越说明算法好7、多项式时间近似方案的近似性能比是1+q,q>0.8、多项式时间近似方案的时间复杂度是P(n,1/q),