一、填空题
1、 算法的复杂性是 算法效率
2、 的度量，是评价算法优劣的重要依据。 1、 设n为正整数，利用大“O(·)”记号，将下列程序段的执行时间表示为n的函数，则
下面程序段的时间复杂度为 O(n) 2、 。 i=1; k=0;
while(i 3、 计算机的资源最重要的是 时间 和 空间 资源。因而，算法的复杂性有 时间复杂度 和 空间复杂度之分。 3、 f(n)= 6×2n+n2，f(n)的渐进性态f(n)= O( 2n 4、 ) 5、 递归是指函数 直接 或者 间接 通过一些语句调用自身。 4、 分治法的基本思想是将一个规模为n的问题分解为k个规模较小的子问题，这些子问 题互相 独立 6、 且与原问题相同。 二、选择题（本题20分，每小题2分） 1、分支限界法与回溯法都是在问题的解空间树T上搜索问题的解,二者( B )。 A.求解目标不同,搜索方式相同 B.求解目标不同,搜索方式也不同 C.求解目标相同,搜索方式不同 D.求解目标相同,搜索方式也相同 2、回溯法在解空间树T上的搜索方式是( A)。 A.深度优先 B.广度优先 C.最小耗费优先 D.活结点优先 3、在对问题的解空间树进行搜索的方法中,一个活结点最多有一次机会成为活结点的是( B )。 A.回溯法 B.分支限界法 C.回溯法和分支限界法 D.回溯法求解子集树问题 4、以下关于判定问题难易处理的叙述中正确的是( C )。 A.可以由多项式时间算法求解的问题是难处理的 B.需要超过多项式时间算法求解的问题是易处理的 C.可以由多项式时间算法求解的问题是易处理的 D.需要超过多项式时间算法求解的问题是不能处理的 5、设f(N),g(N)是定义在正数集上的正函数,如果存在正的常数C和自然数N0,使得当N≥N0时有f(N)≤Cg(N),则称函数f(N)当N充分大时有上界g(N),记作f(N)=O(g(N)),即f(N)的阶( A )g(N)的阶。 A.不高于 B.不低于 C.等价于 D.逼近 6、对于含有n个元素的子集树问题,最坏情况下其解空间的叶结点数目为( B )。 A.n! B.2n C.2n+1-1 D. 2n-1 7、程序可以不满足以下( D )特征 A.输入 B.输出 C.确定性 D.有限性 8、以下( C )不能在线性时间完成排序 1 A.计数排序 B.基数排序 C.堆排序 D.桶排序 9、以下( A )不一定得到问题的最优解 A.贪心算法 B.回溯算法 C.分支限界法 D.动态规划法 10、以下（ C ）不包括在图灵机结构中 A. 控制器 B. 读写磁头 C.计算器 D. 磁带 三、简答题（本题20分，每小题5分） 1、设有n=2k个运动员要进行循环赛，现设计一个满足以下要求的比赛日程表： ①每个选手必须与其他n-1名选手比赛各一次； ②每个选手一天至多只能赛一次； ③循环赛要在最短时间内完成。 （1）如果n=2 ，循环赛最少需要进行几天； （2）当n=22=4时，请画出循环赛日程表。 k 解: （1）2-1天（2分）； （2）当n=22=4时，循环赛日程表（3分）。 k 1 2 3 2 1 4 3 4 1 4 3 2 2、简述最优子结构性质。 4 3 2 1 某个问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质。 3、简单描述回溯法基本思想。 回溯法的基本思想是在一棵含有问题全部可能解的状态空间树上进行深度优先搜索，解为叶子结点。 搜索过程中，每到达一个结点时，则判断该结点为根的子树是否含有问题的解，如果可以确定该子树中不含有问题的解，则放弃对该子树的搜索，退回到上层父结点，继续下一步深度优先搜索过程。在回溯法中，并不是先构造出整棵状态空间树，再进行搜索，而是在搜索过程，逐步构造出状态空间树，即边搜索，边构造。 5、 何谓P、NP问题 P(Polynomial问题)：也即是多项式复杂程度的问题。 NP就是Non-deterministic Polynomial的问题，也即是多项式复杂程度的非确定性问题。 6、 四、算法填空（本题30分，每空2分） 1、Dijkstra算法是解单源最短路径问题的贪心算法。请你阅读下面伪代码并在空白处填上适当的代码。 // G是一个n个结点的有向图，它由成本邻接矩阵w[u,v]表示，D[v]表示结点v到源结 2 点s的最短路径长度，p[v]记录结点v的父结点。 Init-single-source(G,s) 1.for each vertex v∈V[G] 2.do {d[v]=∞ p[v]=NIL} 3. d[s]=0 Relax(u,v,w) 1.if d[v]> d[u]+w[u,v] 2.then {d[v]=d[u]+w[u,v] p[v]=u } dijkstra(G,w,s) 1. init-single-source(G,s) 2. S=Φ 3. Q=V[G] 4.while Q<> Φ do u=min(Q) S=S∪{u} for each vertex v∈adj[u] //所有u的邻接点 v do relax(G,v,w) 2、某工厂预计明年有N个新建项目，每个项目的投资额 w[k]及其投资后的收益 v[k]已知。投资总额为C，问如何选择项目才能使总收益最大。 Invest-Program( ) { for (j=0;j<=C;j++) （5）m[n][j]=0; for (j=w[n];j<=C;j++) m[n][j]=v[n]; for (i=n-1;i>1;i--) { int jMax=min(w[i]-1,c); for(j=0;j<=jMax;j++) m[i][j]= （6）m[i+1][j] ; for (j=w[i];j<=C;j++) m[i][j]=max( （7）m[i+1][j],m[i+1][j-w[i]]+v[i] ); } m[1][c]=m[2][c]; if( （8）c>=w[1] ) m[1][c]=max(m[1][c],m[2][c-w[1]]+v[1]); } 3 3、N后问题 (1)用二维数组A[N][N]存储皇后位置,若第i行第j列放有皇后,则A[i][j]为非0值,否则值为0。 (2)分别用一维数组M[N]、L[2*N-1]、R[2*N-1]表示竖列、左斜线、右斜线是否放有棋子，有则值为1,否则值为0。 for(j=0;j if( !M[j]&&!L[i+j]&&!R[i-j+N] ) /*安全检查 { A[i][j]=i+1; /*放皇后*/ 10 M[j]=L[i+j]=R[i-j+N]=1; ； if(i==N-1) 输出结果； else try(i+1,M,L,R,A)11 ；; /*试探下一行*/ 1 A[i][j]=0 2 ； /*去皇后*/ M[j]=L[i+j]=R[i-j+N]=013 ；; } 4、通过键盘输入一个高精度的正整数n(n的有效位数≤240)，去掉其中任意s个数字后，剩下的数字按原左右次序将组成一个新的正整数。编程对给定的n 和s，寻找一种方案，使得剩下的数字组成的新数最小。 delete（n ,s) {输入s, n; while（ s > 0 ） { i=1 //从串首开始找 while ( (i delete(n,i); //删除串n的第i个字符 s--; } while (length(n)>1)&& (n[1]=‘0’) delete(n,1); //删去串首可能产生的无用零 输出n; } 五、请你阐述prim算法的基本思想。并给出下图的最小生成树（要求画出生成树，分析过程可以省略）（本题10分） 4
