算法设计与分析 期末试卷及答案)
期末试卷配套教材：
书名：算法设计与分析
作者：王红梅
出版社：清华大学出版社
期末试卷概述：
算法设计与分析试卷
填空题（20分，每空2分）
算法的性质包括输入、输出、＿＿＿、有限性。
动态规划算法的基本思想就将待求问题＿＿＿＿＿、先求解子问题，然后从这些子问题的解得到原问题的解。
设计动态规划算法的4个步骤：
找出＿＿＿＿，并刻画其结构特征。
＿＿＿＿＿＿＿。
＿＿＿＿＿＿＿。
根据计算最优值得到的信息，＿＿＿＿＿＿＿。
流水作业调度问题的johnson算法：
令N1=＿＿＿,N2={i|ai>=bj};
将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;k<=j;k++)＿＿＿＿＿;
if(thissum>sum){
sum=thissum;
＿＿＿＿＿＿；
bestj=j;}
}
return sum;
}
设计最优二叉搜索树问题的动态规划算法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]=＿＿＿＿;}
for(int r=0;r