计算机算法试题含答案

1、算法设计与分析试卷一、填空题(20分，每空2分)1、算法的性质包括输入、输出、 、有限性。2、动态规划算法的基本思想就将待求问题 、先求解子问题，然后从这些子问题的解得到原问题的解。3、设计动态规划算法的 4个步骤：(1) 找出，并刻画其结构特征。(2) 。(3) 。(4) 根据计算最优值得到的信息， 。4、流水作业调度问题的johnson算法：(1) 令 N1 ,N2=i|ai>=bj;(2) 将N1中作业依ai的。5、 对于流水作业高度问题，必存在一个最优调度n,使得作业n( i)和 n (i+1 ) 满足 Johnson 不等式。6、 最优二叉搜索树即是的二叉搜索树。二、综合题(5

2、0分)1、当(a1,a2,a3,a4,a5,a6) =(-2,11,-4,13,-5,-2)时，最大子段和为刀ak(2v=k<=4) (5 分)2、 由流水作业调度问题的最优子结构性质可知，T (N , 0) = (5 分)3、最大子段和问题的简单算法(10分)int maxsum(i nt n ,i nt *a,i nt & bestj)in tsum=0;for (i nt i=1;i<=n ;i+)for (in t j=i;j<=n ;j+)int thissum=0;for(i nt k=i;k<=j;k+);if(thissum>sum)sum

3、=thissum; ?bestj=j;return sum;4、设计最优二叉搜索树问题的动态规划算法OptimalBinarysearchTree?(15 分)* w)；Void OptimalB in arysearchTree(i nt a,i nt n ,i nt * * m, int *for(i nt i=0;i<=n;i+)wi+1i=ai; mi+1i=for(i nt r=0;r <n 丁+)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+

4、)int t=mik-1+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)=(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 )建立怎样 的递归式 ? (10 分 )3、 0 1

5、背包求最优值的步骤分为哪几步？(10 分)参考答案：填空题 ：确定性 分解成若干个子问题最优解的性质递归地定义最优值 以自底向上的方式计算出最优值构造最优解 i|ai<bi ai 的非减序排序；将 N2 中作业依 bi 的 非增序排序minb 頑),ani+i) > minb 頑+i),ano 最小平均查找长度综合题： 20 minai+T(N-i,bi)(1=<i<=n)thissum+=ak besti=i 0 mi+1jt<mij法一： min(ai,bj)<=min(aj,bi)因为 min(a1,b2)<=min(a2,b1)所以1-2(先1

6、后2)由 min(a1,b3)<=min(a3,b1)得 1 - 3 (先 1 后 3)同理可得：最后为 1 -3-4-2法二： johnson 算法思想N1= 1 , 3, 4 N2 = 2N11= 1 , 3, 4N12= 2所以 N11 -N12得：1-3-4-2简答题：1 、 ( 1 )a1 :n 的最大子段和与 a1:n/2 的最大子段和相同。 ( 2) a1:n 的最大子段和与的最大子段 an/2+1:n 和相同。(3) a1:n的最大子段和为刀ak(i=vkv=J)，且 1<=i<=n/2,n/2+1<=J<=n 。(j>=wi)2、(1)m(

7、i,j)=maxm(i+1,j),m(i+1,j-wi)+ui或则 m(i,j ) = m(i+1,j)(0<=j<wi)(2) m(n,j)=unj>=wn或则m(n,j)=00<=j<wn3、(1)、 pn+1=(0,0)(2) 、由 pi+1 -qi+1,qi+1=pi+1(wi,vi)(3) 、Mij=pi+1 U qi+1Pi=Mij 其中的受控点=pi+1 U qi+1其中的受控(4) 、重复( 2) - (3)直到求出 P11. 在一个算法中调用另一个算法时，系统需在运行被调用算法之前完成哪些工 作？同时从被调用算法返回调用算法需完成哪些工作？答：在

8、一个算法中调用另一算法时，系统需在运行被调用算法之前先完成三 件事：( 1) 将所有实参指针、返回地址等信息传递给被调用算法；(2) 为被调用算法的局部变量分配存储区；(3) 将控制转移到被调用算法的入口。 在从被调用算法返回调用算法时需完成三件事：( 1) 保存被调用算法的计算结果；(2) 释放分配给被调用算法的数据区；( 3) 依照被调用算法保存的返回地址将控制转移到调用算法。2. 动态规划算法求解问题的步骤？答：动态规划法适用于解最优化问题。通常可以按以下 4 个步骤设计：（ 1） 找出最优解的性质，并刻画其结构特征；（ 2） 递归地定义最优值；（ 3） 以自底向上的方式计算最优值；（

