算法复习2010秋季

2010秋季算法设计与分析复习一简要回答下列问题（8道题 40分）1.如何选择排序、矩阵相乘、树和图算法的时间复杂性计量单位？比较排序：用算法所用的比较次数作为该类算法的运算时间；矩阵相乘：基本运算是两个数的相乘；树的搜索：基本运算是节点的访问；图的算法：节点和边的运算。

2.算法有几种基本结构？各种结构的时间复杂度的计算规则？顺序结构：将运算步骤的时间累计，简单运算只需要1个单位时间。

选择结构：计算复杂的情况复杂度。

循环结构：复杂度计量=循环着次数*循环体的时间函数调用：计算函数的执行时间3.最坏情况下的时间复杂性和平均情况下的时间复杂性的定义？最坏情况、最好情况和平均情况下的时间复杂性，井分别记为：W(n) = max{ T(n，I) } , I∈DnB(n) = min { T(n，I) }, I∈DnA(n)＝∑P( I )T(n，I) I∈DnDn是规模为n的合法输入的集合，P(I)是在算法的应用中出现输入I 的概率。

4.为什么选择时间复杂度的渐进性态评价算法？一个算法的时间复杂度T(n)是该算法的时间耗费，是该算法所求解问题规模n的函数。

当问题的规模n趋向无穷大时，时间复杂度T(n)的数量级(阶)称为算法的复杂性的渐近性态。

分析算法的时间复杂性的目的是为了比较完成同一功能的程序的算法之间的最主要的差别。

5.解释f(n)=O(g(n))的意义。

f(n)是某一算法的时间复杂性函数，g(n)是某一函数，当且仅当存在正的常数C和N0，使得对于所有的n>=N0，有f(n)<=Cg(n)，记作f(n)=O(g(n))即函数f至多是函数g的C倍，当充分大时，g是f的一个上界函数，在相差一个非零常数倍的情况下。

6.有效算法和无效算法的划分原则？区分在于问题是否能够精确求解。

7.用分治法设计算法有什么好处？为什么描述分治算法需要使用递归技术？当要求解一个输入规模为n，且n的取值相当大的问题时，直接求解往往是非常困难的。

如果问题可以将n个输入分成k个不同子集合，得到k个不同的可独立求解的子问题，其中1<k≤n，而且子问题与原问题性质相同，原问题的解可由这些子问题的解合并得出。

递归技术。

反复使用分治策略将这些子问题分成更小的同类型子问题，直至产生出不用进一步细分就可求解的子问题。

8.归并排序算法和快速排序算法划分子问题和合并子问题的解的方法各是是怎样的？1）归并排序的分治是将数组从中间分开，分别对前后来那个部分进行排序，将排序后的两个数组合并成整个数组的排序。

这样分治为递归过程，直到一个元素时返回。

2）快速排序的分治是选取分割元素，以分割元素为界，将数组分成两部分，一部分小于分割元素，一部分大于分割元素，分别对两部分排序。

9.简述二分检索（折半查找）算法为什么比顺序查找的效率高？顺序查找的时间是O(n)，折半查找O(log n)降低了一个数量级。

采用分治策略，每一次比较可以排除一半的数据。

10.贪心法的核心是什么？在贪心算法中采用逐步构造最优解的方法。

在每个阶段，都作出一个看上去最优的决策。

决策一旦作出，就不可再更改。

作出贪心决策的依据称为贪心准则。

选择能产生问题最优解的最优量度标准是使用贪心法设计求解的核心问题。

11.背包问题的目标函数是什么？背包问题贪心算法的最优量度是什么？算法是否获得最优解？用贪心算法解0/1背包问题是否可获得最优解？目标函数是每装入一件物品就使背包获得最大可能的效益值增量。

最优量度是每一次装入的物品应使它占用的每一单位容量获得当前最大的单位效益。

不一定是。

否。

12.活动安排、prim算法的贪心策略？活动安排：活动i能否被安排，取决于si时刻场地是否空闲。

如果所有的活动都有fi≤ sj ，i≠j，则所有活动都可以安排。

考虑从n个活动中选择最早结束的活动i首先安排，则对n-1活动安排影响最小， n-1个活动才可能得到最优安排。

按fi≤ fi+1 对n个作业排序，可能获得最优解。

prim算法：假设G的一棵子树T已经确定；下一步选择的贪心策略：选择G的不在T中、以最小代价边与T相连接的节点加入。

即选择图G的一条权值最小的边e；使得T {e}仍是G的一棵子树，且T增加的代价最小。

13.动态规划法的基本步骤？1、找出最优解的性质，并刻画其结构特征；2、写出动态规划方程；3、以自底向上的方式计算出最优值；4、根据计算最优值时得到的信息，构造一个最优解。

步骤1-3是动态规划算法的基本步骤。

在只需要求出最优值的情形，步骤4可以省略，步骤3中记录的信息也较少；若需要求出问题的一个最优解，则必须执行步骤4，步骤3中记录的信息必须足够多以便构造最优解。

14.N皇后、图的着色、哈密顿环问题的解空间、约束函数。

n皇后问题：可以表示成n-元组(x1,…,xn),其中xi是放在第i行的皇后所在的列号。

于是，解空间由nn个n-元组组成。

显示约束条件为Si={1,2,…….,n},1 i n。

隐式约束条件之一为没有两个xi相同(即任意两个皇后不在同一列上)。

