算法分析与设计试卷(答案).doc

《算法分析与设计试卷(答案).doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、中南大学考试试卷答案（补考）2008--2009学年2学期时间110分钟算法分析与设计课程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）)的定义，下列等式是否

2、成立？（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分）顺序查找的时间是O(n)，折半查找O(logn)降低了一个数量级（2分）采用分治策略，每一次比较可以排除一半的数据。（4分）4、简述归并排序算法和快速排序算法的分治方法。（6分）1）归并排序的分治是将数组从中间分开，分别对前后来那个部分进行排序，将排序后的两个数组合并成整个数组的

3、排序。这样分治为递归过程，直到一个元素时返回。2）快速排序的分治是选取分割元素，以分割元素为界，将数组分成两部分，一部分小于分割元素，一部分大于分割元素，分别对两部分排序。5、一般背包问题的贪心算法可以获得最优解吗？物品的选择策略是什么？（6分）按照p[i]/w[i]≥p[i+1]/w[i+1]排序，选择当前利润/重量比最大的物品，可以获得最优解，6、Prim算法和Dijkstra算法选择下一个节点的标准分别是什么？对于有负边的无向图，Prim算法和Dijkstra算法还能保证获得最优解吗？（6分）1）prim算法的选择标准是选择当前与

4、T连结边的代价最小的节点加入。2）Dijkstra算法的选择标准是在与T邻接的顶点w中，选择从S到w路径最短的顶点。3）prim算法用于有负边的图可以获得最优解，Dijkstra算法不能获得最优解。2、比较回溯法和分支限界法的搜索方式，哪种方法更适合找最优解问题？（6分）1）回溯法是在约束下带跳跃的深度优先搜索。2）分枝限界是广度优先方式的按最小代价选择扩展节点，以上界函数对活节点进行限界的搜索。3）分枝限界法更适合找最优解。二、分析算法的时间复杂性，需要写出分析过程（本大题20分）1、用分割元素v将有n个元素的数组分割成元素大于v和小

5、于v的两部分，需要花多少时间（要讲出道理）。（5分）至少需要对每个元素进行一次比较运算，运算时间是O(n)。2、如果修改归并排序算法，将数组分成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

6、）+(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分）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

7、)=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分）1、在一个空间安排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分）2、写出0/1背包问题的动态规划方程，并简要说明。fi（X）＝ma

8、x{fi-1(X)，{fi-l(X—wi)+pi当X≥wi}（3分）fi（X）是前i个物品，背包容积X子问题的最优值，当第i个物品不选入，fi（X）等于fi-1(X)前i-1个物品，背包容积X子问题的最优值