算法考试试题及答案

1、一、填空题(本题 10分，每空1分)1、 算法的复杂性是的度量，是评价算法优劣的重要依据。2、 设n为正整数，利用大“0( )”记号，将下列程序段的执行时间表示为n的函数，则下面程序段的时间复杂度为。i=1; k=0;while(i n) k=k+10*i;i+; 3、 计算机的资源最重要的是和资源。因而，算法的复杂性有和 之分。n 24、f(n)= 6 x 2+n , f(n)的渐进性态 f(n)= 0( )5、 递归是指函数 或者通过一些语句调用自身。6、 分治法的基本思想是将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相且与原问题相同。、选择题(本题20分，每小题2分)1、

2、分支限界法与回溯法都是在问题的解空间树T上搜索问题的解,二者() NO 时有f(N) w Cg(N),则称函数f(N)当N充分大时有上界 g(N),记作f(N)=O(g(N), 即f(N)的阶()g(N)的阶。A.不咼于B.不低于C.等价于D.逼近6、对于含有n个兀素的子集树问题，最坏情况下其解空间的叶结点数目为()A.n!B.2nC.2n+1 -1D. 2n-17、程序可以不满足以下()特征A.输入B.输出C.确定性D.有限性8、以下()不能在线性时间完成排序A.计数排序B.基数排序C.堆排序D.桶排序9、以下()不一定得到问题的最优解A.贪心算法B.回溯算法C.分支限界法D.动态规划法10

3、、以下()不包括在图灵机结构中A.控制器 B.读写磁头C. 计算器D.磁带三、简答题(本题 20分，每小题 5分)1、设有n=2k个运动员要进行循环赛，现设计一个满足以下要求的比赛日程表： 每个选手必须与其他n-1名选手比赛各一次； 每个选手一天至多只能赛一次； 循环赛要在最短时间内完成。(1) 如果n=2k，循环赛最少需要进行几天；(2) 当n=22 S= Q=VG while Q3do u=min(Q)S=SU ufor each vertex v adju II 所有 u 的邻接点 vdo4 2、某工厂预计明年有N个新建项目，每个项目的投资额wk及其投资后的收益投资总额为 C,问如何选择

4、项目才能使总收益最大。In vest-Program() for (j=0;j1;i-)in t jMax=mi n(wi-1,c);for(j=0;jv=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后问题为非0值，否则(1)用二维数组ANN存储皇后位置，若第i行第j列放有皇后，则Aij值为0。(2)分别用一维数组MN、L2*N-1 、R2*N-1表示竖列、左斜线、右斜线是否放有棋子，有则值为1,否则值为0。for(j=0;j 014/while (15i+；)从串

5、首开始找delete( n,i); /删除串n的第i个字符s-；while (length(n)1)& (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的初始值为1，2，3perm(i nt b, i nt i

6、) int k,j;if(i=N)输出；elsefor(j=i;jdu+w(u,v)(2) Init-single-source(G,s)(3) (4) Relax(u,v,w)2、( 5) mnj=O;(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) (ile ngth( n)&(n i ni+1)五、 阐述prim算法的基本思想(本题1

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