9、4） 根据计算最优值时得到的信息构造最优解。3. 线性规划法中单纯形算法的基本步骤？答：步骤一选入基变量。步骤二选离基变量。步骤三做转轴变换。步骤四转步骤一。4. 分治法的基本思想和原理是什么？答：分治法的基本思想是将一个规模为n的问题分解为k个规模较小的子问 题，这些子问题互相独立且与原问题相同。递归地解这些子问题，然后 将各子问题的解合并得到原问题的解。5. 利用回溯法解决问题包含哪些步骤？答：利用回溯法解题常包含以下 3 步骤：（1）针对所给问题，定义问题的解空间；（2）确定易于搜索的解空间结构；3) 以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。五分析题( 36 分)

10、1求下列函数的渐进表达式：3n2+10n; n2/10+2n; 21+1/n; logn 3; 10log3n分析与解答：3n2+10n=O(n 2);n2/10+2 n=O(2 n);21+1/n=O(1); logn3=O(logn);10log3 n=O(n)2 讨论0(1)和0(2)的区别。分析与解答：根据符号 0 的定义易知 0(1)=0(2) 。用 0(1)或 0(2)表示同一个函数时，差别仅在于其中的常数因子。3 按渐近阶排列表达式按照渐近阶从低到高的顺序排列以下表达式：4n2, logn , 3n, 20n , 2, n2/3。又n!应该排在哪一位？分析与解答：按渐近阶从低到高

11、，函数排列顺序如下：2， logn， n2/3， 20n， 4n2， 3n， n！。4. 算法效率(1) 假设某算法在输入规模为 n时计算时间为T(n)=3*2 n。在某台计算机上实现并完成该算法的时间为t秒。 现有另一台计算机， 其运行速度为第一台的 64 倍， 那么在这台新机器上用同一算法在 t 秒内能解输 入规模为多大的问题？(2) 若上述算法的计算时间改进为 T(n)=n 2，其余条件不变，则在新机器上用 t 秒时间能解输入规模为多 大的问题？(3) 若上述算法的计算时间进一步改进为 T(n)=8 ，其余条件不变，那么在新机器上用 t 秒时间能解输入 规模为多大的问题？分析解答：(1)

12、 设新机器用同一算法在t秒内能解输入规模为n1的问题。因此有：t=3*2 2=3*2n1/64，解得你n1= n+622(2) n1 2=64n2? n1=8n。(3) 由于 T(n)= 常数，因此算法可解任意规模的问题。5. 阶乘函数阶乘函数可递归地定义为：int 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,，称为 Fib on acci数列。它可以递归地定义为： 请对这个无穷数列设计一个算法，并进行描述(自然语言描述

13、和VC+ 描述) .第n个Fibonacci数可递归地计算如下：intfibonacci (int n)if (n <= 1) return 1; returnfibonacci (n-1)+fibonacci (n-2);7循环赛日程表设有n=2k个运动员要进行兵乓球循环赛。现在要设计一个满足以下要求的比赛日程表：(1) 每个选手必须与其他 n-1 个选手各赛一次；(2) 每个选手一天只能赛一次；(3) 循环赛一共进行 n-1 天。请设计一个算法解决以上问题,并进行描述(自然语言和C+ 语言)按分治策略, 将所有的选手分为两半, n 个选手的比赛日程表就可以通过为 n/2 个选手设计的

14、比赛日程表 来决定。递归地用对选手进行分割,直到只剩下2个选手时,比赛日程表的制定就变得很简单。这时只要让这 2 个选手进行比赛就可以了。8 有一批集装箱要装上一艘载重量为c的轮船。其中集装箱i的重量为 Wi。最优装载问题要求确定在装载体积不受限制的情况下,将尽可能多的集装箱装上轮船。分析回答以下两个问题：(1) 分析以上最优装载问题具有贪心选择性质(2) 用 C+ 程序进行正确的算法描述 分析与解答： 设集装箱已依其重量从小到大排序，(X1,X2，,Xn)是最有装载问题的一个最优解。又设k=mini|Xi=1。易知，如果给定的最有装载问题有解，则1< k< n。当k=1时，(X1,X2,Xn)是满足贪心选择性质的最优解。当 k>1 时，取 y1=1;y k=O；y i =Xi,1<i < n,i 工 k,贝U因此, () 是所给最有装载问题的可行解。另一方面,由知, () 是满足贪心选择性质的最优解。所以,最优装载问题具有贪心选择性质。 (2)最优装载问题可用贪心算法求解。采用重量最轻者先装的贪心选择策略,可产生最优装载问