算法考试试题及答案

一、填空题本题10分，每空1分

1、算法的复杂性是欧I度量，是评价算法优劣的重要根据

2、设n为正整数，运用大“・”记号，将下列程序段日勺执行时间表达为n的函数，则下面程序段区J时间复杂度为oi=l;k=0;whilein{k=k+10*i;i++;}

3、计算机的资源最重要的是和资源因而，算法的复杂性有和之分

4、fn=6x2n+n2,fnMl渐进性态fn=

05、递归是指函数或者通过某些语句调用自身

6、分治法的基本思想是将一种规模为n的问题分解为k个规模较小的子问题，这些子问题互相且与原问题相似

二、选择题本题20分，每题2分

1、分支限界法与回溯法都是在问题的解空间树T上搜索问题时解，两者A.求解H日勺不同,搜索方式相似B.求解目的不同,搜索方式也不同C.求解目时相似，搜索方式不同D.求解目的;相似,搜索方式也相似

2、回溯法在解空间树T上的搜索方式是A.深度优先B.广度优先C,最小耗费优先D,活结点优先

3、在对问题的解空间树进行搜索的措施中，一种活结点最多有一次机会成为活结点日勺是oA.回溯法B.分支限界法C.回溯法和分支限界法D.回溯法求解子集树问题

4、如下有关鉴定问题难易解决欧I论述中对的的是A.可以由多项式时间算法求解H勺问题是难解决日勺B.需要超过多项式时间算法求解的问题是易解决的C.可以由多项式时间算法求解日勺问题是易解决日勺D.需要超过多项式时间算法求解的问题是不能解决的

5、设fN,gN是定义在正数集上的|正函数,如果存在正欢J常数C和自然数NO,使得当NNO时有f NCg N,则称函数f N当N充足大时有上界gN,记作f N=0g N，即f N日勺阶gN的阶A.不高于B.不低于C.等价于D.逼近

6、对于具有n个元素的子集树问题，最坏状况下其解空间的J叶结点数目为A.n!B.2n C.2n+1-l D.2-

17、程序可以不流是如下特性A.输入B.输出C.拟定性D.有限性

8、如下下就在线性时间完毕排序C.堆排序D.桶排序A.计数排序B.基数排序

9、如下不一定得到问题时最优解C.分支限界法D.动态规划法A.贪心算法B.回溯算法

10、如下不涉及在图灵机构造中A.控制器B.读写磁头C.计算器D.磁带

三、简答题本题20分，每题5分

1、设有好外个运动员要进行循环赛，现设计一种满足如下规定日勺比赛日程表

①每个选手必须与其他nT名选手比赛各一次；

②每个选手一天至多只能赛一次；

③循环赛要在最短时间内完毕1如果好什，循环赛至少需要进行几天；2当n=

2、4时，请画出循环赛日程表

2、简述最优子构造性质

3、简朴描述回溯法基本思想

4、何谓P、NP问题

四、算法填空本题30分，每空2分

1、Dijkstra算法是解单源最短途径问题的贪心算法请你阅读下面伪代码并在空白处填上合适的代码//G是一种n个结点欧I有向图，它由成本邻接矩阵w[u,v]表达，D[v]表达结点v到源结点s的最短途径长度，p[v]记录结点v日勺父结点Tnit-single-sourceG,s

1.for eachvertex v^V[G]

2.do{d[v]=8p[v]=NIL}

3.d[s]=0Relax u,v,w

1.if

