《算法考试试题及答案》由会员分享，可在线阅读，更多相关《算法考试试题及答案（6页珍藏版）》请在金锄头文库上搜索。
1、算法考试试题及答案一、 填空题（本题10分，每空1分）1、 算法的复杂性是 的度量，是评价算法优劣的重要依据。2、 设n为正整数，利用大“O()”记号，将下列程序段的执行时间表示为n的函数，则下面程序段的时间复杂度为 。i=1; k=0;while(in) k=k+10*i;i+; 3、 计算机的资源最重要的是 和 资源。因而，算法的复杂性有 和 之分。4、 f(n)= 62n+n2，f(n)的渐进性态f(n)= O( )5、 递归是指函数 或者 通过一些语句调用自身。6、 分治法的基本思想是将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相 且与原问题相同。二、选择题（本题20分
2、，每小题2分）1、分支限界法与回溯法都是在问题的解空间树T上搜索问题的解,二者( )。A.求解目标不同,搜索方式相同 B.求解目标不同,搜索方式也不同C.求解目标相同,搜索方式不同 D.求解目标相同,搜索方式也相同2、回溯法在解空间树T上的搜索方式是( )。A.深度优先 B.广度优先 C.最小耗费优先 D.活结点优先3、在对问题的解空间树进行搜索的方法中,一个活结点最多有一次机会成为活结点的是( )。A.回溯法 B.分支限界法 C.回溯法和分支限界法 D.回溯法求解子集树问题4、以下关于判定问题难易处理的叙述中正确的是( )。A.可以由多项式时间算法求解的问题是难处理的B.需要超过多项式时间算
3、法求解的问题是易处理的C.可以由多项式时间算法求解的问题是易处理的D.需要超过多项式时间算法求解的问题是不能处理的5、设f(N),g(N)是定义在正数集上的正函数,如果存在正的常数C和自然数N0,使得当NN0时有f(N)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.2n C.2n+1-1 D. 2n-17、程序可以不满足以下( )特征A.输入 B.输出 C.确定性 D.有限性8、以下( )不能
4、在线性时间完成排序A.计数排序 B.基数排序 C.堆排序 D.桶排序9、以下( )不一定得到问题的最优解A.贪心算法 B.回溯算法 C.分支限界法 D.动态规划法10、以下（）不包括在图灵机结构中A. 控制器 B. 读写磁头 C.计算器 D. 磁带三、简答题（本题20分，每小题5分）1、设有n=2k个运动员要进行循环赛，现设计一个满足以下要求的比赛日程表：每个选手必须与其他n-1名选手比赛各一次；每个选手一天至多只能赛一次；循环赛要在最短时间内完成。（1）如果n=2k ，循环赛最少需要进行几天；（2）当n=22=4时，请画出循环赛日程表。2、简述最优子结构性质。3、简单描述回溯法基本思想。4、
5、何谓P、NP问题四、算法填空（本题30分，每空2分）1、Dijkstra算法是解单源最短路径问题的贪心算法。请你阅读下面伪代码并在空白处填上适当的代码。/ G是一个n个结点的有向图，它由成本邻接矩阵wu,v表示，Dv表示结点v到源结点s的最短路径长度，pv记录结点v的父结点。Init-single-source(G,s)1.for each vertex vVG2.do dv= pv=NIL3. ds=0Relax(u,v,w)1.if 1 2.then dv=du+wu,v pv=u dijkstra(G,w,s)1. 2 2. S= 3. Q=VG4.while Q 3 do u=min(
6、Q) S=Su for each vertex vadju /所有u的邻接点 v do 4 2、某工厂预计明年有N个新建项目，每个项目的投资额 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)用二维数组A
7、NN存储皇后位置,若第i行第j列放有皇后,则Aij为非0值,否则值为0。(2)分别用一维数组MN、L2*N-1、R2*N-1表示竖列、左斜线、右斜线是否放有棋子，有则值为1,否则值为0。for(j=0;j 0 ） 14 /从串首开始找while ( 15 ) i+; delete(n,i); /删除串n的第i个字符 s-;while (length(n)1)& (n1=0) delete(n,1); /删去串首可能产生的无用零输出n; 五、请你阐述prim算法的基本思想。并给出下图的最小生成树（要求画出生成树，分析过程可以省略）（本题10分）六、算法分析题（本题10分）数字全排列问题：任意给出
8、从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 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+
9、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)五、阐述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数组各元素值
