太原理工大学软件学院算法设计与分析复习题目及

太原理工大学软件学院算法设计与解析复习题目及太原理工大学软件学院算法设计与解析复习题目及太原理工大学软件学院算法设计与解析复习题目及一、选择题1、二分找寻算法是利用（

A）实现的算法。A、分治策略

B、动向规划法

C、贪婪法

D、回溯法2、以下不是动向规划算法基本步骤的是（A）。A、找出最优解的性质B、构造最优解C、算出最优解D、定义最优解3、最大效益优先是（A）的找寻方式。A、分支界限法B、动向规划法C、贪婪法D、回溯法回溯法解旅行售货员问题时的解空间树是（B）。A、子集树B、摆列树C、深度优先生成树D、广度优先生成树5．以下算法中平时以自底向上的方式求解最优解的是（B）。A、备忘录法B、动向规划法C、贪婪法D、回溯法6、衡量一个算法利害的标准是（C）。A运转速度快B占用空间少C时间复杂度低D代码短7、以下不行以使用分治法求解的是（D）。A棋盘覆盖问题B选择问题C归并排序D0/1背包问题8.实现循环赛日程表利用的算法是（A）。A、分治策略

B、动向规划法

C、贪婪法

D、回溯法9．下边不是分支界限法找寻方式的是（

D）。A、广度优先

B、最小耗费优先

C、最大效益优先

D、深度优先10．以下算法中平时以深度优先方式系统找寻问题解的是（D）。A、备忘录法B、动向规划法C、贪婪法D、回溯法备忘录方法是那种算法的变形。（B）A、分治法B、动向规划法C、贪婪法D、回溯法12．最长公共子序列算法利用的算法是（B）。A、分支界限法B、动向规划法C、贪婪法D、回溯法13．实现棋盘覆盖算法利用的算法是（A）。A、分治法B、动向规划法C、贪婪法D、回溯法14.下边是贪婪算法的基本因素的是（C）。A、重叠子问题B、构造最优解C、贪婪选择性质D、定义最优解15.回溯法的效率不依赖于以下哪些因素（D）A.满足显拘束的值的个数B.计算拘束函数的时间C.计算限界函数的时间D.确立解空间的时间16.下边哪一种函数是回溯法中为防备无效找寻采纳的策略（B）A．递归函数B.剪枝函数C.随机数函数D.找寻函数（D）是贪婪算法与动向规划算法的共同点。A、重叠子问题B、构造最优解C、贪婪选择性质D、最优子构造性质18.矩阵连乘问题的算法可由（B）设计实现。A、分支界限算法B、动向规划算法C、贪婪算法D、回溯算法19.分支限界法解旅行售货员问题时，活结点表的组织形式是（A）。A、最小堆

B、最大堆

C、栈

D、数组20、Strassen矩阵乘法是利用（A）实现的算法。A、分治策略B、动向规划法C、贪婪法21、使用分治法求解不需要满足的条件是（A）。

D、回溯法子问题一定是相同的子问题不行以重复子问题的解可以归并原问题和子问题使用相同的方法解22、下边问题（B）不可以使用贪婪法解决。A单源最短路径问题

BN皇后问题C最小花销生成树问题

D背包问题23、以下算法中不可以解决0/1背包问题的是（A）A贪婪法B动向规划C回溯法D分支限界法24、回溯法找寻状态空间树是依照（C）的序次。A中序遍历B广度优先遍历C深度优先遍历D层次优先遍历25．实现归并排序利用的算法是（A）。A、分治策略B、动向规划法C、贪婪法D、回溯法26．以下是动向规划算法基本因素的是（D）。A、定义最优解B、构造最优解C、算出最优解D、子问题重叠性质27．以下算法中平时以自底向下的方式求解最优解的是（B）。A、分治法B、动向规划法C、贪婪法D、回溯法28．采纳广度优先策略找寻的算法是（A）。A、分支界限法B、动向规划法C、贪婪法D、回溯法29、归并排序算法是利用（A）实现的算法。A、分治策略

B、动向规划法

C、贪婪法

D、回溯法30、背包问题的贪婪算法所需的计算时间为（

B）A、O（n2n）

B、O（nlogn）

