资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。中南大学考试试卷答案(补考)--2学期时间110分钟算法分析与设计课程48学时3学分考试形式:闭卷专业年级:信安0601-0602总分100分,占总评成绩70%注:此页不作答题纸,请将答案写在答题纸上基本概念题(本大题40分)(6分)1)顺序结构将运算步骤的时间累计,简单运算只需要1个单位时间。(1分)2)选择结构:计算复杂的情况复杂度。(2分)3)循环结构:复杂度计量=循环着次数*循环体的时间(2分)4)函数调用:计算函数的执行时间(1分)设T(n)=n,根据T(n)=O(f(n))的定义,下列等式是否成立?(4分)T(n)=O(n2)(√)O(n2)=T(n)(×)T(n)=O(logn)+O(n)(√)T(n)=O(n)*O(logn)(√)与顺序查找算法相比,折半查找算法的时间复杂性有多大程度的降低?它是如何提高算法的效率的?(6分)顺序查找的时间是O(n),折半查找O(logn)降低了一个数量级(2分)采用分治策略,每一次比较能够排除一半的数据。(4分)简述归并排序算法和快速排序算法的分治方法。(6分)归并排序的分治是将数组从中间分开,分别对前后来那个部分进行排序,将排序后的两个数组合并成整个数组的排序。这样分治为递归过程,直到一个元素时返回。快速排序的分治是选取分割元素,以分割元素为界,将数组分成两部分,一部分小于分割元素,一部分大于分割元素,分别对两部分排序。一般背包问题的贪心算法能够获得最优解吗?物品的选择策略是什么?(6分)按照p[i]/w[i]≥p[i+1]/w[i+1]排序,选择当前利润/重量比最大的物品,能够获得最优解,Prim算法和Dijkstra算法选择下一个节点的标准分别是什么?对于有负边的无向图,Prim算法和Dijkstra算法还能保证获得最优解吗?(6分)prim算法的选择标准是选择当前与T连结边的代价最小的节点加入。Dijkstra算法的选择标准是在与T邻接的顶点w中,选择从S到w路径最短的顶点。prim算法用于有负边的图能够获得最优解,Dijkstra算法不能获得最优解。比较回溯法和分支限界法的搜索方式,哪种方法更适合找最优解问题?(6分)回溯法是在约束下带跳跃的深度优先搜索。分枝限界是广度优先方式的按最小代价选择扩展节点,以上界函数对活节点进行限界的搜索。分枝限界法更适合找最优解。分析算法的时间复杂性,需要写出分析过程(本大题20分)用分割元素v将有n个元素的数组分割成元素大于v和小于v的两部分,需要花多少时间(要讲出道理)。(5分)至少需要对每个元素进行一次比较运算,运算时间是O(n)。如果修改归并排序算法,将数组分成1/3和2/3大小不等的两部分,分别排序后再归并,算法的最坏时间复杂度有什么变化?设对n个元素排序的时间为T(n),对两部分排序的时间分别为T(n/3)和,合并的时间为n-1,得到递归方程:T(n)=T(n/3)+T(2n/3)+n-1n>3(2分)O(1)n≤3考虑n=3kT(n)=T(3k-1)+T(2*3k-1)+n-1=T(3k-2)+2T(2*3k-2)+T(22*3k-2)+(n-1)+(n-2)=T(3k-3)+3T(22*3k-3)+3T(223k-3)+T(233k-3)+(n-1)+(n-2)+(n-3)最后T(2i3k-i)=O(1)时,2i3k-i≤3T(n)≤(n-1)+(n-2)+(n-3)+......+(n-(k-1))=nk-(1+2+......+(k-1))≤nlog3/2n(3分)设函数f1、f2和f3的处理时间分别为O(n)、O(n2)和O(1),分析下列流程的时间复杂性:1)基本结构procedureA1(intn,b)(4分)T(n)=max{O(n),O(n2)}+n*O(1)=O(n2)2)递归结构设A2的时间为T(n)T(n)=T(n-1)+O(1)n>1=O(1)n≤3(3分)T(n)=T(n-2)+2O(n)=......=T(1)+nO(n)=O(n2)(3分)算法理解(本大题24分)在一个空间安排n=5个活动,开始时间和结束时间分别为。写出活动安排贪心算法的运行结果。1)按照结束时间排序(3分)[8,10)1,[9,11:30)3,[11:40,13)4,[12,14)2,[13:30,15)52)可行解1,4,5(3分)写出0/1背包问题的动态规划方程,并简要说明。fi(X)＝max{fi-1(X),{fi-l(X—wi)+pi当X≥wi}(3分)fi(X)是前i个物品,背包容积X子问题的最优值