算法设计试卷模式A答案

南阳理工学院2010－2011学年第一学期试卷参考答案课程：算法设计与分析 (A)评卷人(签名)： 复核人(签名)： 题号一一二三四五总分得分一、选择题(每小题1分，共10分)算法分析是(c)。A．将算法用某种程序设计语言恰当地表示出来B.在抽象数据集合上执行程序，以确定是否会产生错误的结果c.对算法需要多少计算时间和存储空间作定量分析D.证明算法对所有可能的合法输入都能算出正确的答案下列(A)不是描述算法的工具。A.数据流图 B.伪代码 C.自然语言D.程序语言如果某一算法的执行时间不超过输入规模的两倍，那么算法渐进时间复杂度为(B)oA. 0(n2) B. 0(n) C.0(n) D.O(n)下列程序段的S执行的次数为(D)ofor(inti=0;i<n;i++)for(intj=0;j<i;j++)S;//S是基本操作，耗时常数时间A.n2 B.n2/2 C.n(n+1)/2D.n(n-1)/2使用F(n)=n*F(n)递归求F(4)，其中边界条件为F(0)=1，则递归调用子函数的次数为(B)。A. 3次B.4次C.5次D.8次Fibonacci数列的第1项为0,第2项为1,那么它的第10项为(D)。A. 3B. 13C. 21D.347•下列排序算法不是基于交换的是(C)oA冒泡排序B.快速排序C合并排序D.堆排序8.4个结点的二叉查找树可能的形态有(C)种。A4种B. 5种 C.14种D. 15种9.如果背包的容量为100,而物品共有10个，则使用动态规划来解0-1背包问题数组大小为(C)A. 10B. 100C.1000D1000010•对线性表执行折半搜索时，要求线性表必须(C)oA以数组方式存储 B以单链表形式存储C以数组方式存储且关键字有序 D.以单链表形式存储且关健字有序二、填空题(每空2分，共30分)请将合并排序的分治算法补充完整。数组a存放待排序元素，left:为待排序元素最小下标‘right:为待排元素最大下标。voidMergeSort(Typea[],intleft,intright){Type*b=newint[right-left+1];if(left<right){inti=(left+right}/2 ;MergeSort(a,left,i);MergeSort(a,i+l,right):Merge(a,b,left,i,right);copy(a,b,left,right):}}template<classType>voidMerge(Typea[],Typeb[],intleft,intmid,intright){inti=1eft,j=mid+1,k=left:while((i<=mid)&&j<=right)){if(a[i]<=a[j])b[k++]=a[i++]:elseb[k++]=a[j++]:}if(i>mid)for(intq=j:q<=right:q++)b[k++]=a[q]:elsefor(intq=i:q<=mid:q++)b[k++]=a[q]:}template<classType>voidcopy(Typea[],Typeb[],intleft,intright){for(inti=left:i<=right:i++){a「i]=b「i]:}}

