分治法1、二分搜索算法是利用分治策略实现的算法;9. 实现循环赛日程表利用的算法是分治策略27、Strassen矩阵乘法是利用分治策略实现的算法;34．实现合并排序利用的算法是分治策略 ;实现大整数的乘法是利用的算法分治策略 ;17．实现棋盘覆盖算法利用的算法是分治法 ;29、使用分治法求解不需要满足的条件是子问题必须是一样的 ;不可以使用分治法求解的是0/1背包问题 ;动态规划下列不是动态规划算法基本步骤的是构造最优解下列是动态规划算法基本要素的是子问题重叠性质 ;下列算法中通常以自底向上的方式求解最优解的是动态规划法备忘录方法是那种算法的变形; 动态规划法最长公共子序列算法利用的算法是动态规划法 ;矩阵连乘问题的算法可由动态规划算法B设计实现;实现最大子段和利用的算法是动态规划法 ;贪心算法能解决的问题：单源最短路径问题,最小花费生成树问题,背包问题,活动安排问题,不能解决的问题：N皇后问题,0/1背包问题是贪心算法的基本要素的是贪心选择性质和最优子结构性质;回溯法回溯法解旅行售货员问题时的解空间树是排列树 ;剪枝函数是回溯法中为避免无效搜索采取的策略回溯法的效率不依赖于下列哪些因素确定解空间的时间分支限界法最大效益优先是分支界限法的一搜索方式;分支限界法解最大团问题时,活结点表的组织形式是最大堆 ;分支限界法解旅行售货员问题时,活结点表的组织形式是最小堆优先队列式分支限界法选取扩展结点的原则是结点的优先级在对问题的解空间树进行搜索的方法中,一个活结点最多有一次机会成为活结点的是分支限界法.从活结点表中选择下一个扩展结点的不同方式将导致不同的分支限界法,以下除栈式分支限界法之外都是最常见的方式.1队列式FIFO分支限界法：按照队列先进先出FIFO原则选取下一个节点为扩展节点;2优先队列式分支限界法：按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点;最优子结构性质是贪心算法与动态规划算法的共同点;贪心算法与动态规划算法的主要区别是贪心选择性质 ;回溯算法和分支限界法的问题的解空间树不会是无序树.14．哈弗曼编码的贪心算法所需的计算时间为 B ;A、On2nB、OnlognC、O2nD、On21、下面关于NP问题说法正确的是BA NP问题都是不可能解决的问题B P类问题包含在NP类问题中C NP完全问题是P类问题的子集D NP类问题包含在P类问题中40、背包问题的贪心算法所需的计算时间为 BA、On2nB、OnlognC、O2nD、On42．0-1背包问题的回溯算法所需的计算时间为 AA、On2nB、OnlognC、O2nD、On.47.背包问题的贪心算法所需的计算时间为 B ;A、On2nB、OnlognC、O2nD、On53．采用贪心算法的最优装载问题的主要计算量在于将集装箱依其重量从小到大排序,故算法的时间复杂度为 B ;A、On2nB、OnlognC、O2nD、On56、算法是由若干条指令组成的有穷序列,而且满足以下性质D（1）输入：有0个或多个输入（2）输出：至少有一个输出（3）确定性：指令清晰,无歧义（4）有限性：指令执行次数有限,而且执行时间有限A 123 B124 C134 D 1 23457、函数32n+10nlog n的渐进表达式是 B .A. 2nB. 32nC. nlog nD. 10nlog n59、用动态规划算法解决最大字段和问题,其时间复杂性为B .A.lognB.nC.n2D.nlogn61、设fN,gN是定义在正数集上的正函数,如果存在正的常数C和自然数N0,使得当N≥N0时有fN≤CgN,则称函数fN当N充分大时有下界gN,记作fN∈○gN,即fN的阶 A gN的阶.A.不高于B.不低于C.等价于D.逼近二、填空题2、程序是算法用某种程序设计语言的具体实现;3、算法的“确定性”指的是组成算法的每条指令是清晰的,无歧义的;6、算法是指解决问题的一种方法或一个过程 ;7、从分治法的一般设计模式可以看出,用它设计出的程序一般是递归算法 ;11、计算一个算法时间复杂度通常可以计算循环次数、基本操作的频率或计算步;14、解决0/1背包问题可以使用动态规划、回溯法和分支限界法,其中不需要排序的是动态规划 ,需要排序的是回溯法 ,分支限界法 ;15、使用回溯法进行状态空间树裁剪分支时一般有两个标准：约束条件和目标函数的界,N皇后问题和0/1背包问题正好是两种不同的类型,其中同时使用约束条件和目标函数的界进行裁剪的是 0/1背包问题 ,只使用约束条件进行裁剪的是 N皇后问题 ;30.回溯法是一种既带有系统性又带有跳跃性的搜索算法;33．回溯法搜索解空间树时,常用的两种剪枝函数为约束函数和限界函数 ;34.任何可用计算机求解的问题所需的时间都与其规模有关;35.快速排序算法的性能取决于划分的对称性 ;36. Prim算法利用贪心策略求解最小生成树问题,其时间复杂度是On2;37. 图的m着色问题可用回溯法求解,其解空间树中叶子结点个数是m n,解空间树中每个内结点的孩子数是m ;4.若序列X={B,C,A,D,B,C,D},Y={A,C,B,A,B,D,C,D},请给出序列X和Y的一个最长公共子序列 {BABCD}或{CABCD}或{CADCD｝;5.用回溯法解问题时,应明确定义问题的解空间,问题的解空间至少应包含一个最优解8.0-1背包问题的回溯算法所需的计算时间为__on2n__,用动态规划算法所需的计算时间为___omin{nc,2n}_;二、综合题50分1.写出设计动态规划算法的主要步骤;①问题具有最优子结构性质；②构造最优值的递归关系表达式；3最优值的算法描述；④构造最优解；2.流水作业调度问题的johnson算法的思想;①令N1={i|ai<bi},N2={i|ai>=bi}；②将N1中作业按ai的非减序排序得到N1’,将N 2中作业按bi的非增序排序得到N2’；③N1’中作业接N2’中作业就构成了满足Johnson法则的最优调度;3.若n=4,在机器M1和M2上加工作业i所需的时间分别为ai 和bi,且a 1,a2,a3,a4=4,5,12,10,b1,b2,b3,b4=8,2,15,9求4个作业的最优调度方案,并计算最优值;步骤为：N1={1,3},N2={2,4}；N 1’={1,3}, N2’={4,2}；最优值为：384.使用回溯法解0/1背包问题：n=3,C=9,V={6,10,3},W={3,4,4},其解空间有长度为3的0-1向量组成,要求用一棵完全二叉树表示其解空间从根出发,左1右0,并画出其解空间树,计算其最优值及最优解;解空间为{0,0,0,0,1,0,0,0,1,1,0,0,0,1,1,1,0,1,1,1,0,1,1,1};解空间树为：该问题的最优值为：16 最优解为：1,1,05.设S=｛X1,X2,···,Xn｝是严格递增的有序集,利用二叉树的结点来存储S中的元素,在表示S的二叉搜索树中搜索一个元素X,返回的结果有两种情形,1在二叉搜索树的内结点中找到X=Xi ,其概率为bi;2在二叉搜索树的叶结点中确定X∈X i ,Xi+1,其概率为ai;在表示S的二叉搜索树T中,设存储元素Xi的结点深度为Ci；叶结点Xi ,Xi+1的结点深度为di,则二叉搜索树T的平均路长p为多少假设二叉搜索树Tij=｛Xi ,Xi+1,···,Xj｝最优值为mij,Wij= ai-1+bi+···+bj+aj,则mij1<=i<=j<=n递归关系表达式为什么二叉树T的平均路长P=∑=+ni1Ci)(1*bi+∑=nj0dj*aj{mij=0 i>j6.描述0-1背包问题;已知一个背包的容量为C,有n件物品,物品i的重量为Wi ,价值为Vi,求应如何选mij=Wij+min{mik+mk+1j} 1<=i<=j<=n,mii-1=0择装入背包中的物品,使得装入背包中物品的总价值最大;三、简答题30分1.流水作业调度中,已知有n个作业,机器M1和M2上加工作业i所需的时间分别为ai 和bi,请写出流水作业调度问题的johnson法则中对ai和bi的排序算法;函数名可写为sorts,n2.最优二叉搜索树问题的动态规划算法设函数名binarysearchtree 1.void sortflowjope s,int n{int i,k,j,l;fori=1;i<=n-1;i++//-----选择排序{k=i;whilek<=n&&sk.tag=0 k++;ifk>n break;//-----没有a i,跳出else{forj=k+1;j<=n;j++ifsj.tag==0ifsk.a>sj.a k=j;swapsi.index,sk.index;swapsi.tag,sk.tag; }}l=i;//-----记下当前第一个b i的下标fori=l;i<=n-1;i++{k=i;forj=k+1;j<=n;j++ifsk.b<sj.b k=j;swapsi.index,sk.index; //-----只移动index和tagswapsi.tag,sk.tag; }}2.void binarysearchtreeint a,int b,int n,int m,int s,int w{int i,j,k,t,l;fori=1;i<=n+1;i++{ wii-1=ai-1;mii-1=0;}forl=0;l<=n-1;l++//----l是下标j-i的差fori=1;i<=n-l;i++{ j=i+l;wij=wij-1+aj+bj;mij=mii-1+mi+1j+wij;sij=i;fork=i+1;k<=j;k++{ t=mik-1+mk+1j+wij;ift<mij{ mij=t;sij=k;}}}}一、填空题本题15分,每小题1分1、算法就是一组有穷的规则 ,它们规定了解决某一特定类型问题的一系列运算2、在进行问题的计算复杂性分析之前,首先必须建立求解问题所用的计算模型;3个基本计算模型是随机存取机RAM 、随机存取存储程序机RASP 、图灵机 ;3、算法的复杂性是算法效率的度量,是评价算法优劣的重要依据;4、计算机的资源最重要的是时间和空间资源5、fn= 6×2n+n2,fn的渐进性态fn= O 2^n6、贪心算法总是做出在当前看来最好的选择;也就是说贪心算法并不从整体最优考虑,它所做出的选择只是在某种意义上的局部最优结构二、简答题本题25分,每小题5分1、简单描述分治法的基本思想;2、简述动态规划方法所运用的最优化原理;3、何谓最优子结构性质4、简单描述回溯法基本思想;5、何谓P、NP、NPC问题三、算法填空本题20分,每小题5分1、n后问题回溯算法1用二维数组ANN存储皇后位置,若第i行第j列放有皇后,则Aij为非0值,否则值为0;2分别用一维数组MN、L2N-1、R2N-1表示竖列、左斜线、右斜线是否放有棋子,有则值为1,否则值为0;forj=0;j<N;j++if 1 /安全检查/{ Aij=i+1; /放皇后/2 ；ifi==N-1 输出结果；else 3 ；; /试探下一行/4 ； /去皇后/5 ；;}2、数塔问题;有形如下图所示的数塔,从顶部出发,在每一结点可以选择向左走或是向右走,一起走到底层,要求找出一条路径,使路径上的值最大;forr=n-2;r>=0;r-- //自底向上递归计算forc=0; 1 ;c++if tr+1c>tr+1c+1 2 ；else 3 ；3、Hanoi算法Hanoin,a,b,cif n==1 1 ；else{ 2 ；3 ；Hanoin-1,b, a, c;}4、Dijkstra算法求单源最短路径du:s到u的距离 pu:记录前一节点信息Init-single-sourceG,sfor each vertex v∈VGdo { dv=∞; 1 }ds=0Relaxu,v,wif dv>du+wu,vthen { dv=du+wu,v;2}dijkstraG,w,s1. Init-single-sourceG,s2. S=Φ3. Q=VG4.while Q<> Φdo u=minQS=S∪{u}for each vertex 3do 4四、算法理解题本题10分根据优先队列式分支限界法,求下图中从v1点到v9点的单源最短路径,请画出求得最优解的解空间树;要求中间被舍弃的结点用×标记,获得中间解的结点用单圆圈○框起,最优解用双圆圈◎框起;五、算法理解题本题5分设有n=2k个运动员要进行循环赛,现设计一个满足以下要求的比赛日程表：①每个选手必须与其他n-1名选手比赛各一次；②每个选手一天至多只能赛一次；③循环赛要在最短时间内完成;1如果n=2k,循环赛最少需要进行几天；2当n=23=8时,请画出循环赛日程表;六、算法设计题本题15分分别用贪心算法、动态规划法、回溯法设计0-1背包问题;要求：说明所使用的算法策略；写出算法实现的主要步骤；分析算法的时间;七、算法设计题本题10分通过键盘输入一个高精度的正整数nn的有效位数≤240,去掉其中任意s个数字后,剩下的数字按原左右次序将组成一个新的正整数;编程对给定的n 和s,寻找一种方案,使得剩下的数字组成的新数最小;样例输入178543S=4样例输出13二、简答题本题25分,每小题5分6、分治法的基本思想是将一个规模为n的问题分解为k个规模较小的子问题,这些子问题互相独立且与原问题相同；对这k个子问题分别求解;如果子问题的规模仍然不够小,则再划分为k个子问题,如此递归的进行下去,直到问题规模足够小,很容易求出其解为止；将求出的小规模的问题的解合并为一个更大规模的问题的解,自底向上逐步求出原来问题的解;7、“最优化原理”用数学化的语言来描述：假设为了解决某一优化问题,需要依次作出n个决策D1,D2,…,Dn,如若这个决策序列是最优的,对于任何一个整数k,1 < k < n,不论前面k个决策是怎样的,以后的最优决策只取决于由前面决策所确定的当前状态,即以后的决策Dk+1,Dk+2,…,Dn也是最优的;8、某个问题的最优解包含着其子问题的最优解;这种性质称为最优子结构性质;9、回溯法的基本思想是在一棵含有问题全部可能解的状态空间树上进行深度优先搜索,解为叶子结点;搜索过程中,每到达一个结点时,则判断该结点为根的子树是否含有问题的解,如果可以确定该子树中不含有问题的解,则放弃对该子树的搜索,退回到上层父结点,继续下一步深度优先搜索过程;在回溯法中,并不是先构造出整棵状态空间树,再进行搜索,而是在搜索过程,逐步构造出状态空间树,即边搜索,边构造;10、PPolynomial问题：也即是多项式复杂程度的问题;NP就是Non-deterministic Polynomial的问题,也即是多项式复杂程度的非确定性问题;NPCNP Complete问题,这种问题只有把解域里面的所有可能都穷举了之后才能得出答案,这样的问题是NP 里面最难的问题,这种问题就是NPC 问题; 三、算法填空本题20分,每小题5分 1、n 后问题回溯算法 1 Mj&&Li+j&&Ri-j+N 2 Mj=Li+j=Ri-j+N=1; 3 tryi+1,M,L,R,A 4 Aij=05 Mj=Li+j=Ri-j+N=0 2、数塔问题; 1c<=r2trc+=tr+1c 3trc+=tr+1c+1 3、Hanoi 算法 1movea,c2Hanoin-1, a, c , b 3Movea,c 4、1pv=NIL 2pv=u3 v ∈adju 4Relaxu,v,w四、算法理解题本题10分五、18天2分；2当n=23=8时,循环赛日程表3分;六、算法设计题本题15分 1贪心算法 Onlogn➢ 首先计算每种物品单位重量的价值Vi/Wi,然后,依贪心选择策略,将尽可能多的单位重量价值最高的物品装入背包;若将这种物品全部装入背包后,背1 2 3 4 5 6 7 82 1 43 6 5 8 73 4 1 2 7 8 5 64 3 2 1 8 7 6 55 6 7 8 1 2 3 46 5 87 2 1 4 37 8 5 6 3 4 1 28 7 6 5 4 3 2 1包内的物品总重量未超过C,则选择单位重量价值次高的物品并尽可能多地装入背包;依此策略一直地进行下去,直到背包装满为止; ➢ 具体算法可描述如下：void Knapsackint n,float M,float v,float w,float x {Sortn,v,w; int i;for i=1;i<=n;i++ xi=0; float c=M;for i=1;i<=n;i++ {if wi>c break; xi=1; c-=wi; }if i<=n xi=c/wi; }2动态规划法 Oncmi,j 是背包容量为j,可选择物品为i,i+1,…,n 时0-1背包问题的最优值;由0-1背包问题的最优子结构性质,可以建立计算mi,j 的递归式如下;void KnapSackint v,int w,int c,int n,int m11 {int jMax=minwn-1,c;for j=0;j<=jMax;j++ /mn,j=0 0=<j<wn/ mnj=0;for j=wn;j<=c;j++ /mn,j=vn j>=wn/ mnj=vn;for i=n-1;i>1;i--{ int jMax=minwi-1,c;for j=0;j<=jMax;j++ /mi,j=mi+1,j 0=<j<wi/ mij=mi+1j;for j=wi;j<=c;j++/mn,j=vn j>=wn/ mij=maxmi+1j,mi+1j-wi+vi; }m1c=m2c; ifc>=w1m1c=maxm1c,m2c-w1+v1; }3回溯法 O2ncw:当前重量 cp:当前价值 bestp ：当前最优值i i i i w j w j j i m v w j i m j i m j i m <≤≥⎩⎨⎧++-++=0),1(}),1(),,1(max{),(nn nw j w j v j n m <≤≥⎩⎨⎧=00),(void backtrack int i//回溯法 i初值1{ ifi > n //到达叶结点{ bestp = cp; return; }ifcw + wi <= c //搜索左子树{ cw += wi;cp += pi;backtracki+1;cw -= wi;cp -= pi;}ifBoundi+1>bestp//搜索右子树backtracki+1;}七、算法设计题本题10分为了尽可能地逼近目标,我们选取的贪心策略为：每一步总是选择一个使剩下的数最小的数字删去,即按高位到低位的顺序搜索,若各位数字递增,则删除最后一个数字,否则删除第一个递减区间的首字符;然后回到串首,按上述规则再删除下一个数字;重复以上过程s次,剩下的数字串便是问题的解了;具体算法如下：输入s, n;while s > 0{ i=1; //从串首开始找while i < lengthn && ni<ni+1{i++;}deleten,i,1; //删除字符串n的第i个字符s--;}while lengthn>1&& n1=‘0’deleten,1,1; //删去串首可能产生的无用零输出n;三、算法填空1.背包问题的贪心算法void Knapsackint n,float M,float v,float w,float x{Sortn,v,w;int i;for i=1;i<=n;i++ xi=0;float c=M;for i=1;i<=n;i++ {if wi>c break;xi=1;c - =wi;}if i<=n xi=c/wi;}2.最大子段和: 动态规划算法int MaxSumint n, int a{int sum=0, b=0； //sum存储当前最大的bj, b存储bjforint j=1； j<=n； j++ {if b>0 b+= aj ；else b=ai; ； //一旦某个区段和为负,则从下一个位置累和 ifb>sum sum=b;}return sum；}3.快速排序template<class Type>void QuickSort Type a, int p, int r{if p<r {int q=Partitiona,p,r;QuickSort a,p,q-1; //对左半段排序QuickSort a,q+1,r; //对右半段排序}}4.排列问题Template <class Type>void permType list, int k, int m{ //产生listk:m的所有排列ifk==m{ //只剩下一个元素for int i=0;i<=m;i++ cout<<listi;cout<<endl;}else //还有多个元素待排列,递归产生排列for int i=k; i<=m; i++{swaplistk,listi;permlist,k+1;m;swaplistk,listi;}}5.给定已按升序排好序的n个元素a0:n-1,现要在这n个元素中找出一特定元素x;据此容易设计出二分搜索算法：template<class Type>int BinarySearchType a, const Type& x, int l, int r{while l<=r {int m = l+r/2;if x == am return m;if x < am r = m-1; else l = m+1;}return -1;}6、合并排序描述如下：template<class Type>void MergesortType a , int left, int right{if left<right{int i= left+right/2;Mergesorta, left, i ;Mergesorta, i+1, right;Mergea,b, left,i,right;//合并到数组bCopya,b, left,right ; //复制到数组a}}7、以下是计算x m的值的过程int power x, m{//计算x m的值并返回;y= 1 ;i=m;Whilei- - >0y=yx;return y ;}四、问答题1.用计算机求解问题的步骤：1、问题分析2、数学模型建立3、算法设计与选择4、算法指标5、算法分析6、算法实现7、程序调试8、结果整理文档编制2. 算法定义：算法是指在解决问题时,按照某种机械步骤一定可以得到问题结果的处理过程3.算法的三要素1、操作2、控制结构3、数据结构13. 分治法与动态规划法的相同点是：将待求解的问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解;两者的不同点是：适合于用动态规划法求解的问题,经分解得到的子问题往往不是互相独立的;而用分治法求解的问题,经分解得到的子问题往往是互相独立的;回溯法中常见的两类典型的解空间树是子集树和排列树;22.请叙述动态规划算法与贪心算法的异同;共同点：都需要最优子结构性质,都用来求有优化问题;不同点：动态规划：每一步作一个选择—依赖于子问题的解;贪心方法：每一步作一个选择—不依赖于子问题的解;动态规划方法的条件：子问题的重叠性质;可用贪心方法的条件：最优子结构性质；贪心选择性质;动态规划：自底向上求解；贪心方法：自顶向下求解;可用贪心法时,动态规划方法可能不适用；可用动态规划方法时,贪心法可能不适用; 23. 请说明动态规划方法为什么需要最优子结构性质;答：最优子结构性质是指大问题的最优解包含子问题的最优解;动态规划方法是自底向上计算各个子问题的最优解,即先计算子问题的最优解,然后再利用子问题的最优解构造大问题的最优解,因此需要最优子结构.24. 请说明：1优先队列可用什么数据结构实现2优先队列插入算法基本思想3优先队列插入算法时间复杂度答：1堆;2在小根堆中,将元素x插入到堆的末尾,然后将元素x 的关键字与其双亲的关键字比较, 若元素x 的关键字小于其双亲的关键字,则将元素x 与其双亲交换,然后再将元素x 与其新双亲的关键字相比,直到元素x 的关键字大于双亲的关键字,或元素x 到根为止; 3O log n26. 在算法复杂性分析中,O 、Ω、Θ这三个记号的意义是什么 在忽略常数因子的情况下,O 、Ω、Θ分别提供了算法运行时间的什么界 答：如果存在两个正常数c 和N 0,对于所有的N ≥N 0,有|fN |≤C |gN |,则记作：fN = OgN ;这时我们说fN 的阶不高于gN 的阶;若存在两个正常数C 和自然数N0,使得当N ≥ N 0时有|f N|≥C |gN |,记为fN =ΩgN ;这时我们说fN 的阶不低于gN 的阶;如果存在正常数c1,c2和n0,对于所有的n ≥n0,有c1|gN| ≤|fN| ≤ c2|gN| 则记作 fN = g ,NO 、Ω、Θ分别提供了算法运行时间的上界、下界、平均 五、算法设计与分析题1．用动态规划策略求解最长公共子序列问题： 1给出计算最优值的递归方程;2给定两个序列X={B,C,D,A},Y={A,B,C,B},请采用动态规划策略求出其最长公共子序列,要求给出过程;答：1⎪⎩⎪⎨⎧≠>--=>+--===时y 0且x j 当i,)j]1,c[i 1],j max(c[i,时y 0且x j 当i,11]j 1,c[i 0时0或j 当i 0j]c[i,i i i i2Ｙ Ａ Ｂ Ｃ Ｂ Ｘ 0 0 0 0 Ｂ 0 0 1 1 1ΘＣ 0 0 1 2 2 Ｄ 0 0 1 2 2Ａ0 1 1 2 2 最长公共子序列：｛ＢＣ｝2．对下列各组函数f n 和g n,确定f n = O g n 或f n =Ωg n 或fn =θgn,并简要说明理由;1 fn=2n ； gn=n2 fn=n ； g n=log n 23 fn=100； gn=log1004 fn=n 3； gn= 3n5 fn=3n ； gn=2n 答：(1) fn = Ogn 因为gn 的阶比fn 的阶高; (2) fn = Ωgn 因为gn 的阶比fn 的阶低; (3) fn = θgn 因为gn 与fn 同阶; (4) fn = Ogn 因为gn 的阶比fn 的阶高; (5) fn = Ωgn 因为gn 的阶比fn 的阶低;3．对下图所示的连通网络G ,用克鲁斯卡尔Kruskal 算法求G 的最小生成树T ,请写出在算法执行过程中,依次加入T 的边集TE 中的边;说明该算法的贪心策略和算法的基本思想,并简要分析算法的时间复杂度;答：TE={3,4, 2,3,1,5,4,64,5}贪心策略是每次都在连接两个不同连通分量的边中选权值最小的边; 基本思想：首先将图中所有顶点都放到生成树中,然后每次都在连接两个不同连通分量的边中选权值最小的边,将其放入生成树中,直到生成树中有n-1条边;时间复杂度为：Oeloge4. 请用分治策略设计递归的归并排序算法,并分析其时间复杂性要求：分别给出divide 、conquer 、combine 这三个阶段所花的时间,并在此基础上列出递归方程,最后用套用公式法求出其解的渐进阶; 答 ： Template <class Type>void MergeSort Type a , int left, int right { if left<right { int i=left+right/2; MergeSorta, left, i; MergeSorta, i+1, right; Mergea, b, left, right; Copya, b, left, right; }}Divide 阶段的时间复杂性： O1 Conquer 阶段的时间复杂性： 2Tn Combine 阶段的时间复杂性： Θn用套用公式法：a=2, b=2, n log b a = n , fn=n, 因为fn 与n log b a 同阶, ∴Tn =Θnlogn⎩⎨⎧>+==1当n θ(n)2T(n/2)1当n θ(1)T(n)1 2 3 4 5 6 75、设有n=2k个运动员要进行循环赛,现设计一个满足以下要求的比赛日程表:每个选手必须与其他n-1名选手比赛各一次;每个选手一天至多只能赛一次;循环赛要在最短时间内完成.14分循环赛最少需要进行n-1 天.26分当n=23=8时,请画出循环赛日程表:6、考虑用哈夫曼算法来找字符a,b,c,d,e,f 的最优编码;这些字符出现在文件中的频数之比为20:10:6:4:44:16;要求：14 分简述使用哈夫曼算法构造最优编码的基本步骤；25 分构造对应的哈夫曼树,并据此给出a,b,c,d,e,f 的一种最优编码;解：1、哈夫曼算法是构造最优编码树的贪心算法;其基本思想是,首先所有字符对应n 棵树构成的森林,每棵树只有一个结点,根权为对应字符的频率;然后,重复下列过程n-1 次：将森林中的根权最小的两棵树进行合并产生一个新树,该新树根的两个子树分别是参与合并的两棵子树,根权为两个子树根权之和;2、根据题中数据构造哈夫曼树如下图所示;由此可以得出a,b,c,d,e,f 的一组最优的编码：01,0000,00010,00011, 1,001;7.考虑在序列A1..n中找最大最小元素的问题;一个分治算法描述如下：如果n≤2 就直接求解;否则,将序列等分成两个子序列A1..n/2和An/2+1..n,分别找出这两子序列的最大最小元素x1,y1 和x2,y2；然后据此求出A1..n的最大元素x=max{x1,x2}及最小元素y=min{y1,y2};请给出该算法计算时间Tn满足的递归方程,并解方程来确定算法的时间复杂度;假定n=2k k 为正整数;答：算法时间复杂度满足如下递归方程：Tn=2Tn/2+2n>2；T2=1;因为n=2 k k 为正整数,所以,Tn= T2 k= 2T2 k-1+2= 22T2 k-2+ 22+2⋯= 2k-1T2+ 2k-2+⋯+23+22+2= 2k-1+⋯+23+22+2;因此,Tn= n;8.考虑使用动态规划方法求解下列问题：01背包数据如下表,求：能够放入背包的最有价值的物品集合;如设： Vi, j —— 前 i 个物品中能够装入承重量 j 的背包中的最大总价值;请将如下递推式填写完整： V0, j = 00个物品,Vi, 0 = 0承重量0Vi, j = Vi-1, j 第 i 个物品不能装入, j < wi 超重Vi, j = max { , } j > wi 不超重 i 在最优子集中 i 不在最优子集中 自底向上：按行或列填写下表;答：V0, j = 00个物品,Vi, 0 = 0承重量0Vi, j = Vi-1, j 第 i 个物品不能装入, j < wi 超重Vi, j = max { v i + Vi-1,j-w j , Vi-1, j } j > wi 不超重 i 在最优子集中 i 不在最优子集中V j=0 1 2 3 4 5i=0 0 0 0 0 0 01 0 0 12 12 12 122 0 10 12 22 22 223 0 10 12 22 30 324 0 10 15 25 30 379.请画出用回溯法解4皇后问题的解空间树和搜索空间树：解空间树：用回溯法的搜索空间树：10.考虑用分支限界解0-1背包问题给定n 种物品和一背包;物品i 的重量是wi,其价值为vi,背包的容量为C;问应如何选择装入背包的物品,使得装入背包中物品的总价值最大示例：n=3, C=30, w={16, 15, 15}, v={45, 25, 25} 求：1、问题的解空间树2、约束条件 2、如何剪枝解：问题的解空间树：11c xw ni ii ≤∑=约束条件： 如何剪枝 ：设r 是当前尚未考虑的剩余物品价值总和；Cv 是当前价值；bestv 是当前最优价值;当r ＋Cv ≤bestv 时,可剪去右子树;11,请画出用回溯法解n=3的0-1背包问题的解空间树和当三个物品的重量为{20, 15, 10},价值为{20, 30, 25},背包容量为25时搜索空间树; 答：解空间树：搜索空间树：1111111123457 8 1112 14 15310691不可行解价值=20价值=55价值=30价值=25价值=011 110 0 01128 1112 14 15 131069。
