3、M3需要的最少的乘法次数为（）。A．540B．320C．720D．3005．用贪心策略设计算法的关键是（）。A．将问题分解为多个子问题来分别处理B．选好贪心策略C．获取各阶段间的递推关系式D．满足最优性原理二、填空题（每小题4分，共20分）1．某算法的计算时间T(n)满足递归关系式：T(n)=2T(n/2)+1，n>1；T(1)=1。则Ｔ(n)=。2.子集和数问题一般陈述如下：已知n+1个正数：wi(1≤i≤n)和M，要求找出wi的和数是M的所有子集。其解可以表示为n-元组(x1,x2,⋯,xn)，
4、这里xi∈{0,1}，1≤i≤n。如果没有选择wi，则相应的xi=0；如果选择了wi，则xi=1。考虑以下实例：n=6，M=20，W(1:6)=(3,7,10,12,13,15)。其解向量可表示为6元组(x1,x2,x3,x4,x5,x6)，其中xi=0或1，1≤i≤6。该问题的所有解为___________。3．用方法对状态空间树进行搜索时，每个结点最多只有一次机会成为扩展结点。4．已知将两个分别包含n个和m个记录的已分类文件归并在一起得到一个分类文件需作n+m次记录移动。现有五个已分类文件F1,
5、F2,F3,F4,F5，它们的记录个数分别为25,40,15,10,40，将这五个文件归并成一个分类文件最少需要做次记录移动。注：每一步归并只能包含两个文件的归并。5．使用算法LCS找两个序列A=“xzyzzyx”和B=“zxyyzxz”的最长的公共子序列。它的一个最长公共子序列为，长度是。三、问答题（每小题5分，共20分）1.合并排序算法是根据分治策略来设计的，简述其基本思想。2．简述拉斯韦加斯算法的算法特点及提高拉斯韦加斯算法得到解得概率的方法？3．简述分枝限界法的基本思想。4．简述最小生成树的
6、Prim算法的基本思想四、求解题1.（5分）设f(N)、g(N)是定义在正数集上的正函数。如果存在正的常数C和自然数N0，使得当N≥N0时有f(N)≤Cg(N)，则成函数f(N)当N充分大时上有界，且g(N)是它的一个上界，记为f(N)=O(g(N))。证明：O(f(N))+O(g(N))=O((f(N)+g(N))。2．（8分）给定7个作业，要在两台机器M1、M2组成的流水线上完成加工。每个作业都是先在M1上加工，然后在M2上加工。在M1上处理时间为：（a1,a2,a3,a4,a5,a6,a7）=
7、(3,8,2,9,5,4,4)，在M2上的处理时间为：(b1,b2,b3,b4,b5,b6,b7)=(2,6,7,10,5,3,8)，按照流水作业调度问题的Johnson算法步骤，给出该问题的最优调度方案。（要求：先写出Johnson算法步骤，然后写出每一个步骤对应的求解情况）3.（10分）给定下图的一个网络及网络上的可行流，从给定的可行流出发，采用增广路算法找出最大网络流。有向边上对应的值为（容量cap，流量flow）。要求：解答体现在网络中标号过程和找到的增广路，每一次增流后的可行流及最后的最大
8、流。（按顶点序号由小到大的原则选择已标号未检查的点）4（10分）使用回溯算法来求解图的m(m=3)着色问题的如下图实例。(1)给出解向量的形式，指出解空间树的类型。(2)描述搜索过程。(3)画出找到一个解所生成的部分搜索树，并给出这个解。五、算法设计（共12分）：说明：任意选择所使用的算法策略。要求：说明所使用的算法策略；写出算法实现的主要步骤（可用自然语言描述，也可以计算机编程语言描述）；题目：0-1背包问题
