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

算法设计与分析试卷一、填空题（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分)intmaxsum(intn,int*a,int&bestj){intsum=0;for(inti=1;i=n;i++)for(intj=i;j=n;j++)intthissum=0;for(intk=i;k=j;k++)＿＿＿＿＿;if(thissumsum){sum=thissum;＿＿＿＿＿＿；bestj=j;}}returnsum;}4、设计最优二叉搜索树问题的动态规划算法OptimalBinarysearchTree?(15分)VoidOptimalBinarysearchTree(inta,intn,int**m,int**w){for(inti=0;i=n;i++){w[i+1][i]=a[i];m[i+1][i]=＿＿＿＿;}for(intr=0;rn;r++)for(inti=1;i=n-r;i++){intj=i+r;w[i][j]=w[i][j-1]+a[j]+b[j];m[i][j]=＿＿＿＿＿＿;s[i][j]=i;for(intk=i+1;k=j;k++){intt=m[i][k-1]+m[k+1][j];if(＿＿＿＿＿){m[i][j]=t;s[i][j]=k;}}m[i][j]=t;s[i][j]=k;}}5、设n=4,(a1,a2,a3,a4)=(3,4,8,10),(b1,b2,b3,b4)=(6,2,9,15)用两种方法求4个作业的最优调度方案并计算其最优值？（15分）三、简答题（30分）1、将所给定序列a[1:n]分为长度相等的两段a[1:n/2]和a[n/2+1:n]，分别求出这两段的最大子段和，则a[1:n]的最大子段和有哪三种情形？(10分)答：2、由0——1背包问题的最优子结构性质，可以对m（i,j）建立怎样的递归式?(10分)3、0——1背包求最优值的步骤分为哪几步？（10分）参考答案：填空题：确定性分解成若干个子问题最优解的性质递归地定义最优值以自底向上的方式计算出最优值构造最优解{i|aibi}ai的非减序排序；将N2中作业依bi的非增序排序min{bπ(i),aπ(i+1)}≥min{bπ(i+1),aπ(i)}最小平均查找长度综合题：20min{ai+T(N-{i},bi)}(1=i=n)thissum+=a[k]besti=i0m[i+1][j]tm[i][j]法一：min(ai,bj)=min(aj,bi)因为min(a1,b2)=min(a2,b1)所以1→2(先1后2)由min(a1,b3)=min(a3,b1)得1→3（先1后3）同理可得：最后为1→3→4→2法二：johnson算法思想N1＝{1，3，4}N2＝{2}N¹1＝{1，3，4}N¹2＝{2}所以N¹1→N¹2得：1→3→4→2简答题：1、（1）a[1:n]的最大子段和与a[1:n/2]的最大子段和相同。（2）a[1:n]的最大子段和与的最大子段a[n/2+1:n]和相同。（3）a[1:n]的最大子段和为∑ak(i=k=J)，且1=i=n/2,n/2+1=J=n。2、（1）m（i,j）=max{m(i+1,j),m(i+1,j-wi)+ui}(j=wi)或则m（i,j）=m(i+1,j)(0=jwi)（2）m(n,j)=unj=wn或则m(n,j)=00=jwn3、（1）、p[n+1]={(0,0)}（2）、由p[i+1]→q[i+1],q[i+1]=p[i+1]⊕(wi,vi)（3）、Mij=p[i+1]∪q[i+1]Pi=Mij——其中的受控点＝p[i+1]∪q[i+1]——其中的受控（4）、重复（2）-（3）直到求出P[1]