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

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

1、4.2在下列情况下求解递归关系式心號25〃足够小否则当①n二214g(n)=0(1)和f(n)=O(n)；@n=2kg(n)=0⑴和f(n)=0(1)。解：T(n)=T(2k)=2T(2k_1)+f(2k)=2(2T(2W)+f(2kH))+f(2k)=22T(2k_2)+21f(2k_l)+f(2k)=2kT(l)+2k_lf⑵+2k_2f(22)+・・・+2°f(2k)=2kg(n)+2k_lf⑵+2k_2f(22)+・・・+2°f(2k)①当g(n)=O⑴和f(n)=O(n)时，不妨设g(n)=a,f(n

2、)=bn,a,b为正常数。则T(n)=T(2k)=2ka+2k_l*2b+2k_2*22b+-+2°*2kb=2ka+kb2k=an+bnlog2n=O(nlog2n)②当g(n)=O(1)和f(n)=O⑴时，不妨设g(n)=c,f(n)=d,c,d为正常数。贝UT(n)=T(2k)=c2k+2k_,d+2k_2d+-+2°d=c2k+d(2-1)=(c+d)n~d=0(n)4.3根据教材屮所给出的二分检索策略，写一个二分检索的递归过程。ProcedureBINSRCIKA,1ow,high,x,j)integ

3、ermidiflowWhighthenmid〜［(low+high)/2Jifx=A(mid)thenj—mid;cndififx>A(mid)thenB1NSRCH(A,mid+1,high,x,j);endififx

4、况下的计算复杂度。ProcedureThriSearch(A,x,n,j)integerlow,high,pl,p2low—1;high—nwhilelowWhighdopl—_(2low+high)/3」；p2〜［(low+2high)/3Jcase:x=A(pl):jjpl；return:x二A(p2):j—p2;Teturn:xA(p2)::else:endcasehighjplTlow—p2+llowjpl+1;highjp2Trepeatj—oendThriSearch刃足够小否

5、则g(n)二O⑴f(n)二O⑴成功:0(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,1=0,所以E=I+2n成立；②假设nWk(k>0)时，E二I+2n成立;③则当n二k+1U寸，不妨假定找到某个内结点x为叶结点(根据二元扩展树的定义，一定存在这样的结点x,且设该结点的层数为

6、h),将结点x及其左右子结点(外结点)从原树中摘除，生成新二元扩展树。此时新二元扩展树内部结点为k个，则满足Ek=lk+2k,考察原树的外部路径长度为亦二Ek-(h-1)+2h,内部路径长度为Ik沪Ik+(h-1),所以Ek+严Ik+2k+h+l二I亦+2k+2二W2(k+1),综合①②③知命题成立。4.10过程MERGESORT的最坏情况时间是O(nlogn),它的最好情况时间是什么？能说归并分类的时间是®(nlogn)吗？最好情况：是对有序文件进行排序。分析：在此情况下归并的次数不会发生变化一一log(n)

7、次归并屮比较的次数会发生变化(两个长n/2序列归并)最坏情况两个序列交错大小，需要比较n-1次最好情况一个序列完全大于/小于另一个序列，比较n/2次差异都是线性的，不改变复杂性的阶因此最好情况也是nlogn,平均复杂度nlogno可以说归并分类的时间是®(nlogn)4.11写一个“由底向上”的归并分类算法，从而取消对栈空间的利用。答：见《数据结构》算法MPass(R,n,length.X)MP1［初始化］i〜1・MP2［合并相邻的两个长度为length的子文件］WHILEiWn-2*lcngth+1DO(Me

8、rge(R,i,i+length-1,i+2*length-1.X)・i<—i+2*length)・MP3［处理余留的长度小于2*length的子文件］IFi+length-1〈nTHENMerge(R,i,i+length-1,n.X)ELSEFORj=iTOnDOXj-Rj

9、算法MSort(R,n)//直接两路合并排序算法，X是辅助文件，其记录结构与R相同MSI［初始化］lengt