算法分析试卷A4卷答案

PAGEPAGE5系系专业班级姓名学号课程：算法设计与分析答案（启用前保密）题号一二三四五总分得分一、选择题（每题2分，共10分）1．下列说法正确的是（D）A．算法就是程序，程序就是算法。B．算法和程序都能直接在计算机上执行C．算法能直接在计算机上执行。D．程序能直接在计算机上执行。2．对于函数f(n)=logn2，g(n)=logn+5，下列说法错误的是（D）A．f(n)=(g(n))B．f(n)=(g(n))C．f(n)=(g(n))D．以上说法不全对3．用贪心算法解决背包问题时的贪心策略是（C）A．重量小的物品优先装入背包。B．价值大的物品优先装入背包。C．单位重量的价值大的物品优先装入背包。D．单位重量的价值小的物品优先装入背包。4．回溯法求解n个顶点的图的最大团问题时，算法的复杂度是（C）A．O(nmn)B.O(n2)C.O(n2n)C.O(2n)5．给定有序序列T[]={1,4,6,8,10,12}，现在要用二分搜索算法查找给定元素x=8是否出现在序列T中，元素x要和序列元素比较（B）次能够得出结论。A．5B．3C．4D．2二、填空题（每空2分，共30分）1．算法是由若干条指令组成的有穷序列，且满足输入、输出、确定性、有限性和能行性共5条性质。2．用二分搜索算法在一个有序序列a[1:n]中查找某指定元素x是否存在。在查找的过程中，假定当前查找的范围是a[low:high]，其中1≤low≤high≤n。分治策略中的分解操作是(low+high)/2。3．用A[1:n]表示A1…An连乘，用动态规划求解A[1:n]时，计算各子问题最优值的复杂度是O(n3)。4．回溯法算法框架中定义问题的解空间时，解的形式是(x1,x2,…,xn)；解空间结构的组织形式通常有子集树、排列树、满m叉树。5．分支限界法中，从活结点表中选择下一个扩展结点的不同方式导致了不同的分支限界法，最常见的有队列式分支限界法和优先队列式分支限界法。6．一般情况下，可将随机化算法大致分成4类，分别是数值随机化算法、拉斯维加斯算法、舍伍德算法和蒙特卡罗算法。7．一般线性规划问题的约束条件如果是小于等于的约束，可以通过添加一个非负变量的方法将其转换为等于的约束。8．给定一个网络G=(V,E)及其上的可行流flow，假设网络G上的某条(v,w)的流量为95，容量为95，那么该边对应于残流网络中反方向的一条边，它的容量为95。三、简答题（每小题5分，共20分）1．简述蒙特卡罗算法的特点并举例说明。答：在某些实际应用中经常会遇到一些问题，不论采用确定性算法还是概率算法都无法保证每次得到正确的解。蒙特卡罗算法在一般情况下，可以保证对问题的所有实例都以高概率给出正确解，但是通常无法判定一个具体解是否正确。使用蒙特卡罗算法肯定能得到问题的一个解，但是这个解未必是正确的。如主元素问题，统计随机产生的元素是否为主元素，当返回true时，结论一定是正确的，当返回false时，结论不一定正确。但是得到的结论为正确解的概率大于0.5。2．简述分治法的基本思想。答：将规模为n的问题分解为k个规模较小的子问题，子问题相互独立并且与原问题相同。递归地解决这些子问题，然后将子问题的解合并得到原问题的解。3．简述哈夫曼编码算法的思想。答：将n个字符看做是n可孤立的树，组成一个结合。重复做如下操作：从集合中取出两棵出现频率最低的树，让它们作为左右子树构成一棵新树，新树的频率为左右子树频率之和。然后将新树插入到树的集合中；算法知道集合中只剩下一棵树为止。4．简述动态规划算法的基本要素。答：动态规划算法的基本要素包括最优子结构性质、重叠子问题及自底向上的求解方法。四、求解题（5+5+9+11=30分）1．（5分）采用合并排序的思想将给定序列T[1:9]={5,3,8,2,1,9,23,12,6}由小到大排序。(要求：只写出首次分解得到两个子问题的过程、递归的结果、子问题的解合并成原问题的解的过程)解：(1)(1+9)/2=5(2)两个子问题分别是：T[1:5]和T[6:9](3)递归的结果T1:5]={1,2,3,5,8}T[6:9]={6,9,12,23}(4)将两个子问题的解合并得到原问题的解，合并过程如下：a)根据合并算法，首先将1,2,3,5放到辅助数组中b)将6放到辅助数组中c)将8放到辅助数组中，d)将9,12,23放到辅助数组中。这样就得到一个有序的序列。(5)将辅助数组中的元素复制到数组T中，得到T[1:9]={1,2,3,5,6,8,9,12,23}2．（5分）请用Kruskal算法求解下图所示的最小生成树（要求：写出生成最小生成树的过程）解：先将图中的边按照边上的权由小到大排序，排好序的序列如下：(1,3)、(4,6)、(2,5)、(3,6)、(2,3)、(4,3)、(1,4)、(1,2)、(5,3)、(6,5)。3．（9分）有0-1背包问题如下：n=4，c=12，P=（18，15，8，12），W=（10，2，3，4）。试用动态规划的跳跃点算法求出问题的最优解和最优值。（要求先写出公式，再写出求解过程）解：公式：初始化p[n+1]={(0,0)}q[i+1]=p[i+1](wi,vi)p[i]=p[i+1]∪q[i+1]去掉受控点求解过程：初始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,12)}q[4]={(3,8),(7,20)}p[3]={(0,0),(3,8),(4,12),(7,20)}q[3]={(2,15),(5,23),(6,27),(9,35)}p[2]={(0,0),(2,15),(5,23),(6,27),(9,35)}q[2]={(10,18),(12,33)}p[1]={(0,0),(2,15),(5,23),(6,27),(9,35)}由此得：该0-1背包问题的最优值为35，此时装入背包的物品的重量为9，根据构造最优解的算法的最优解为：（0111）4．（11分）用增广路算法找出下图所示网络的最大流，其中，顶点1为源点，顶点6为汇点，边上的权为(cap,flow)。（要求：解答体现在网络中标号过程和找到的增广路，每一次增流后的可行流及最后的最大流。按顶点序号由小到大的原则选择已标号未检查的点）解：标号法找增广路如图1所示。注：增广路在图中用黑粗线表示。沿着增广路增流，增加的流量d=3。增流后得到的新的可行流如图2所示.。根据增广路算法，取消所有顶点的标号，给它们重新标号如图3所示。沿着增广路增流，增加的流量d=1。增流后的可行流如图4所示。根据增广路算法，取消所有顶点的标号，给它们重新标号如图5所示。沿着增广路增流，增加的流量d=2，增流后的可行流如图6所示。重新开始标号，标号过程进行到3号顶点后无法继续进行，当前网络中已没有关于当前可行流的可增广路，该可行流已达到了最大流，如图7所示。五、算法设计（10分）说明：选用任意算法设计策略。要求：写出算法策略的思想；写出算法实现的主要步骤；题目：n后问题，给出一种放置方案。解：策略1：回溯法（定义解的结构，确定解空间树，确定约束函数和限界函数，深度优先方式搜索，判断当前是否到叶子节点，若到了叶子节点，则修正最优值，若是中间节点，左子树判断是否满足约束条件，若满足，则深一步搜索，否则剪枝。右子树判断是否满足限界函数，若满足，则深一步搜索，若不满足，则剪枝）策略2：分支限界法（定义解的结构，确定解空间树，确定约束函数和限界函数，当前背包的价值