中南大学算法试卷

中南大学考试试卷2012--2013学年上学期时间120分钟2013年1月4日算法分析与设计课程48学时3学分考试形式：闭卷专业年级：10级计算机、信安、物联本科生，总分100分，占总评成绩70%注：此页不作答题纸，请将答案写在答题纸上1.(15分)本期学了很多类算法，请针对以下几类设计策略，举出相应的例子，详细描述算法细节，以说明它们为什么是属于相应的设计策略？（1）分治法（2）动态规划（3）贪心策略2.（30分）请判断下列陈述是否正确。（1）根据Master定理，可得到递归式T(n)=4T(n/2)+n2的解为T(n)=O(n2logn).（2）归并排序在最好情况下的时间复杂度为O(nlogn).（3）具有n个结点的二叉排序树的树高均为O(logn)。（4）如果一个问题是NP完全问题，它肯定也是NP问题。（5）给定n个数，可以在O（n）的时间内找到10个最大数与10个最小数之间的中间数。（6）Kruskal算法利用了动态规划思想寻找给定图中的最小生成树。（7）n!=O(2n)。（8）回溯法借鉴了广度优先的策略得到问题的最优解。（9）对于一个有n个顶点m条边的无向图G，有两个不同的顶点st，则在O(m+n)的时间内可以找到s与t之间的最短路径。（10）在最坏情况下，快速排序耗费O(N2)。（11）如果图中包含负权值的边，则Dijkstra算法不可适用。（12）分治法是属于自底向上的算法策略；动态规划是属于自顶向下的算法策略。（13）有一个算法，将n个整数a1,...,an作为输入，算法的时间复杂度是O(a1+a2+......+an)。它是一个多项式时间算法。（14）有一个图G=(V,E)，每条边e∈E的权We0,如果一棵生成树T最小化Σe∈TWe，那么T也最小化Σe∈TWe2，反之也成立（即图中边的权值都平方后，生成树T仍是这个图的最小生成树）。（15）给定两个判定性问题Q1、Q2，如果Q1可以在多项式时间内规约到Q2，则Q1和Q2具有同等难度。3.（20分）算法设计（选做两题）（1）（10分）设计一个算法判断一个多边形是否是凸多边形，并分析你的算法的时间性能(注：输入是沿着多边形逆时针的顶点系列)。（2）（10分）给定图G=(V,E)，利用深度优先算法统计图G中连通块的个数。给出统计算法.（3）(10分)给定边加权图G=(V,E)，图G中的最大生成树为图G中所有生成树中权值最大的生成树。设计构造最大生成树的算法4.（10分）求解下列递归式。T(1)=1.（1）T(n)=2T(n-1)+1（2）T(n)=T(n/2)+T(n/4)+n25.（25分）对于0/1背包问题，给定n个物品，每个物品都具有一定的权重和价值，寻找物品的一个子集，使得当把这些物品放到背包中时，物品的总重量不会超过背包的容量M。假设n=4，W={10,7,8,4}，V={100,63,56,12}，M=16。（1）设计该问题的动态规划递归式（5分）（2）给出利用动态规划技术得到最优解的具体过程（10分）（3）给出利用分支限界技术求得最优解的具体过程（10分）注：上界函数可定义为：ub=V+(M-w)(vi+1/wi+1)