《计算机算法基础》第三版_课后习题答案

《《计算机算法基础》第三版_课后习题答案》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、上机实验 书上121页 5。2 5。3 书上151 6。1 6。3 6。6他说搞懂这几题和实验就没问题了4.2在下列情况下求解递归关系式T(n)=当①n=2kg(n)=O(1)和f(n)=O(n)；②n=2kg(n)=O(1)和f(n)=O(1)。解:T(n)=T(2k)=2T(2k-1)+f(2k)=2(2T(2k-2)+f(2k-1))+f(2k)=22T(2k-2)+21f(2k-1)+f(2k)=……=2kT(1)+2k-1f(2)+2k-2f(22)+…+20f(2k)=2kg(n)+2k-1f(2)

2、+2k-2f(22)+…+20f(2k)①当g(n)=O(1)和f(n)=O(n)时，不妨设g(n)=a，f(n)=bn，a，b为正常数。则T(n)=T(2k)=2ka+2k-1*2b+2k-2*22b+…+20*2kb=2ka+kb2k=an+bnlog2n=O(nlog2n)②当g(n)=O(1)和f(n)=O(1)时，不妨设g(n)=c，f(n)=d，c，d为正常数。则T(n)=T(2k)=c2k+2k-1d+2k-2d+…+20d=c2k+d(2k-1)=(c+d)n-d=O(n)4.3根据教材中所给出

3、的二分检索策略，写一个二分检索的递归过程。ProcedureBINSRCH(A,low,high,x,j)integermidiflow≤highthenmid←ifx=A(mid)thenj←mid;endififx>A(mid)thenBINSRCH(A,mid+1,high,x,j);endififx

4、查2n/3处的元素；这样，或者找到x，或者把集合缩小到原来的1/3。分析此算法在各种情况下的计算复杂度。ProcedureThriSearch(A,x,n,j)integerlow,high,p1,p2low←1;high←nwhilelow≤highdop1←;p2←case:x=A(p1):j←p1;return:x=A(p2):j←p2;return:xA(p2):low←p2+1:else:low←p1+1;high←p2-1endcaserepeatj←0endT

5、hriSearchT(n)=g(n)=O(1)f(n)=O(1)成功:O(1),O(log3(n)),O(log3(n))最好，平均，最坏失败:O(log3(n)),O(log3(n)),O(log3(n))最好，平均，最坏4.6对于含有n个内部结点的二元树，证明E=I+2n，其中，E，I分别为外部和内部路径长度。证明：数学归纳法①当n=1时，易知E=2，I=0，所以E=I+2n成立；②假设n≤k(k>0)时，E=I+2n成立；③则当n=k+1时，不妨假定找到某个内结点x为叶结点（根据二元扩展树的定义，一定存在

6、这样的结点x，且设该结点的层数为h），将结点x及其左右子结点（外结点）从原树中摘除，生成新二元扩展树。此时新二元扩展树内部结点为k个，则满足Ek=Ik+2k，考察原树的外部路径长度为Ek+1=Ek-（h-1）+2h，内部路径长度为Ik+1=Ik+（h-1），所以Ek+1=Ik+2k+h+1=Ik+1+2k+2=Ik+1+2(k+1)，综合①②③知命题成立。4.10过程MERGESORT的最坏情况时间是O(nlogn)，它的最好情况时间是什么？能说归并分类的时间是Θ(nlogn)吗？最好情况：是对有序文件进行排序

7、。分析：在此情况下归并的次数不会发生变化----log(n)次归并中比较的次数会发生变化（两个长n/2序列归并）最坏情况两个序列交错大小，需要比较n-1次最好情况一个序列完全大于/小于另一个序列，比较n/2次差异都是线性的，不改变复杂性的阶因此最好情况也是nlogn,平均复杂度nlogn。可以说归并分类的时间是Θ(nlogn)5.2①求以下情况背包问题的最优解，n=7，m=15，=(10,5,15,7,6,18,3)和=(2,3,5,7,1,4,1)。②将以上数据情况的背包问题记为I。设FG(I)是物品按的非增

8、次序输入时由GREEDY-KNAPSACK所生成的解，FO(I)是一个最优解。问FO(I)/FG(I)是多少?③当物品按的非降次序输入时，重复②的讨论。解：①按照/的非增序可得(/，/，/，/，/，/，/)=(6,5,9/2,3,3,5/3,1)W的次序为(1,2,4,5,1,3,7),解为(1,1,1,1,1,2/3,0)所以最优解为：（1,2/3,1,0,1,1,1）FO(I)=1