将其加入到显式条件中，于是解空间的大小由nn个元组减少到n！个元组。

图的着色：约束：如果 A[i,j]=1 and xi = xj 则是不合理的着色，两个节点之间有边，则不能着相同的颜色。

对于给定的图G(V,E)，从顶点i出发，经其他的顶点各一次，再回到顶点i，构成的环。

求哈密顿环：所有的哈密顿环。

15.回溯法的基本控制流程中“while k>0 do”的含义。

16.简述分枝限界方法的基本思想。

分支限界法的求解目标则是找出满足约束条件的一个解，或是在某种意义下的最优解。

分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树T。

在扩展结点处，先生成其所有的儿子结点（分支），将它们存入活节点表，然后再从当前的活结点表中选择下一个扩展节点。

为了有效地选择下一扩展结点，以加速搜索的进程，在每一活结点处，计算一个函数值（限界），并根据这些已计算出的函数值，从当前活结点表中选择一个最有利的结点作为扩展结点，使搜索朝着解空间树上有最优解的分支推进，以便尽快地找出一个最优解。

17.带限期作业调度问题、0/1背包问题的分枝限界算法的解空间、上下界函数。

二、算法时间复杂性分析 （2题，16分）1． 分析包含顺序、选择、循环结构和子过程调用的流程的时间复杂性。

顺序结构将运算步骤的时间累计，简单运算只需要1个单位时间。

顺序结构：T(n)=O(c) 选择结构：计算复杂的情况复杂度。

选择结构：T(n)=O(c)循环结构：复杂度计量=循环着次数*循环体的时间循环结构：T(n)=O(n)函数调用：计算函数的执行时间2． 用递归方程分析算法MAXMIN 、归并排序、Hanoi 塔算法的时间复杂度。

（需要递归方程解）T(n)=2T(n/2)+2=2(2T(n/4)+2)+2=4T(n/4)+4+2……=2k-1T(2)+2k-1+……+2=2k-1+2k-2=3n/2-2 T(n) ≤ 3n/2-2cn n T +)2/(2 )log ()(n n O n T =T(n)=2T(n-1)+1=2[2T(n-2)+1]+1= 22T(n-2)+2+1= 23T(n-3)+22+2+1……= 2n-1T(1)+2n-2+…..2+1= 2n -1三、算法理解 （20分）1． 贪心算法的一般流程。

1）根据题意，选取一种量度标准。

2）按这种量度标准对这n 个输入排序，3）依次选择输入量加入部分解中。

如果当前这个输入量的加入，不满足约束条件，则不把此输入加到这部分解中。

2． 归并排序算法procedure MERGESORT(low ，high)global A[1..n]if low<highthen mid ← (low+high)/2 //求这个集合的分割点//{MERGESORT(low ，mid) //将一个子集合排序//MERGESORT(mid+1，high) //将另一个子集合排序MERGE(low ，mid ，high) //归并两个已排序的子集合//}end3． 多段图算法procedure FGRAPH(G ，k ，n ，P){//G 有n 个结点的k 段图。

E 是边集，c[i ，j]是边<i,j>的成本。

P[1：k]是最小成本路径。

//COST[n]， D[n 一1]，P[k]，r ，j ，k ，nCOST[n]← 0for j←n-1to 1 by -1 do //计算COST[j]//{设r是一个这样的结点，(j，r) E且使c[j，r]+COST[r]取最小值COST[j]←c[j，r]+COST[r]D[j]←r} //向前对j-1进行决策//P[1]←1P[k]←nfor j←2 to k-1 do //找路径上的第j个节点//P[j]←D [ P[j-1] ]}4．n后问题递归算法procedure NQUEENS(n)X(1)←0；k←1 //k是当前行；X(k)是当前列//While k>0 do //对所有的行执行以下语句//1){ X(k)←X(k)+1 //移到下一列//While X(k)≤n and not PLACE(k) do2)X(k)←X(k)十lif X(k)≤n //找到一个位置//then if k=n //是一个完整的解吗//then print(X) //是，打印这个数组//3)else {k←k+1；X(k)←0；}4)else k←k－1 //回溯//}end NQUEENS5．图的着色非递归形式算法。

B_mcolor(k)for x[k] ←1 to m doif place(k)=true thenif k=n then print xelse B_mcolor(k+1)endifrepeat6．子集和数算法X(k)←1if s+W(k)＝M then //子集找到//print Xelseif s+W(k)+W(k+1)≤M then //Bk＝true//call SUMOFSUB(s+W(k)，k+1，r－W(k))endifendif//生成右儿子和计算Bk的值//if s+r－W(k)≥M and s＋W(k+1)≤M //Bk＝true//then X(k)←0call SUMOFSUB(s，k+1，r－W(k))endifend SUMOFSUB四. 算法设计（3题 24分）1、深度优先算法（判断有向图是否存在环等问题）判断图是否存在环（8分）procedure DFS_Visit(G,u){color[u]←Grayfor each edge(u,v) do{ if color[v]=White thenDFS_Visit(G,v)if color[v]= Gray thenf← 1returncolor[u]←Black}procedure DFS(G)for each vertex u∈V docolor[u]←Whitef ←0for vertex each u∈V do{if color[u]=Whitethen { DFS_Visit(G, u)if f=1 then{ print “Yes”return}}}print “No”}if f=1 then print “Yes”else print “No”2、归并排序、回溯法3、多处理机调度、活动安排、找零钱、装箱问题的贪心算法。