算法分析期末试题集答案(6套)

算法分析与设计期末复习题(一)一、 选择题.应用Jsn法则的流水作业调度采用的算法是(D）A. 贪心算法 . 分支限界法 C分治法 .动态规划算法.Hnoi塔问题如下图所示。现规定将塔座A上的的所有圆盘移到塔座B上，并仍按同样顺序叠置。移动圆盘时遵守anoi塔问题的移动规则。由此设计出解Haoi塔问题的递归算法对的的为：(B）A. void hanoi(int n, int A, int C, int B) if (n 0) hanoi(n-1,A,C, B); move(n,a,b); hanoi(n-1, C, B, A); Hanoi塔B. void hanoi(int n, int A, int B, int C) if (n 0) hanoi(n-1, A, C, B); move(n,a,b); hanoi(n-1, C, B, A); C. void hanoi(int n, int C, int B, int A) if (n 0) hanoi(n-1, A, C, B); move(n,a,b); hanoi(n-1, C, B, A); D. void hanoi(int n, int C, int A, int B) if (n 0) hanoi(n-1, A, C, B); move(n,a,b); hanoi(n-1, C, B, A); . 动态规划算法的基本要素为（)A. 最优子构造性质与贪心选择性质B.重叠子问题性质与贪心选择性质C最优子构造性质与重叠子问题性质D.预排序与递归调用4. 算法分析中,记号O表达(B)， 记号表达（A）,记号表达()。.渐进下界.渐进上界C非紧上界D紧渐进界E非紧下界5. 如下有关渐进记号的性质是对的的有:(A)AB. C. O(f(n)+(g（n)）= O(minf(n),() D. . 能采用贪心算法求最优解的问题,一般具有的重要性质为：（A)A 最优子构造性质与贪心选择性质B.重叠子问题性质与贪心选择性质C最优子构造性质与重叠子问题性质D. 预排序与递归调用7. 回溯法在问题的解空间树中,按（)方略,从根结点出发搜索解空间树。A 广度优先 活结点优先 C.扩展结点优先 D. 深度优先8分支限界法在问题的解空间树中，按(A)方略，从根结点出发搜索解空间树。 A. 广度优先 . 活结点优先 .扩展结点优先 .深度优先9. 程序块（A）是回溯法中遍历排列树的算法框架程序。void backtrack (int t) if (tn) output(x); else for (int i=t;in) output(x); else for (int i=0;in) output(x); else for (int i=0;in) output(x); else for (int i=t;i0,存在正数和n0 0使得对所有n0有：0 f()0,存在正数和n0 0使得对所有n有:0cg（） 0,存在正数和n0 0使得对所有n0有：(n）0使得对所有nn0有:0 g(n） f(n）；二、 填空题1. 下面程序段的所需要的计算时间为( )。int MaxSum(int n, int *a, int &besti, int &bestj)int sum=0;for(int i=1;i=n;i+) int thissum=0;for(int j=i;jsum)sum=thissum;besti=i;bestj=j;return sum;2. 有1个待安排的活动，它们具有下表所示的开始时间与结束时间，如果以贪心算法求解这些活动的最优安排(即为活动安排问题：在所给的活动集合中选出最大的相容活动子集合),得到的最大相容活动子集合为活动( 1，4，11 )。1413121110987654fi122886535031Si1110987654321i3. 所谓贪心选择性质是指(所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到)。4. 所谓最优子构造性质是指(问题的最优解涉及了其子问题的最优解）。5. 回溯法是回溯法是指（具有限界函数的深度优先生成法）。6. 用回溯法解题的一种明显特性是在搜索过程中动态产生问题的解空间。在任何时刻,算法只保存从根结点到目前扩展结点的途径。如果解空间树 中从根结点到叶结点的最长途径的长度为h(n）,则回溯法所需的计算空间一般为(O(n)）)。7.回溯法的算法框架按照问题的解空间一般分为(子集树）算法框架与(排列树)算法框架。8. 用回溯法解/1背包问题时，该问题的解空间构造为(子集树)构造。9.用回溯法解批解决作业调度问题时,该问题的解空间构造为（排列树）构造。10用回溯法解0/1背包问题时,计算结点的上界的函数如下所示,请在空格中填入合适的内容:Typep Knap:Bound(int i)/ 计算上界 Typew cleft = c - cw; / 剩余容量 Typep b = cp; / 结点的上界 / 以物品单位重量价值递减序装入物品 while (i = n & wi = cleft) cleft -= wi; b += pi; i+; / 装满背包 if (i = n) （b += pi/wi * cleft）; return b;1.用回溯法解布线问题时，求最优解的重要程序段如下。如果布线区域划分为的方格阵列，扩展每个结点需O()的时间,L为最短布线途径的长度，则算法共耗时 ( O(m) ），构造相应的最短距离需要(（L）)时间。for (int i = 0; i NumOfNbrs; i+) nbr.row = here.row + offseti.row; nbr.col = here.col + offseti.col; if (gridnbr.rownbr.col = 0) / 该方格未标记 gridnbr.rownbr.col = gridhere.rowhere.col + 1; if (nbr.row = finish.row) & (nbr.col = finish.col) break; / 完毕布线 Q.Add(nbr); 1. 用回溯法解图的m着色问题时,使用下面的函数K检查目前扩展结点的每一种儿子所相应的颜色的可用性，则需耗时（渐进时间上限）（O（m)）。Bool Color:OK(int k)/ for(int j=1;j=n;j+)if(akj= =1)&(xj= =xk) return false;return true;旅行售货员问题的解空间树是(排列树）。6.7.三、 解答题1. 机器调度问题。问题描述：目前有n件任务和无限多台的机器,任务可以在机器上得到解决。每件任务的开始时间为s，完毕时间为fi,if。si，f为解决任务的时间范畴。两个任务i，j重叠指两个任务的时间范畴区间有重叠,而并非指i,j的起点或终点重叠。例如:区间1，4与区间2,4重叠，而与4,7不重叠。一种可行的任务分派是指在分派中没有两件重叠的任务分派给同一台机器。因此，在可行的分派中每台机器在任何时刻最多只解决一种任务。最优分派是指使用的机器至少的可行分派方案。问题实例:若任务占用的时间范畴是,4,2,5，4，,2，6，4,则准时完毕所有任务至少需要几台机器？(提示:使用贪心算法）画出工作在相应的机器上的分派状况。2. 已知非齐次递归方程： ，其中，b、c是常数，g()是n的某一种函数。则(n）的非递归体现式为:。既有Hanoi塔问题的递归方程为： ,求（)的非递归体现式。解:运用给出的关系式,此时有:b=2, c=1， g()1, 从n递推到1,有：3. 单源最短途径的求解。问题的描述:给定带权有向图(如下图所示）G=（V，E）,其中每条边的权是非负实数。此外，还给定中的一种顶点，称为源。目前要计算从源到所有其他各顶点的最短路长度。这里路的长度是指路上各边权之和。这个问题一般称为单源最短途径问题。解法:现采用Dijksta算法计算从源顶点1到其他顶点间最短途径。请将此过程填入下表中。432110030maxint10-1初始dist5dist4dist3dist2uS迭代.请写出用回溯法解装载问题的函数。装载问题：有一批共n个集装箱要装上2艘载重量分别为c1和c2的轮船,其中集装箱i的重量为wi，且。装载问题规定拟定与否有一种合理的装载方案可将这n个集装箱装上这2艘轮船。如果有，找出一种装载方案。解:voiacktrak(t i) /搜索第i层结点 if (i ) / 达到叶结点 更新最优解etx，bestw;etrn; r-=wi; if (cw+ wi besw) xi 0; /搜索右子树 backtrc(i + 1); r =wi; 5. 用分支限界法解装载问题时,对算法进行了某些改善，下面的程序段给出了改善部分；试阐明斜线部分完毕什么功能，以及这样做的因素，即采用这样的方式,算法在执行上有什么不同。/ 检查左儿子结点 Type wt = Ew + wi; / 左儿子结点的重量 if (wt bestw) bestw = wt; / 加入活结点队列 if (i bestw & i 故wrbstw总是成立。也就是说,此时右子树测试不起作用。为了使上述右子树测试尽早生效，应提早更新betw。又知算法最后找到的最优值是所求问题的子集树中所有可行结点相应重量的最大值。而结点所相应得重量仅在搜索进入左子树是增长,因此，可以在算法每一次进入左子树时更新btw的值。7 最长公共子序列问题：给定2个序列x，x2,m和y1,2,yn，找出和Y的最长公共子序列。由最长公共子序列问题的最优子构造性质建立子问题最优值的递归关系。用ci记录序列Xi和Yj的最长公共子序列的长度。其中, Xi=x1,i；Yj,2,yj。当0或=时,空序列是Xi和Yj的最长公共子序列。故此时Cij=0。其他状况下，由最优子构造性质可建立递归关系如下:在程序中，ij记录Ci的值是由哪一种子问题的解得到的。（1） 请填写程序中的空格，以使函数SLenth完毕计算最优值的功能。void LCSLength(int m，int n，char *x，char *y，int *c，int *b) int i，j; for (i = 1; i = m; i+) ci0 = 0; for (i = 1; i = n; i+) c0i = 0; for (i = 1; i = m; i+) for (j = 1; j =cij-1) cij=ci-1j; bij=2; else cij=cij-1; bij=3; （2） 函数LC实现根据的内容打印出X和Yj的最长公共子序列。请填写程序中的空格，以使函数C完毕构造最长公共子序列的功能（请将bi的取值与(1）中您填写的取值相应,否则视为错误)。void LCS(int i，int j，char *x，int *b) if (i =0 | j=0) return; if (bij= 1) LCS(i-1，j-1，x，b); cout0 ) printf(%dn ,k); f(k-1); f(k-1); 算法分析与设计期末复习题(二)一、简要回答问题 :1. 算法重要特性是什么？2. 算法分析的目的是什么？3. 算法的时间复杂性与问题的什么因素有关?4. 算法的渐进时间复杂性的含义？5. 最坏状况下的时间复杂性和平均时间复杂性有什么不同？6. 简述二分检索(折半查找）算法的基本过程。7. 背包问题的目的函数和贪心算法最优化量度相似吗？8. 采用回溯法求解的问题,其解如何表达?有什么规定？9. 回溯法的搜索特点是什么? 10. n皇后问题回溯算法的鉴别函数pace的基本流程是什么？11. 为什么用分治法设计的算法一般有递归调用?12. 为什么要分析最坏状况下的算法时间复杂性? 13. 简述渐进时间复杂性上界的定义。14. 二分检索算法最多的比较次数?15. 迅速排序算法最坏状况下需要多少次比较运算？16. 贪心算法的基本思想?17. 回溯法的解（x,x2，xn)的隐约束一般指什么?18. 论述归并排序的分治思路。19. 迅速排序的基本思想是什么。 20. 什么是直接递归和间接递归？消除递归一般要用到什么数据构造？21. 什么是哈密顿环问题?22. 用回溯法求解哈密顿环,如何定义鉴定函数？23. 请写出rm算法的基本思想。参照答案：1.拟定性、可实现性、输入、输出、有穷性2 分析算法占用计算机资源的状况，对算法做出比较和评价,设计出额更好的算法。. 算法的时间复杂性与问题的规模有关，是问题大小n的函数。4当问题的规模n趋向无穷大时，影响算法效率的重要因素是T(n)的数量级，而其她因素仅是使时间复杂度相差常数倍，因此可以用(n)的数量级（阶)评价算法。时间复杂度T(n)的数量级(阶)称为渐进时间复杂性。5 最坏状况下的时间复杂性和平均时间复杂性考察的是n固定期，不同输入实例下的算法所耗时间。最坏状况下的时间复杂性取的输入实例中最大的时间复杂度：W（n） = maT(n,） ， IDn平均时间复杂性是所有输入实例的解决时间与各自概率的乘积和：A(n）P（)T(n,I) D. 设输入是一种按非降顺序排列的元素表Ai: 和x,选用A(i+j)/与x比较，如果（ij)/=x,则返回(+j)/,如果A(+j)/2x,则Ai:(ij)/2-1找,否则在(+j)2+1:j 找x。上述过程被反复递归调用。回溯法的搜索特点是什么7. 不相似。目的函数：获得最大利润。最优量度：最大利润/重量比。8.问题的解可以表达为元组:(x1,x2,x)，xiSi, 为有穷集合,Si,(x1,x2,xn）具有完备性，即（x1,x2,xn)是合理的，则（x1,x2,x）(in)一定合理。 在解空间树上跳跃式地深度优先搜索,即用鉴定函数考察k的取值,如果xk是合理的就搜索k为根节点的子树,如果k取完了所有的值，便回溯到xk-。1. 将第K行的皇后分别与前k-1行的皇后比较，看与否与它们相容,如果不相容就返回false，测试完毕则返回t。11 . 子问题的规模还很大时,必须继续使用分治法,反复分治,必然要用到递归。12 最坏状况下的时间复杂性决定算法的优劣,并且最坏状况下的时间复杂性较平均时间复杂性游可操作性。 13.T(n)是某算法的时间复杂性函数，f(n)是一简朴函数，存在正整数No和，nNo,有T(n)f(n），这种关系记作T（n)=O(f(n)。14 .二分检索算法的最多的比较次数为 lg n 。15.最坏状况下迅速排序退化成冒泡排序，需要比较n2次。6 是一种根据最优化量度依次选择输入的分级解决措施。基本思路是：一方面根据题意，选用一种量度原则；然后按这种量度原则对这n个输入排序，依次选择输入量加入部分解中。如果目前这个输入量的加入，不满足约束条件，则不把此输入加到这部分解中。1回溯法的解(x,x2，xn)的隐约束一般指个元素之间应满足的某种关系。 1 讲数组一分为二，分别对每个集合单独排序,然后将已排序的两个序列归并成一种含n个元素的分好类的序列。如果分割后子问题还很大,则继续分治,直到一种元素。1.迅速排序的基本思想是在待排序的N个记录中任意取一种记录，把该记录放在最后位置后，数据序列被此记录提成两部分。所有核心字比该记录核心字小的放在前一部分,所有比它大的放置在后一部分,并把该记录排在这两部分的中间，这个过程称作一次迅速排序。之后反复上述过程,直到每一部分内只有一种记录为止。20在定义一种过程或者函数的时候又浮现了调用本过程或者函数的成分,既调用它自己自身,这称为直接递归。如果过程或者函数P调用过程或者函数Q，Q又调用,这个称为间接递归。消除递归一般要用到栈这种数据构造。21.哈密顿环是指一条沿着图G的N条边环行的途径，它的访问每个节点一次并且返回它的开始位置。22.目前选择的节点k是从未到过的节点，即XkXi（i1,2，,)，且C(k-1, Xk),如果k=-1，则C(k, X1） 。3. 思路是:最初生成树为空,依次向内加入与树有最小邻接边的n-1条边。解决过程：一方面加入最小代价的一条边到，根据各节点到的邻接边排序,选择最小边加入,新边加入后,修改由于新边所变化的邻接边排序,再选择下一条边加入,直至加入n-条边。二、复杂性分析1、 MERGSOR(low,high） ifowhi; the i(lo,high)/2； MERGSOT(ow，md）； RSORT(mid+,hi); MER(ow，mid，high）； en ed MERGESOR答:、 递归方程 设=2k解递归方程：2、 procedre S1(,W，M，,n) i; 0 while i do f （i)M en retur end aai i+1 ; rpt end 解: i1 ;s0 时间为：(1） ie i do 循环n次 循环体内所用时间为O（1） 因此 总时间为:T（)=O(） nO()= O（n)3.proceure PRTITION(m,p） Ingr ，,i；glol A(:p1) v(m);i lolop ii1 uti () v repeaop pp-1 u (p) reea if i1时F(n）的时间复杂度与F2(2,n，1,1)的时间复杂度相似即为为 O（n)5.poedure X(A,j) ax(1);j1 ori2o n do i(i）xmax the maxA（i); j；edif pend MAX 解：xaxA(1)；j1 时间为:O(1) fo i o ndo 循环最多n-1次 因此 总时间为:(n）=O(1)+ (n-1）O(1)= O(n)6.prode BNSCH(A，n,) g l,hig,md,j，; w1;ighn hile loigdo d_(low+high）2_ s ：A（mid）:lowmi+:els：jmi; reurn endcse pea j en NRC解:log2n+三、算法理解1、写出多段图最短路经动态规划算法求解下列实例的过程,并求出最优值。52863174各边的代价如下：(1，2)=3,C（1，3)= ,(1,4）2 C（2，)=8,(2，7)=4，(3,5)5 ，（3,)=4, （4,5）=2,C(4,6)C(5,8）=, C(6,8)= ,C(，8)=6解：Cst(4,8)=0Co（3,7）=C（,8)+0=6，D5=8Cost（3，6)= (6,8)=5,6=8Cst(,5)= C（5,)+0=4 D7Cost（，4）= minC(，6）+ Cst(3,6), C(4,)+ s(3,) m1 5, 2+=6 D4=Cos(2,3）= mnC(3，)+ st（3,6) = min+5=9 D3s(,2)=minC(2,6） Cost(3,), （2，)+ Ct（,) = min8+5, 4+6=10 D2=7Cst（,1）= minC（,2)+ Cot(2，2), (1，3)+ ost（,)， (1,4) Cot（2,) = mn310， ，+= 8D1414682、 写出maxmin算法对下列实例中找最大数和最小数的过程。数组 A=(48,12,61，3,5,19,32，7) 解：写出mamin算法对下列实例中找最大数和最小数的过程。数组 () 1、 48,，1,3, ,19，32,7、4，12 1,3 5,19 32，73、486，123 193,574、 12 35、 6 33、 迅速排序算法对下列实例排序,算法执行过程中，写出数组A第一次被分割的过程。 A(65,70,75,80，85,55,50,2)解:第一种分割元素为65(1) (2) (3) (4) (5) (6) (7) (8) i p65 70 75 80 85 55 50 2 2 865 2 75 80 85 55 50 70 3 765 2 50 80 85 55 75 70 4 665 2 50 55 85 80 75 70 4 655 70 75 80 85 65 50 24、 归并排序算法对下列实例排序,写出算法执行过程。 A=(8,12,6,3，5，19,3,) 解: 48，1,6,3 ,19,3,748,12 6,3 ,19 2，712，4 ,1 5,19 7，32 3, 12， 4, ， 7， 19,323，5,7,1,19，32,8,1 5、 写出图着色问题的回溯算法的判断X与否合理的过程。解：0wile ik o ik,i=1 andk= thn rturn fle i1eeat if = k ten retur te6、 对于下图,写出图着色算法得出一种着色方案的过程。2314解:K1X 1 ， 返回 trueX2,返回fls; X2X2+=2,返回 tueX31 ,返回fale; X3+1=2，返回ase；X33+1=3， 返回 treX4,返回fals; 4X4+1=2， 返回fase；X4X4+1=, 返回 tue找到一种解 （1,2,3，)7、 写出第7题的状态空间树。解:X1=1X2=2X3=33X4=338、写出归并排序算法对下列实例排序的过程。(6,9,3,1，8,7)解:调用第一层次 6，, ,1，8,7 提成两个子问题 调用第二层次 6,2 9,3 5，1 8,7 提成四个子问题调用第三层次 6 2 9 3 5 1 8 7 提成八个子问题 调用第四层次 只有一种元素返回上一层第三层归并 2 ,6 3, 9 1,5 7, 返回上一层第二层归并 2,3,6, 9 1,5,7,8 返回上一层第一层归并 1， 2 ,3，5 ， 7, 8, 排序结束，返回主函数、写出用背包问题贪心算法解决下列实例的过程。 P=(1,12,4,) =（1,10，8,3) 解： 实例符合P（i)/W(i）P(i+1)/W(i+1）的顺序。 CU5,X W1 ： x11; CUW1=1; W210时 m(x）=x-10；当x=10时 m(x)m(（+11）;编写一种递归函数计算给定x的m(x)值。解:Cathy函数定义如下：当x100时 m（x)=-1;当x10) rturn(x-00)；l y=m(x+11)； return (m(y）)； 15、 设计一种算法在一种向量A中找出最大数和最小数的元素。解:设计一种算法在一种向量A中找出最大数和最小数的元素。Vod mxmn(,n）Vctor A;int n;it max,mn，i; max=A1;minA1;fo(i=2；icu thn exit endif () 1 cucu-W(i) rpeat end GREE-KNAPSACK 根据算法得出的解: X(，1,1,1,1,0,0)获利润52, 而解(1,1，1, 0, 1,0）可获利润5 因此贪心法不一定获得最优解。 设计只求一种哈密顿环的回溯算法。解:miltnian(n)k1；k0; Whil k0 do xk xk+1; hile B(k）=alse and xkn do x x+1; repeat Ifxkn hen if k=n tpint ;eturn ese k k+;x0; endf ee k k-1 nrpatendrocure B(k) Gk-,k 1thenreurnflse; for i1 to k-1 o fxixk henurn fale;endif peat retn rue; 5.运用对称性设计算法，求为偶数的皇后问题所有解。解：运用对称性设计算法，求n为偶数的皇后问题所有解。rocdueNQUEENS1（n） /计数器清零（1)0；k /k是目前行;X(k）是目前列/ While 0do /对所有的行执行如下语句/） X(k)X()+1 /移到下一列/Whie X(k) nd ot PLAC（k) d2) X(k)()十l if X()n then if k= / tnprin(),a+1 /找到一种解计数器a加/ =n2 thn turn / 找到n/2个解算法结束3) else kk+1；（k）0; 4) eskk1 /回溯/ n NQUENS武汉工业学院工商学院 第 学期算法分析考试试卷（卷）课程名称 算法分析 编号 308012 题号一二三四