《算法设计与分析》复习题

第1页共9页填空1．直接或间接地调用自身的算法称为递归。2．算法的复杂性是算法效率的度量，是评价算法优劣的重要依据。3．以广度优先或以最小耗费方式搜索问题解的算法称为分支限界法。4．回溯法解题的显著特点是在搜索过程中动态产生问题的解空间。在任何时刻，算法只保存从根结点到当前扩展结点的路径。如果解空间树中从根结点到叶结点的最长路径的长度为h(n)，则回溯法所需的计算空间通常为o(h(n))。5．人们通常将问题的解决方案分为两大类：一类是可以通过执行若干个步骤就能得出问题结论的，叫做算法方案方案；另一类是不能通过若干个步骤直截了当地得出结论，而是需要反复验证才能解决的，叫做启发式方案方案。6．算法就是一组有穷的规则，它们规定了解决某一特定类型问题的一系列运算。7．在进行问题的计算复杂性分析之前，首先必须建立求解问题所用的计算模型。3个基本计算模型是随机存取机、随机存取存储程序机、图灵机。8．快速排序算法的性能取决于划分的对称性。9．计算机的资源最重要的是内存和运算资源。因而，算法的复杂性有时间和空间之分。10．贪心算法总是做出在当前看来最优的选择。也就是说贪心算法并不从整体最优考虑，它所做出的选择只是在某种意义上的局部最优解。11．许多可以用贪心算法求解的问题一般具有2个重要的性质：最优子结构的性质和贪心选择的性质。12．常见的两种分支限界法为队列式和优先队列式。13．解决0/1背包问题可以使用动态规划、回溯法和分支限界法，其中需要排序的是回溯法，不需要排序的是动态规划和分支限界法。14．f(n)=6×2n+n2，f(n)的渐进性态f(n)=O(2^n)。15．对于含有n个元素的排列树问题，最好情况下计算时间复杂性为，最坏情况下计算时间复杂性为n!。16．在忽略常数因子的情况下，O、和三个符号中，提供了算法运行时间的一个上界。17．回溯法的求解过程，即在问题的解空间树中，按深度优先策略从根结点出发搜索解空间树。18．分支限界法的求解过程，即在问题的解空间树中，按广度优先策略从根结点出发搜索解空间树。19．多项式10()mmAnanana的上界为2^n。20．用分支限界法解布线问题时，对空间树搜索结束的标志是活结点表为空。21．使用回溯法进行状态空间树裁剪分支时一般有两个标准：约束条件和目标函数的界，N皇后问题和0/1背包问题正好是两种不同的类型，其中同时使用约束条件和目标函数的界进第2页共9页行裁剪的是0-1背包，只使用约束条件进行裁剪的是N皇后。简答1.算法分析的目的是什么？分析算的的效率以求改进2.算法的渐进时间复杂性的含义？当问题的规模n趋向无穷大时，影响算法效率的重要因素是T（n）的数量级，而其他因素仅是实用时间复杂度相差的常熟倍，因此可以用T（n）的数量级（阶）评价算法。时间复杂度T（n）的数量级（阶）称为渐进时间复杂性3.最坏情况下的时间复杂性和平均时间复杂性有什么不同？最坏情况下的时间复杂性和平均时间复杂性考察的是n固定时，不同输入实例下的算法所耗时间。最坏情况下的时间复杂性取的输入实例中最大的时间复杂度：W(n)=max{T(n，I)},I∈Dn平均时间复杂性是所有输入实例的处理时间与各自概率的乘积和：A(n)=∑P(I)T(n，I)I∈Dn4.简述分治法的基本思想。分治法的是将一个规模为n的问题分解为k个规模较小的子问题，这些子问题相互独立且与原题相同5.简述动态规划方法所运用的最优化原理。“最优化原理”用数学化的语言来描述：假设为了解决某一优化问题，需要依次作出n个决策D1，D2，…，Dn，如若这个决策序列是最优的，对于任何一个整数k，1kn，不论前面k个决策是怎样的，以后的最优决策只取决于由前面决策所确定的当前状态，即以后的决策Dk+1，Dk+2，…，Dn也是最优的。6.简述最优子结构性质。一道动态规划问题其实就是一个递推问题，假设当前决策结果是f[n]，则最优子结构就是要让f[n-k]最优，最优子结构性质就是能让转移到n的状态是最优的，并且与后面的决策没有关系，即让后面的决策安心地使用前面的局部最优解的一种性质7.简述回溯法基本思想。回溯法的基本做法是搜索，在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。算法搜索至解空间树的任意一点时，先判断该结点是否包含问题的解。如果肯定不包第3页共9页含，则跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索。8.用回溯法求解的问题，其解如何表示？有什么规定？问题的解可以表示为n元组：（x1,x2,„„xn），xi∈Si,Si为有穷集合，xi∈Si,（x1,x2,„„xn）具备完备性，即（x1,x2,„„xn）是合理的，则（x1,x2,„„xi）(in)一定合理。9.回溯法的搜索特点是什么？在解空间树上跳跃式地深度优先搜索，即用判定函数考察x[k]的取值，如果x[k]是合理的就搜索x[k]为根节点的子树，如果x[k]取完了所有的值，便回溯到x[k-1]。10.贪心算法的基本思想？是一种依据最优化量度依次选择输入的分级处理方法。基本思路是：首先根据题意，选取一种量度标准；然后按这种量度标准对这n个输入排序，依次选择输入量加入部分解中。如果当前这个输入量的加入，不满足约束条件，则不把此输入加到这部分解中。11.什么是直接递归和间接递归？消除递归一般要用到什么数据结构？在定义一个过程或者函数的时候又出现了调用本过程或者函数的成分，既调用它自己本身，这称为直接递归。如果过程或者函数P调用过程或者函数Q，Q又调用P，这个称为间接递归。消除递归一般要用到栈这种数据结构。第4页共9页算法填空1．n后问题回溯算法（1）用二维数组A[N][N]存储皇后位置，若第i行第j列放有皇后，则A[i][j]为非0值，否则值为0。（2）分别用一维数组M[N]、L[2*N-1]、R[2*N-1]表示竖列、左斜线、右斜线是否放有棋子，有则值为1，否则值为0。for(j=0;jN;j++)if(!M[j]&&!L[i+j]&&!R[i-j+N]){//安全检查A[i][j]=i+1;//放皇后M[j]=L[i+j]=R[i-j+N]=1;;if(i==N-1)输出结果;elsetry(i+1,M,L,R,A);//试探下一行A[i][j]=0;//去皇后M[j]=L[i+j]=R[i-j+N]=0;}2．数塔问题。有形如下图所示的数塔，从顶部出发，在每一结点可以选择向左走或是向右走，一起走到底层，要求找出一条路径，使路径上的值最大。for(r=n-2;r=0;r--)//自底向上递归计算for(c=0;;c++)if(t[r+1][c]t[r+1][c+1]);else;3．用回溯法解0/1背包问题时，计算结点的上界的函数如下所示，请在空格中填入合适的内容：privatestaticdoublebound(inti){doublecleft=c-cw;//剩余容量doublebound=cp;//结点的上界while(i=n&&w[i]=cleft){cleft-=w[i];bound+=p[i];i++;}if(i=n)bound+=p[i]*cleft/w[i];returnbound;第5页共9页}4．用回溯法解图的m着色问题时，使用下面的函数OK检查当前扩展结点的每一个儿子所相应的颜色的可用性，则需耗时（渐进时间上限）。privatestaticbooleanok(intk){//检查颜色可用性for(intj=1;j=n;j++)if(a[k][j]&&x[j]==x[k])returnfalse;returntrue;}5．Hanoi算法Hanoi(n,a,b,c){if(n==1)move(a,c);else{Hanoi(n-1,a,c,b);Move(a,c);Hanoi(n-1,b,a,c);}}算法应用1．给定多项式p(x)=anxn+an-1xn-1+…+a1x+a0，假设使用以下方法求解：p=a0;xpower=1;for(i=1;i=n;i++){xpower=x*xpower;p=p+ai*xpower;}（1）该算法最坏情况下使用的加法和乘法分别为多少次？（2）能不能对算法的性能进行提高？如果可以，请写出改进算法。（1）该算法最坏情况下使用的加法n次，乘法2n次第6页共9页（2）改进的算法为：floatHorner(A,floatx){p=A[n+1];for(j=1;j=n;j++)p=x*p+A[n-j];returnp;}该算法中使用加法n次，乘法n次2．假设有7个物品，它们的重量和价值如下表所示。若这些物品均不能被分割，且背包容量M＝150，使用回溯方法求解此背包问题。请写出状态空间搜索树。物品ABCDEFG重量35306050401025价值104030503540303．已知在如下所示的电路板中，阴影部分是已作了封锁标记的方格，请按照队列式分支限界法在图中确定a到b的最短布线方案，要求布线时只能沿直线或直角进行，在图中标出求得最优解时各方格情况。ba4．设有n=2k个运动员要进行循环赛，现设计一个满足以下要求的比赛日程表：①每个选手必须与其他n-1名选手比赛各一次；②每个选手一天至多只能赛一次；③循环赛要在最短时间内完成。（1）如果n=2k，循环赛最少需要进行多少天；如果n≠2k，循环赛最少需要进行多少天。（2）当n=23=8时，请画出循环赛日程表：第7页共9页5．已知1()*()iikkijrrAa，k=1，2，3，4，5，6，r1=5，r2=10，r3=3，r4=12，r5=5，r6=50，r7=6，求矩阵链积A1×A2×A3×A4×A5×A6的最佳求积顺序。使用算法进行求解。最优值数组为：123456123456最优断开位置数组为：123456123456因此，最佳乘积序列为。共执行乘法次。6．棋盘覆盖问题。（1）将下图特殊棋盘进行L型骨牌填充。（2）算法时间复杂性。7．用分支限界法解装载问题时，对算法进行了一些改进，下面的程序段给出了改进部分。试说明划线部分完成什么功能，以及这样做的原因，即采用这样的方式，算法在执行上有什么不同。第8页共9页//检查左儿子结点intwt=ew+w[i];//左儿子结点的重量if(wt=c){//可行结点if(wtbestw)bestw=wt;//加入活结点队列if(in)queue.put(newInteger(wt));}//检查右儿子结点if(ew+rbestw&&in)queue.put(newInteger(wt));//可能含最优解ew=((Integer)queue.remove()).intValue();//取下一扩展结点8．单源最短路径的求解。给定带权有向图（如下图所示）G=(V，E)，其中每条边的权是非负实数。另外，还给定V中的一个顶点，称为源。现在要计算从源到所有其它各顶点的最短路长度。这里路的长度是指路上各边权之和。这个问题通常称为单源最短路径问题。请用Dijkstra算法计算从源顶点1到其它顶点间最短路径。请将此过程填入下表中。算法设计1．用分治算法求给定二叉树的高度。2．用合适算法求解装载问题。432110030maxint10-{1}初始dist[5]dist[4]dist[3]dist[2]uS迭代第9页共9页3．用贪心法求解部分背包问题，已知n=3，C=40，（w1，w2，w3）=（28，15，24），（p1，p2，p3）=（35，25，24）。4．给定a，用二分法设计出求an的算法。5．用回溯法求解{1，2，3，4，5}，这5个自然数中任取3个数的组合。