南阳理工学院2009－2010学
年第二学期试卷
课程：算法设计与分析
（A）
评卷人（签名）：复核人（签名）：
一、选择题（每小题3分，共15分）
1．算法分析是（）。
A．将算法用某种程序设计语言恰当地表示出来
B．在抽象数据集合上执行程序，以确定是否会产生错误的结果
C．对算法需要多少计算时间和存储空间作定量分析
D．证明算法对所有可能的合法输入都能算出正确的答案
2．设A[1..60]={11，12,…，70}。
二分搜索算法在A 上搜索x=7、33、70、77 时执行的元素比较次数分别为a、b、c、d，则（）。
A．a<b<c<d B．a>b=c=d C．a<b=c=d D．a<c<b=d
3．背包问题：n=6，C=10，V(1:6)=(15，59，21，30，60，5)，W(1:6)=(1，5，2，3，6，1）。
该问题的最大价值为（）。
A．101 B．110 C．115 D．120 4．矩阵连乘问题：M1(5×10)，M2(10×4),，
M3(4×6)。
矩阵链乘M1M2M3需要的最少的乘法次数为（）。
A．540 B．320 C．720 D．300 5．用贪心策略设计算法的关键是（）。
A．将问题分解为多个子问题来分别处理B．选好贪心策略
C．获取各阶段间的递推关系式
D．满足最优性原理
二、填空题（每小题4分，共20分）
1．某算法的计算时间T(n)满足递归关系式：T(n)=2T(n/2)+1，n>1；T(1)=1。
则Ｔ(n)= 。
2. 子集和数问题一般陈述如下：已知n+1个正数：w i(1≤i≤n)和M，要求找出w i的和数是M 的所有子集。
其解可以表示为n-元组(x1, x2,⋯, x n)，这里x i∈{0,1}，1≤i≤n。
如果没有选择w i，则相应的x i=0；如果选择了w i，则x i=1。
考虑以下实例：n=6，M=20，
W(1:6)=(3,7,10,12,13,15)。
其解向量可表示为6元组(x1 ,x2 ,x3 ,x4 ,x5 ,x6)，其中x i=0 或1，1≤i≤6。
该问题的所有解为
________ _ __ 。
3．用方法对状态空间
树进行搜索时，每个结点最多只有一次机会成
为扩展结点。
4．已知将两个分别包含n 个和m 个记录的已
分类文件归并在一起得到一个分类文件需作
n+m 次记录移动。
现有五个已分类文件
F1,F2,F3,F4,F5，它们的记录个数分别为25,40,15,10,40，将这五个文件归并成一个分类文件最少需要做次记录移动。
注：每一步归并只能包含两个文件的归并。
5．使用算法LCS 找两个序列A=“xzyzzyx”和
B=“zxyyzxz”的最长的公共子序列。
它的一个最长公共子序列为，长度是。
三、问答题（每小题5分，共20分）
1.合并排序算法是根据分治策略来设计的，简述其基本思想。
2．简述拉斯韦加斯算法的算法特点及提高拉斯韦加斯算法得到解得概率的方法？
3．简述分枝限界法的基本思想。
4．简述最小生成树的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）=(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）。
要求：解答体现在网络中标号过程和找到的增广路，每一次增流后的可行流及最后的最大流。
（按顶点序号由小到大的原则选择已标号未检查的点）
4（10分）使用回溯算法来求解图的m(m=3)着色问题的如下图实例。
(1) 给出解向量的形式，指出解空间树的类型。
(2) 描述搜索过程。
(3) 画出找到一个解所生成的部分搜索树，并给出这个解。
五、算法设计（共12分）：
说明：任意选择所使用的算法策略。
要求：说明所使用的算法策略；
写出算法实现的主要步骤（可用自
然语言描述，也可以计算机编程语
言描述）；
题目：0-1背包问题。