算法设计与分析复习题目及答案

分治法1、二分搜索算法是利用(分割策略)实现的算法。9 .实现循环比赛时间表利用的算法是(分治战略)27、Strassen矩阵乘法是利用(分割战略)实现的算法。34 .实现综合排序利用的算法是(分割策略)。实现大整数的乘法是利用的算法(分割策略)。17 .实现盘盖算法利用的算法是(分治法)。29 .运用分治法解决不应满足的条件(子问题必须相同)。不能用分治法解决的是(0/1背包问题)。动态规划以下不是动态规划算法的基本步骤(构筑最佳解)动态规划算法的基本要素包括(子问题的重叠性质) :用以下算法一般用自下而上方式解最优解的是(动态规划法)备忘录方法是其算法的变形。 (动态规划法)最长的公共子序列算法所利用的算法是(动态规划法)。矩阵协方问题的算法可由(动态规划算法b )设计实现。实现最大的子段和利用的算法是(动态规划法)。贪婪法可解决的问题：单源最短路径问题、最小成本生成树问题、背包问题、活动安排问题无法解决的问题： n皇后问题，0/1背包问题贪婪算法的基本要素是(贪婪选择性性质和最佳子结构性质)。回溯法用回溯法解决旅行店员问题时的解空间树是(排列树)。剪枝函数是回溯法避免无效搜索的策略回溯法的效率不依赖于以下哪个因素(决定解空间的时间)。分支边界法最大利益优先是(分歧边界法)的探索方式。分支界限法解最大集团问题时，活节点表的组织形式为(最大堆)。用分支界限法解决旅行销售员的问题时，活节点表的组织形式是(最小堆)优先队列式分歧边界法选择扩展节点的原则是(节点的优先度)在检索问题的解空间树的方法中，有一个活节点最大变成一次活节点的机会的是(分支界限法)从活动节点表中选择下一个扩展节点的方案引起不同的分支边界方法，其是除了堆栈分支边界方法之外的最常见的方案(1)队列式(FIFO )分支边界法：按照队列先进先出(FIFO )的原则，选择下一个节点作为扩展节点。(2)优先队列式分歧边界法：按照优先队列中规定的优先度，选择优先度最高的节点作为当前的扩展节点。(最佳子结构的性质)贪婪算法和动态规划算法的共同点。贪婪算法和动态规划算法的主要区别在于(贪婪选择的性质)。回溯算法和分歧边界法问题的解空间树不是(无序树)14 .霍夫曼编码的贪婪算法所需要的计算时间为(b )。a，O(n2n)B，O(nlogn)C，O(2n)D，O(n )21、以下关于NP问题正确的是(b )A NP问题都是不能解决的问题B P类问题包括在NP类问题中C NP完全问题是p类问题的子集D NP类问题包括在p类问题中40、背包问题的贪婪算法所需的计算时间为(b )a，O(n2n) B，O(nlogn) C，O(2n) D，O(n )42.0-1背包问题的回溯算法所需要的计算时间为(a )。a，O(n2n)B，O(nlogn)C，O(2n)D，O(n ).47 .背包问题的贪婪算法所需的计算时间为(b )。a，O(n2n)B，O(nlogn)C，O(2n)D，O(n )53 .采用贪婪算法的最优装载问题的主要计算量是按容器重量由小到大的顺序排序，算法的时间复杂度是(b )。a，O(n2n)B，O(nlogn)C，O(2n)D，O(n )56、该算法是由若干指令组成的穷序列，并且满足以下性质(d ) :(1)输入：有0个以上的输入(2)输出：至少有一个输出(3)确定性：命令明确，无歧义(4)有限性：指令的执行次数有限，而且执行时间有限a (1)、(2)、(3) b (1)、(2)、(4) c (1)、(3)、(4) d (1)、(2)、(3)、(4)57、函数32n 10nlogn的渐进式为(b )A. 2n B. 32n C. nlogn D. 10nlogn59 .动态规划算法解决最大字段和问题，其时间复杂度为(b )A.logn B.n C.n2 D.nlogn61、将f(N )、g(N )设为正数的集合中定义的正函数，若在nN0时以成为f(N )CG (n )的方式存在正常数c和自然数N0，则函数f(N )在n足够大时记作有下限g(N )f(N)(g(N ) )是f(N )层(A )g(N )的层.等于a.b.c.d .近似二、填空问题2、程序是用有算法的程序设计语言的具体实现。3、算法的“确定性”意味着构成算法的所有指令都是明确的，没有模糊性。6、算法是解决问题的一种方法或过程。7 .从分治法的一般设计模式可以看出，用它设计的程序一般是递归算法。11 .计算算法的时间复杂度通常可计算循环数目、基本操作的频率或计算步骤。为了解决14，0/1背包问题，可以使用动态规划、背景法和分支极限法，其中不需要排序的是动态规划，需要排序的是背景法、分支极限法。15 .采用回溯法进行状态空间树的修剪分支时，一般有两个标准：约束条件与目标函数的边界，n皇后问题与0/1背包问题是不同类型，其中同时使用约束条件与目标函数的边界进行修剪是0/1背包问题，只使用约束条件进行修剪30 .回溯法是一种系统的、跳跃的搜索算法。33 .用回溯法搜索解空间树时，常用的两个剪枝函数是约束函数和极限函数。34 .计算机能解的问题所需时间与其规模有关。35 .快速排序算法的性能取决于划分对称性。36. Prim算法利用贪婪策略解最小生成树问题，其时间复杂度为O(n2)。37 .图的m着色问题可以用回溯法解决，其解空间树的叶节点数为mn，解空间树的每个内节点的孩子数为m。4 .对于序列X=B，c，a，d，b，c，D，Y=A，c，b，a，b，d，c，D，指定序列x和y的最长公共子序列abcd或CABCD或CADCD。5 .当用回溯法求解问题时，应当清楚地定义问题的解空间并在问题的解空间中包含至少一个(最佳)解8.0-1背包问题的回溯算法所需的计算时间为_o(n*2n)_，动态规划算法所需的计算时间为_o(minnc，2n_ )。二、综合问题(50分)1 .编写设计动态规划算法的主要步骤。问题具有最佳子结构的性质构筑最佳值的递归关系式的3最佳值的算法记述结构最佳解2 .流水作业安排问题的约翰逊算法思想。N1=i|ai=bi； 在n-1中作业按照ai的非降序为n-1，在n-2中作业按照bi的非升序为n-2，在n-1中作业按照n-2作业是满足约翰逊法则的最佳时间表。3 .在n=4的情况下，机器M1和M2加工作业I所需的时间分别是ai和bi，(a1、a2、a3、a4)=(4、5、12、10 )、(b1、b2、b3、b4)=(8、2、15、9 )求出四个作业的最佳调度方案，并计算最佳值。步骤为n1= 1，3 、n2= 2，4 ；n 1= 1，3 ，n 2= 4，2 ；最佳值为384 .用回溯法求解0/1背包问题： n=3，C=9，v= 6，10，3 ，w= 3，4，4 ，其解空间由长度为3的0-1向量构成，其解空间用一根完全二叉树表示(从根出发，从左向右0 )，画出其解空间树，其最佳值和最佳值解空间为 (0，0，0 )，(0，1，0 )，(0，0，1 )，(1，0，0 )，(0，1，1 )，(1，0，1 ) (1，1，0 )、(1，1，1 ) 。解空间树如下所示a.a乙组联赛c.cf.fed.dgK日本职业足球联赛Iho.onml11100001011010这个问题的最佳值是： 16最佳解： (1，1，0 )S=X1，X2，Xn作为严格增加的规则集，在二叉树的节点中存储s中的要素，在表示s的二叉搜索树中搜索一个要素x的结果，(1)有时在二叉搜索树的内部节点中发现X=Xi，将其概率设为bi。 (2)在二叉搜索树的叶节点上决定X(Xi，Xi 1)，将其概率作为ai。 在表示s二叉搜索树t中，将收纳要素Xi的节点深度设为Ci，将叶节点(Xi，Xi 1)的节点深度设为di，则二叉搜索树t的平均路长p为多少，将二叉搜索树Tij=Xi，Xi 1，Xj的最佳值设为mij，w I j =ai-1 bi二叉树t平均路长P=m I j =w I j min m I k m k1 j (1=I=j=n，mii-1=0)mij=0 (ij )6.0-1说明背包的问题。背包的容量有c，n个物品，物品I的重量为Wi，价值为Vi，要求如何选择装在背包里的物品，使装在背包里的物品的总价值最大化。三、简要解答(30分钟)1 .在流水作业计划中，已知n个作业，机器M1和M2加工作业I所需的时间分别为ai和bi，请根据流水作业计划问题的johnson法则编写ai和bi的排序算法。 (函数名称可以写成sort(s，n ) )2 .最优二叉搜索树问题的动态规划算法(设函数名为binarysearchtree )。1.void sort(flowjope s，int n )装模作样int i、k、j、l；for(i=1； i=n-1； i )/-选择排序装模作样k=i；while(k=nsk.tag！=0) k；if(kn)