中南大学考试试卷2008--2009学年2学期时间110分钟算法分析与设计课程注：此页不作答题纸，请将答案写在答题纸上基本概念题（本大题40分）一般情况下，如何计算执行顺序、选择、循环、子过程调用结构的运算时间？（6分）设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分）简述归并排序算法和快速排序算法的分治方法。（6分）一般背包问题的贪心算法可以获得最优解吗？物品的选择策略是什么？（6分）Prim算法和Dijkstra算法选择下一个节点的标准分别是什么？对于有负边的无向图，Prim算法和Dijkstra算法还能保证获得最优解吗？（6分）比较回溯法和分支限界法的搜索方式，哪种方法更适合找最优解问题？（6分）分析算法的时间复杂性，需要写出分析过程（本大题20分）用分割元素v将有n个元素的数组分割成元素大于v和小于v的两部分，需要花多少时间（要讲出道理）。（5分）如果修改归并排序算法，将数组分成1/3和2/3大小不等的两部分，分别排序后再归并，算法的最坏时间复杂度有什么变化？（5分）设函数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分）在一个空间安排n=5个活动，开始时间和结束时间分别为[8,10),[12,14),[9,11:30),[11:40,13)，[13:30,15)。写出活动安排贪心算法的运行结果。（6分）写出0/1背包问题的动态规划方程，并简要说明。（6分）修改图的m-着色的回溯算法，找到一个解，算法就结束。（6分）用分支限界法解0/1背包问题，若物品i选入，则x[i]=1，否则x[i]=0。如何选用上下界函数？（6分）算法设计（本大题16分）对于给定的无向图G=(V,E),分别设计具有下列功能的深度优先算法。1)判断图是否为连通图。（8分）2)判断图是否存在环。（8分）中南大学考试试卷答案（补考）2008--2009学年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算法不能获得最优解。