(完整版)算法设计与分析期末考试卷及答案a.doc

1、一.填空题(每空 2 分，共 30 分)1.算法的时间复杂性指算法中的执行次数。2.在忽略常数因子的情况下，0、和三个符号中，提供了算法运行时间的一个上界。3.设Dn表示大小为n的输入集合，t表示输入为I时算法的运算时间，p表示输入I出现的概率，则算法的平均情况下时间复杂性A6)=o4.分治算法的时间复杂性常常满足如下形式的递归方程：f6)d,nnofh)af(n/c)gS),nno其中，gh)表示o5.分治算法的基本步骤包括o6.回溯算法的基本思想是o7.动态规划和分治法在分解子问题方面的不同点是o8.贪心算法中每次做出的贪心选择都是最优选择。9.PQ式的分支限界法中，对于活结点表中的结点，

2、其下界函数值越小，优先级越O10.选择排序、插入排序和归并排序算法中，算法是分治算法。11.随机算法的一个基本特征是对于同一组输入，不同的运行可能得到的仑12.对于下面的确定性快速排序算法，只要在步骤3前加入随机化步骤，就可得到 f 随-机r化快部序算法,该随机化步骤的功能是o算法QUEKSORT输入：n个元素的数组Al.no输出：按非降序排列的数组A中的元素。1.i.1i.i1.1.F1J.1.1:.,.学.1.栏芬1.01.姓.:息.级1.01t.年线！1.信.10一i业.B专订生.Bi.B.一系i10.i.!考1.1.一装.0tI.81.,1.:!.学一i1L1.quicksort。，n

3、)endQUEKSORT程quicksort(A,bw,high)/Abw.hjgh中的元素按非降序排序。2.3.4.5.6.ifbwhighthenw二SPLIT(A,bw,high)法SPLIT以Abw主元将Abw.high划分成两部怜,返回主元的新位置。quicksort(A,bw,w-1)quicksort(A,w+1,high)endifendquicksort下面算法的基本5E算是运算，算法的复性)o算法SPLIT入：正整数n,数ALn。出:。Fln,x=A1forj=2tonifAj=xthenifijthenA田Aj|endifendforelseADOAlww,AendSPL

4、IT二.计算题和简答题(每小题 7 分，共 21 分)1.用0、表示函数f与g之的关系，并分指出下列函数中最低和最高的函数:(1)f6)=100(2)f(h)=6n+nbgn(5)氏D二2.下面是一个算法，其中,prol和pro2的运算分是T(n)足的方程，并求解方程，估T(n)的(用表示)。算法EX1入:正整数n,n=2koexl0)endEX1程exl(h)ifn=lthenprol(h)(3)f(h)=n/bgn-1出算法的复性gS)二3ng&)=3npro2(h)exl6/S)endifreturnendexl3.用Fbyd算法求下图每一对顶点之间的最短路径长度，计算矩阵Do,

5、Di,D2和D3,其中DkEij表示从顶点i到顶点j的不经过编号大于k的顶点的最短路径长度。三.算法填空题（共 34 分）（10分）设n个不同的整数按升序存于数组Al. n中，求使得AKH的下标i。下面是求解该问题的分治算法。算法SEARCH输入：正整数n,存储n个按升序排列的不同整数的数组Al.no输出：Al.n中使得AEfl=i的一个下标i,若不存在，则输出nosolution。Ffhd(ifDOthenoutputielseouiput“nosolitibnendSEARCH过程find（bw,hfeh）求Abw.hgh中使得Ai=i的一个下标并返回，若不存在,1.0)返回0oif(2)

6、thenreturn0elsemid=(bwh迪h)/2ifG)thenreturnmidelseifAfoilmidthenreturnAid)elsereturnS)endifendifendifendfed2niiHI矩，,M,M,MrrFl,2,n,求算M1M2-Mn所需的最少数量乘法次数。Mij=MiMwMj,K=j。C11l8.Ifcrk=frltojx=6）.ifxC11henI!=x.endifendforendfori.iendfor.:0return（5）.jendMATCHA1N.I3.（14分）下面是用回溯法求解马的周游问题的算法。马的周游问题：给出一个nxn棋盘，已知

7、一个中国象棋马在.棋盘上的某个起点位置（xO,yO）,求一条访问每个棋盘格点恰好一次，最后回到起点的周游路线。（设马走日字。）算法HORSETRAVEL!输入：正整数n,马的起点位置（xO,yO）,1=X0,yOlm=nFl;ki=Owhile(1)andnotfhgwhileki(3)ifFmthenfhg=trueeseF(4)(5)endifendifendwhileFil(6)G)endwhileifflag1henoutputoute(k)输出路径elseoutput“nosolitbn”endHORSETRAVEL一.填空题:i.元运算I 四.算法设计题（15 分）I.1.一个旅行

8、者要驾车从A地到B地，A、B两地间距离为s。A、B两地之间有n个加油站，已知第i个加油站离起点A的距离为di公里，.:iO=did2dns,车加满油后可行驶m公里，出发之前汽车，e.|油箱为空。应如何加油使得从A地到B地沿途加油次数最少？给出.I用贪心法求解该最优化问题的贪心选择策略，写出求该最优化问题I的最优值和最优解的贪心算法，并分析算法的时间复杂性。算法设计与分析期考试卷（A）标准答案2. 03.p(I)tQ)IDn4.将规模为n的问题分解为子问题以及组合相应的子问题的解所需的时间5.分解，递归，组合6.在问题的状态空间树上作带剪枝的DFS搜索(或：DFS+剪枝)7.前者分解出的子问题有重叠的，而后者分解出的子问题是相互独立(不重叠)的8.局部9.高10.归并排序算法11.不同12. v=iandom(bw,hh);交换ADow和A切的值随机选主元13.比较n二.计算题和简答题：1阶的关系：(Df(n)-Ofe(n)f(n)=(g(n)(3)f(h)=(g(n)f(n)=Ofe(n)(5)f(n)-(g(n)阶最低的函数是：100阶最高的函数是：3n2.该递归算法的时间复杂性T(n)满足下列递归方程：T(h)1,n1T6)T以)bg2n,n1将n-2k,a二1,c=2,g(nbg2n,d=l代入该