算法设计试卷模式B答案

共3页1南阳理工学院2010－2011学年第一学期试卷答案课程：算法设计与分析（B）评卷人（签名）：复核人（签名）：题号一二三四五总分得分一、选择题（每小题1分，共10分）1.选出不是算法所必须具有的特征(C)。A．有限性B．确定性C．高效性D．能行性2.下列(A)不是描述算法的工具。A．数据流图B．伪代码C．自然语言D．程序语言3.下列程序段的算法时间复杂度为(D)。for(inti=0;i=n;i++）for(intj=0;j=m;j++)S;//S是基本操作，耗时常数时间A．)(2nOB.)(2mOC.)(mnOD．)(nmO4.5个矩阵连乘可能的计算次序有(C)种。A．4种B．5种C．14种D．15种5.折半查找算法在最坏情况下的复杂度为(D)。A．O(n)B．O(n2)C．O(nlogn)D．O(logn)6.Fibonacci数列的第1项为0，第2项为1，那么它的第9项为(C)。A．3B．13C．21D．347.如果X序列包含20个字符，Y序列包含30个字符，则使用动态规划来解最长公共子序列问题，记录各子问题最优值的数组大小为(A)A．651B．600C．620D．6308.背包问题：n=6，C=10，V(1:6)=(15，59，21，30，60，5)，W(1:6)=(1，5，2，3，6，1）。该问题的最大价值为（C）。A．101B．110C．115D．1209.用贪心策略设计算法的关键是（B）。A．将问题分解为多个子问题来分别处理B．选好贪心策略C．获取各阶段间的递推关系式D．满足最优性原理10.下列排序算法不是基于交换的是(C)．A冒泡排序B．快速排序C合并排序D．堆排序二、填空题（每空2分，共30分）1．请将快速排序的分治算法补充完整。数组a存放待排序元素，left:为待排序元素最小下标，right:为待排元素最大下标。intPartition(inta[],intleft,intright){intx=a[left];inti=left+1;intj=right;while(true){while(a[i]x&&ihigh)i++;while(a[j]x)j--;if(i=j)break;swap(a[i],a[j]);}a[left]=a[j];a[j]=x;returnj;}voidQuickSort(inta[],intleft,intright){if(leftright){intp=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）子问题的解能够合并成原问题的解。系专业班级姓名考号（密封线内不准答题）共3页22．简述单源最短路径问题的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}作业编号的集合。则xi∈S-{x1,x2,…,xi-1},i=1,2,3,…,n四、求解题1.（8分）用优先队列式分支限界法解如下旅行售货员问题。假设当前旅行售货员的住地为1号城市，边上的权为城市之间的交通费用，要求从1号城市出发，到其它城市各去一次推销商品，然后再回到住地所花费的总交通费用最少的路线。（要求：做好搜索前的准备，然后用搜索树展示搜索过程）123410126458解：优先级；当前活结点的费用，费用越小，优先级越高。判断标准：a[x[t-1]][x[t]]!=∞并且cf+rcostbestf或cf+a[x[t-1]][x[t]]bestf搜索树：x1=1x2=234x3=342423x4=22.（8分）用动态规划解决0-1背包问题的跳跃点算法求解如下实例：n=4，c=12，v=（18，15，8，12），w=（10，2，3，4）。（要求：先写出计算公式，再写具体的求解过程，指出最优值和最优解）解：初始p[n]={(0,0)}q[i+1]=p[i+1](wi,vi)p[i]=p[i+1]∪q[i+1]并且去掉受控点（受控点指的是重量增加，价值反而下降的点）p[5]={(0,0)}q[5]={(4,12)}p[4]={(0,0),(4,5)}q[4]={(3,8),(7,13)}p[3]={(0,0),(3,8),(7,13)}q[3]={(2,15),(5,23),(9,28)}p[2]={(0,0),(2,15),(5,23),(9,28)}q[2]={(10,18),(12,33)}p[1]={(0,0),(2,15),(5,23),(9,28),(12,33)}由此得：该0-1背包问题的最优值为33，此时装入背包的物品的重量为12，根据构造最优解的算法的最优解为：（1100）3.（12分）用单纯性算法求解下面约束标准型线性规划问题：minz=x2-3x3+2x4s.t.-2x2+4x3+x5=12-4x2+3x3+8x4≤10x1+3x2-x3+2x4=7xi≥0（i=1,2,3,4,5）解：将线性规划问题转化为约束标准型如下：maxz=-x2+3x3-2x4s.t.-2x2+4x3+x5=12-4x2+3x3+8x4+x6=10x1+3x2-x3+2x4=7xi≥0（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共3页3由单纯形表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背包问题解：回溯法（定义解的结构，确定解空间树，确定限界函数，深度优先方式搜索，判断当前是否到叶子节点，若到了叶子节点，则修正最优值，若是中间节点，判断是否满足约束函数和限界函数，满足则深一步搜索，若不满足，则剪枝）分支限界法：（定义解的结构，确定解空间树，确定限界函数，深度优先方式搜索，判断当前是否到叶子节点，若到了叶子节点，则修正最优值，若是中间节点，一次性生成该节点的所有孩子节点，判断是否满足约束函数和限界函数，若满足则将其保留在活结点表中；若不满足，则剪枝）动态规划：分析最优子结构性子特征，建立递归关系式，写出计算最优值和构造最优解的算法线性规划：用单纯形算法，写出单纯形算法的步骤：（1）选如基变量（2）选离基变量（3）转轴变换，算法直到找到最优解或判断目标无界为止。共3页4薃肀莂蒃袂肀肂虿袈聿芄薂螄肈莇螇蚀肇葿薀罿肆腿莃袅肅芁薈螁膄莃莁蚇膄肃薇薃膃芅荿羁膂莈蚅袇膁蒀蒈螃膀膀蚃虿腿节蒆羈芈莄蚁袄芈蒆蒄螀芇膆蚀蚆袃莈蒃蚂袂蒁螈羀袁膀薁袆袁芃螆螂袀莅蕿蚈衿蒇莂羇羈膇薇袃羇艿莀蝿羆蒂薆螅羅膁蒈蚁羅芄蚄罿羄莆蒇袅羃蒈蚂螁羂膈蒅蚇肁芀蚁薃肀莂蒃袂肀肂虿袈聿芄薂螄肈莇螇蚀肇葿薀罿肆腿莃袅肅芁薈螁膄莃莁蚇膄肃薇薃膃芅荿羁膂莈蚅袇膁蒀蒈螃膀膀蚃虿腿节蒆羈芈莄蚁袄芈蒆蒄螀芇膆蚀蚆袃莈蒃蚂袂蒁螈羀袁膀薁袆袁芃螆螂袀莅蕿蚈衿蒇莂羇羈膇薇袃羇艿莀蝿羆蒂薆螅羅膁蒈蚁羅芄蚄罿羄莆蒇袅羃蒈蚂螁羂膈蒅蚇肁芀蚁薃肀莂蒃袂肀肂虿袈聿芄薂螄肈莇螇蚀肇葿薀罿肆腿莃袅肅芁薈螁膄莃莁蚇膄肃薇薃膃芅荿螀羀膆蒃蚆肀芈芆薂聿羈蒂蒈肈肀芅袆肇芃薀螂肆莅莃蚈肅肅薈薄蚂膇莁蒀蚁艿薇蝿螀罿荿蚅蝿肁薅薁螈膄莈薇螈莆膀袆螇肆蒆螁螆膈艿蚇螅芀蒄薃螄羀芇葿袃肂蒃螈袂膄芅蚄袂芇蒁蚀袁肆芄薆袀腿蕿蒂衿芁莂螁袈羁薇蚇袇肃莀薃羆膅薆葿羆芈荿螇羅羇膁螃羄膀莇虿羃节芀薅羂羂蒅蒁羁肄芈螀羀膆蒃蚆肀芈芆薂聿羈蒂蒈肈肀芅袆肇芃薀螂肆莅莃蚈肅肅薈薄蚂膇莁蒀蚁艿薇蝿螀罿荿蚅蝿肁薅薁螈膄莈薇螈莆膀袆螇肆蒆螁螆膈艿蚇螅芀蒄薃螄羀芇葿袃肂蒃螈袂膄芅蚄袂芇蒁蚀袁肆芄薆袀腿蕿蒂衿芁莂螁袈羁薇蚇袇肃莀薃羆膅薆葿羆芈荿螇羅羇膁螃羄膀莇虿羃节芀薅羂羂蒅蒁羁肄芈螀羀膆蒃蚆肀芈芆薂聿羈蒂蒈肈肀芅袆肇芃薀螂肆莅莃蚈肅肅薈薄蚂膇莁蒀蚁艿薇蝿螀罿荿蚅蝿肁薅薁螈膄莈薇螈莆膀袆螇肆蒆螁螆膈艿蚇螅芀蒄薃螄羀芇葿袃肂蒃螈袂膄芅蚄袂芇蒁蚀袁肆芄薆袀腿蕿蒂衿芁莂螁袈羁薇蚇袇肃莀薃羆膅薆葿羆芈荿螇羅羇膁螃羄膀莇虿羃节芀薅羂羂蒅蒁羁肄芈螀羀膆蒃蚆肀芈芆薂聿羈蒂蒈肈肀芅袆肇芃薀螂肆莅莃蚈肅肅薈薄蚂膇莁蒀蚁艿薇蝿螀罿荿蚅蝿肁薅薁螈膄莈薇螈莆膀袆螇肆蒆螁螆膈艿蚇螅芀蒄薃螄羀芇葿袃肂蒃螈袂膄芅蚄袂芇蒁蚀袁肆芄薆袀腿蕿蒂衿芁莂螁袈羁薇蚇袇肃莀薃羆膅薆葿羆芈荿螇羅羇膁螃羄膀莇虿羃节芀薅羂羂蒅蒁羁肄芈螀羀膆蒃蚆肀芈芆薂聿羈蒂蒈肈肀芅袆肇芃薀螂肆莅莃蚈肅肅薈薄蚂膇莁蒀蚁艿薇蝿螀罿荿蚅蝿肁薅薁螈膄莈薇螈莆膀袆螇肆蒆螁螆膈艿蚇螅芀蒄薃螄羀芇葿袃肂蒃螈袂膄芅蚄袂芇蒁蚀袁肆芄薆袀腿蕿蒂衿芁莂螁袈羁薇蚇袇肃莀薃羆膅薆葿羆芈荿螇羅羇膁螃羄膀莇虿羃节芀薅羂羂蒅蒁羁肄芈螀羀膆蒃蚆肀芈芆薂聿羈蒂蒈肈肀芅袆肇芃薀螂肆莅莃蚈肅肅薈薄蚂膇莁蒀蚁艿薇蝿螀罿荿蚅蝿肁薅薁螈膄莈薇螈莆膀袆螇肆蒆螁螆膈艿蚇螅芀蒄薃螄羀芇葿袃肂蒃螈袂膄芅蚄袂芇蒁蚀袁肆芄薆袀腿蕿蒂衿芁莂螁袈羁薇蚇袇肃莀薃羆膅薆葿羆芈荿螇羅羇膁螃羄膀莇虿羃节芀薅羂羂蒅蒁羁肄芈螀羀膆蒃蚆肀芈芆薂聿羈蒂蒈肈肀芅袆肇芃薀螂肆莅莃蚈肅肅薈薄蚂膇莁蒀蚁艿薇蝿螀罿荿蚅蝿肁薅薁螈膄莈薇螈莆膀袆螇肆蒆螁螆膈艿蚇螅芀蒄薃螄羀芇葿袃肂蒃螈袂膄芅蚄袂芇蒁蚀袁肆芄薆袀腿