2.动态规划的基本要素包括重叠子问题、自底向上的解决方法、最优子结构性质。3•矩阵连乘问题算法借助于二维数组存放各子问题的最优值。4•给定序列X={SREABEDBWD},Y={RBAEFEA的最长公共子序列的长度为_3 。5•活动安排问题的贪心策略是一选择结束时间最早的活动优先安排。6最大团问题的解空间树是一棵一子集_树，n皇后问题的满足不同行、不同列要求的解空间树是一棵排列树。7随机化算法中，蒙特卡罗算法用于求准确解，数值随机化算法用于求近似解：用于求问题的正确解拉斯维加斯算法算法，但是,算法的每一次运行不一定得到解。当确定性算法中，最坏情况和最好情况下时间的相差很大时，用舍伍德算法削弱这种差异。三、 问答题（每小题5分，共20分）分治算法有何特征。答：分治算法具有以下特征：（1）问题规模足够小时容易解决；（2）将规模大的问题分成规模较小的子问题；（3）子问题相互独立；（4）子问题的解决方法与原问题相同；（5）递归解决子问题；（6）子问题的解能够合并成原问题的解。简述构造哈夫曼树的算法思想。答：将n个字符看做是n可孤立的树，组成一个结合。重复做如下操作：从集合中取出两棵出现频率最低的树，让它们作为左右子树构成一棵新树，新树的频率为左右子树频率之和。然后将新树插入到树的集合中；算法知道集合中只剩下一棵树为止。3•简述图的m着色问题解空间的定义。答：图的m着色问题解的形式为一个n元组（X],x2,…,xn），其中n表示图的顶点个数。Xi:表示图中第i个顶点着第X号色。每个分量的取值范围均为1~~给定的颜色数m4•简述分支限界法的思想。答：从根结点开始，以广度优先（最小耗费优先或最大效益优先）的方式进行搜索。根结点插入活结点表中，重复做如下操作：从活结点表中取出一个活结点作为当前的扩展结点，一次性生成扩展结点的所有孩子结点，判断孩子结点是舍弃还是保留，保留那些有可能导致可行解或可能导致最优解的孩子结点，将保留下来的孩子结点插入到活结点表中。算法直到找到问题的解或活结点表为空为止。四、 求解题（共28分）1.（8分）用回溯法解如下旅行售货员问题。假设当前旅行售货员的住地为1号城市，边上的权为城市之间的交通费用，要求从1号城市出发，到其它城市各去一次推销商品，然后再回到住地所花费的总交通费用最少的路线。（要求：做好搜索前的准备，然后用搜索树展示搜索过程）解：（1）解的形式为n元组（x1,x2,x3,x4），其中xi表示第i个要去推销商品的城市为X号城市。令城市集合为S={1,2,3,4}则x1=1,x2={2,3,4}x3=S-{x1»x2},x4=S-{x1,x2,x3}（2）解空间的组织结构：排列树，深度为4⑶搜索：约束条件:a[x[t-1]][x[t]]!=8限界条件：cf+rcost<bestf或cf+a[x[t-1]][x[t]]<bestf其中a[]□为图的邻接矩阵，cf:当前已花费的费用，bestf：当前最优路线所花费的费用，rcost：剩余费用的最小值。搜索树如下x1=1x2=2x3=3 4x4=4（8分）给定7个作业，要在两台机器M]、M2组成的流水线上完成加工。每个作业都是先在上加工,然后在M上加工。在M上处理时间为：（a,a,a,a,a,a,a）=（3,8,2,9,5,4,4）,在M上的处理时间为:2112345672（b,b,b,b,b,b,b）=（2,6,7,10,5,3,8）,按照流水作业调度问题的Johnson算法步骤，给出该问题1 2 3 4 5 6 7的最优调度方案。（要求：先写出Johns。n算法步骤，然后写出每一个步骤对应的求解情况）解：1）N’={i|a.<b.}={347} N2={i|a.Mb.}={l256}1ii2ii2） 将叫按照a.非减序排序，将N2按照b.非增序排序。1.2.N={374}N={2561}123） N接N即为所求的最优调度N=NN={3742561}1212（12分）给定下图的一个网络及网络上的可行流，从给定的可行流出发，采用增广路算法找出最大网络流。有向边上对应的值为（容量：ap，流量flow）。要求：解答体现在网络中标号过程和找到的增广路，每一次增流后的可行流及最后的最大流。2竺4（3,3）/*1/（1,1）按顶点序号由小到大的原则选择已标号未检查的点）解：(5,1)(1,1)'3.(2,0)■冬(5,3)(3,0)76上5乙1)0,+®0,+®0,+®(3,3)zx1(5,2)五、算法设计(-5,1)2 (4,3)IA丄(5,2)4(5,3)(1,1(卜0)n(5,1)丫”5严)(1,4) (3,2)(3,3)(5,3)(3,3)(5,3)\o"CurrentDocument"(-5,1) (5,1)\o"CurrentDocument"2 (4,3) 42 4・\Xi一 I(5,4)(1,1(3,1)6 (4,1)3 (13)(2,2)二丫2,2)(3,1)2 (4,3)人__x 、)3)(1,1(3,1)¥、6(2,2)共12分）：说明：任意选择所使用的算法策略。要求：说明所使用的算法策略；写出算法实现的主要步骤（可用自然语言描述，也可以计算机编程语言描述）；题目：0-1背包问题解：回溯法（定义解的结构，确定解空间树，确定限界函数，深度优先方式搜索，判断当前是否到叶子节点，若到了叶子节点，则修正最优值，若是中间节点，判断是否满足约束函数和限界函数，满足则深一步搜索，若不满足，则剪枝）分支限界法：（定义解的结构，确定解空间树，确定限界函数，深度优先方