1算法解析总结计划复习计划题目

1、1、算法剖析复习题目及答案一。选择题1、二分搜寻算法是利用（A）实现的算法。A、分治策略B、动向规划法C、贪婪法D、回溯法2、以下不是动向规划算法基本步骤的是（A）。A、找出最优解的性质B、结构最优解C、算出最优解D、定义最优解3、最大效益优先是（A）的一搜寻方式。A、分支界线法B、动向规划法C、贪婪法D、回溯法4、在以下算法中有时找不到问题解的是（B）。A、蒙特卡罗算法B、拉斯维加斯算法C、舍伍德算法D、数值概率算法5.回溯法解旅游售货员问题时的解空间树是（B）。A、子集树B、摆列树C、深度优先生成树D、广度优先生成树6以下算法中往常以自底向上的方式求解最优解的是（B）。A、备忘录法B、动向

2、规划法C、贪婪法D、回溯法7、权衡一个算法利害的标准是（C）。A运转速度快B占用空间少C时间复杂度低D代码短8、以下不可以够使用分治法求解的是（D）。A棋盘覆盖问题B选择问题C合并排序D0/1背包问题9.实现循环赛日程表利用的算法是（A）。A、分治策略B、动向规划法C、贪婪法D、回溯法10、以下随机算法中运转时有时成功有时失败的是（C）A数值概率算法B舍伍德算法C拉斯维加斯算法D蒙特卡罗算法11下边不是分支界线法搜寻方式的是（D）。A、广度优先B、最小耗资优先C、最大效益优先D、深度优先12以下算法中往常以深度优先方式系统搜寻问题解的是（D）。A、备忘录法B、动向规划法C、贪婪法D、回溯法13

3、.备忘录方法是那种算法的变形。（B）A、分治法B、动向规划法C、贪婪法14哈弗曼编码的贪婪算法所需的计算时间为（BA、O（n2n）B、O（nlogn）C、O（2n）15分支限界法解最大团问题时，活结点表的组织形式是（A、最小堆B、最大堆C、栈16最长公共子序列算法利用的算法是（BA、分支界线法B、动向规划法C、贪婪法17实现棋盘覆盖算法利用的算法是（AA、分治法B、动向规划法C、贪婪法18.下边是贪婪算法的基本因素的是（CA、重叠子问题B、结构最优解C、贪婪选择性质19.回溯法的效率不依靠于以下哪些因素（D）D、回溯法）。D、O（n）B）。D、数组）。D、回溯法）。D、回溯法）。D、定义最优解

4、A.知足显拘束的值的个数B.计算拘束函数的时间C.计算限界函数的时间D.确立解空间的时间20.下边哪一种函数是回溯法中为防止无效搜寻采纳的策略（B）A递归函数B.剪枝函数C。随机数函数D.搜寻函数21、下边对于NP问题说法正确的选项是（B）NP问题都是不行能解决的问题P类问题包括在NP类问题中NP完整问题是P类问题的子集NP类问题包括在P类问题中22、蒙特卡罗算法是（B）的一种。A、分支界线算法B、概率算法C、贪婪算法D、回溯算法23.以下哪一种算法不是随机化算法（C）蒙特卡罗算法B.拉斯维加斯算法C.动向规划算法D.舍伍德算法24.（D）是贪婪算法与动向规划算法的共同点。A、重叠子问题B、结

5、构最优解C、贪婪选择性质D、最优子结构性质25.矩阵连乘问题的算法可由（B）设计实现。A、分支界线算法B、动向规划算法C、贪婪算法D、回溯算法分支限界法解旅游售货员问题时，活结点表的组织形式是（A）。A、最小堆B、最大堆C、栈D、数组27、Strassen矩阵乘法是利用（A）实现的算法。A、分治策略B、动向规划法C、贪婪法D、回溯法29、使用分治法求解不需要知足的条件是（A）。子问题一定是同样的子问题不可以够重复子问题的解能够合并原问题和子问题使用同样的方法解30、下边问题（B）不可以使用贪婪法解决。A单源最短路径问题BN皇后问题C最小花销生成树问题D背包问题31、以下算法中不可以解决0/1背

6、包问题的是（A）A贪婪法B动向规划C回溯法D分支限界法33、以下随机算法中运转时有时成功有时失败的是（C）A数值概率算法B舍伍德算法C拉斯维加斯算法D蒙特卡罗算法34实现合并排序利用的算法是（A）。A、分治策略B、动向规划法C、贪婪法D、回溯法35以下是动向规划算法基本因素的是（D）。A、定义最优解B、结构最优解C、算出最优解D、子问题重叠性质37采纳广度优先策略搜寻的算法是（A）。A、分支界线法B、动向规划法C、贪婪法D、回溯法38、合并排序算法是利用（A）实现的算法。A、分治策略B、动向规划法C、贪婪法D、回溯法39、在以下算法中获得的解未必正确的选项是（B）。A、蒙特卡罗算法B、拉斯维加

