《算法导论(第二版)》(中文版)课后答案.pdf 15页

'《算法导论（第二版）》参考答案2.3-3数学归纳法证明即可，略（注：几乎所有人都对）2.3-4下面是最坏情况下的T(n)3.1-1证明：只需找出c1,c2,n0,使得0<=c1*(f(n)+g(n))<=max(f(n),g(n))<=c2*(f(n)+g(n))取c1=0.5,c2=1，由于f(n),g(n)是非负函数，所以在n>=0时恒成立，所以得证。3.1-8参照写定义即可，略（注：几乎所有人都对）注：题目中的要求使用递归树的方法，最好是像书上画一颗递归树然后进行运算。1 《算法导论（第二版）》参考答案注意题目中的要求使用递归树的方法，最好是像书上画一颗递归树然后进行运算。4.2.2证略4.2.3i由2n得i=lgnlgnlgn1i2122T(n)2cncn2cncn(n)i0214.3-12a)n2b)nlgn3c)n4.3-42 《算法导论（第二版）》参考答案22nlgn7.1-2(1)使用P146的PARTION函数可以得到q=r注意每循环一次i加1，i的初始值为p1，循环总共运行(rp1)1次，最终返回的i1p1(r1)p11r(2)由题目要求q=(p+r)/2可知，PARTITION函数中的i，j变量应该在循环中同时变化。Partition(A,p,r)x=A[p];i=p-1;j=r+1;while(TRUE)repeatj--;untilA[j]<=x;repeati++;untilA[i]>=x;if(iO(nlgn)14.3-2Note:注意Overlap的定义稍有不同，需要重新定义。算法：只要将P314页第三行的改成>就行。14.3-3INTERVAL-SEARCH-SUBTREE(x,i)1whilex≠nil[T]andidoesnotoverlapint[x]2doifleft[x]≠nil[T]andmax[left[x]]≥low[i]3thenx←left[x]4elsex←right[x]5returnxINTERVAL-SEARCH-MIN(T,i)2y←INTERVAL-SEARCH-SUBTREE(root[T],i)先找第一个重叠区间3z←y4whiley≠nil[T]andleft[y]≠nil[T]在它的左子树上查找5 《算法导论（第二版）》参考答案5doz←y调用之前保存结果6y←INTERVAL-SEARCH-SUBTREE(y,i)如果循环是由于y没有左子树，那我们返回y否则我们返回z，这时意味着没有在z的左子树找到重叠区间7ify≠nil[T]andioverlapint[y]8thenreturny9elsereturnz15.1-5由FASTEST-WAY算法知：fj[]fj[1]ta122,jj11,fj[]fj[1]ta211,jj12,所以有：fj[]fj[]fj[1]tafj[1]ta1222,j11,j11,j12,j由课本P328（15.6）(15.7)式代入，可得：min([fj1]a,[fj1]ta)min([fj1]a,[fj1]ta)11,j22,j11,j22,j11,j12,jmin([fj1],[fj1]t)amin([fj1],[fj1]t)a122,j11,j211,j12,jfj[1]tafj[1]ta22,j11,j11,j12,j化简得：min([fj1],[fj1]t)min([fj1],[fj1]t)122,jj1211,1fj[1]tfj[1]t22,jj111,1而：min([fj1],[fj1]t)fj[1]t122,jj122,1min([fj1],[fj1]t)fj[1]t211,jj111,1等号在：fj[1]fj[1]t211,j1fj[1]fj[1]t122,j1时成立，但是t，t不为负数，矛盾。2,j11,j115.2-1参照P336算法，P337例子就可以算得答案：20106 《算法导论（第二版）》参考答案最终答案：((A1A2)((A3A4)(A5A6)))15.2-215.3-2没有重叠的子问题存在15.3-4这题比较简单,由P328的(15.6)(15.7)展开两三步就可以看出来.15.4-3先初始化c数组元素为无穷大7 《算法导论（第二版）》参考答案15.5-28 《算法导论（第二版）》参考答案15.5-33O(n)P360上面的（15.17）式花费的时间是O(n)。注意算法OPTIMAL-BST，虽然将w[i,j]用15.17式计算，但是这个结果的w[i,j]可以用于第10行中的计算，因3此总的来说，时间复杂度仍然为O(n)*O(n)*(O(n)+O(n))=O(n).16.1-29 《算法导论（第二版）》参考答案16.2-4略16.3-116.3-2前n个数的编码为：10 《算法导论（第二版）》参考答案11...1,11...10,11...10,...,10,1nn12n16.3-4反证16.4-116.5-1AnswersByZhifangWang17.1-1这题有歧义a)如果StackOperations包括PushPopMultiPush,答案是可以保持,解释和书上的PushPopMultiPop差不多.b)如果是StackOperations包括PushPopMultiPushMultiPop,答案就是不可以保持,因为MultiPush,MultiPop交替的话,平均就是O(K).17.1-2Increment操作每次最多可以使k位翻转,同样,Decrement也是k位,所以不难得到结论.17.2-117.3-111 《算法导论（第二版）》参考答案17.3-417.4-3假设第i个操作是TABLE_DELETE,考虑装载因子:=(第i次循环之后的表i中的entry数)/(第i次循环后的表的大小)=numsize/ii19.1-1.Ifxisnotarootnode,thenDegree[x]=Degree[sibling[x]]+1Ifxisarootnode,thenDegree[x]