算法考试试题及答案-6页

1、一、 填空题（本题10分，每空1分）1、 算法的复杂性是 的度量，是评价算法优劣的重要依据。2、 设n为正整数，利用大“O()”记号，将下列程序段的执行时间表示为n的函数，则下面程序段的时间复杂度为 。i=1; k=0;while(i du+wu,v 2.then dv=du+wu,v pv=u dijkstra(G,w,s)1. init-single-source(G,s) 2. S= 3. Q=VG4.while Q do u=min(Q) S=Su for each vertex vadju /所有u的邻接点 v do relax(G,v,w) 2、某工厂预计明年有N个新建项目，每个项

2、目的投资额 wk及其投资后的收益 vk已知。投资总额为C，问如何选择项目才能使总收益最大。Invest-Program( ) for (j=0;j=C;j+) 5 for (j=wn;j1;i-) int jMax=min(wi-1,c); for(j=0;j=jMax;j+) mij= 6 ; for (j=wi;j=C;j+) mij=max( 7 ); m1c=m2c;if( 8 )m1c=max(m1c,m2c-w1+v1);3、N后问题(1)用二维数组ANN存储皇后位置,若第i行第j列放有皇后,则Aij为非0值,否则值为0。(2)分别用一维数组MN、L2*N-1、R2*N-1表示竖列

3、、左斜线、右斜线是否放有棋子，有则值为1,否则值为0。for(j=0;j 0 ） i=1 /从串首开始找while ( (ilength(n) & ni1)& (n1=0) delete(n,1); /删去串首可能产生的无用零输出n; 五、请你阐述prim算法的基本思想。并给出下图的最小生成树（要求画出生成树，分析过程可以省略）（本题10分）六、算法分析题（本题10分）数字全排列问题：任意给出从1到N的N个连续的自然数的各种排列。如N=3时，共有以下6种排列方式：123，132，213，231，312，321。算法描述如下。画出N=3时递归调用时堆栈变化情况,写出相对应i,j的值。设数组b的初

4、始值为1，2，3。perm(int b, int i)int k,j;if(i=N)输出；else for(j=i;jdu+w(u,v) （2）Init-single-source(G,s) （3） （4）Relax(u,v,w)2、（5）mnj=0; （6）mi+1j （7）mi+1j,mi+1j-wi+vi （8）c=w13、(9) !Mj&!Li+j&!Ri-j+N(10) Mj=Li+j=Ri-j+N=1;(11) try(i+1,M,L,R,A) (12) Aij=0 (13) Mj=Li+j=Ri-j+N=0 4、（14）i=1;（15）(ilength(n)&(nini+1)五、

5、阐述prim算法的基本思想（本题10分）(5分) prim算法的基本思想是：设G=(V,E)是连通带权图，V=1,2,n。首先置U=1，然后，只要U是V的真子集，就作如下的贪心选择：选取满足条件iU，jV-U，且cij最小的边，将顶点j添加到U中。这个过程一直进行到U=V时为止。在这个过程中选取到的所有边恰好构成G的一棵最小生成树。（5分）最小生成树如下：输出2，1，3(5)i=3,j=2(4)i=1,j=2(3) i=3,j=3(1) i=1,j=1弹出、清空输出1，3，2输出1，2，3(2) i=3,j=2(7)i=1,j=3输出2，3，1(6)i=3,j=3(9)i=3,j=3输出3,2,1(8)i=3,j=2输出3,1,2六、算法设计题（本题10分）perm(int b, int i)int k,j;if(i=N)输出b数组各元素值；else for(j=i;j=N;j+) swa