算法设计与分析试卷一、 填空题（20分，每空2分）1、 算法的性质包括输入、输出、有限性。2、 动态规划算法的基本思想就将待求问题、先求解子问题，然后从这些子问题的解得到原问题的解。3、 设计动态规划算法的4个步骤：（1） 找出，并刻画其结构特征。（2） 。（3） 。（4） 根据计算最优值得到的信息，。4、 流水作业调度问题的johnson算法：（1） 令N1=,N2=i|ai=bj;（2） 将N1中作业依ai的。5、对于流水作业高度问题，必存在一个最优调度，使得作业（i）和（i+1）满足Johnson不等式。6、最优二叉搜索树即是的二叉搜索树。二、综合题（50分）1、当（a1,a2,a3,a4,a5,a6）=(-2,11,-4,13,-5,-2)时，最大子段和为ak(2=k=4)（5分）2、由流水作业调度问题的最优子结构性质可知，T（N，0）=（5分）3、最大子段和问题的简单算法(10分)int maxsum(int n,int *a,int & bestj)intsum=0;for (int i=1;i=n;i+)for (int j=i;j=n;j+)int thissum=0;for(int k=i;ksum)sum=thissum;；bestj=j; return sum;4、 设计最优二叉搜索树问题的动态规划算法OptimalBinarysearchTree? (15分)Void OptimalBinarysearchTree(int a,int n,int * * m, int * * w)for(int i=0;i=n;i+) wi+1i=ai; mi+1i=;for(int r=0;rn;r+)for(int i=1;i=n-r;i+)int j=i+r;wij=wij-1+aj+bj;mij=;sij=i;for(int k=i+1;k=j;k+)int t=mik-1+mk+1j;if() mij=t; sij=k;mij=t; sij=k;5、设n=4, (a1,a2,a3,a4)=(3,4,8,10), (b1,b2,b3,b4)=(6,2,9,15) 用两种方法求4个作业的最优调度方案并计算其最优值？（15分）三、简答题（30分）1、将所给定序列a1:n分为长度相等的两段a1:n/2和an/2+1:n，分别求出这两段的最大子段和，则a1:n的最大子段和有哪三种情形？(10分)答： 2、由01背包问题的最优子结构性质，可以对m（i,j）建立怎样的递归式? (10分)3、01背包求最优值的步骤分为哪几步？（10分）参考答案：填空题：确定性 分解成若干个子问题 最优解的性质 递归地定义最优值 以自底向上的方式计算出最优值构造最优解 i|aibi ai的非减序排序；将N2中作业依bi的非增序排序 minb(i),a(i+1)minb(i+1),a(i) 最小平均查找长度综合题：20 minai+T(N-i,bi)(1=i=n) thissum+=ak besti=i 0 mi+1j tmij法一：min(ai,bj)=min(aj,bi)因为 min(a1,b2)=min(a2,b1)所以 12 (先1后2)由 min(a1,b3)=min(a3,b1)得 13 （先1后3）同理可得：最后为1342法二：johnson算法思想N11，3，4 N22N11，3，4 N22所以 N1N2得：1342简答题：1 、 （1）a1:n的最大子段和与a1:n/2的最大子段和相同。 （2）a1:n的最大子段和与的最大子段an/2+1:n和相同。 （3）a1:n的最大子段和为ak(i=k=J)，且1=i=n/2,n/2+1=J=wi) 或则 m（i,j）= m(i+1,j) (0=j=wn 或则m(n,j)=0 0=jwn3、（1）、pn+1=(0,0)（2）、由pi+1qi+1, qi+1=pi+1(wi,vi)（3）、Mij=pi+1qi+1Pi=Mij其中的受控点pi+1qi+1其中的受控（4）、重复（2）-（3）直到求出P11. 在一个算法中调用另一个算法时，系统需在运行被调用算法之前完成哪些工作？同时从被调用算法返回调用算法需完成哪些工作？答：在一个算法中调用另一算法时，系统需在运行被调用算法之前先完成三件事：（1） 将所有实参指针、返回地址等信息传递给被调用算法；（2） 为被调用算法的局部变量分配存储区；（3） 将控制转移到被调用算法的入口。在从被调用算法返回调用算法时需完成三件事：（1） 保存被调用算法的计算结果；（2） 释放分配给被调用算法的数据区；（3） 依照被调用算法保存的返回地址将控制转移到调用算法。2. 动态规划算法求解问题的步骤？答：动态规划法适用于解最优化问题。通常可以按以下4个步骤设计：（1） 找出最优解的性质，并刻画其结构特征；（2） 递归地定义最优值；（3） 以自底向上的方式计算最优值；（4） 根据计算最优值时得到的信息构造最优解。3. 线性规划法中单纯形算法的基本步骤？答：步骤一选入基变量。步骤二选离基变量。步骤三做转轴变换。步骤四转步骤一。4. 分治法的基本思想和原理是什么？答：分治法的基本思想是将一个规模为的问题分解为个规模较小的子问题，这些子问题互相独立且与原问题相同。递归地解这些子问题，然后将各子问题的解合并得到原问题的解。5. 利用回溯法解决问题包含哪些步骤？答：利用回溯法解题常包含以下3步骤：（1） 针对所给问题，定义问题的解空间；（2） 确定易于搜索的解空间结构；（3） 以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。五分析题（36分）1求下列函数的渐进表达式：3n2+10n; n2/10+2n; 21+1/n; logn3; 10log3n分析与解答：3n2+10n=O(n2); n2/10+2n=O(2n); 21+1/n=O(1); logn3=O(logn); 10log3n=O(n)2讨论O(1)和O(2)的区别。分析与解答：根据符号O的定义易知O(1)=O(2)。用O(1)或O(2)表示同一个函数时，差别仅在于其中的常数因子。3按渐近阶排列表达式按照渐近阶从低到高的顺序排列以下表达式：4n2，logn，3n，20n，2，n2/3。又n!应该排在哪一位？分析与解答：按渐近阶从低到高，函数排列顺序如下：2，logn，n2/3，20n，4n2，3n，n！。4.算法效率(1)假设某算法在输入规模为n时计算时间为T(n)=3*2n。在某台计算机上实现并完成该算法的时间为t秒。现有另一台计算机，其运行速度为第一台的64倍，那么在这台新机器上用同一算法在t秒内能解输入规模为多大的问题？(2)若上述算法的计算时间改进为T(n)=n2，其余条件不变，则在新机器上用t秒时间能解输入规模为多大的问题？(3)若上述算法的计算时间进一步改进为T(n)=8，其余条件不变，那么在新机器上用t秒时间能解输入规模为多大的问题？分析解答：(1)设新机器用同一算法在t秒内能解输入规模为n1的问题。因此有：t=3*22=3*2n1/64，解得你n1=n+6。(2)n12=64n2n1=8n。(3)由于T(n)=常数，因此算法可解任意规模的问题。5阶乘函数阶乘函数可递归地定义为：int factorial(int n)if(n=0) return 1;return n* factorial(n-1);6Fibonacci数列无穷数列1，1，2，3，5，8，13，21，34，55，称为Fibonacci数列。它可以递归地定义为：请对这个无穷数列设计一个算法，并进行描述（自然语言描述和VC+描述）.第n个Fibonacci数可递归地计算如下：intfibonacci(int n) if (n 1时，取y1=1;yk=0;yi=xi,1in,ik,则因此，()是所给最有装载问题的可行解。另一方面，由知，()是满足贪心选择性质的最优解。所以，最优装载问题具有贪心选择性质。(2)最优装载问题可用贪心算法求解。采用重量最轻者先装的贪心选择策略，可产生最优装载问题的最优解。具体算法描述如下。templatevoidLoading(int x, Type w, Type c, int n)int *t = ne