《算法分析与设计考试复习题及参考 答案jing》由会员分享，可在线阅读，更多相关《算法分析与设计考试复习题及参考 答案jing（16页珍藏版）》请在金锄头文库上搜索。
1、一、 填空题1、 算法的复杂性是 算法效率2、 的度量，是评价算法优劣的重要依据。1、 设n为正整数，利用大“O()”记号，将下列程序段的执行时间表示为n的函数，则下面程序段的时间复杂度为 O(n)2、 。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）mnj=0; for (j=wn;j1;i-) int jMax=min(wi-1,c); for(j=0;j=jMax;j+) mij= （6）mi+1j ; for (j=wi;j=w1 )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分）prim算法的基本思想是：设G=(V,E)是连通带权图，V=1,2,n。首先置U=1，然后，只要U是V的真子集，就作如下的贪心选择：选取满足条件iU，jV-U，且cij最小的边，将顶点j添加到U中。这个过程一直进行到U=V时为止。在这个过程中选取到的所有边恰好构成G的一棵最小生成树
4、。（5分）最小生成树如下：六、算法分析题（本题10分）数字全排列问题：任意给出从1到N的N个连续的自然数的各种排列。如N=3时，共有以下6种排列方式：123，132，213，231，312，321。算法描述如下。画出N=3时递归调用时堆栈变化情况,写出相对应i,j的值。设数组b的初始值为1，2，3。perm(int b, int i)int k,j;if(i=N)输出；else 输出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
5、(9)i=3,j=3 输出3,2,1(8)i=3,j=2 输出3,1,2 for(j=i;j=num;j+) swap(bi,bj); perm(b,i+1); swap(bj,bi); /*初始调用时i = 1;*/ 答案：perm(int b, int i)int k,j;if(i=N)输出b数组各元素值；else for(j=i;j=N;j+) swap(bi,bj); perm(b,i+1); (1)(2)(3)(4)(5)(6)(7)(8)(9) swap(bj,bi); /*初始调用时i = 1;*/ 一、 简答题 ：1. 算法重要特性是什么？ 确定性、可实现性、输入、输出、有穷性2. 算法分析的目的是什么
