算法设计与分析试卷

一、 填空题（20分，每空2分）

1、 算法的性质包括输入、输出、确定性、有限性。 2、 动态规划算法的基本思想就将待求问题分解成若干个

子问题、先求解子问题，然后从这些子问题的解得到原问题的解。

3、 设计动态规划算法的4个步骤：

（1） 找出最优解的性质，并刻画其结构特征。 （2） 递归的定义最优值。

（3） 以自底向上的方式计算出最优值。

（4） 根据计算最优值得到的信息，构造最优解。 4、 流水作业调度问题的johnson算法： （1） 令N1={i|ai=bj};

（2） 将N1中作业依ai的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）

=min{ai+T(N-{i},bi)}(1=

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

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]=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分） 法

一

：

同理可得：最后为1→3→4→2

为

法二：johnson算法思想 N1＝{1，3，4} N2＝{2} N11＝{1，3，4} N12＝{2} 所以 N11→N12 得：1→3→4→2

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）

三、简答题（30分）