中南大学现代远程教育课程考试复习试题及参考答案

中南大学现代远程教育课程考试复习试题及参考答案《算法分析与设计》一简答题1.算法的复杂性分析主要是分析算法的什么耗费情况？2.算法的重要特性是什么？3.算法的时间复杂度用什么计量？4.用比较树模型描述三个数排序的过程。5.分治法的基本思想。6.二分检索算法为什么可以提高查找的效率？7.简述顺序选择select算法的基本流程。8.简述顺序选择select2算法的改进思路。9.简述快速排序的基本思想。10.快速排序算法的最坏时间复杂性和平均时间复杂性函数。11.快速排序算法怎样抽取分割元素？12.partition怎样将数组划分成3段？13.分治合并排序的是怎样分治的？14.分治合并排序的二分归并过程在最坏情况下花费多少时间？15.分治合并排序的二分归并过程在最好情况下花费多少时间？16.MaxMin算法是怎样分治的？17.贪心法的基本思路是什么？18.用贪心法求解的问题有什么特点？19.背包问题的目标函数是什么，最优量度是什么？20.带限期的作业调度的贪心策略是什么？约束条件是什么？21.说明n皇后问题的解（x1,x2,….,xn）的含义。22.简述n皇后算法的place函数的功能。23.简述动态规划方法所运用最优化原理。24.用多段图说明最优化原理。二解释下列动态规划优解的一般递归形式。1）0/1背包2）货郎担问题3）流水作业调度三算法分析。1．分析汉诺塔算法的时间复杂性。2．计算冒泡排序算法时间复杂性的阶。3．分析maxmin算法的时间复杂性。4．分析分治合并排序算法的时间复杂性。5．分析二分检索的时间复杂性。6．背包问题贪心算法的时间复杂性。7．快速排序的partition过程中，进行了多少次元素之间的比较。8．多段图算法的时间复杂性。四算法段填空。1．MaxMin算法Maxmin(i,j,max,min)ifthen对两元素进行比较;return;else{maxmin(i,m,max1,min1);//其中max1和min1为解子问题1的解}2．Hanoi算法Hanoi(n,a,b,c)Ifn=1thenElse{;Hanoi(n-1,b,a,c);}3．二分检索BINSRCH(A,n,x,j)low←1;high←n;whilelowhighdo{________________mid←(low+high)/2;case：x=A[mid]：j←mid;return;：xA[mid]：_________________high←mid-1;：xA[mid]：_________________low←mid+1;endcase}j←0;end4．快速排序Quicksort(p,q)ifpqthen_____________{callpartition(p,j);call_______________________call_______________________}end5．贪心方法的抽象化控制procedureGREEDY(A，n)//A(1：n)包含n个输入//solutions←；fori←1todo{x←SELECT(A)ifFEASIBLE(solution，x)thensolutions←；endif}return(solution)endGREEDY6．背包问题贪心算法procedureGREEDY-KNAPSACK(P，W，M，X，n)X←0；cu←M；fori←1tondo{ifthenexitendifX(i)←_；cu←；}ifi≤nthenX(i)←；endifendGREEDY-KNAPSACK7．分治合并排序算法procedureMERGESORT(low,high)iflowhighthenmid←_______________________________________________________MERGE(low,mid,high)endifendMERGESORT8．多段图动态规划算法procedureFGRAPH(E，k，n，P)1realCOST(n)，integerD(n一1)，P(k)，r，j，k，n2；3forto1by－1do4设r是一个这样的结点，(j，r)E且使c(j，r)+COST(r)取最小值5COST(j)←；6；7repeat8P(1)←1；P(k)←n；9fordo10P(j)←D(P(j-1))11repeat12endFGRAPH9．n后问题递归算法procedureRNQUEENS(K)globalx(1:m),n;forx(k)←1to_____doifplace(k)=truethenifk=nthen________else_____________endifendifrepeatendENQUEENS五.设计算法1．写递归形式的二分检索算法2．设计三分检索算法3．有n个大小相同而重量不同的集装箱，重量分别为(w1,w2,……,wn)，已知货船的额定载重量为M，ΣwiM,i=1,2,3，…，n。最优解是货船能够装载最多的集装箱。设计贪心算法。4．有n个程序和长度为L的磁带，程序i的长度为ai，已知Lanii1，求最优解(xi，x2，...，xi，…，xn)，1,xi=1，表示程序i存入磁带，xi=0，表示程序i不存入磁带，满足Laxniii1，且存放的程序数目最多。参考答案一、简答题1.算法的复杂性是算法运行所需要的计算机资源的耗费量，需要的时间资源的耗费量称作时间复杂性。2.有5个基本特性是：确定性、能行性、输入给定、产生输出、有穷性。3.算法复杂性用算法的基本运算步骤计量，运算步骤与算法要解的问题的规模、算法的输入有关。4.比较树模型5.分治的基本思想是将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题相同。找出各部分的解，然后把各部分的解组合成整个问题的解。6.分治算法时间是这样确定的：解决子问题所需的工作总量由子问题的个数、解决每个子问题的工作量、合并所有子问题所需的工作量所决定。折半查找最坏情况下，也只需要在原问题一半大小的子问题中查找，而且不需要合并子问题。7.首先对于数组a[p：q]进行划分，以元素v为基准元素将a划分为三段a[p：j-1]，a[j]和a[j+1：q]，使得a[p：j-1]中任何一个元素都小于v，a[j+1：q]中任何一个元素大于等于v，下标j在划分中确定。如果k=j，则返回v；如果kj，则在a[p：j-1]中选择；如果kj，则在a[j+1：q]中选择；8.select算法的最坏情况下的时间复杂性的阶为O(n2)，其原因是a[p：j-1]和a[j+1：q]的大小不是均衡的。Select2算法的基本思路就是改随即抽取v为经过经处理产生，保证在最坏情况下a[p：j-1]和a[j+1：q]的元素个数不会小于原规模的1/4。9.快速排序是基于分治策略的一个排序算法。基本思路：a)分解(Divide)以元素v为基准元素将a划分为三段a[p：j-1]，a[j]和a[j+1：q]，使得a[p：j-1]中任何一个元素都小于v，a[j+1：q]中任何一个元素大于等于v，下标j在划分中确定。b)递归求解，通过递归调用快速排序算法分别对a[p:j-1]和a[j+1:q]进行排序。不必进行任何合并操作。10.快速排序算法的最坏情况下的时间复杂性的阶为O(n2)，其原因是a[p：j-1]和a[j+1：q]的大小不是均衡的。快速排序算法的平均时间复杂性的阶为O(nlogn)。11.采用随机抽取。对于数组a[p：q]，用v=a[p]作为分割元素。12.使v=a[p]，q=q+1while(pq)do{dop++;while(a[p]v);doq++;while(a[q]v);if(pq)交换a[p]和a[q]；}13.if问题不可分then求解else{m=(p+q)/2;对a[p,m]排序；对a[m+1，q]排序；将a[p,m]和a[m+1，q]合并；}14.分治合并排序的二分归并过程在最坏情况下需比较n-1次，花费可用cn表示。15.最好情况下需比较n/2次。16.Maxmin(p,q,max,min)if问题不可分：n=2then对两元素进行比较产生max,min;return;else{m=(p+q)/2;Maxmin(p,m,max1,min1);maxmin(m+1,q,max2,min2);max=maxnum(max1,max2);min=minnum(min1,min2);}17.贪心算法的基本思路：从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快的地求得更好的解。当达到某算法中的某一步不能再继续前进时，算法停止。18.具备最优子结构。19.目标函数：∑pi最大，最优量度是选择有最大利润/重量的物品。20.∑pi最大，i属于可完工子集。21.xi表示第i行上的皇后所在的列。22.place函数的功能是判断第k行皇后的位置和前k-1个皇后是否相容。最优化原理：无论过程的初始状态是什么，其余的决策都必须相对于初始决策所产生的状态是最优的。通俗地讲，每一步最优都是上一步最优加上本段的最优。即当前最优只与上一步有关。24.向前决策到第i段时，第i段的节点j的最优可以用第i-1段的最优值加上本段的长度：cost(i,j)=min{cost(i-1,l)+c(j,l)}l是i-1段的节点j的后继节点。二、动态规划递归式1.fi(X)=max{fi-1(X-wi)+pi，fi-1(X)},（0=X=M）fi(X)是背包容积为X时前i个物品的最优值。fi-1(X-wi)+pi是前i-1个物品的最优值加上第i个物品放入获得的利润，fi(X)等于第i个物品放入或不放入两种情况的较大值。2.g(s,i)=min{c(i,j)+g(s-{j},j)|js,is}s是不包含起始点1的任意顶点子集，g(s,i)是从顶点i出发经s中顶点各一次后到达顶点1的最优值。g(s,i)等于i到j的代价c(i,j)加上从顶点j出发经s-{j}中顶点各一次后到达顶点1的最优值。3.g(s,t)=min{ai+g(s-{i},bi+max{t-ai,0})|is}s任意作业子集，g(s,t)是处理机2需要t时间才能开工条件下的对s进行调度的最优值。从顶点i出发经s中顶点各一次后到达顶点1的最优值。g(s,i)等于i到j的代价c(i,j)加上从顶点j出发经s-{j}中顶点各一次后到达顶点1的最优值。三、算法分析1.分析汉诺塔算法的时间复杂性汉诺塔算法如下：Hanoi(n,a,b,c)①Ifn=1thenmove(a,c);Else{②Hanoi(n-1,a,c,b);③move(a,c);④Hanoi(n-1,b,a,c);}用移动圆盘的次数作为计量，Hanoi(n,a,b,c)所花的时间为T(n)。当n=1执行①,T(1)=1当n1执行②③④,T(n)=2T(n-1)+1。用递推式求T(n)。T(n)=2T(n-1)+1=2{2T(n-2)+1}+1=22T(n-2)+2+1=22{2T(n-3)+2+1=23T(n-3)+22+2+1=23{2T(n-4)+1}+22+2+1=24T(n-4)+23+22+2+1……=2n-1T(1)+2n-2……+22+2+1=2n-12.计算冒泡排序算法时间复杂度冒泡排序的主要步骤：fori=1ton-1doforj=1ton-idoifa[j]a[j+1]then交换a[j]，a[j+1]；用比较次数作为算法的计量，比较一次所花的时间为常数，用O(1)表示，内循环所花时间ΣO(1)=O(n-i)，外循环所花时间：ΣO(n-i)=O(n(n-1)/2)=O(n2)3.分析MaxMin的比较次数：当n=2，T(2)=1当n2时，比较次数T(n)=2T(n/2)+2设n是2的k次幂，n=2kT(n)=2T(2k-1)+2=2[2T(2k-1)+2]+2=22T(2k-2)+22+2……=2k-1T(2)+2k-1+……22+2