计算机算法设计分析试题及答案

1、精选优质文档-倾情为你奉上算法设计与分析试卷一、 填空题（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、最优二叉搜索树即是的二叉搜索树。二、综合题（5

2、0分）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;k<=j;k+);if(thissum>sum)sum=thissum;；bestj=j;

3、 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;r<n;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() mi

4、j=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分）参考答案：填空题：确定性 分解成若干个子问题 最优解的性质 递归地定

5、义最优值 以自底向上的方式计算出最优值构造最优解 i|ai<bi 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 t<mij法一：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

6、算法思想N11，3，4 N22N¹11，3，4 N¹22所以 N¹1N¹2得：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<=n。 2、（1）m（i,j）=maxm(i+1,j),m(i+1,j-wi)+ui (j>=wi) 或则 m（i,j）= m(i+1,j) (0<=j<wi)（2）m(n,j)=un j>=wn 或则m(n,j)=0 0<=j<wn3、（1）、pn+1=(0,0)（2