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

算法设计与分析试卷填空题(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分)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(thissum>sum){sum=thissum;______;bestj=j;}}returnsum;}设计最优二叉搜索树问题的动态规划算法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;r<n;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|ai<bi}ai的非减序排序;将N2中作业依bi的非增序排序min{bπ(i),aπ(i+1)}≥min{bπ(i+1),aπ(i)}最小平均查找长度综合题:20min{ai+T(N-{i},bi)}(