算法设计与分析试卷
一、填空题（20分，每空2分）
1、算法的性质包括输入、输出、＿确定性＿＿、有限性。
2、动态规划算法的基本思想就将待求问题＿＿分解成若干个
子问题＿＿＿、先求解子问题，然后从这些子问题的解得
到原问题的解。
3、设计动态规划算法的4个步骤：
（1）找出＿＿最优解的性质＿＿，并刻画其结构特征。
（2）＿＿递归的定义最优值＿＿＿＿＿。
（3）＿＿以自底向上的方式计算出最优值＿＿＿＿＿。
（4）根据计算最优值得到的信息，＿＿构造最优解＿＿＿＿＿。
4、流水作业调度问题的johnson算法：
（1）令N1=＿{i|ai<bi}＿＿,N2={i|ai>=bj};
（2）将N1中作业依ai的＿非减序排序，将N2中作业依bi 的非增序排序＿＿。
5、对于流水作业高度问题，必存在一个最优调度π，使得作业π（i）和π（i+1）满足Johnson不等式＿min{bπ(i),aπ(i+1)}≥min{bπ(i+1),aπ(i)}＿＿＿。
6、最优二叉搜索树即是＿最小平均查找时间＿＿的二叉搜索树。
二、综合题（50分）
1、当（a1,a2,a3,a4,a5,a6）=(-2,11,-4,13,-5,-2)时，最大子段和为∑ak(2<=k<=4)＿＿＿20＿（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++)＿＿thissum+=a【k】＿＿＿;
if(thissum>sum){
sum=thissum;
＿＿besti=i＿＿＿＿；
bestj=j;}
}
return sum;
}
4、设计最优二叉搜索树问题的动态规划算法
OptimalBinarysearchTree? (15分)
Void OptimalBinarysearchTree(int a,int n,int * * m, int * * w) {
for(int i=0;i<=n;i++) {w[i+1][i]=a[i]; m[i+1][i]=＿0＿＿＿;} for(int r=0;r<n;r++)
for(int i=1;i<=n-r;i++){
int j=i+r;
w[i][j]=w[i][j-1]+a[j]+b[j];
m[i][j]=＿m[i+1][j]＿＿＿＿＿;
s[i][j]=i;
for(int k=i+1;k<=j;k++){
int t=m[i][k-1]+m[k+1][j];
if(＿t<m[i][j]＿＿＿＿) {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|ai<bi} ai的非减序排序；将N2中作业依
bi的非增序排序min{bπ(i),aπ(i+1)}≥min{bπ(i+1),aπ(i)}
最小平均查找长度
综合题：20 min{ai+T(N-{i},bi)}(1=<i<=n) thissum+=a[k] besti=i 0 m[i+1][j] t<m[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<=j<wi)
（2）m(n,j)=un j>=wn 或则
m(n,j)=0 0<=j<wn
3、（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]。