厦门大学-算法分析试卷-08即.pdf

该【厦门大学-算法分析试卷-08即 】是由【小屁孩】上传分享，文档一共【7】页，该文档可以免费在线阅读，需要了解更多关于【厦门大学-算法分析试卷-08即 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。:..厦门大学《算法分析》课程试卷软件学院软件工程系08级软件工程专业主考教师:刘昆宏试卷类型:(A卷)(每空3分,共24分)。,t(I)表示输入为I时算法的运算时间,p(I)表示输入I出现的概率,则n算法的平均情况下时间复杂性A(n)=。(n)=n2+log50n,g(n)=2n×logn,则O(f(n))+O(g(n))=。:?f(n)?d,n?n0??f(n)?af(n/c)?g(n),n?n0其中,g(n)表示。,只要在步骤3前通过算法,就可得到一个随机化快速排序算法,获得很好的平均性能。算法QUICKSORT输入:n个元素的数组A[1..n]。输出:按非降序排列的数组A中的元素。(1,n)//对A[low..high]中的元素按非降序排序。<=SPLIT(A,low,high)//算法SPLIT以A[low]为主元将A[low..high]划分成两部//分,返回主元的新位置。(A,low,w-1)(A,w+1,high),该算法的时间复杂性阶为?()。算法SPLIT输入:正整数n,数组A[1..n]。SPLIT:i=1x=A[1]forj=2tonifA[j]<=xtheni=i+1ifi?jthenA[i]?A[j]endifendforA[i]?A[1]w=ireturnw,APage1of7:..//(n)=5×2n,在某台机上实现并完成该算法的时间为t秒。如果使用64倍的运算时间在同一台机子上进行计算,则能解的问题规模为。.?p(I)t(I)I?=n+(每小题2分,共12分):首先将原问题分成更小的子问题,保存这些子问题的解,并由它们来计算原问题的一个解。下列的问题求解中哪一个不能使用动态规划算法?()-:给n个人分派n件工作,把工作j分派给第i个人的成本为cost(i,j),1≤i,j≤n,要求在给每个人分派一件工作的情况下使得总成本最小。此问题的解可表示成n元组(X1,?,Xn),其中Xi是给第i个人分配的工作号,且Xi≠Xj(i≠j)。此解空间的状态空间有()个n元组,此解空间的状态空间树被称为()。!()。,其中在()上算法所作元素比较次数最少。A.(5,5,5,5,5)B.(3,1,5,2,4)C.(1,2,3,4,5)D.(5,4,3,2,1)(),对所有问题都能很快获得问题的最优解。。,从而简化或减少了原问题的复杂度。。(),而且所求得的解总是正确的。,而是设法消除这种最坏情形行为与特定实例之间的关联性。,但该解未必正确。。(64分)1.(10分)用O、?、?表示函数f与g之间的关系:(1)f(n)=100g(n)=100n(2)f(n)=6n+n?logn?g(n)=3nPage2of7:..(3)f(n)=n/logn-1g(n)=2n(4)f(n)=2n?n2g(n)=3n(5)f(n)=logng(n)=logn32(1)f(n)=O(g(n))(2)f(n)=?(g(n))(3)f(n)=?(g(n))(4)f(n)=O(g(n))(5)f(n)=?(g(n))2.(10分)设n个不同的整数按升序存于数组A[1..n]中,求使得A[i]=i的下标i。下面是求解该问题的分治算法。算法SEARCH输入:正整数n,存储n个按升序排列的不同整数的数组A[1..n]。输出:A[1..n]中使得A[i]=i的一个下标i,若不存在,则输出nosolution。i=find((1))ifi>0thenoutputielseoutput“nosolution”endif//endSEARCH过程------------------------------------------------------------find(low,high)//求A[low..high]中使得A[i]=i的一个下标并返回,若不存在,则返回0。if(2)thenreturn0elsemid=?(low?high)/2?if(3)thenreturnmidelseifA[mid]<midthenreturnfind((4))elsereturn(5)endifendifendif//endfind过程(1)1,n(2)low>high(3)A[mid]=mid(4)mid+1,high(5)find(low,mid-1)3.(12分)图中的共有n项工作,第i项工作在si时间开始,在fi时间结束。如果两项工作没有交叠,则称它们相容。Page3of7:..(1)如果希望找出最大的相容工作子集,你准备采用哪种类型算法(分治,动态规划等)?(1分)(2)设计相应的算法解决这个问题,请写出解决问题算法对应的伪代码,说明算法初始条件,并作出适当的标注。(5分)(3)请分析或证明这种方法能否获得最优解。(6分):(1)贪心算法(2)<=f2<=...<=fnSolutionsetAisemptyatstartforj=1ton{if(patiblewithA)//,breakloopAddjtoA}returnA(3)从最优子结构和贪心选择性质两个角度分析。(1)假设E为给定工作的集合,按结束时间的非减序排序。如果该问题有一个最优解A不包含工作1,且A中的工作也按活动的非减序排序,则可以将A中的第一个活动替换为工作1而不违背相容约束,从而构成最优解B。由于A是最优解,则其包含的工作数量最多。而B也是最优解,因其包含的工作数量和A一样多。可见存在以贪心选择开始的最优活动方案。(2)如果A是原问题的最优解,则A’=A‐{1}为E’={i∈E,si≥fi}的最优解。因为如果存在E’的一个最优解B’比A’包含的工作个数更多,则将工作1加入B’后,会生成比A更多获得的E的最优解。因此,满足最优子结构性质。4.(10分)设计一个算法,描述算法的思路,找出由n个数组成的序列的最长单调递增子序列,分析相应的时间复杂度。(时间复杂度越低的算法分数越高)5.(10分)请设计两种算法找到下图中的最短路径,用图表的方式给出解决问题的过程。如果是用搜索算法,请画出搜索树。说明相关算法的类型。Page4of7:..:方法1:Dijkstra算法:方法2:优先队列式搜索:相关搜索图例如下:方法3:回溯法搜索:相关搜索图例如下:Page5of7:..91417813322029928161932186.(12分)设有如下结构的移动将牌游戏:BBWWE其中,B表示黑色将牌,W表是白色将牌,E表示空格。游戏的规定走法是:(1)任意一个将牌可移入相邻的空格,规定其代价为1;(2)任何一个将牌可相隔1个其它的将牌跳入空格,其代价为2。游戏要达到的目标是把所有W都移到B的左边。对这个问题,请设计一个优先队列式分支限界算法(只需给出相关的优先函数,并画出用这个算法产生的搜索树)。解:设f(x)=当前移动的代价+3*当前节点中每个W左边的B的个数,其搜索树如下:f(x)=0+12=12BBWWEf(x)=1+12=13f(x)=2+12=14BBWEWBBEWWf(x)=2+12=14f(x)=3+9=12BBEWWBEWBWf(x)=4+9=13EBWBWf(x)=6+6=12WBEBWPage6of7:..f(x)=8+3=11WBWBEf(x)=9+3=12WBWEBf(x)=11+0=11WEWBBPage7of7