中南大学算法分析练习(45分钟)(2026205924)

1、中南大学算法分析练习试卷总计60分 时间45分钟、填空题此题10分，每空1分1、 回溯法在解空间树 T上的搜索方式是【1】。2、 贪心算法总是做出在当前看来最好的选择。也就是说贪心算法并不从【2】考虑，它所做出的选择只是在某种意义上的【3】。3、 算法就是一组有穷的,4，它们规定了解决某一特定类型问题的【5】。4、 算法的复杂性是【6】的度量，是评价算法优劣的重要依据。5、 f(n)= 6 农+n2, f(n)的渐进性态 f(n)= 0(【7】)6、 许多可以用贪心算法求解的问题一般具有2个重要的性质：【8】性 质和【9】性质。7、 分治法的根本思想是将一个规模为n的问题分解为k个规模较小的子

2、问题，这些子问题互相【10】 且与原问题相同。1、选择题此题10分，每题1分1、分支限界法与回溯法都是在问题的解空间树T上搜索问题的解，二者()。A.求解目标不冋，搜索方式相冋B.求解目标不冋，搜索方式也不冋C.求解目标相冋，搜索方式不冋D.求解目标相同,搜索方式也相冋2、回溯法在解空间树 T上的搜索方式是()。A.深度优先 B.广度优先C.最小消耗优先D.活结点优先3、 在对问题的解空间树进行搜索的方法中，一个活结点最多有一次时机 成为活结点的是()。A.回溯法B.分支限界法C.回溯法和分支限界法D.回溯法求解子集树4、 以下关于判定问题难易处理的表达中正确的选项是()。A. 可以由多项式时

3、间算法求解的问题是难处理的B. 需要超过多项式时间算法求解的问题是易处理的C可以由多项式时间算法求解的问题是易处理的D.需要超过多项式时间算法求解的问题是不能处理的5、 设f(N),g(N)是定义在正数集上的正函数 ，如果存在正的常数 C和自然 数N0,使得当N沐0时有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.2nC.2n+1-1D. 2n-17、程序可以不满足以下()特征A.输入

4、B.输出C.确定性D.有限性8、以下()不能在线性时间完成排序A.计数排序B.基数排序C.堆排序D.桶排序9、以下()不一定得到问题的最优解A.贪心算法B.回溯算法C.分支限界法D.动态规划法10、以下不包括在图灵机结构中A.控制器B.读写磁头C.计算器D.磁带算法填空此题16分，每空2分1、Dijkstra算法是解单源最短路径问题的贪心算法。请你阅读下面伪代码并在空白处填上适当的代码。/ G是一个n个结点的有向图，它由本钱邻接矩阵wu,v表示，Dv表示结点v到源结点s的最短路径长度，pv记录结点v的父结点。In it-s in gle-source(G,s)1. for each verte

5、x v VG2. do dv=g pv=NIL3. ds=0Relax(u,v,w)1.if【1】2. then dv=du+wu,vPv=udijkstra(G,w,s)1. 【22. S=3. Q=VG4. while Q<> 【3do u=min(Q)S=S U ufor each vertex v adju / 所有 u 的邻接点 vdo【42、某工厂预计明年有N个新建工程，每个工程的投资额wk及其投资后的收益vk。投资总额为C，问如何选择工程才能使总收益最大。In vest-Program() for (j=0;j<=C;j+)【5】for (j=w n;j<

6、=C;j+)m nj=v n;for (i=n-1;i>1;i-) int jMax=mi n(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);四、 归纳技术应用题共4分考虑使用基数排序算法对以下8个数据进行排序，请给出中间排序的结果。2756 7352 3725 3762 5273 2375 5732 5627五、贪心法应用题共10分用Prim算法求以下列图的最小生成树。 要求用图或表格展示主要计算过程统一从A结吉点开始。六、动态规划法应用共10分请使用动态规划法求解以下0-1背包问题实例：n=4个物品，大小分别为W=2,3,4,6,价值分别为P=3,6,5,9，背包容量为 M=10。1、 4分请给出递推计算公式用 Vij表示在物品1,2,?,i中挑选物品 装入容