算法设计试卷模式B答案.doc

系 专业班级姓名考号（密封线内不准答题）南阳理工学院20102011学年第一学期试卷答案课程： 算法设计与分析 （B）评卷人（签名）： 复核人（签名）： 题号一二三四五总分得分一、选择题（每小题1分，共10分）1. 选出不是算法所必须具有的特征( C )。A有限性 B确定性 C高效性 D 能行性2. 下列( A )不是描述算法的工具。A数据流图 B伪代码 C自然语言 D程序语言3. 下列程序段的算法时间复杂度为( D )。for(int i=0;i=n;i+）for(int j=0;j=m;j+) S;/S是基本操作，耗时常数时间A B. C. D4. 5个矩阵连乘可能的计算次序有( C )种。A4种 B5种 C14种 D15种5. 折半查找算法在最坏情况下的复杂度为( D )。 A O(n) B O(n2) C O(nlogn) D O(logn)6. Fibonacci数列的第1项为0，第2项为1，那么它的第9项为( C )。 A 3 B 13 C 21 D347. 如果X序列包含20个字符，Y序列包含30个字符，则使用动态规划来解最长公共子序列问题，记录各子问题最优值的数组大小为( A )A651 B600 C620 D6308. 背包问题：n=6，C=10，V(1:6)=(15，59，21，30，60，5)，W(1:6)=(1，5，2，3，6，1）。该问题的最大价值为（C ）。A101 B110 C115 D1209. 用贪心策略设计算法的关键是（ B ）。A将问题分解为多个子问题来分别处理 B选好贪心策略C获取各阶段间的递推关系式 D满足最优性原理10. 下列排序算法不是基于交换的是( C )A冒泡排序 B 快速排序 C 合并排序 D 堆排序二、填空题（每空2分，共30分）1请将快速排序的分治算法补充完整。数组a存放待排序元素，left:为待排序元素最小下标，right:为待排元素最大下标。int Partition(int a,int left,int right)int x=aleft;int i=left+1;int j=right;while(true)while(ai x & i x) j- ;if(i=j) break ;swap(ai,aj);aleft=aj;aj=x;return j;void QuickSort(int a,int left,int right)if(leftright)int p=Partition(a,left,right);QuickSort (a,left,p-1);QuickSort (a,p+1,right);2动态规划四大解题步骤包括最优子结构性质分析、 建立最优值的递归关系式 、自底向上求最优值并记录相关信息、根据记录下来的信息构造最优解。3矩阵连乘问题求最优直算法的复杂度是 O(n3) 。4哈夫曼编码算法中采用的贪心策略是 从树的集合中取出两棵出现频率最低的树，让它们作为左右子树构造一棵新树，插入到树的集合中。5旅行商问题的解空间树是一棵 排列 树，n皇后问题的满足不同行要求的解空间树是一棵满n叉树。图的m着色问题的解空间树是一棵满m叉树。6随机化算法中， 蒙特卡罗 算法用于求准确解， 数值随机化 算法用于求近似解；用于求问题的正确解 拉斯维加斯算法 算法，但是，算法的每一次运行不一定得到解。当确定性算法中，最坏情况和最好情况下时间的相差很大时，用 舍伍德 算法削弱这种差异。三、问答题（每小题分，共20分）1分治算法有何特征。答：分治算法具有以下特征：（1）问题规模足够小时容易解决；（2）将规模大的问题分成规模较小的子问题；（3）子问题相互独立；（4）子问题的解决方法与原问题相同；（5）递归解决子问题；（6）子问题的解能够合并成原问题的解。2简述单源最短路径问题的Dijkstra算法的思想。答：初始时令S=源点，Dist数组记录最短特殊路径长度，重复做如下操作：选择一条特殊路径长度最短的，将其连接的V-S中的点加入到S中 。同时考察有没有更优的特殊路径出现。若有，则修正。算法直到S=顶点全集V为止。根据前驱数组的记录，构造最优解。3简述回溯法搜索的思想。答：从根节点出发，以深度优先的方式进行搜索。判断当前是否到叶子节点，若到了叶子节点，则修正最优值，若是中间节点，判断是否满足约束函数和限界函数，满足则深一步搜索，若不满足，则剪枝）4简述批处理作业调度问题的解空间的定义。答：批处理作业调度问题解的形式为一个n元组（x1,x2,xn），其中n表示作业数。xi:表示第i个要处理的作业编号为xi号，i=1,2,3,n。每个分量的取值如下；令S=1,2,3，n作业编号的集合。则xiS-x1,x2,xi-1,i=1,2,3,n四、求解题1.（8分）用优先队列式分支限界法解如下旅行售货员问题。假设当前旅行售货员的住地为1号城市，边上的权为城市之间的交通费用，要求从1号城市出发，到其它城市各去一次推销商品，然后再回到住地所花费的总交通费用最少的路线。（要求：做好搜索前的准备，然后用搜索树展示搜索过程）解：优先级；当前活结点的费用，费用越小，优先级越高。判断标准：axt-1xt!= 并且 cf+rcostbestf或cf+ axt-1xtbestf搜索树：2.（8分）用动态规划解决0-1背包问题的跳跃点算法求解如下实例：n=4，c=12，v=（18，15，8，12），w=（10，2，3，4）。（要求：先写出计算公式，再写具体的求解过程，指出最优值和最优解）解：初始pn=(0,0)qi+1=pi+1(wi,vi)pi= pi+1 qi+1并且去掉受控点（受控点指的是重量增加，价值反而下降的点）p5=(0,0) q5=(4,12) p4=(0,0),(4,5) q4=(3,8),(7,13) p3=(0,0),(3,8),(7,13) q3=(2,15),(5,23),(9,28) p2=(0,0),(2,15),(5,23),(9,28) q2=(10,18),(12,33) p1=(0,0),(2,15),(5,23),(9,28),(12,33)由此得：该0-1背包问题的最优值为33，此时装入背包的物品的重量为12，根据构造最优解的算法的最优解为：（1 1 0 0）3.（12分）用单纯性算法求解下面约束标准型线性规划问题：min z= x2-3x3+2x4s.t . -2x2+4x3 +x5=12-4x2+3x3+8x410x1+3x2- x3 +2x4 = 7 xi0 （i=1,2,3,4,5）解：将线性规划问题转化为约束标准型如下： max z=-x2+3x3-2x4s.t . -2x2+4x3 +x5=12 -4x2+3x3 +8x4+x6=10x1+3x2- x3 +2x4 = 7xi0 （i=1,2,3,4,5,6）有约束标准型可知：x1,x5,x6是基变量，x2,x3,x4是非基变量，将上述表达式中所包含的信息记录在单纯形表1中x2x3x4cz-13-20x13-127x5-24012x6-43810单纯形表1基本可行解为X（0）=（7,0,0,0,12,10）,z=0由单纯形表1可知：x3为入基变量，x5为离基变量，迭代得单纯形表2x2x4x5cz1/2-2-3/49x15/221/410x3-1/201/43x6-5/28-3/41单纯形表2基本可行解为X(1)=（10,0,3,0,0,1）,z=9由单纯形表2可知：x2为入基变量，x1为离基变量，迭代得单纯形表3x1x4x5cz-1/5-12/5-4/511x22/54/51/104x31/52/53/105x6110-1/211单纯形表3基本可行解为X（2）=（0,4,5,0,0,11）,z=11单纯形表3中z行非基变量的系数全部为负值，目标函数的最优值为11，最优解为：X(2)=（0,4,5,0,0,11）。故原问题的最小值为-11，最优解为：X(2)=（0,4,5,0,0,11）五、算法设计（共12分）：说明：任意选择所使用的算法策略。 要求：说明所使用的算法策略；写出算法实现的主要步骤（可用自然语言描述，也可以计算机编程语言描述）；题目：0-1背包问题解：回溯法（定义解的结构，确定解空间树，确定限界函数，深度优先方式搜索，判断当前是否到叶子节点，若到了叶子节点，则修正最优值，若是中间节点，判断是否满足约束函数和限界函数，满足则深一步搜索，若不满足，则剪枝）分支限界法：（定义解的结构，确定解空间树，确定限界函数，深度优先方式搜索，判断当前是否到叶子节点