计算机算法试题（含答案） 

.

算法设计与分析试卷

一、 填空题（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分) 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; }

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]=＿＿＿

＿;}

.

.

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]=＿＿＿＿＿＿; s[i][j]=i;

for(int k=i+1;k<=j;k++){ int t=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|ai

综合题：20 min{ai+T(N-{i},bi)}(1=

法一：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} N11＝{1，3，4} N12＝{2} 所以 N11→N12 得：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=

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=wn 或则

m(n,j)=0 0<=j

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]

1. 在一个算法中调用另一个算法时，系统需在运行被调用算法之前完成哪些工作？同时从

被调用算法返回调用算法需完成哪些工作？

答：在一个算法中调用另一算法时，系统需在运行被调用算法之前先完成三件事：

（1） 将所有实参指针、返回地址等信息传递给被调用算法； （2） 为被调用算法的局部变量分配存储区； （3） 将控制转移到被调用算法的入口。 在从被调用算法返回调用算法时需完成三件事：

.