《算法导论(第二版)》课后答案

1、算法导论（第二版）参考答案3数学归纳法证明即可，略(注：几乎所有人都对)4下面是最坏情况下的T(n)0,Sc(c为常量)T(-1)+0(”),否则1证明：只需找出5C2,no,使得0=ci*(f(n)+g(n)=max(f(n),g(n)=0时恒成立，所以得证。8参照写定义即可，略(注：几乎所有人都对)1(注意：上血的证明用到了课木p51的公式(3.4J.7)因为有-个常数1在里面,所以在使用替换方法的肘候,考虑可能要证明下面的式了:I(n),假设该不等式刈必2成立，那么T()=T(/2)+lSolg(/2-b)+lSclg(”+l)/2-0)+1=clg(w一b+1-Z?)/2)+1=clg

2、(w-Z+l-d)+l-c1andh4.1-2使用替换方海要证明Q(wlgn)即要证明T(n)c(n+b)lg(+b)假设上面的不等式对L2成立，那么7(w)c(n+b)lg(“+b)T(w)2c(|_w/2J+)lg(|_w/2j+b)+nc(n-1+2b)lg(-l)/2+)+w=c(n+b+b-V)lg(+b+b-l)/2)+n=c(n+b+b1)lg(w+b+b-1)+(1-c)n一c(l-2b)+b)lg(n+b)6-101一00且(1一ne)=n匸(3/2卩+0(芒3)1=0=n=2(n(3/2)1n-nJ+Ofn3)3hnta=21x-211+0(1?)=2-3lgn-2n+9(

3、nlg3)=2n13-2n+9(nlg3)=0(nlg3)assununingthatT(n/2J)Ccn/2J3cn/2JT(n)=3T(n/2J)+nW3cn/2_lgSc匕/2_+n3cnlg3cn$cnU3_+n厶Wcnlg3注意题目中的要求使用递归树的方法，最好是像书上画一颗递归树然后进行运由21=n得i=lgn2-1lgnT(n)=Rzcn=cni=01n2rlgnn342使用P146的PARTION函数可以得到q=r注意每循环一次i加i的初始值为p-1,循环总共运行(r-l)-p+l次，最终返回的i+l=p-l+(r-1)-p+l+l=r(2)由题目要求q=(p+r)/2可知，P

4、ARTITION函数中的i,j变量应该在循环中同时变化。Partition(A,p,r)x=Ap;=p-1；j=r+1;while(TRUE)repeatj；untilAj=x;if(ij)Swap(A,i,j)；elsereturnj;2由Quicksort算法最坏情况分析得知：n个元素每次都划n1和个，因为是pvr的时候才调用，所以为0(n)最好情况是每次都在最中间的位置分，所以递推式是：N(n)=1+2*N(n/2)不难得到：N(n)=0(n)2T(n)=2*T(n+0(n)可以得到T(n)=0(nIgn)由P46Theorem3.1可得：Q(nIgn)5prove:Byproperty

5、5thelongestandshortestpathmustcontainthesamenumberofblacknodes.Byproperty4everyothernodesinthelongestpathmustbeblackandthereforethelengthisatmosttwicethatoftheshortestpath.算法导论（第二版）参考答案算法导论(第二版)参考答案 62k-122k-13a的深度増加b的深度不变c的深度减少15采用反证法证明：假设时，树中没有红色结点。那么当树中何nl个结点时,由假设可知仍没冇红色结点。当用REINSERT算法插入第n个结点时，在R

6、B-INSERT的16行-，执行了colorzl的时候,树中至少有一个红色结点。直接执行步骤23ri接执彳j步骤2313.4-3解释：箭头代农一步第一步不执行RB-DELETE-FIXUP第二步符合RB-DELETE-FIXUP的第三步不执彳fRB-DELETE-FIXUPflkthenreturnOS-KEY-R.XXK(IcftfTLk)elseictumsizeleftrootT1+12S4CEYRANK(righlT,k)2题目要求:能否将红黑树中节点的黑高度作为一个域来进行有效的维护?町以.因为个节点的黑崗度可以从该节点和它的两个孩了的信息计算得到。做法：如果一个卩点的孩子的黑高度是

7、m并H该孩子的颜色为黑色则该节点的黑高度为n+l否则为m根据Page309的定理14丄插入和删除操作仍然可以在0(lgn)的时间内实现。TOC o 1-5 h z3不可以，性能改变时间复杂度由0(lgn)-0(nlgn)2Note:注意Overlap的定义稍有不同，需要重新定义。算法：只要将P314页第三行的2改成就行。3INTERVAL-SEARCH-SUBTREE(x,/)whilexini!Tand/doesnotoverlap/nfx|doif/ef/x去M7andmax/ef/xlowiithenxelsexrighxreturnxINTERVAL-SEARCH-MIN(7；/)2y

8、先找第一个重盜区间A在它的左子树上查找zywhilen/77andidoz-yo调用之前保存结果y如果循环是由于y没有左子树，那我们返回y否则我们返回乙这时意味着没有在n的左子树找到重叠区间ify#niTand/overlapintythenreturnyelsereturnz5由FASTEST-WAY算法知：j=塩j-i+L_i+%jtj=址1+_1+仏所以有：址j+tj=切-1+5戸+%+址1+_+%由课本P328(15.6)(15.7)式代入，可得:min(址j-1+aM,f2j+a】J+min(芯j-1+a2j,fjjl+t】円+a2j)=11曲(址j-1，-ll+tJ+aij+nii

9、n(f,j-1,fjj-1+4戸)+仏化简得：min(址j-1,f3j-l+t2j_1)+niin(tj-1,址j7+tJ=J-1l+t2J-l+j-1+一1而：min(址j-1,f2j-1+S)f2j-1+切7-1,j-1J+V1)圮jT+t中等号在：址j=以j-l+tw时成立，但是s，t,戸不为负数，矛盾。1参照P336算法，P337例子就可以算得答案：2010算法导论（第二版）参考答案算法导论（第二版）参考答案 # Solvethematrixchainorderforaspecificproblem.ThiscanbedonebycomputingMatrix-Chain-Order(

10、p)wherep=5,10312,5,50,6)orsimplyusingtheequation:m.j=foifi=j讥十mk十j十Pt_iPkPjifici-1,jthenccjj-1belsec2JC”-l,jbij734568910111213141516171815.5-2算法导论(第二版)参考答案算法导论(第二版)参考答案16.1-216.1-2亡i、j的值如下:S52.S”$+也就是耙活动按照开始时间的从丿、到小的顺序先排列好figure16.1的结果集合中各元素的顺序变为他1，鸟，6,4具体的证明步骤略。4略前n个数的编码为:算法导论(第二版)参考答案算法导论(第二版)参考答案