12.then{d[v]=d[u]+w[u,v]p[vU}di jkstraG,w,s

1.______2______

2.S=

03.Q=V[G]

4.while Q3do u=minQS=SU{u}for eachvertex v^adj[u]〃所有u日勺邻接点vdo________4______

2、某工厂估计来年有N个新建项目，每个项目日勺投资额w[k]及其投资后的收益v[k]已知投资总额为C,问如何选择项目才干使总收益最大Invest-Program{for j=0；j〈=C;j++5for j=w[n];j=C;j++m[n][j]=v[n];for i=n-l;il;i--{int jMax=minw[i]-l,c;forj=0;j=jMax;j++m[i][j]=6;for j=w[i];j=C;j++m[i][j]=max7;m[l][c]=m

[2][c];if8m[l][c]=maxm[l][c],m

[2][c-w[l]]+v[l];

3、N后问题1用二维数组A[N][N]存储皇后位置,若第i行第j列放有皇后,则A[i][j]为非0值,否则值为Oo2分别用一维数组M[N]、L[2*N-1]、R[2*NT]表达竖列、左斜线、右斜线与否放有棋子,有则值为1,否则值为0forj=0;jN;j++if9/*安全检查*/{A[i][j]=i+l;/*放皇后*/10;ifi==N-l输出成果；else11；;/*试探下一行*/12；/*去皇后*/13；;

4、通过键盘输入一种高精度的正整数nn的有效位数W240,去掉其中任意s个数字后，剩余的数字按原左右顺序将构成一种新的正整数编程对给定日勺n和s,寻找一种方案，使得剩余欧I数字构成区I新数最小delete n,s{输入s,n;whiles0{14〃从串首开始找while15i++；delete n,i;//删除串n H勺第i个字符s—；while lengthn1n[l]=Odeleten,1;〃删去串首也许产生的J无用零输出n;

五、请你论述prim算法的基本思想并给出下图的最小生成树规定画出生成树，分析过程可以省略本题10分

六、算法分析题本题10分数字全排列问题任意给出从1到N日勺N个持续的自然数的多种排列如N=3时，共有如下6种排列方式123,132,213,231,312,321算法描述如下画出N=3时递归调用时堆栈变化状况，写出相相应i,j的值设数组b的初始值为1,2,3opermint b[],int i{int kJ;ifi==N输出；elseforj=i;j=num;j++{swapb[i],b[j];permb,i+l;swapb[j],b[i];}/*初始调用时i=1；*/答案:

一、填空题本题10分，每空1分

1、算法效率

2、On

3、时间、空间时间复杂度、空间复杂度

4、2n

5、直接间接

6、独立

二、选择题本题20分，每题2分1-5BABCA6-10BDCAC

三、简答题本题20分，每题5分

1、121天2分；2当『22二4时,循环赛日程表3分

12342143341243212、某个问题时最优解涉及着其子问题的最优解这种性质称为最优子构造性质

3、回溯法的基本思想是在一棵具有问题所有也许解日勺状态空间树上进行深度优先搜索，解为叶子结点搜索过程中，每达到一种结点时，则判断该结点为根的子树与否具有问题口勺解，如果可以拟定该子树中不具有问题日勺解，则放弃对该子树的搜索，退回到上层父结点，继续下一步深度优先搜索过程在回溯法中，并不是先构造出整棵状态空间树，再进行搜索，而是在搜索过程，逐渐构造出状态空间树，即边搜索，边构造

4、PPolynomial问题:也即是多项式复杂限度H勺问题NP就是Non-deterministic Polynomial日勺问题，也即是多项式复杂限度的非拟定性问题

四、算法填空本题30分，每空2分

1、1d[v]d[u]+wu,v2Init-single-sourceG,s304Relax u,v,w

2、5m[n][j]=0;6m[i+l][j]7m[i+l][j],m[i+l][j-w[i]]+v[i]8c=w[l]

3、9!M[j]!L[i+j]!R[i-j+N]10M[j]=LEi-Fj]=R[i-j+N]=l;11tryi+l,M,U R,A12A[i][j]=O13M[j]=L[i+j]=R[i-j+N]=O

4、14i=l;15ilengthnn[i]n[i+l]

五、论述prim算法的基本思想本题10分5分prim算法的基本思想是设G二V,E是连通带权图,V二｛1,2,…，n｝一方面置U二｛1｝,然后，只要U是VH勺真子集，就作如下的1贪心选择选用满足条件i£U,jeV-U,且最小的边，将顶点j添加到U中这个过程始终进行到U=V时为止在这个过程中选用到的所有边正好构成G的一棵最小生成树5分最小生成树如下1」

六、算法设计题本题10分permint b[],int i{int kJ;ifi==N输出数组各元素值；belseforj=i;j=N;j++{swapb[i],b[j];li=l,i=lpermb i+1;⑴⑵⑶4⑸6⑺8⑼9swapb[j],b[i];2i=3,j=2输出1,2,3}/*初始调用时i=l；*/3i=3,j=3输出2,3,1输出1,3,2⑺i=l,i=3尸4i=l28i=3J=2⑸i=3J=2输出』3,2输出2,1,39i=3,j=3尸6i=33输出』,32。