《算法设计技巧与分析报告报告材料问题详解》由会员分享，可在线阅读，更多相关《算法设计技巧与分析报告报告材料问题详解（20页珍藏版）》请在金锄头文库上搜索。
1、算法设计技巧与分析参考答案第1章算法分析基本概念1.1(a) 6 (b)5 (c)6 (d)61.4算法执行了 7+6+5+4+3+2+仁28次比较1.5(a) 算法MODSELECTIONSO执行的元素赋值的最少次数是0,元素已按非降序排列的时候达到最小值。(b) 算法MODSELECTIONSO执行的元素赋值的最多次数是呼，元素已按非升序排列的时候达到最小值。1.71次由上图可以看到执行的比较次数为1+1+2+2+2+6+2=16次1.11由上图可以得出比较次数为5+6+6+9=26次1.13FTF,TTT,FTF,TFF,FTF1.16(a) 执行该算法，元素比较的最少次数是n-1。元素
2、已按非降序排列时候达到最小值。(b) 执行该算法，元素比较的最多次数是丄口)。元素已2按非升序排列时候达到最大值。(c) 执行该算法，元素赋值的最少次数是0。元素已按非降序排列时候达到最小值。(d) 执行该算法，元素赋值的最多次数是如 1)。元素已2按非升序排列时候达到最大值。(e) n用O符号和符号表示算法 BUBBLESOR的运行时间：2t =0(n )，t (n)(f) 不可以用0符号来表示算法的运行时间：0是用来表示 算法的精确阶的，而本算法运行时间由线性到平方排列， 因此不能用这一符号表示。1.27不能用关系来比较n2和100n2增长的阶1100=02. n lim 2 n :100
3、n2n2不是o(100n2)的，即不能用关系来比较n2和100n2增长 的阶。1.32(a) 当n为2的幕时，第六步执行的最大次数是：2k, j =2kJ 时，nn、k _、log n二 n log ni 4i 4(b) 由(a)可以得到：当每一次循环j都为2的幕时，第六 步执行的次数最大，kk则当n =3k,j=32m (其中-取整)时，22nn m log(3k-1)= nlog( n-1)i 4i 4(c)用门符号表示的算法的时间复杂性是0(nlog n)已证明n=2k的情况，下面证明 n=2k+1的情况：所以n=2k+1时，第六步执行的最大次数仍是n log n 。2k2k +12 一
4、12 一因为有(d)用|符号表示的算法的时间复杂性是门(n)当n满足j =n/2取整为奇数时，算法执行的次数是n次，其他情况算法执行次数均大于n。(e) O更适合表示算法的时间复杂性。因为本算法时间复 杂性从门(n)到O(n log n)，而心是表示精确阶的。1.38对n个数进行排序。第5章归纳法5.3 (本题不仅有以下一个答案)1. max( n)过程：max(i)if n=1 retur n a1t=max(i-1)if ai-1t return ai-1else retur n tend if5.6最多次数:C(n)二 1c(n -1) + (n-1),n 兰2n(n 1)2最少次数:C
5、(n)0,n =1C(n _ 1)+1,n M2C( n)二n-1 5.7参考例5.15.14(a)不稳定，例如:124545241124545241224454512244545可见SELECTI0NS0RT1等元素的序在排序后改变。(b)(c)(d)(f)稳定5.17(a)利用 Pn(X)二 XPn4(X)a取 x =3，F5(3)t P4(3)t B(3)t P2(3)t R(3)t P(3)P2(3) =3* R(3) 4R(3) =3* P(3) 2 =11 P(3) =3:F3(3) =3*P2(3)1=112 F4(3) =3*F3(3)2=338 P5(3)=3*F4(3)5
6、= 10195.18(a)p(2,5) p(2,2) p(2,1) p(2,0)2 2 2 y=4 *2： y=2 =4： y=1 *2 ： y=1第6章分治6.3输入：A1,2,n输出：max,min1. for i=1 to mid2. j=high-i3. if aiaj, the n excha nge ai,aj4. e nd for5. for i=low to mid6. if ai+1ahigh, the n excha nge ahigh,ai+110. e nd for6.5输入：一个整数数组 A1,2,n输出：sum1.if high-low=1 the n2. sum=
7、alow+ahigh3. else4. mid=(low+high)/25 sum1=sum(low,mid)6 sum2=sum(mid+1,high)7. sum=sum1+sum28. e nd if9. retur n sum算法需要的工作空间为36.10.12251719513245182237151215171819222532374551122517195132121719253251451822371515182237451225171217251951321932514518221822453715153717322237151225122517122512251951195
8、1321951451818452218453715195145186.3127133118451617532713311845161753271331184516175327131831451617532713183145161753271318164531175327131816173145531713181627314553彩色代表i,j所指的数字j总在i前6.36233227184511631219162552141418111219162332452725526312111112111116161919272718191616181932452725526325273245526325
9、27252745526345526352635263631r 1rVvVIFV1112141618192325273245526363标准文案1418111219161211141819166.42Quicksort不是稳定的。6.43bcefg均为适应的，a、h不是适应的第7章动态规划7.1(c),算法 BOTTOMUPSORT7.5字符串A=” xzyzzyx ”和B=” zxyyzxz ”的最长公共子序列长度为 4,共有6个最长公共子序列，分别是： zyyx zyzz zyzx xyyx xyzz xyzx7.9C1,5=C1,1+C2,5+r1*r2*r6=307C1,5=C1,2+C
10、3,5+r1*r3*r6=252C1,5=C1,3+C4,5+r1*r4*r6=372C1,5=C1,4+C5,5+r1*r5*r6=260所以最优括号表达式为(M1M)(M3M4)M5)7.15Ddi,j二minDi, j, Di,1 D1,j D41 05131209113402、16200716 D1 =oO094402J820D2【i,j =minD1【i, j, Ddi,2 D/2, joO70196、00D2 =44021820D3【i,j = min D2【i, j,D2【i,3D2【3, j0513 D3 =130911440262D4【i,j二min D3【i, j,D3【i,4 D3A j广513、D4 =12911342627.2112345678911113333333333234477777773344778991212434477811112147.23当物品体积为负值时，运行算法会发生溢出错误。第八章贪心算法8.12由算法从s到t要选择先到a然后到t,其结果为4,而从s到t距离为2,所以探索不总是 产生从s到t的距离8