7、斯算法C、舍伍德算法D、数值概率算法40、背包问题的贪婪算法所需的计算时间为（B）A、O（n2n）B、O（nlogn）C、O（2n）D、O（n）41实现大整数的乘法是利用的算法（C）。A、贪婪法B、动向规划法C、分治策略D、回溯法420-1背包问题的回溯算法所需的计算时间为（A）A、O（n2n）B、O（nlogn）C、O（2n）D、O（n）43采纳最大效益优先搜寻方式的算法是（A）。A、分支界线法B、动向规划法C、贪婪法D、回溯法44贪婪算法与动向规划算法的主要差别是（B）。A、最优子结构B、贪婪选择性质C、结构最优解D、定义最优解45.实现最大子段和利用的算法是（B）。A、分治策略B、动向规

8、划法C、贪婪法D、回溯法46.优先行列式分支限界法选用扩展结点的原则是（C）。A、先进先出B、后进先出C、结点的优先级D、随机47.背包问题的贪婪算法所需的计算时间为（B）。A、O（n2n）B、O（nlogn）C、O（2n）D、O（n）48、广度优先是（A）的一搜寻方式。A、分支界线法B、动向规划法C、贪婪法D、回溯法49、舍伍德算法是（B）的一种。A、分支界线算法B、概率算法C、贪婪算法D、回溯算法50、在以下算法中有时找不到问题解的是（B）。A、蒙特卡罗算法B、拉斯维加斯算法C、舍伍德算法D、数值概率算法51以下哪一种算法是随机化算法（D）贪婪算法B.回溯法C.动向规划算法D.舍伍德算法一

9、个问题可用动向规划算法或贪婪算法求解的重点特点是问题的（B）。A、重叠子问题B、最优子结构性质C、贪婪选择性质D、定义最优解53采纳贪婪算法的最优装载问题的主要计算量在于将集装箱依其重量从小到大排序，故算法的时间复杂度为(B)。A、O（n2n）B、O（nlogn）C、O（2n）D、O（n）以深度优先方式系统搜寻问题解的算法称为(D)。A、分支界线算法B、概率算法C、贪婪算法D、回溯算法55.实现最长公共子序列利用的算法是（A、分治策略B、动向规划法BC、贪婪法）。D、回溯法二、填空题1.算法的复杂性有时间复杂性和空间复杂性之分。2、程序是算法用某种程序设计语言的详细实现。3、算法的“确立性”指

10、的是构成算法的每条指令是清楚的，无歧义的。4.矩阵连乘问题的算法可由动向规划设计实现。5、拉斯维加斯算法找到的解必定是正确解。6、算法是指解决问题的一种方法或一个过程。7、从分治法的一般设计模式能够看出，用它设计出的程序一般是递归算法。8、问题的最优子结构性质是该问题可用动向规划算法或贪婪算法求解的重点特点。9、以深度优先方式系统搜寻问题解的算法称为回溯法。10、数值概率算法常用于数值问题的求解。11、计算一个算法时间复杂度往常能够计算循环次数、基本操作的频次或计算步。12、利用概率的性质计算近似值的随机算法是_数值概率算法，运转时以必定的概率获得正确解的随机算法是_蒙特卡罗算法_。14、解决

11、0/1背包问题能够使用动向规划、回溯法和分支限界法，此中不需要排序的是动向规划，需要排序的是回溯法，分支限界法。15、使用回溯法进行状态空间树裁剪分支时一般有两个标准：拘束条件和目标函数的界，N皇后问题和0/1背包问题正好是两种不一样的种类，此中同时使用拘束条件和目标函数的界进行裁剪的是0/1背包问题，只使用拘束条件进行裁剪的是N皇后问题。16、贪婪选择性质是贪婪算法可行的第一个基本因素，也是贪婪算法与动向规划算法的主要差别。17、矩阵连乘问题的算法可由动向规划设计实现。18、拉斯维加斯算法找到的解必定是正确解。19.贪婪算法的基本因素是贪婪选择质和最优子结构性质。21.动向规划算法的基本思想

12、是将待求解问题分解成若干子问题，先求解子问题，而后从这些子问题的解获得原问题的解。22.算法是由若干条指令构成的有穷序列，且要知足输入、输出、确立性和有限性四条性质。23、大整数乘积算法是用分治法来设计的。24、以广度优先或以最小耗资方式搜寻问题解的算法称为分支限界法。25、舍伍德算法总能求得问题的一个解。26、贪婪选择性质是贪婪算法可行的第一个基本因素，也是贪婪算法与动向规划算法的主要差别。27.迅速排序算法是鉴于分治策略的一种排序算法。28.动向规划算法的两个基本因素是.最优子结构性质和重叠子问题性质。30.回溯法是一种既带有系统性又带有跳跃性的搜寻算法。31.分支限界法主要有行列式（FI

