算法复杂性分析期末复习软件05算法考试试卷

《算法复杂性分析期末复习软件05算法考试试卷》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、中南大学考试试卷2007--2008学年下学期时间门0分钟2008年6月算法复杂性分析课程48学时3学分考试形式：冈—卷专业年级：软件0501、软件0601、0602总分100分，占总评成绩坐%注：此页不作答题纸，请将答案写在答题纸上一、填空题(本题15分，每小题1分)1、算法就是一组有穷的，它们规定了解决某一特定类型问题的O2、在进行问题的计算复杂性分析之前，首先必须建立求解问题所用的计算模型。3个基本计算模型是、、。3、算法的复杂性是的度量，是评价算法优劣的重要依据。4、计算机的资源最重要的是和资源。因而，算法的复杂性有和之分。5、f(n)=6x2n+n2,f(n)的渐进性态f(

2、n)=0()6、贪心算法总是做出在当前看來的选择。也就是说贪心算法并不从整体最优考虑，它所做出的选择只是在某种意义上的07、许多可以用贪心算法求解的问题一般具有2个重要的性质:性质和性质。二、简答题(本题25分，每小题5分)1、简单描述分治法的基本思想。2、简述动态规划方法所运用的最优化原理。3、何谓最优子结构性质？4、简单描述冋溯法基本思想。5、何谓P、NP、NPC问题三、算法填空(本题20分，每小题5分)1、n后问题回溯算法⑴用二维数组A[N][N]存储皇后位置，若第i行第j列放有皇后，则A[i][j]为非0值,否则值为0o(2)分别用一维数组M[N]、L[2*N-1]、R[2*

3、N-1]表示竖列、左斜线、右斜线是否放有棋子，有则值为1,否则值为0。for(j=0;j=0;1'--)//自底向上递归计算for(c二0;1;C++)if(t[r+l][c]>t[r+l][c+1])2else3；3、Hanoi算法Hanoi(n,a,b,c)if

4、(n==l)1；else{2:3；Hanoi(n-l,b,a,c);}4、Dijkstra算法求单源最短路径d[u]:s到u的距离p[u]:记录前一节点信息Init-single-source(G,s)foreachvertexv^V[G]do{d[v]二8；}d[s]=0Relax(u,v,w)ifd[v]>d[u]+w(u,v)then{d[v]二d[u]+v[u,v];2}dijkstra(G,w,s)1.Init-single-source(G,s)2.S二①3.Q二V[G]4.whileQ<>0dou=min(Q)S=SU{u}foreachvertex3do4V6四、算

5、法理解题（本题10分）根据优先队列式分支限界法，求下图中从vl点到v9点的单源最短路径，请画出求得最优解的解空间树。要求屮间被舍弃的结点用X标记，获得中间解的结点用单圆圈O框起，最优解用双圆圈◎框起。五、算法理解题（本题5分）设有n=2k个运动员要进行循环赛，现设计一个满足以下要求的比赛F1程表：①每个选手必须与其他ml名选手比赛各一次；②每个选手一天至多只能赛一次；③循环赛要在最短时间内完成。（1）如果n=2k,循环赛最少需要进行几天；（2）当n=23=8时，请画出循环赛H程表。六、算法设计题（本题15分）分别用贪心算法、动态规划法、冋溯法设计0・1背包问题。要求：说明所使用的算法

6、策略;写出算法实现的主要步骤；分析算法的时间。七、算法设计题（本题2分）通过键盘输入一个高精度的正整数n（n的有效位数W240）,去掉其中任意s个数字后，剩下的数字按原左右次序将组成一个新的正整数。编程对给定的n和s,寻找一种方案，使得剩下的数字组成的新数最小。【样例输入】178543S=4【样例输出】13