_中南大学算法考试试卷及答案

_中南大学算法考试试卷及答案

ID:1789181

大小:42.00 KB

页数:7页

时间:2017-11-13

_中南大学算法考试试卷及答案_第1页
_中南大学算法考试试卷及答案_第2页
_中南大学算法考试试卷及答案_第3页
_中南大学算法考试试卷及答案_第4页
_中南大学算法考试试卷及答案_第5页
资源描述:

《_中南大学算法考试试卷及答案》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库

1、中南大学考试试卷2008--2009学年2学期时间110分钟算法分析与设计课程注:此页不作答题纸,请将答案写在答题纸上一、基本概念题(本大题40分)1、一般情况下,如何计算执行顺序、选择、循环、子过程调用结构的运算时间?(6分)2、设T(n)=n,根据T(n)=O(f(n))的定义,下列等式是否成立?(4分)1)T(n)=O(n2)2)O(n2)=T(n)3)T(n)=O(logn)+O(n)4)T(n)=O(n)*O(logn)3、与顺序查找算法相比,折半查找算法的时间复杂性有多大程度的降低?它是如何提高算法的效率的?(6分)4、简述归并排序算

2、法和快速排序算法的分治方法。(6分)5、一般背包问题的贪心算法可以获得最优解吗?物品的选择策略是什么?(6分)6、Prim算法和Dijkstra算法选择下一个节点的标准分别是什么?对于有负边的无向图,Prim算法和Dijkstra算法还能保证获得最优解吗?(6分)7、比较回溯法和分支限界法的搜索方式,哪种方法更适合找最优解问题?(6分)二、分析算法的时间复杂性,需要写出分析过程(本大题20分)1、用分割元素v将有n个元素的数组分割成元素大于v和小于v的两部分,需要花多少时间(要讲出道理)。(5分)2、如果修改归并排序算法,将数组分成1/3和2/3

3、大小不等的两部分,分别排序后再归并,算法的最坏时间复杂度有什么变化?(5分)3、设函数f1、f2和f3的处理时间分别为O(n)、O(n2)和O(1),分析下列流程的时间复杂性:1)基本结构procedureA1(intn,b)(4分)ifb<3thenf1elsef2fori←1ton-1dof3end2)递归结构procedureA2(intn)(6分)ifn=1then{f3return}else{A2(n-1)f1}end一、算法理解(本大题24分)1、在一个空间安排n=5个活动,开始时间和结束时间分别为[8,10),[12,14),[9,

4、11:30),[11:40,13),[13:30,15)。写出活动安排贪心算法的运行结果。(6分)2、写出0/1背包问题的动态规划方程,并简要说明。(6分)3、修改图的m-着色的回溯算法,找到一个解,算法就结束。(6分)4、用分支限界法解0/1背包问题,若物品i选入,则x[i]=1,否则x[i]=0。如何选用上下界函数?(6分)二、算法设计(本大题16分)对于给定的无向图G=(V,E),分别设计具有下列功能的深度优先算法。1)判断图是否为连通图。(8分)2)判断图是否存在环。(8分)中南大学考试试卷答案(补考)2008--2009学年2学期时间1

5、10分钟算法分析与设计课程48学时3学分考试形式:闭卷专业年级:信安0601-0602总分100分,占总评成绩70%注:此页不作答题纸,请将答案写在答题纸上一、基本概念题(本大题40分)1、(6分)1)顺序结构将运算步骤的时间累计,简单运算只需要1个单位时间。(1分)2)选择结构:计算复杂的情况复杂度。(2分)3)循环结构:复杂度计量=循环着次数*循环体的时间(2分)4)函数调用:计算函数的执行时间(1分)2、设T(n)=n,根据T(n)=O(f(n))的定义,下列等式是否成立?(4分)1)T(n)=O(n2)(√)2)O(n2)=T(n)(×)

6、3)T(n)=O(logn)+O(n)(√)4)T(n)=O(n)*O(logn)(√)3、与顺序查找算法相比,折半查找算法的时间复杂性有多大程度的降低?它是如何提高算法的效率的?(6分)顺序查找的时间是O(n),折半查找O(logn)降低了一个数量级(2分)采用分治策略,每一次比较可以排除一半的数据。(4分)4、简述归并排序算法和快速排序算法的分治方法。(6分)1)归并排序的分治是将数组从中间分开,分别对前后来那个部分进行排序,将排序后的两个数组合并成整个数组的排序。这样分治为递归过程,直到一个元素时返回。2)快速排序的分治是选取分割元素,以分

7、割元素为界,将数组分成两部分,一部分小于分割元素,一部分大于分割元素,分别对两部分排序。5、一般背包问题的贪心算法可以获得最优解吗?物品的选择策略是什么?(6分)按照p[i]/w[i]≥p[i+1]/w[i+1]排序,选择当前利润/重量比最大的物品,可以获得最优解,6、Prim算法和Dijkstra算法选择下一个节点的标准分别是什么?对于有负边的无向图,Prim算法和Dijkstra算法还能保证获得最优解吗?(6分)1)prim算法的选择标准是选择当前与T连结边的代价最小的节点加入。2)Dijkstra算法的选择标准是在与T邻接的顶点w中,选择从

8、S到w路径最短的顶点。3)prim算法用于有负边的图可以获得最优解,Dijkstra算法不能获得最优解。7、比较回溯法和分支限界法的搜索

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。