13、FO）分支限界法和优先行列式分支限界法。32分支限界法是一种既带有系统性又带有跳跃性的搜寻算法。33回溯法搜寻解空间树时，常用的两种剪枝函数为拘束函数和限界函数。34.任何可用计算机求解的问题所需的时间都与其规模相关。35.迅速排序算法的性能取决于区分的对称性。三、算法填空背包问题的贪婪算法voidKnapsack(intn,floatM,floatv,floatw,floatx)Sort(n,v,w);inti;for(i=1;i=n;i+)xi=0;floatc=M;for(i=1;ic)break;xi=1;c-=wi;if(i0)b+=aj；jsum)sum=b;returnsum；贪

14、婪算法求装载问题templatevoidLoading(intx,Typew,Typec,intn)int*t=newintn+1;Sort(w,t,n);for(inti=1;i=n;i+)xi=0;for(inti=1;i=n&wti=c;i+)xti=1;C-=wti;贪婪算法求活动安排问题templatevoidGreedySelector(intn,Types,Typef,boolA)A1=true;intj=1;for(inti=2;i=fj)Ai=true;j=i;elseAi=false;5.迅速排序templatevoidQuickSort(Typea,intp,intr)i

15、f(pr)intq=Partition(a,p,r);QuickSort(a,p,q-1);/对左半段排序QuickSort(a,q+1,r);/对右半段排序摆列问题Templatevoidperm(Typelist,intk,intm)/产生listk:m的全部摆列if(k=m)/只剩下一个元素for(inti=0;i=m;i+)coutlisti;coutendl;else/还有多个元素待摆列，递归产生摆列for(inti=k;in)output(x);elsefor(inti=f(n,t);i=g(n,t);i+)xt=h(i);if(constraint(t)&bound(t)back

16、track(t+1);分治法所能解决的问题一般拥有的几个特点是：1）该问题的规模减小到必定的程度就能够简单地解决；2）该问题能够分解为若干个规模较小的同样问题，即该问题拥有最优子结构性质;3）利用该问题分解出的子问题的解能够合并为该问题的解；4）原问题所分解出的各个子问题是相互独立的，即子问题之间不包括公共的子问题。用分支限界法设计算法的步骤是：(1)针对所给问题，定义问题的解空间（对解进行编码）；分(2)确立易于搜寻的解空间结构（按树或图组织解）；(3)以广度优先或以最小耗资（最大利润）优先的方式搜寻解空间，并在搜寻过程顶用剪枝函数防止无效搜寻。8.常有的两种分支限界法的算法框架（1）行列式

17、(FIFO)分支限界法：依据行列先进先出（FIFO）原则选用下一个节点为扩展节点。2）优先行列式分支限界法：依据优先行列中规定的优先级选用优先级最高的节点成为目前扩展节点。回溯法中常有的两类典型的解空间树是子集树和摆列树。当所给的问题是从n个元素的会合S中找出知足某种性质的子集时，相应的解空间树称为子集树。这种子集树往常有2n个叶结点，遍历子集树需O(2n)计算时间。当所给的问题是确立n个元素知足某种性质的摆列时，相应的解空间树称为摆列树。这种摆列树往常有n!个叶结点。遍历摆列树需要O(n!)计算时间。分支限界法的搜寻策略是：在扩展结点处，先生成其全部的儿子结点（分支），而后再从目前的活结点表

18、中选择下一个扩展结点。为了有效地选择下一扩展结点，加快搜寻的进度，在每一个活结点处，计算一个函数值（限界），并依据函数值，从目前活结点表中选择一个最有益的结点作为扩展结点，使搜寻朝着解空间上有最优解的分支推动，以便赶快地找出一个最优解。五、算法题给定已按升序排好序的n个元素a0:n-1，现要在这n个元素中找出一特定元素x，返回其在数组中的地点，假如未找到返回-1。写出二分搜寻的算法，并剖析其时间复杂度。1.templateintBinarySearch(Typea,constType&x,intn)/在a0:n中搜寻x，找到x时返回其在数组中的地点，不然返回-1Intleft=0;intright=n-1;While(leftamiddle)left=middle+1;elseright=middle-1;Return-1;时间复杂性为O(logn)利用分治算法写出合并排序的算法，并剖析其时间复杂度voidMergeSort(Typea,intleft,intright)if(leftright)/起码有2个元素inti=(left+right)/2;/取中点mergeSort(a,left,i);mergeSort(a,i+1,ri