C、O（2n）

D、O（n）31．实现大整数的乘法是利用的算法（C）。A、贪婪法

B、动向规划法

C、分治策略

D、回溯法32．0-1

背包问题的回溯算法所需的计算时间为（

A）A、O（n2n）

B、O（nlogn）

C、O（2n）

D、O（n）33．采纳最大效益优先找寻方式的算法是（A）。A、分支界限法B、动向规划法C、贪婪法D、回溯法34．贪婪算法与动向规划算法的主要差别是（B）。A、最优子构造B、贪婪选择性质C、构造最优解D、定义最优解35.优先队列式分支限界法采纳扩展结点的原则是（C）。A、先进先出

B、后进先出

C、结点的优先级

D、随机36.背包问题的贪婪算法所需的计算时间为（

B）。A、O（n2n）B、O（nlogn）

C、O（2n）

D、O（n）37、广度优先是（A）的找寻方式。A、分支界限法B、动向规划法C、贪婪法D、回溯法38.一个问题可用动向规划算法或贪婪算法求解的要点特色是问题的（B）。A、重叠子问题B、最优子构造性质C、贪婪选择性质D、定义最优解39．采纳贪婪算法的最优装载问题的主要计算量在于将集装箱依其重量从小到大排序，故算法的时间复杂度为(B)。A、O（n2n）B、O（nlogn）C、O（2n）D、O（n）以深度优先方式系统找寻问题解的算法称为(D)。A、分支界限算法B、概率算法C、贪婪算法D、回溯算法41.实现最长公共子序列利用的算法是（B）。A、分治策略B、动向规划法C、贪婪法D、回溯法42、算法是由若干条指令构成的有穷序列，并且满足以下性质（D）1）输入：有0个或多个输入2）输出：最少有一个输出3）确立性：指令清楚，无歧义4）有限性：指令执行次数有限，并且执行时间有限A(1)(2)(3)B(1)(2)(4)C(1)(3)(4)D(1)(2)(3)(4)43、函数32n+10nlogn的渐进表达式是(B).A.2nB.32nC.nlognD.10nlogn44、大整数乘法算法是(A).算法A.分治B.贪婪C.动向规划D.穷举45、解决活动安排问题，最好用（B）算法A.分治B.贪婪C.动向规划D.穷举46、设f(N),g(N)是定义在正数集上的正函数,假如存在正的常数C和自然数N0,使合适N≥N0时有f(N)≤则称函数f(N)当N充分大时有下界g(N),记作Cg(N),f(N)∈○(g(N)),即f(N)的阶(A)g(N)的阶.A.不高于B.不低于C.等价于D.迫近47、回溯法在解空间树T上的找寻方式是(A).A.深度优先B.广度优先C.最小耗费优先D.活结点优先48、回溯算法和分支限界法的问题的解空间树不会是(D).A.有序树B.子集树C.摆列树D.无序树49、在对问题的解空间树进行找寻的方法中,一个活结点最多有一次机遇成为活结点的是(B).A.回溯法B.分支限界法C.回溯法和分支限界法D.回溯法求解子集树问题50、从活结点表中选择下一个扩展结点的不一样方式将以致不一样的分支限界法,以下除(C)以外都是最常有的方式.A.队列式分支限界法B.优先队列式分支限界法C.栈式分支限界法D.FIFO分支限界法二、填空题1.算法的复杂性有时间复杂性和空间复杂性之分。2、程序是算法用某种程序设计语言的详尽实现。3、算法的“确立性”指的是构成算法的每条指令是清楚的，无歧义的。4.矩阵连乘问题的算法可由动向规划设计实现。5、算法是指解决问题的一种方法或一个过程。6、从分治法的一般设计模式可以看出，用它设计出的程序一般是递归算法。7、问题的最优子构造性质是该问题可用动向规划算法或贪婪算法求解的要点特色。8、以深度优先方式系统找寻问题解的算法称为9、计算一个算法时间复杂度平时可以计算

回溯法循环次数

。、

