南阳理工学院试卷模式A.doc

系 专业班级姓名考号（密封线内不准答题）南阳理工学院20092010学年第二学期试卷课程： 算法设计与分析 （A）评卷人（签名）： 复核人（签名）： 题号一二三四五总分得分一、选择题（每小题3分，共15分）1算法分析是（ ）。A 将算法用某种程序设计语言恰当地表示出来B 在抽象数据集合上执行程序，以确定是否会产生错误的结果C 对算法需要多少计算时间和存储空间作定量分析D 证明算法对所有可能的合法输入都能算出正确的答案2设A1.60=11，12,，70。二分搜索算法在A 上搜索x=7、33、70、77 时执行的元素比较次数分别为a、b、c、d，则（ ）。Aabcb=c=d Cab=c=d Dac1；T(1)=1。则(n)= 。2. 子集和数问题一般陈述如下：已知n+1个正数：wi (1in)和M，要求找出wi 的和数是M 的所有子集。其解可以表示为n-元组(x1 , x2 , xn)，这里xi0,1，1in。如果没有选择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，1i6。该问题的所有解为 _ _ _ 。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，使得当NN0时有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) 画出找到一个解所生成的部分搜索树，并给出这个解。五、算法设计（共1