欢迎来到天天文库
浏览记录
ID:56795769
大小:366.00 KB
页数:16页
时间:2020-07-12
《算法设计与分析C语言描述课后答案.doc》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、第一章1-3.最大公约数为1。快1414倍。主要考虑循环次数,程序1-2的while循环体做了10次,程序1-3的while循环体做了14141次(14142-2循环)若考虑其他语句,则没有这么多,可能就601倍。第二章2-8.(1)画线语句的执行次数为。。划线语句的执行次数应该理解为一格整体。(2)画线语句的执行次数为。。(3)画线语句的执行次数为。。(4)当n为奇数时画线语句的执行次数为,当n为偶数时画线语句的执行次数为。。2-10.(1)当时,,所以,可选,。对于,,所以,。(2)当时,,所以,可选,。对于,,所以,。(3
2、)由(1)、(2)可知,取,,,当时,有,所以。2-11.(1)当时,,所以,。可选,。对于,,即。注意:是f(n)和g(n)的关系。(2)当时,,所以,。可选,。对于,,即。(3)因为,。当时,,。所以,可选,,对于,,即。第二章2-17.证明:设,则。当时,。所以,。第五章5-4.SolutionTypeDandC1(intleft,intright){while(!Small(left,right)&&left3、(x>P[m])left=m+1;elsereturnS(P)}}5-7.templateintSortableList::BSearch(constT&x,intleft,intright)const{if(left<=right){intm=(right+left)/3;if(xl[m])returnBSearch(x,m+1,right);elsereturnm;}return-1;}第五章9.证明:因为该算法在成功搜索4、的情况下,关键字之间的比较次数至少为,至多为。在不成功搜索的情况下,关键字之间的比较次数至少为,至多为。所以,算法的最好、最坏情况的时间复杂度为。假定查找表中任何一个元素的概率是相等的,为,那么,不成功搜索的平均时间复杂度为,成功搜索的平均时间复杂度为。其中,是二叉判定树的内路径长度,是外路径长度,并且。11.步数012345初始时111111[11]1[11]∞2[1]11[11]∞3111[11]∞4111[1]1∞排序结果11111∞步数01234567初始时5583432∞1[4233]5[85]∞2[323]45[855、]∞3[32]345[85]∞4[2]3345[85]∞523345[5]8∞排序结果2334558∞12.(1)证明:当或或时,程序显然正确。当n=right-left+1>2时,程序执行下面的语句:intk=(right-left+1)/3;StoogeSort(left,right-k);StoogeSort(left+k,right);StoogeSort(left,right-k);①首次递归StoogeSort(left,right-k);时,序列的前2/3的子序列有序。②当递归执行StoogeSort(left+k6、,right);时,使序列的后2/3的子序列有序,经过这两次递归排序,使原序列的后1/3的位置上是整个序列中较大的数,即序列后1/3的位置上数均大于前2/3的数,但此时,前2/3的序列并不一定是有序的。③再次执行StoogeSort(left,right-k);使序列的前2/3有序。经过三次递归,最终使序列有序。所以,这一排序算法是正确的。(2)最坏情况发生在序列按递减次序排列。,,。设,则。冒泡排序最坏时间复杂度为,队排序最坏时间复杂度为,快速排序最坏时间复杂度为。所以,该算法不如冒泡排序,堆排序,快速排序。13.templa7、teselect(T&x,intk){if(m>n)swap(m,n);if(m+n8、9、k<=0){cout<<"OutOfBounds";returnfalse;}int*p=newtemp[k];intmid,left=0,right=n-1,cnt=0,j=0,r=0;for(inti=0;i0){do{mid=(left+right)/2;if(a[mid]b[i])right=mid;else{cnt=mid;10、break;}}while(leftcnt){if(cnt>0){for(j=0;j
3、(x>P[m])left=m+1;elsereturnS(P)}}5-7.templateintSortableList::BSearch(constT&x,intleft,intright)const{if(left<=right){intm=(right+left)/3;if(xl[m])returnBSearch(x,m+1,right);elsereturnm;}return-1;}第五章9.证明:因为该算法在成功搜索
4、的情况下,关键字之间的比较次数至少为,至多为。在不成功搜索的情况下,关键字之间的比较次数至少为,至多为。所以,算法的最好、最坏情况的时间复杂度为。假定查找表中任何一个元素的概率是相等的,为,那么,不成功搜索的平均时间复杂度为,成功搜索的平均时间复杂度为。其中,是二叉判定树的内路径长度,是外路径长度,并且。11.步数012345初始时111111[11]1[11]∞2[1]11[11]∞3111[11]∞4111[1]1∞排序结果11111∞步数01234567初始时5583432∞1[4233]5[85]∞2[323]45[85
5、]∞3[32]345[85]∞4[2]3345[85]∞523345[5]8∞排序结果2334558∞12.(1)证明:当或或时,程序显然正确。当n=right-left+1>2时,程序执行下面的语句:intk=(right-left+1)/3;StoogeSort(left,right-k);StoogeSort(left+k,right);StoogeSort(left,right-k);①首次递归StoogeSort(left,right-k);时,序列的前2/3的子序列有序。②当递归执行StoogeSort(left+k
6、,right);时,使序列的后2/3的子序列有序,经过这两次递归排序,使原序列的后1/3的位置上是整个序列中较大的数,即序列后1/3的位置上数均大于前2/3的数,但此时,前2/3的序列并不一定是有序的。③再次执行StoogeSort(left,right-k);使序列的前2/3有序。经过三次递归,最终使序列有序。所以,这一排序算法是正确的。(2)最坏情况发生在序列按递减次序排列。,,。设,则。冒泡排序最坏时间复杂度为,队排序最坏时间复杂度为,快速排序最坏时间复杂度为。所以,该算法不如冒泡排序,堆排序,快速排序。13.templa
7、teselect(T&x,intk){if(m>n)swap(m,n);if(m+n8、9、k<=0){cout<<"OutOfBounds";returnfalse;}int*p=newtemp[k];intmid,left=0,right=n-1,cnt=0,j=0,r=0;for(inti=0;i0){do{mid=(left+right)/2;if(a[mid]b[i])right=mid;else{cnt=mid;10、break;}}while(leftcnt){if(cnt>0){for(j=0;j
8、
9、k<=0){cout<<"OutOfBounds";returnfalse;}int*p=newtemp[k];intmid,left=0,right=n-1,cnt=0,j=0,r=0;for(inti=0;i0){do{mid=(left+right)/2;if(a[mid]b[i])right=mid;else{cnt=mid;
10、break;}}while(leftcnt){if(cnt>0){for(j=0;j
此文档下载收益归作者所有