11、17.3-117.3-1TOC o 1-5 h z11.1J1.10J1.10J04nn-1n-24反证1根据|5_tpa驴393的matroid的定义，分别证明(S,lk)中S为右穷IE空集合,满足hereditary性质和exchange性质即可。1AnswersByZhifangWang1这题有歧义如果StackOperations包括PushPopMultiPush,答案是可以保持，解释和书上的PushPopMultiPop差不多.如果是StackOperations包括PushPopMultiPushMultiPop,答案就是不可以保持，因为MultiPush,MultiPop交替的

12、话，平均就是0(K).TOC o 1-5 h z2Increment操作每次最多可以使k位翻转，同样Decrement也是k位，所以不难得到结论.1使用会计方法,因为栈的大小始终不会超过k,所以如果我们给每个栈操作都赋予多些的代价，那么就可以有足够的余款來支付复制整个栈的代价。对栈操作赋予以卜的平摊代价：PUSH3POP0MULTIPOP0COPY0算法导论（第二版）参考答案算法导论（第二版）参考答案 定义为；(x)=(x)-k【天I为(DJ(Z)o)=k所以(D(DJ=(D(0)斤no(I)(Z0)=(I)(Z)o)-=O根据公式17.3,用(D和计算的平摊代价是相等的4怎义势函数栈中对象的

13、个数，PUSH的半摊代价为2,MULTIPOP利POP的T押:代价为0注总：这电是根抑;公式174而不是公A17-3.考虑故坏情况，最终的结果是2卄-每3假设第i个操作是TABLE_DELETE,考虑装载因子a-.a=(第i次循环之后的表中的entry数)/(第i次循环后的表的大小)=mm/size】case1.Ifai-i=1/2,ax1/2c】=Ci+厂=1+(size,_2nunii)-(2numM-size)=1+(sizej-i一2(nunii-i1)(2numi.i-sizei)=3+2size4numi=3+2size,.!4aijsizeS-l+2sizeM-4/2size=3

14、case2.If1/3WaaiW1/2J-thoperationwouldnotcauseacontractionc,=Cj+(I)f,/=1+(size：一2numi)(size：.-2numi.)=1+(sizeM一2(nuirii.rl)-(sizeij-2numi.|)=3case3.Ifai=l/3,1/2thusi-thoperationwouldcauseacontractionCi=Ci+(I)j=nuirii+1+(size；一2numi)-(sizej-i-2numi.)=num,.i1+1+(2/3sizei-i一2(numi.)-1)-(sizeM-2numi.)Thu

15、stheamortizedcostofTABLE-DELETEisboundedby3.1.Ifxisnotarootnode,thenDegreex=Degreesiblingx+1Ifxisarootnode,thenDegreexDegreesiblingx2Degreexdegreepx261答案：参考I5I：Page484I.的图20.3以及Page486的CONSOLIDATE算法3因为Fibonacciheap是一组无序的二项树，因而根据二项树的性质可以容易得证，具体过程略。1答案：1.X是如何成为有标记的根的？在某个时刻,x是一个根，然后x彼链接到另一卩点，且x失掉一个孩了，则

16、markx为TRUE2.说明x有无标记对分析來说没有彩响根据书Page492的(t(H)+c)+2(m(H)-c+2)-(t(H)+2m(H)=4-c,势的改变与m(H)无关，因此，x冇无标记对分析來说都没的影响26.1-1如果(“，巧幺E,(v,w)纟E,那么c(u9v)=0,c(v,u)=0由capacityconstraint,f(”,v)-c(v,z/)=0(2)由(1)(2)可得/(z/,v)=0,同理/(匕)二026.1-2根据flowconsenation,对于所仃的uGV一sj,工/(,v)=0,以及(26.2)宦义的thevertotalpositiveflow不难得出证明，八体步骤略1根据|5_hPage655的netflow和capacity的定义以及图26.4的例子。不难得到/(S,T)=/(s,片)+f(y2，片)+f(v2,v3)+/(v4,v3)+/(v4,t)=ll+l+(-4)+7+4=19o(S,T)=c(s,片)+c(v2，片)+c(v4，卩3)