基本操作的频率或计算步。10、解决0/1背包问题可以使用动向规划、回溯法和分支限界法，此中不需要排序的是动向规划，需要排序的是回溯法，分支限界法。11、使用回溯法进行状态空间树裁剪分支时一般有两个标准：拘束条件和目标函数的界，N皇后问题和0/1背包问题正好是两种不一样的种类，此中同时使用拘束条件和目标函数的界进行裁剪的是0/1背包问题，只使用拘束条件进行裁剪的是N皇后问题。12、贪婪选择性质是贪婪算法可行的第一个基本因素，也是贪婪算法与动向规划算法的主要差别。13、矩阵连乘问题的算法可由动向规划设计实现。14.贪婪算法的基本因素是贪婪选择性质和最优子构造性质。动向规划算法的基本思想是将待求解问题分解成若干子问题，先求解子问题，而后从这些子问题的解获取原问题的解。16.算法是由若干条指令构成的有穷序列，且要满足输入、输出、确立性和有限性四条性质。17、大整数乘积算法是用分治法来设计的。18、以广度优先或以最小耗费方式找寻问题解的算法称为分支限界法。19、贪婪选择性质是贪婪算法可行的第一个基本因素，也是贪婪算法与动向规划算法的主要差别。20.快速排序算法是基于分治策略的一种排序算法。动向规划算法的两个基本因素是最优子构造性质和重叠子问题性质。回溯法是一种既带有系统性又带有跳跃性的找寻算法。分支限界法主要有队列式（FIFO）分支限界法和优先队列式分支限界法。24．分支限界法是一种既带有系统性又带有跳跃性的找寻算法。25．回溯法找寻解空间树时，常用的两种剪枝函数为拘束函数和限界函数。26.任何可用计算机求解的问题所需的时间都与其规模有关。27.快速排序算法的性能取决于划分的对称性。28.Prim算法利用贪婪策略求解最小生成树问题，其时间复杂度是O(n2)。29.图的m着色问题可用回溯法求解，其解空间树中叶子结点个数是mn，解空间树中每个内结点的孩子数是m。三、算法的程序填空背包问题的贪婪算法voidKnapsack(intn,floatM,floatv[],floatw[],floatx[]){Sort(n,v,w);inti;for(i=1;i<=n;i++)x[i]=0;floatc=M;for(i=1;i<=n;i++){if(w[i]>c)break;x[i]=1;c-=w[i];}if(i<=n)x[i]=c/w[i];}最大子段和:动向规划算法intMaxSum(intn,inta[]){intsum=0,b=0；//sum储存当前最大的b[j],b储存b[j]for(intj=1；j<=n；j++){if(b>0)b+=a[j]；elseb=a[i];；//一旦某个区段和为负，则从下一个地址累和if(b>sum)sum=b;}returnsum；}快速排序template<classType>voidQuickSort(Typea[],intp,intr){if(p<r){intq=Partition(a,p,r);QuickSort(a,p,q-1);//

对左半段排序QuickSort(a,q+1,r);//

对右半段排序}}摆列问题Template<classType>voidperm(Typelist[],intk,intm){//产生[list[k:m]的全部摆列if(k==m){//只剩下一个元素for(inti=0;i<=m;i++)cout<<list[i];cout<<endl;}else//还有多个元素待摆列，递归产生摆列for(inti=k;i<=m;i++){swap(list[k]，list[i]);perm(list,k+1;m);swap(list[k],list[i]);}}给定已按升序排好序的n个元素a[0:n-1]，现要在这n个元素中找出一特定元素x。据此简单设计出二分找寻算法：template<classType>intBinarySearch(Typea[],constType&x,intl,intr){while(l<=r){intm=((l+r)/2);if(x==a[m])returnm;if(x<a[m])r=m-1;elsel=m+1;}return-1;}6、归并排序描述以下：template<classType>voidMergesort(Typea[],intleft,intright){if(left<right){inti=(left+right)/2;Mergesort(a,left,i);Mergesort(a,i+1,right);Merge(a,b,left,i,right

);//归并到数组

