《算法设计试卷模式B答案》由会员分享，可在线阅读，更多相关《算法设计试卷模式B答案（3页珍藏版）》请在金锄头文库上搜索。
1、南阳理工学院南阳理工学院 2010201020112011 学年第一学期试卷答案学年第一学期试卷答案课程：课程： 算法设计与分析算法设计与分析 （B B）评卷人（签名）： 复核人（签名）： 题号一二三四五总分得分一、选择题（每小题 1 分，共 10 分） 1.选出不是算法所必须具有的特征( C )。 A有限性 B确定性 C高效性 D 能行性 2.下列( A )不是描述算法的工具。 A数据流图 B伪代码 C自然语言 D程序语言 3.下列程序段的算法时间复杂度为( D )。 for(int i=0;i x)j-j- ;if(i=j) breakbreak ; ;swap(ai,aj);aleft=
2、aj;aj=x;return j;void QuickSort(int a,int left,int right)if(leftright)int p=Partition(a,left,right);QuickSortQuickSort (a,left,p-1);(a,left,p-1);QuickSort (a,p+1,right); 2动态规划四大解题步骤包括最优子结构性质分析最优子结构性质分析、 建立最优值的递归关系式建立最优值的递归关系式 、自底向上求最优 值并记录相关信息、根据记录下来的信息构造最优解。 3矩阵连乘问题求最优直算法的复杂度是 O(n3) 。 4哈夫曼编码算法中采用的贪
3、心策略是 从树的集合中取出两棵出现频率最低的树，让它们作为左右从树的集合中取出两棵出现频率最低的树，让它们作为左右 子树构造一棵新树，插入到树的集合中。子树构造一棵新树，插入到树的集合中。 5旅行商问题的解空间树是一棵 排列排列 树，n 皇后问题的满足不同行要求的解空间树是一棵满满 n 叉叉 树树。图的 m 着色问题的解空间树是一棵满满 m 叉叉树。 6随机化算法中， 蒙特卡罗蒙特卡罗 算法用于求准确解， 数值随机化数值随机化 算法用于求近似解；用于求问题的 正确解 拉斯维加斯算法拉斯维加斯算法 算法，但是，算法的每一次运行不一定得到解。当确定性算法中，最坏情况 和最好情况下时间的相差很大时，
4、用 舍伍德舍伍德 算法削弱这种差异。 三、问答题（每小题分，共 20 分） 1分治算法有何特征。 答：分治算法具有以下特征：（答：分治算法具有以下特征：（1）问题规模足够小时容易解决；（）问题规模足够小时容易解决；（2）将规模大的问题分成规模较小）将规模大的问题分成规模较小 的子问题；（的子问题；（3）子问题相互独立；（）子问题相互独立；（4）子问题的解决方法与原问题相同；（）子问题的解决方法与原问题相同；（5）递归解决子问题；）递归解决子问题； （6）子问题的解能够合并成原问题的解。）子问题的解能够合并成原问题的解。系 专业 班级 姓名 考号 （密 封 线 内 不 准 答 题）2简述单源最短
5、路径问题的 Dijkstra 算法的思想。 答：初始时令答：初始时令 S=源点源点，Dist 数组记录最短特殊路径长度，重复做如下操作：数组记录最短特殊路径长度，重复做如下操作： 选择一条特殊路径长度最短的，将其连接的选择一条特殊路径长度最短的，将其连接的 V-S 中的点加入到中的点加入到 S 中中 。同时考察有没有更优的特殊路。同时考察有没有更优的特殊路 径出现。若有，则修正。算法直到径出现。若有，则修正。算法直到 S=顶点全集顶点全集 V 为止。根据前驱数组的记录，构造最优解。为止。根据前驱数组的记录，构造最优解。 3简述回溯法搜索的思想。答：从根节点出发，以深度优先的方式进行搜索。判断当
6、前是否到叶子节点，若到了叶子节点，答：从根节点出发，以深度优先的方式进行搜索。判断当前是否到叶子节点，若到了叶子节点，则修正最优值，若是中间节点，判断是否满足约束函数和限界函数，满足则深一步搜索，若不满足，则修正最优值，若是中间节点，判断是否满足约束函数和限界函数，满足则深一步搜索，若不满足，则剪枝）则剪枝）4简述批处理作业调度问题的解空间的定义。答：答：批处理作业调度问题解的形式为一个解的形式为一个 n 元组（元组（x1,x2,xn） ，其中，其中 n 表示作业数。表示作业数。xi:表示第表示第 i 个要个要 处理的作业编号为处理的作业编号为 xi 号，号，i=1,2,3,n。每个分量的取值
7、如下；令。每个分量的取值如下；令 S=1,2,3，n作业编号的集合。作业编号的集合。 则则 xiS-x1,x2,xi-1,i=1,2,3,niS-x1,x2,xi-1,i=1,2,3,n四、求解题 1.（8 分）用优先队列式分支限界法解如下旅行售货员问题。假设当前旅行售货员的住地为 1 号城市， 边上的权为城市之间的交通费用，要求从 1 号城市出发，到其它城市各去一次推销商品，然后再回到 住地所花费的总交通费用最少的路线。 （要求：做好搜索前的准备，然后用搜索树展示搜索过程）123410126458解：优先级；当前活结点的费用，费用越小，优先级越高。解：优先级；当前活结点的费用，费用越小，优先
8、级越高。 判断标准：判断标准：axt-1xt!= 并且并且 cf+rcostbestfcf+rcostbestf 或或 cf+cf+ axt-1xtbestfbestf 搜索树：搜索树：x1=1x2=234x3=342423x4=22.（8 分）用动态规划解决 0-1 背包问题的跳跃点算法求解如下实例： n=4，c=12，v=（18，15，8，12） ，w=（10，2，3，4） 。 （要求：先写出计算公式，再写具体的求解过 程，指出最优值和最优解）解：初始解：初始 pn=(0,0)pn=(0,0)qi+1=pi+1qi+1=pi+1(wi,vi)(wi,vi) pi=pi= pi+1pi+1
9、qi+1qi+1并且去掉受控点（受控点指的是重量增加，价值反而下降的点）并且去掉受控点（受控点指的是重量增加，价值反而下降的点）p5=(0,0)p5=(0,0) q5=(4,12)q5=(4,12)p4=(0,0),(4,5)p4=(0,0),(4,5) q4=(3,8),(7,13)q4=(3,8),(7,13)p3=(0,0),(3,8),(7,13)p3=(0,0),(3,8),(7,13) q3=(2,15),(5,23),(9,28)q3=(2,15),(5,23),(9,28)p2=(0,0),(2,15),(5,23),(9,28)p2=(0,0),(2,15),(5,23),(
10、9,28) q2=(10,18),(12,33)q2=(10,18),(12,33)p1=(0,0),(2,15),(5,23),(9,28),(12,33)p1=(0,0),(2,15),(5,23),(9,28),(12,33) 由此得：该由此得：该 0-10-1 背包问题的最优值为背包问题的最优值为 3333，此时装入背包的物品的重量为，此时装入背包的物品的重量为 1212，根据构造最优解的算法，根据构造最优解的算法 的最优解为：（的最优解为：（1 1 1 1 0 0 0 0）3.（12 分）用单纯性算法求解下面约束标准型线性规划问题：min z= x2-3x3+2x4 s.t . -2
11、x2+4x3 +x5=12 -4x2+3x3+8x410 x1+3x2- x3 +2x4 = 7 xi0 （i=1,2,3,4,5） 解：将线性规划问题转化为约束标准型如下：解：将线性规划问题转化为约束标准型如下：maxmax z=-xz=-x2 2+3x+3x3 3-2x-2x4 4 s.ts.t . . -2x-2x2 2+4x+4x3 3 +x+x5 5=12=12-4x-4x2 2+3x+3x3 3 +8x+8x4 4+x+x6 6=10=10 x x1 1+3x+3x2 2- - x x3 3 +2x+2x4 4 = = 7 7 x xi i00 （i=1,2,3,4,5,6i=1,
12、2,3,4,5,6） 有约束标准型可知：有约束标准型可知：x x1 1,x,x5 5,x,x6 6是基变量，是基变量，x x2 2,x,x3 3,x,x4 4是非基变量，将上述表达式中所包含的信息记录在是非基变量，将上述表达式中所包含的信息记录在 单纯形表单纯形表 1 1 中中x x2 2x x3 3x x4 4c cz z-1-13 3-2-20 0x x1 13 3-1-12 27 7x x5 5-2-24 40 01212x x6 6-4-43 38 81010单纯形表单纯形表 1 1 基本可行解为基本可行解为 X X（0 0）= =（7,0,0,0,12,107,0,0,0,12,10
13、）,z=0,z=0 由单纯形表由单纯形表 1 1 可知：可知：x x3 3为入基变量，为入基变量，x x5 5为离基变量，迭代得单纯形表为离基变量，迭代得单纯形表 2 2x x2 2x x4 4x x5 5c cz z1/21/2-2-2-3/4-3/49 9x x5/25/22 21/41/410101 1 x x3 3-1/2-1/20 01/41/43 3x x6 6-5/2-5/28 8-3/4-3/41 1单纯形表单纯形表 2 2 基本可行解为基本可行解为 X X(1)(1)= =（10,0,3,0,0,110,0,3,0,0,1）,z=9,z=9由单纯形表由单纯形表 2 2 可知：
14、可知：x x2 2为入基变量，为入基变量，x x1 1为离基变量，迭代得单纯形表为离基变量，迭代得单纯形表 3 3x x1 1x x4 4x x5 5c cz z-1/5-1/5-12/5-12/5-4/5-4/51111x x2 22/52/54/54/51/101/104 4x x3 31/51/52/52/53/103/105 5x x6 61 11010-1/2-1/21111单纯形表单纯形表 3 3 基本可行解为基本可行解为 X X（2 2）= =（0,4,5,0,0,110,4,5,0,0,11）,z=11,z=11 单纯形表单纯形表 3 3 中中 z z 行非基变量的系数全部为负
15、值，目标函数的最优值为行非基变量的系数全部为负值，目标函数的最优值为 1111，最优解为：，最优解为： X X(2)(2)= =（0,4,5,0,0,110,4,5,0,0,11） 。故原问题的最小值为。故原问题的最小值为-11-11，最优解为：，最优解为：X X(2)(2)= =（0,4,5,0,0,110,4,5,0,0,11）五、算法设计（共 12 分）：说明：任意选择所使用的算法策略。 要求：说明所使用的算法策略；写出算法实现的主要步骤（可用自然语言描述，也可以计算机编程语言描述） ；题目：0-1 背包问题解：回溯法（定义解的结构，确定解空间树，确定限界函数，深度优先方式搜索，判断当前是否解：回溯法（定义解的结构，确定解空间树，确定限界函数，深度优先方式搜索，判断当前是否到叶子节点，若到了叶子节点，则修正最优值，若是中间节点，判断是否满足约束函数和限界函数，到叶子节点，若到了叶子节点，则修正最优值，若是中间节点，判断是否满足约
