资源描述：
《中南大学算法分析练习(45分钟).doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、中南大学算法分析练习试卷总计60分时间45分钟一、填空题（本题10分，每空1分）1、回溯法在解空间树T上的搜索方式是【1】。2、贪心算法总是做出在当前看来最好的选择。也就是说贪心算法并不从【2】考虑，它所做出的选择只是在某种意义上的【3】。3、算法就是一组有穷的【4】，它们规定了解决某一特定类型问题的【5】。4、算法的复杂性是【6】的度量，是评价算法优劣的重要依据。5、f(n)=6×2n+n2，f(n)的渐进性态f(n)=O( 【7】 )6、许多可以用贪心算法求解的问题一般具有2个重要的性质：【8】性质和【9】性质。7、分治法的
2、基本思想是将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相【10】且与原问题相同。二、选择题（本题10分，每小题1分）1、分支限界法与回溯法都是在问题的解空间树T上搜索问题的解,二者()。A.求解目标不同,搜索方式相同B.求解目标不同,搜索方式也不同C.求解目标相同,搜索方式不同D.求解目标相同,搜索方式也相同2、回溯法在解空间树T上的搜索方式是()。A.深度优先B.广度优先C.最小耗费优先D.活结点优先3、在对问题的解空间树进行搜索的方法中,一个活结点最多有一次机会成为活结点的是()。A.回溯法B.分支限界法C.回
3、溯法和分支限界法D.回溯法求解子集树4、以下关于判定问题难易处理的叙述中正确的是()。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)的阶()g(N)的阶。A.不高于B.不低于C.等价于D.逼近6
4、、对于含有n个元素的子集树问题,最坏情况下其解空间的叶结点数目为()。A.n!B.2nC.2n+1-1D.2n-17、程序可以不满足以下()特征A.输入B.输出C.确定性D.有限性8、以下()不能在线性时间完成排序A.计数排序B.基数排序C.堆排序D.桶排序9、以下()不一定得到问题的最优解A.贪心算法B.回溯算法C.分支限界法D.动态规划法10、以下（）不包括在图灵机结构中A.控制器B.读写磁头C.计算器D.磁带一、算法填空（本题16分，每空2分）1、Dijkstra算法是解单源最短路径问题的贪心算法。请你阅读下面伪代码并在空白
5、处填上适当的代码。//G是一个n个结点的有向图，它由成本邻接矩阵w[u,v]表示，D[v]表示结点v到源结点s的最短路径长度，p[v]记录结点v的父结点。Init-single-source(G,s)1.foreachvertexv∈V[G]2.do{d[v]=∞p[v]=NIL}3.d[s]=0Relax(u,v,w)1.if【1】2.then{d[v]=d[u]+w[u,v]p[v]=u}dijkstra(G,w,s)1.【2】2.S=Φ3.Q=V[G]4.whileQ<>【3】dou=min(Q)S=S∪{u}foreach
6、vertexv∈adj[u]//所有u的邻接点vdo【4】2、某工厂预计明年有N个新建项目，每个项目的投资额w[k]及其投资后的收益v[k]已知。投资总额为C，问如何选择项目才能使总收益最大。Invest-Program(){for(j=0;j<=C;j++)【5】for(j=w[n];j<=C;j++)m[n][j]=v[n];for(i=n-1;i>1;i--){intjMax=min(w[i]-1,c);for(j=0;j<=jMax;j++)m[i][j]=【6】;for(j=w[i];j<=C;j++)m[i][j]=m
7、ax(【7】);}m[1][c]=m[2][c];if(【8】)m[1][c]=max(m[1][c],m[2][c-w[1]]+v[1]);}二、归纳技术应用题（共4分）考虑使用基数排序算法对下列8个数据进行排序，请给出中间排序的结果。27567352372537625273237557325627一、贪心法应用题（共10分）用Prim算法求下图的最小生成树。要求用图或表格展示主要计算过程（统一从A结点开始）。二、动态规划法应用（共10分）请使用动态规划法求解下列0-1背包问题实例：n=4个物品，大小分别为W={2,3,4,6}
8、，价值分别为P={3,6,5,9}，背包容量为M=10。1、（4分）请给出递推计算公式（用V[i][j]表示在物品1,2,⋯,i中挑选物品装入容量是j的背包中的最大价值）。2、（6分）根据递推计算公式用二维表格展示出计算过程，并给出最优结果（注意：
