算法设计技巧与分析答案

精品资料1.11.4算法设计技巧与分析参考答案第 1 章 算法分析基本概念(a)6(b)5(c)6(d)6算法执行了7+6+5+4+3+2+1=28次比较453324451212241212332445451224121212244545332412121212454533242412121224453345241212122424334545121212242433454512121224243345451.5(a) 算法 modselectionsort执行的元素赋值的最少次数是 0,元素已按非降序排列的时候达到最小值。(b) 算法 modselectionsort执行的元素赋值的最多次数是 3n(n21) ,元素已按非升序排列的时候达到最小值。1.74312567291 次341 次34122 次345122 次3456122 次34567126 次234567122 次234567912由上图可以看到执行的比较次数为1+1+2+2+2+6+2=16次。1.11比较 9 次24578111213151719比较为 6 次24581113171971215比较为 3 次， 2 次， 1 次25171948111371215比较均为1次，共 5 次2175191113481215721719513114815127由上图可以得出比较次数为5+6+6+9=26次。1.13ftf,ttt,ftf,tff,ftf 1.16(a) 执行该算法，元素比较的最少次数是n-1 。元素已按非降序排列时候达到最小值。(b) 执行该算法，元素比较的最多次数是n(n21) 。元素已按非升序排列时候达到最大值。(c) 执行该算法，元素赋值的最少次数是0。元素已按非降序排列时候达到最小值。(d) 执行该算法，元素赋值的最多次数是3n(n21) 。元素已按非升序排列时候达到最大值。(e) n 用 o 符号和符号表示算法bubblesort的运行时间：to(n2 ) ， t(n)(f) 不可以用符号来表示算法的运行时间：是用来表示算法的精确阶的，而本算法运行时间由线性到平方排列， 因此不能用这一符号表示。1.27不能用关系来比较 n 2 和100 n2 增长的阶。2limn10n100 n2100n2 不是的阶。1.32o(100n 2 ) 的，即不能用关系来比较n 2 和100n 2 增长(a) 当 n 为 2 的幂时，第六步执行的最大次数是：n2k , j2 k 1 时，nnklog nn log ni 1i 1k(b) 由(a) 可以得到：当每一次循环j 都为 2 的幂时，第六步执行的次数最大，则当 n3k , j3 22m （其中3取整）时，k2nnimlog(3 k1)n log( n1)i 1i 1(c) 用符号表示的算法的时间复杂性是o(n log n)已证明 n=2 k 的情况，下面证明n=2 k+1的情况：k因为有222k12所以 n=2 k+1 时，第六步执行的最大次数仍是n log n 。(d) 用符号表示的算法的时间复杂性是( n) 。当 n 满足 jn / 2 取整为奇数时，算法执行的次数是n 次，其他情况算法执行次数均大于n 。(e) o更适合表示算法的时间复杂性。因为本算法时间复杂性从(n) 到o(n log n) ，而是表示精确阶的。1.38对 n 个数进行排序。第 5 章 归纳法5.3（本题不仅有以下一个答案） 1.max(n)过程： max(i)if n=1 return a1 t=max(i-1)if ai-1t return ai-1 else return tend if5.6最多次数：0,n1c(n1)( n1),nnjj 1n(n1)2c(n)2c(n)最少次数：c ( n)c (n0,n1)11, n2c(n)=n-1 5.7参考例 5.15.14(a)不稳定，例如：12454524124545241224454512244545可见 selectionsort中相等元素的序在排序后改变。(b)(c)(d)(f) 稳定5.17(a)利用pn (x)xpn1 ( x)a0取x3 ，p5 (3)p4 (3)p3 (3)p2 (3)p1 (3)p0 (3)p2 (3)3*p1 (3)437p1(3)3*p0 (3)211p0 (3)3p3 (3)3*p2 (3)1112p4 (3)3*p3 (3)2338p5 (3)3*p4 (3)510195.18(a)p(2,5)p (2,2)p(2,1)p (2,0)y42 *2y224y12 *2y1第 6 章 分 治6.3输入： a1,2,n 输出： max,min 1.for i=1 to mid2. j=high-i3. if aiaj, then exchange ai,aj 4.end for5. for i=low to mid6. if ai+1ahigh, then exchange ahigh,ai+1 10.end for6.5输入：一个整数数组a1,2,n输出： sum1. if high-low=1 then2. sum=alow+ahigh 3.else4.mid=(low+high)/25 sum1=sum(low,mid)6 sum2=sum(mid+1,high)7.sum=sum1+sum2 8.end if9.return sum算法需要的工作空间为36.10.32151415111725511114151517253251321514151117255114151532111725513215141511172551153214151117255132151415111725513215141511172551122517195132451822371512151718192225323745511225171951324518223715121719253251151822374512251719513245182237151217251932511822451537122517195132451822371512251719513218452237151225195145181225195145186.3127133118451617532713311845161753271331184516175327131831451617532713183145161753271318164531175327131816173145531713181627314553彩色代表 i,j 所指的数字 j 总在 i 前6.362332271845116312191625521414181112191623324527255263141811121916121114181916121111121111181916161819161619193245272552632527324552632527252727274552634552635263526363精品资料63111214161819232527324552636.42quicksort不是稳定的。6.43bcefg 均为适应的， a、h 不是适应的。第 7 章 动态规划7.1(c),算法 bottomupsort 7.5字符串 a=”xzyzzyx ”和 b=”zxyyzxz ”的最长公共子序列长度为4，共有 6 个最长公共子序列，分别是：zyyxzyzzzyzxxyyxxyzzxyzx7.9c1,5=c1,1+c2,5+r1*r2*r6=307c1,5=c1,2+c3,5+r1*r3*r6=252c1,5=c1,3+c4,5+r1*r4*r6=372c1,5=c1,4+c5,5+r1*r5*r6=260所以最优括号表达式为（m1m2 ） (m3m4)m5) 7.15min d 0 i, j , d 0 i ,1d01, j d4051312091134021620d1i , j 精品资料07160944021820d1d2 i ,j min d1 i,j , d1i, 2d12,j 07160944021820d2d3 i ,j mind2 i ,j , d2 i ,3d 2 3,j 051313091144021620d3d4 i ,j mind3i ,j , d3 i , 4d3 4,j 051312091134021620d47.2101234567891011000000000000010033333333332003447777777300344778991212400344778101112147.23当物品体积为负值时，运行算法会发生溢出错误。第八章贪心算法8.121sa2 t3由算法从s 到 t 要选择先到a 然后到 t,其结果为4，而从 s 到 t 距离为 2 ，所以探索不总是产生从 s 到t 的距离8.1392412145364153135991224129821241251436145364154153135341359921220412981221641451236528414361543413513153413513821291641214536284153135124138.23 （共有 4 棵最小生成树，此处仅举一例）135135135246246246