算法设计与分析A11卷答案

PAGEPAGE1共3页系系专业班级姓名考号（密封线内不准答题）课程：算法设计与分析评卷人（签名）：复核人（签名）：题号一二三四五总分得分一、选择题（每小题3分，共15分）1．算法与程序的主要区别在于算法具有（）。A．能行性B．确定性C．有限性D．输入和输出答案：C。2．对一个有序序列，以比较为基础的搜索算法的最坏情况时间复杂性的下界为（）。A．Ω(n)B．Ω(n2)C.Ω(nlogn)D．Ω(logn)答案：D。3．背包问题：n=6，C=10，V(1:6)=(15,59,21,30,60,5)，W(1:6)=(1,5,2,3,6,1）。该问题的最大价值为（）。A．101B．110C．115D．120答案：C。4．矩阵连乘积问题：M1(5×10),M2(10×4),M3(4×6)。矩阵链乘M1M2M3需要的最少乘法次数为（）。A．348B．328C．720D．320答案：D。5．用贪心策略设计算法的关键是（）。A．将问题分解为多个子问题来分别处理B．选好贪心策略C．获取各阶段间的递推关系式D．满足最优性原理答案：B。二、填空题（每小题4分，共20分）1．某算法的计算时间T(n)满足递归关系式：T(n)=2T(n-1)+O(1)，n>1；T(1)=1。则T(n)=。答案：2n-1。2．用方法对状态空间树进行搜索时，每个结点有可能多次成为扩展结点。3．子集和数问题一般陈述如下：已知n+1个正数：wi(1≤i≤n)和M，要求找出wi的和数是M的所有子集。其解可以表示为n-元组(x1,x2,⋯,xn)，这里xi∈{0,1}，1≤i≤n。如果没有选择wi，则相应的xi=0；如果选择了wi，则xi=1。此解空间的空间树上有个叶结点，共有个结点。答案：2n,2n+1-1。4．已知将两个分别包含n个和m个记录的已分类文件归并在一起得到一个分类文件需作n+m次记录移动。现有五个已分类文件F1,F2,F3,F4,F5，它们的记录个数分别为25,40,15,10,40，将这五个文件归并成一个分类文件需作次记录移动。注：每次只能归并两个文件。答案：285。5．两个序列A=“xyxxzxyzxy”和B=“zxzyyzxxyxxz”的最长的公共子序列的长度为________。其中一个最长公共子序列为。答案：6,xzyzxy。三、问答题（每小题5分，共20分）1.快速排序算法是根据分治策略来设计的，简述其基本思想。答：快速分类算法是根据分治策略设计出来的算法。其关键步骤就是“划分”：根据某个元素v为标准，将序列中的元素重新整理，使得整理后的序列中v之前的元素都不大于v，而v之后的元素都不小于v。此时，元素v即找到了其最终的位置。要得到序列的排序结果，再只需对v之前的元素和v之后的元素分别排序即可，这可通过递归处理来完成。2．简述蒙特卡罗算法的特点及提高蒙特卡罗算法得到的为正确的概率的措施？答：在某些实际应用中经常会遇到一些问题，不论采用确定性算法还是概率算法都无法保证每次得到正确的解。蒙特卡罗算法在一般情况下，可以保证对问题的所有实例都以高概率给出正确解，但是通常无法判定一个具体解是否正确。使用蒙特卡罗算法肯定能得到问题的一个解，但是这个解未必是正确的。可以通过重复调用同一个蒙特卡洛算法多次来提高获得正确解的概率。3．简述回溯法的基本思想。答：回溯法的基本思想是：深度优先搜索+剪枝。从根结点开始，以深度优先的方式进行搜索，搜索的过程中，每搜索到一个结点，检查是否满足约束函数和限界函数，如果满足，则更深一层的搜索，如果不满足，则剪枝，搜索过程直到找到问题的解或所有活结点变成死结点为止。回溯法用来求问题的多个解。4．简述最小生成树的Kruskal算法的基本思想。答：按照图中边权由大到小的次序依次考虑每条边是否加入最小生成树中。当考虑到某条边时，如果该边与已经加入到最小生成树中的边不形成回路，则将该边加入进去。四、求解题1．（5分）设f(N)、g(N)是定义在正数集上的正函数。如果存在正的常数C和自然数N0，使得当N≥N0时有f(N)≤Cg(N)，则成函数f(N)当N充分大时上有界，且g(N)是它的一个上界，记为f(N)=O(g(N))。证明：O(f(N))+O(g(N))=O(max{f(N)，g(N)})。解：2．（8分）用动态规划解决0-1背包问题的改进算法求解如下实例：n=4，c=12，v=（18，15，8，12），w=（10，2，3，4）。（要求：先写出计算公式，再写具体的求解过程，指出最优值和最优解）解：p[n+1]={(0,0)}p[i]=p[i+1]∪p[i+1](wi,vi)去掉受控点。P[5]={(0,0)}P[4]={(0,0),(4,12)}P[3]={(0,0),(3,8),(4,12),(7,20)}P[2]={(0,0),(2,15),(5,23),(6,27),(9,35)}P[1]={(0,0),(2,15),(5,23),(6,27),(9,35)}最优值为35，最优解为（0,1,1,1）3.（10分）用单纯性算法求解下面线性规划问题：maxz=-x2+3x3-2x4s.t.x1+3x2-x3+2x4=7-4x2+3x3+8x4≤102x2-4x3≥-12xi≥0（i=1,2,3,4）要求：（1）步骤描述（2）写清每一迭代步的选择，单纯形表，可行解及可行解对应的目标函数的值。解：线性规划的约束标准型为：maxz=-x2+3x3-2x4s.t.x1+3x2-x3+2x4=7x5-4x2+3x3+8x4=10x6-2x2+4x3=12xi≥0（i=1,2,3,4,5,6）初始单纯形表Cx2x3x4z0-13-2x173-12x510-438x612-240z=0,x=(7,0,0,0,10,12)第一步迭代（1）选入基变量x3（2）选离基变量x6（3）转轴变换Cx2x6x4z91/2-3/4-2x1105/21/42x51-5/2-3/48x33-1/21/40z=9,x=(10,0,3,0,1,0)第二步迭代（1）选入基变量x2（2）选离基变量x1（3）转轴变换Cx1x6x4z11-1/5-4/5-12/5x242/51/104/5x5111-1/210x351/53/102/5Z行非基变量的系数全部为负，迭代结束，最大值为11，最优解为（0,4,5,0,11,0）4.（10分）单源最短路径问题：在下图实例上指定源点为1，目标点为6，应用优先队列式分支限界法找出1到6的最短路径。（要求写明优先级，画出搜索树，标出最短路径）解：优先级：当前结点所代表的最短路径长度，长度越小，优先级越高搜索树：五、算法设计（共13分）：说明：任意选择所使用的算法策略。要求：说明所使用的算法策略；写出算法实现的主要步骤；题目：n后问题策略1：回溯法（定义解的结构，确定解空间树，确定约束函数，深度优先方式搜索，判断当前是否到叶子节点，若到了叶子节点，则找到了一种着色方案，将其方案输出，并将方案个数加1，若是中间节点，判断是否满足约束条件，若满足，