bCopy(a,b,left,right

);//复制到数组a}}7、分治法求最大、最小元template<classT>voidSortableList<T>::MaxMin(inti,intj,T&max,T&min)const{//前置条件：i和j，0≤i≤j＜表长，是表的下标范围的界Tmin1,max1;if(i==j)max=min=l[i];//表中只有一个元素时elseif(i==j-1)//表中有两个元素时if(l[i]<l[j]){max=l[j];min=l[i];}else{max=l[i];min=l[j];}else{//表中多于两个元素时intm=(i+j)/2;//对半切割MaxMin(i,m,max,min);//求前半部子表中的最大、最小元MaxMin(m+1,j,max1,min1)//求后半部子表中的最大、最小元if(max<max1)max=max1;//两子表最大元的大者为原表最大元if(min>min1)min=min1;//两子表最小元的小者为原表最小元}四、问答题1.用计算机求解问题的步骤：1、问题解析2、数学模型成立3、算法设计与选择4、算法指标5、算法解析6、算法实现7、程序调试8、结果整理文档编制算法定义：算法是指在解决问题时，依照某种机械步骤必定可以获取问题结果的办理过程3.算法的三因素（1）操作（2）控制构造（3）数据构造算法拥有以下5个属性：有穷性：一个算法一定总是在执行有穷步以后结束，且每一步都在有穷时间内完成。确立性：算法中每一条指令一定有确实的含义。不存在二义性。只有一个入口和一个出口可行性：一个算法是可行的就是算法描述的操作是可以经过已经实现的基本运算执行有限次来实现的。输入：一个算法有零个或多个输入，这些输入取自于某个特定对象的会集。输出：一个算法有一个或多个输出，这些输出同输入有着某些特定关系的量。算法设计的质量指标：正确性：算法应满足详尽问题的需求；可读性：算法应该好读，以有益于读者对程序的理解；强壮性：算法应拥有容错办理，当输入为非法数据时，算法对付其作出反应，而不是产生平白无故的输出结果。效率与储存量需求：效率指的是算法执行的时间；储存量需求指算法执行过程中所需要的最大储存空间。一般这二者与问题的规模有关。常常采纳的算法主要有迭代法、分治法、贪婪法、动向规划法、回溯法、分支限界法迭代法:也称“展转法”，是一种不停用变量的旧值递推出新值的解决问题的方法。利用迭代算法解决问题，需要做好以下三个方面的工作：、确立迭代模型。在可以用迭代算法解决的问题中，最少存在一个直接或间接地不停由旧值递推出新值的变量，这个变量就是迭代变量。、成立迭代关系式。所谓迭代关系式，指如何从变量的前一个值推出其下一个值的公式（或关系）。迭代关系式的成立是解决迭代问题的要点，平时可以使用递推或倒推的方法来完成。、对迭代过程进行控制。在什么时候结束迭代过程？这是编写迭代程序一定考虑的问题。不可以让迭代过程无休止地重复执行下去。迭代过程的控制平时可分为两种状况：一种是所需的迭代次数是个确立的值，可以计算出来；另一种是所需的迭代次数没法确立。关于前一种状况，可以成立一个固定次数的循环来实现对迭代过程的控制；关于后一种状况，需要进一步解析出用来结束迭代过程的条件。分治法的基本思想是：将一个规模为n的问题分解为k个规模较小的子问题，这些子问题相互独立且与原问题相同。递归地解这些子问题，而后将各个子问题的解归并获取原问题的解。9.分治法所能解决的问题一般拥有以下几个特色：1）该问题的规模减小到必定的程度就可以简单地解决；2）该问题可以分解为若干个规模较小的相同问题，即该问题拥有最优子构造性质；3）利用该问题分解出的子问题的解可以归并为该问题的解；4）该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。10、分治法的基本步骤分治法在每一层递归上都有三个步骤：1）分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题；2）解决：若子问题规模较小而简单被解决则直接解，不然递归地解各个子问题；3）归并：将各个子问题的解归并为原问题的解。动向规划的基本思想前文主要介绍了动向规划的一些理论依照，我们将前文所说的拥有明显的阶段划分和状态转移方程的动向规划称为标准动向规划，这种标准动向规划是在研究多阶段决策问题时推导出来的，拥有严格的数学形式，适适用于理论上的解析。在实质应用中，好多问题的阶段划分其实不明显，这时假如成心地域分阶段法反而麻烦。一般来说，只要该问题可以划分成规模更小的子问题，并且原问题的最优解中包含了子问题的最优解（即满足最优子化原理），则可以考虑用动向规划解决。动向规划的实质是分治思想和解决冗余，所以，动向规划是一种将问题实例分解为更小的、相似的子问题，并储存子问题的解而防备计算重复的子问题，以解决最优化问题的算法策略。由此可知，动向规划法与分治法和贪婪法近似，它们都是将问题实例归纳为更小的、相似的子问题，并经过求解子问题产生一个全局最优解。贪婪法的当前选择可能要依赖已经作出的全部选择，但不依赖于有待于做出的选择和子问题。所以贪婪法自顶向下，一步一步地作出贪婪选择；而分治法中的各个子问题是独立的（即不包含公共的子问题），所以一旦递归地求出各子问题的解后，即可自下而上地将子问题的解归并成问题的解。不足之处：假如当前选择可能要依赖子问题的解时，则难以经过局部的贪婪策略达到全局最优解；假如各子问题是不独立的，则分治法要做好多不用要的工作，重复地解公共的子问题。解决上述问题的方法是利用动向规划。该方法主要应用于最优化问题，这种问题会有多种可能的解，每个解都有一个值，而动向规划找出此中最优（最大或最小）值的解。若存在若干个取最优值的解的话，它只取此中的一个。在求解过程中，该方法也是经过求解局部子问题的解达到全局最优解，但与分治法和贪婪法不一样的是，动向规划同意这些子问题不独立，（亦即各子问题可包含公共的子问题）也同意其经过自己子问题的解作出选择，该方法对每一个子问题只解一次，并将结果保存起来，防备每次遇到时都要重复计算。所以，动向规划法所针对的问题有一个明显的特色，即它所对应的子问题树中的子问题表现大批的重复。动向规划法的要点就在于，关于重复出现的子问题，只在第一次遇到时加以求解，并把答案保存起来，让今后再遇到时直接引用，不用重新求解。12、动向规划算法的基本步骤设计一个标准的动向规划算法，平时可按以下几个步骤进行：1）划分阶段：依照问题的时间或空间特色，把问题分为若干个阶段。注意这若干个阶段必定假如有序的也许是可排序的（即无后向性），不然问题就没法用动向规划求解。2）选择状态：将问题发展到各个阶段时所处于的各种客观状况用不一样的状态表示出来。自然，状态的选摘要满足无后效性。3）确立决策并写出状态转移方程：之所以把这两步放在一起，是由于决讲和状态转移有着天然的联系，状态转移就是依据上一阶段的状态和决策来导出本阶段的状态。所以，假如我们确立了决策，状态转移方程也就写出来了。但事实上，我们常常是反过来做，依据相邻两段的各状态之间的关系来确立决策。4）写出规划方程（包含界限条件）：动向规划的基本方程是规划方程的通用形式化表达式。一般说来，只要阶段、状态、决讲和状态转移确立了，这一步还是比较简单的。动向规划的主要难点在于理论上的设计，一旦设计完成，实现部分就会特别简单。依据动向规划的基本方程可以直接递归计算最优值，但是一般将其改为递推计算。实质应用中间常常不显式地依照上边步骤设计动向规划，而是按以下几个步骤进行：1）解析最优解的性质，并刻划其构造特色。2）递归地定义最优值。3）以自底向上的方式或自顶向下的记忆化方法（备忘录法）计算出最优值。4）依据计算最优值时获取的信息，构造一个最优解。步骤（1）～（3）是动向规划算法的基本步骤。在只要要求出最优值的情况，步骤（4）可以省略，若需要求出问题的一个最优解，则一定执行步骤（4）。此时，在步骤（3）受骗算最优值时，平时需记录更多的信息，以便在步骤（4）中，依据所记录的信息，快速地构造出一个最优解。总结：动向规划实质上就是最优化的问题，是指将原问题的大实例等价于同一最优化问题的较小实例，自底向上的求解最小实例，并将所求解存放起来，存放的结果就是为了准备数据。与递归对比，递归是不停的调用子程序求解，是自顶向下的调用和求解。分治法与动向规划法的相同点是：将待求解的问题分解成若干个子问题，先求解子问题，而后从这些子问题的解获取原问题的解。二者的不一样点是：合适于用动向规划法求解的问题，经分解获取的子问题往往不是相互独立的。而用分治法求解的问题，经分解获取的子问题常常是相互独立的。回溯法回溯法也称为尝试法，该方法第一临时放弃关于问题规模大小的限制，并将问题的候选解按某种序次逐个列举和检验。当发现当前候选解不行能是解时，就选择下一个候选解；假如当前候选清除了还不满足问题规模要求外，满足全部其余要求时，连续扩大当前候选解的规模，并连续尝试。假如当前候选解满足包含问题规模在内的全部要求时，该候选解就是问题的一个解。在回溯法中，放弃当前候选解，找寻下一个候选解的过程称为回溯。扩大当前候选解的规模，以连续尝试的过程称为向前尝试。分支限界法：这是一种用于求解组合优化问题的消除非解的找寻算法。近似于回溯法，分枝定界法在找寻解空间时，也常常使用树形构造来组织解空间。但是与回溯法不一样的是，回溯算法使用深度优先方法找寻树构造，而分枝定界一般用宽度优先或最小耗费方法来找寻这些树。所以，可以很简单比较回溯法与分枝定界法的异同。相对而言，分枝定界算法的解空间比回溯法大得多，所以当内存容量有限时，回溯法成功的可能性更大。算法思想：分枝限界（branchandbound）是另一种系统地找寻解空间的方法，它与回溯法的主要差别在于对E-节点的扩大方式。每个活节点有且仅有一次机遇变为E-节点。当一个节点变为E-节点时，则生成从该节点挪动一步即可到达的全部新节点。在生成的节点中，扔掉那些不行能导出（最优）可行解的节点，其余节点加入活节点表，而后从表中选择一个节点作为下一个E-节点。从活节点表中拿出所选择的节点并进行扩大，直到找到解或活动表为空，扩大过程才结束。有两种常用的方法可用来选择下一个E-节点（固然也可能存在其余的方法）：先进先出（FIFO）即从活节点表中拿出节点的序次与加入节点的序次相同，所以活节点表的性质与队列相同。（优先队列）最小耗费或最大收益法在这种模式中，每个节点都有一个对应的耗费或收益。假如查找一个拥有最小耗费的解，则活节点表可用最小堆来成立，下一个E-节点就是拥有最小耗费的活节点；假如希望找寻一个拥有最大收益的解，则可用最大堆来构造活节点表，下一个E-节点是拥有最大收益的活节点分支限界法与回溯法的相同点是：都是一种在问题的解空间树T中找寻问题解的算法。不一样点：（1）求解目标不一样；（2）找寻方式不一样；（3）对扩展结点的扩展方式不一样；（4）储存空间的要求不一样。分治法所能解决的问题一般拥有的几个特色是：（1）该问题的规模减小到必定的程度就可以简单地解决；（2）该问题可以分解为若干个规模较小的相同问题，即该问题拥有最优子构造性质;（3）利用该问题分解出的子问题的解可以归并为该问题的解；4）原问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。用分支限界法设计算法的步骤是：(1)针对所给问题，定义问题的解空间（对解进行编码）；(2)确立易于找寻的解空间构造（按树或图组织解）；(3)以广度优先或以最小耗费（最大收益）优先的方式找寻解空间，并在找寻过程顶用剪枝函数防备无效找寻。常有的两种分支限界法的算法框架：1）队列式(FIFO)分支限界法：依照队列先进先出（FIFO）原则采纳下一个节点为扩展节点。2）优先队列式分支限界法：依照优先队列中规定的优先级采纳优先级最高的节点成为当前扩展节点。回溯法中常有的两类典型的解空间树是子集树和摆列树。当所给的问题是从n个元素的会集S中找出满足某种性质的子集时，相应的解空间树称为子集树。这种子集树平时有2n个叶结点，遍历子集树需O(2n)计算时间。当所给的问题是确立n个元素满足某种性质的摆列时，相应的解空间树称为摆列树。这种摆列树平时有n!个叶结点。遍历摆列树需要O(n!)计算时间。分支限界法的找寻策略是：在扩展结点处，先生成其全部的儿子