《算法设计与分析C语言描述陈慧南版课后答案终稿》由会员分享，可在线阅读，更多相关《算法设计与分析C语言描述陈慧南版课后答案终稿（10页珍藏版）》请在金锄头文库上搜索。
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由1、2可知,取,当时,有,所以。2-11. 当时,所以,。可选,。对于,即。注意：是f和g的关系。2当时,所
2、以,。可选,。对于,即。3因为,。当时,。所以,可选,对于,即。第二章2-17. 证明：设,则。当时,。所以,。第五章5-4.SolutionType DandC1while!Small&leftint m=Divide;ifxP right=m-1; else ifPm left=m+1; else return S5-7.template int SortableList:BSearch constif leftint m=/3;if x return BSearch;else if lm return BSearch;else return m;return -1;第五章9证明：因为该算
3、法在成功搜索的情况下,关键字之间的比较次数至少为,至多为。在不成功搜索的情况下,关键字之间的比较次数至少为,至多为。所以,算法的最好、最坏情况的时间复杂度为。假定查找表中任何一个元素的概率是相等的,为,那么,不成功搜索的平均时间复杂度为,成功搜索的平均时间复杂度为。其中,是二叉判定树的内路径长度,是外路径长度,并且。11.步数012345初始时11111111111211111311111411111排序结果11111步数01234567初始时55834321423358523234585332345854233458552334558排序结果233455812.1证明：当或或时,程序显然正确
4、。当n=right-left+12时,程序执行下面的语句：int k=/3;StoogeSort;StoogeSort;StoogeSort;首次递归StoogeSort;时,序列的前2/3的子序列有序。当递归执行StoogeSort;时,使序列的后2/3的子序列有序,经过这两次递归排序,使原序列的后1/3的位置上是整个序列中较大的数,即序列后1/3的位置上数均大于前2/3的数,但此时,前2/3的序列并不一定是有序的。再次执行StoogeSort;使序列的前2/3有序。经过三次递归,最终使序列有序。所以,这一排序算法是正确的。2最坏情况发生在序列按递减次序排列。,。设,则。冒泡排序最坏时间复杂
5、度为,队排序最坏时间复杂度为,快速排序最坏时间复杂度为。所以,该算法不如冒泡排序,堆排序,快速排序。13.template select ifn swap;ifm+nk|k coutOut Of Bounds; return false;int *p=new tempk;int mid,left=0,right=n-1,cnt=0,j=0,r=0;forint i=0;iwhile0domid=/2;ifamid left=mid;else ifbi right=mid;else cnt=mid; break;whileleftifaleft cnt=left;else cnt=left-1;
6、ifcntif0forj=0;jtempj=ar;r+;left=cnt;k-=cnt;elsetempj=bi;left=0;k-;elseforj=0;jtempj=ar;r+;left=cnt;k-=cnt;return tempk-1;第六章1.由题可得：,所以,最优解为,最大收益为。8.第六章6-9.普里姆算法。因为图G是一个无向连通图。所以n-1=m=n /2; O=m=O;克鲁斯卡尔对边数较少的带权图有较高的效率,而,此图边数较多,接近完全图,故选用普里姆算法。6-10. T仍是新图的最小代价生成树。证明：假设T不是新图的最小代价生成树,T是新图的最小代价生成树,那么costco
7、st。有cost-ccost-c,即在原图中存在一颗生成树,其代价小于T的代价,这与题设中T是原图的最小代价生成树矛盾。所以假设不成立。证毕。第七章1. Bcost=0; Bcost=c+Bcost=5 Bcost=c+Bcost=2 Bcost=minc+Bcost,c+Bcost=min6+2,3+5=8 Bcost=c+Bcost=5+2=7 Bcost=minc+Bcost,c+Bcost=min3+5,8+2=8 Bcost=minc+Bcost,c+Bcost,c+Bcost=min1+8,6+7,6+8=9 Bcost=minc+Bcost,c+Bcost,c+Bcost=min
8、4+8,2+7,6+8=9Bcost=minc+Bcost,c+Bcost=min7+9,3+9=122.向后递推的计算过程如上题所示向前递推过程如下： cost=0 cost=7,cost=3 cost=min1+cost,4+cost=7, cost=min6+cost,2+cost=5cost=min6+cost,2+cost=5cost=min3+cost,3+cost=8cost=min6+cost,8+cost,5+cost=10cost=min5+cost,2+cost=12所以,d=d=8, d=d=d=7, d=5, d=4, d=2从s到t的最短路径为 0, d=2, d=
9、4, d=7, d=8,路径长为12。第七章9. char A8=0,x,z,y,z,z,y,x B8=0,z,x,y,y,z,x,z cij bsij所以,最长公共字串为 。第七章11. void LCS:CLCS if return;if CLCS ;Coutai; else if =cij-1 CLCS ; else CLCS ; 12. int LCS:LCSLength for int i =1; i ci0=0;for i =1; i c0i=0;for i =1; i for int j =1; j if cij=ci-1j-1+1; else if =cij-1 cij=ci-1j; else cij=cij-1;return cmn; 15. , , , , , ,8-1状态空间：描述问题的各种可能的情况,一种情况对呀状态空间的一个状态。显示约束：用于规定每个xi取值的约束条件称为显示约束隐式约
