《算法考试试的题目及问题详解》由会员分享，可在线阅读，更多相关《算法考试试的题目及问题详解（7页珍藏版）》请在金锄头文库上搜索。
1、word、填空题此题10分，每空1分1、算法的复杂性是的度量，是评价算法优劣的重要依据。2、 设n为正整数，利用大“ 0( ) 记号，将如下程序段的执行时间表示为n的函数，如此下面程序段的时间复杂度为。i=1; k=0;while(in) k=k+10*i;i+; 3、计算机的资源最重要的是和资源。因而，算法的复杂性有和之分。4、 f(n)= 6 x 2n+ n2, f(n)的渐进性态 f(n)= O( )5、递归是指函数或者通过一些语句调用自身。6、 分治法的根本思想是将一个规模为n的问题分解为k个规模较小的子问题，这些子问题 互相且与原问题一样。.、选择题此题 20分，每一小题2分1、 分
2、支限界法与回溯法都是在问题的解空间树T上搜索问题的解，二者()。A.求解目标不同，搜索方式一样 B.求解目标不同，搜索方式也不同C.求解目标一样，搜索方式不同 D.求解目标一样，搜索方式也一样2、回溯法在解空间树 T上的搜索方式是()。3、在对问题的解空间树进展搜索的方法中，一个活结点最多有一次机会成为活结点的是()。4、以下关于判定问题难易处理的表示中正确的答案是()5、 设f(N),g(N)是定义在正数集上的正函数，如果存在正的常数C和自然数NO,使得当NNO时有f(N) Cg(N),如此称函数f(N)当N充分大时有上界 g(N),记作f(N)=O(g(N), 即f(N) 的阶()g(N)
3、的阶。6、 对于含有n个元素的子集树问题，最坏情况下其解空间的叶结点数目为()。nn+1n /-1 D. 2 -17、程序可以 不满足以下()特征8、以下()不能在线性时间完成排序9、以下()不一定得到问题的最优解10、以下不包括在图灵机结构中A.控制器B.读写磁头C.计算器D.磁带三、简答题此题 20分，每一小题5分1、设有n=2k个运动员要进展循环赛，现设计一个满足以下要求的比赛日程表： 每个选手必须与其他n-1名选手比赛各一次； 每个选手一天至多只能赛一次； 循环赛要在最短时间内完成。1如果n=2k，循环赛最少需要进展几天；2当n=22=4时，请画出循环赛日程表。2、简述最优子结构性质。
4、3、简单描述回溯法根本思想。4、何谓P、NP问题四、算法填空此题 30分，每空2分1、Dijkstra算法是解单源最短路径问题的贪心算法。请你阅读下面伪代码并在空白处填上适当的代码。/ G是一个n个结点的有向图，它由本钱邻接矩阵wu,v表示，Dv表示结点v到源结点s的最短路径长度，pv记录结点v的父结点。In it-s in gle-source(G,s)1. for each vertex v VG2. do dv=g pv=NIL3. ds=0Relax(u,v,w)1.if _J2. then dv=du+wu,vPv=udijkstra(G,w,s)1. _22. S=3. Q=VG4
5、. while Q _3do u=min(Q)S=SU ufor each vertex v adju / 所有 u 的邻接点 vdo4 2、某工厂预计明年有N个新建项目，每个项目的投资额wk与其投资后的收益 vk。投资总额为C,问如何选择项目才能使总收益最大。In vest-Program()for (j=0;j=C;j+)for (j=w n;j1;i-) int jMax=mi n(wi-1,c);for(j=0;j=jMax;j+)mij= 6;for (j=wi;j=C;j+)mij=max( 7 _J;m1c=m2c;if( 8_J_m1c=max(m1c,m2c-w1+v1);3
6、、N后问题(1)用二维数组ANN存储皇后位置，假如第i行第j列放有皇后，如此Aij 为非0值, 否如此值为0。 分别用一维数组 MN、L2*N-1 有如此值为1,否如此值为0。for(j=0;j 014 /从串首开始找while (15)i+;delete(n,i); / 删除串n的第i个字符s-;while (length(n)1)& (n1= 0)delete( n,1); /删去串首可能产生的无用零输出n;word五、请你阐述prim算法的根本思想。并给出如下图的最小生成树要求画出生成树，分析过 程可以省略此题10分BEL)*12 = 六、算法分析题此题 10分 数字全排列问题：任意给出
7、从1到N的N个连续的自然数的各种排列。如N=3时，共有以下6种排列方式：123，132，213，231，312，321。算法描述如下。画出N=3时递归调用时堆栈变化情况，写出相对应i,j的值。设数组b的初始值为1，2,3。perm(i nt b, int i)int k,j;if(i=N)输出；elsefor(j=i;jdu+w(u,v)2Init-single-source(G,s)3【4Relax(u,v,w)2、 5mnj=0;6mi+1j7mi+1j,mi+1j-wi+vi8c=w13、(9) !Mj&!Li+j&!Ri-j+N(10) Mj=Li+j=Ri-j+N=1;(11) tr
8、y(i+1,M,L,R,A)(12) Aij=0(13) Mj=Li+j=Ri-j+N=04、 14i=1;15(ilength(n)&(nini+1)五、阐述prim算法的根本思想此题 10分 (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分最小生成树如下：六、算法设计题此题10分perm(i nt b, int i) int k,j;if(i=N)输出b数组各元素值；elsefor(j=i;j=N;j+)swap(bi,bj);perm(b,i+1); (1) (2)(3)(5)(6 7)(8)(9) swap(bj,bi);(1) i=1,j=1 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,2/*初始调用时i = 1;*/# / 6
