《计算机算法试题》由会员分享，可在线阅读，更多相关《计算机算法试题（9页珍藏版）》请在装配图网上搜索。
1、算法设计与分析试卷一、填空题(20分，每空2分)1、算法的性质包括输入、输出、有限性。2、动态规划算法的基本思想就将待求问题、先求解子问题，然后从这些子问题的解得到原问题的解。3、设计动态规划算法的4个步骤:找出，并刻画其结构特征。(2)(3)(4)根据计算最优值得到的信息,4、流水作业调度问题的johnson算法: 令N1=,N2=i|ai=bj;(2) 将N1中作业依ai的5、对于流水作业高度问题，必存在一个最优调度n 使得作业 n (i)和 n (i+1)满足 Johnson 不等式。6、最优二叉搜索树即是的二叉搜索树。二、综合题(50分)1、当(a1,a2,a3,a4,a5,a6) =
2、(-2,11,-4,13,-5,-2)时，最大子段和为E ak(2=k=4)(5分)2、由流水作业调度问题的最优子结构性质可知，T (N, 0) =_(5分)3、最大子段和问题的简单算法（10分）int maxsum (int n,int *a,i nt & bes tj)intsum=0;for (int i=1;i二n;i+)for (int j=i;j=n;j+)int thissum=0;for(int k=i;ksum) sum=thissum;bestj二j;return sum;4、设计最优二叉搜索树问题的动态规划算法OptimalBinarysearchTree?(15 分)V
3、oid Opti malBinarysearchTree(i nt a,i nt n,int * * m, int* * w)for(int i=0;i=n;i+)wi+1i=ai; mi+1i =;for(int r=O;rn;r+)for(i nt i=1;i=n-r;i+)int j=i+r;wij=wij-1+aj+bj;mij=;sij=i;for(int k=i+1;k=j;k+)int t=mikT+mk+1j;if() mij= t; sij=k;mij= t; sij=k;5 、设 n=4,(a1,a2,a3,a4) = (3,4,8, 10),(b1,b2,b3,b4) =
4、 (6,2,9,15)用两种方法求4个作业的最优调度方案并计算其最优值？（15分） 三、简答题（30分）1、将所给定序列a1:n分为长度相等的两段a1:n/2和 an/2+1:n，分别求出这两段的最大子段和，则a1:n的最大 子段和有哪三种情形？（10 分） 答: 2、由01背包问题的最优子结构性质，可以对m （i,j）建3、01背包求最优值的步骤分为哪几步？（10分）参考答案：填空题：确定性分解成若干个子问题最优解的性质递归地定义最优值以自底向上的方式计算出最优值构造最优解iaibiai的非减序排序；将N2中作业依bi的非增序排序minbn（i）,an（i+i）鼻minbn（i+i）,an（
5、i） 最小平均查找长度综合题：20minai+T(N-i,bi)(1=i=n)thissum+=akt mijbes ti=i0mi+1j法一：min(ai,bj)=min(aj,bi) 因为 min(a1,b2)=min(a2,b1) 所以2(先1后2)由 min(a1,b3)=min(a3,b1) 得 3 (先1后3) 同理可得：最后为1f 342 法二：johnson算法思想N1=1, 3, 4N2=2N】1=1, 3, 4N】2=2所以 N】1fN】2得：1亠 34 2简答题：1、(1) a1:n的最大子段和与a1:n/2的最大子段和相同。(2) a1:n的最大子段和与的最大子段an/
6、2+1:n和相同。(3 ) a1:n的最大子段和为E ak(i=k=J),且1=i=n/2,n/2+1=J=wi)或则 m (i,j) = m(i+1,j)(0=j=wn或则m(n,j)=00=j 0int factorial(int n)if(n=0) return 1; return n* factorial(n-1);6. Fibonacci 数列无穷数列1, 1, 2, 3, 5, 8, 13, 21, 34, 55,，称为Fibonacci数列。它可以递归 地定义为：1n二0F (n) =1请对这个无穷数列设计一个算法，并进行描述(自然语言描述和VC+描述). 第n个Fibonacc
7、i数可递归地计算如下：intfibonacci(int n)if (n 1 时，取 y =1;y =0;y =x ,1iWn,iMk,贝1ki i因此，()是所给最有装载问题的可行解。另一方面，由知，()是满足贪心选择性质的最优解。所以，最优装载问题具有贪心 选择性质。(2) 最优装载问题可用贪心算法求解。采用重量最轻者先装的贪心选择策略，可产生最优 装载问题的最优解。具体算法描述如下。templateclass TypevoidLoading (int x, Type w, Type c, int n)int *t 二 new int n+1;Sort(w, t, n);for (int i 二 1; i 二 n; i+) xi = 0;for (int i 二 1; i二 n & wti二 c; i+) x ti = 1; c 二 wti;
计算机算法试题
