计算机算法基础课后答案.docx

《计算机算法基础课后答案.docx》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、计算机算法分析—习题课第四章：2、3、5、6、10、11、23P99-2在下列情况下求解4.1节的递归关系式T(n)=()2(/2)()gnnTnfn⎧⎨⎩足够小＋否则当①g(n)=O(1)和f(n)=O(n)；②g(n)=O(1)和f(n)=O(1)。P99-2递推表达式设n=2k则: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)+…

2、+20f(2k)=2kg(n)+2k-1f(2)+2k-2f(22)+…+20f(2k)g(n)=O(1)和f(n)=O(n)当g(n)=O(1)和f(n)=O(n)时不妨设g(n)=a，f(n)=bn，则：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)=O(1)和f(n)=O(1)时，不妨设g(n)=c，f(n)=d，则：T(n)=T(2k)=c2k+2k-1d

3、+2k-2d+…+20d=c2k+d(2k-1)=(c+d)n-d=O(n)P99-3?根据2.2节开始所给出的二分检索策略，写一个二分检索的递归过程。ProcedureBINSRCH(A,low,high,x,j)integermidiflow≤highthenmid←⎣(low+high)/2⎦ifx=A(mid)thenj←mid;endififx>A(mid)thenBINSRCH(A,mid+1,high,x,j);endififx

4、x,j);endifelsej←0;endifendBINSRCHP99-5?作一个“三分”检索算法，它首先检查n/3处的元素是否等于某个x的值，然后检查2n/3处的元素。这样，或者找到x，或者把集合缩小到原来的1/3。分析此算法在各种情况下的计算复杂度。ProcedureThriSearch(A,x,n,j)integerlow,high,p1,p2low←1;high←nwhilelow≤highdop1←⎣(high+2low)/3⎦p2←⎣(2high+low)/3⎦case:x=A(p1):j

5、←p1;return:x=A(p2):j←p2;return:xA(p2):low←p2+1:else:low←p1+1;high←p2-1endcaserepeatj←0endThriSearch实例运行{1,2,3,4,5,6,7,8,9}361时间复杂度?成功:?O(1),O(log3(n)),O(log3(n))?最好，平均，最坏?失败:?O(log3(n)),O(log3(n)),O(log3(n))?最好，平均，最坏P99-6对于含有n个部结点的二元树，

6、证明E=I+2n其中，E，I分别为外部和部路径长度。证明：数学归纳法当n=1时，易知E=2，I=0，所以E=I+2n成立；假设n≤k(k>0)时，E=I+2n成立；此时新树部结点为k个，则满足：Ek=Ik+2k（1）考察原树的外部路径长度和部路径长度：Ek+1=Ek-h+2(h+1)（2）Ik+1=Ik+h（3）综合（1）（2）（3）式：Ek+1=Ik+2k+h+2=Ik+1-h+2k+h+2=Ik+1+2(k+1)故命题成立。P99-10过程MERGESORT的最坏情况时间是O(nlogn)，它的最好

7、情况时间是什么？能说归并分类的时间是Θ(nlogn)吗？?最好情况：?对有序文件进行排序?分析?归并的次数不会发生变化----log(n)次?归并中比较的次数会发生变化（两个长n/2序列归并）?最坏情况?两个序列交错大小?需要比较n-1次?最好情况?一个序列完全大于/小于另一个序列?比较n/2次?差异都是线性的，不改变复杂性的阶?最好情况也是nlog(n),平均复杂度nlog(n)。P99-11?写一个“由底向上”的归并分类算法，从而取消对栈空间的利用。?见《数据结构》---第九章P238算法MPass

8、（R，n，1ength．X）MP1[初始化]i←1．MP2[合并相邻的两个长度为length的子文件]WHILEi≤n–2*length+1DO（Merge（R，i，i＋length–l，i＋2*length–1．X）.i←i＋2*length）．MP3[处理余留的长度小于2*length的子文件]IFi+length–1