本文格式為Word版，下載可任意編輯——描述算法的語言第一章1-3.最大公約數(shù)為1?？?414倍。

主要考慮循環(huán)次數(shù)，程序1-2的while循環(huán)體做了10次，程序1-3的while循環(huán)體做了14141次（14142-2循環(huán)）若考慮其他語句，那么沒有這么多，可能就601倍。

其次章2-8.（1）畫線語句的執(zhí)行次數(shù)為。。劃線語句的執(zhí)行次數(shù)理應(yīng)理解為一格整體。

（2）畫線語句的執(zhí)行次數(shù)為。。

（3）畫線語句的執(zhí)行次數(shù)為。。

（4）當n為奇數(shù)時畫線語句的執(zhí)行次數(shù)為，當n為偶數(shù)時畫線語句的執(zhí)行次數(shù)為。。

2-10.（1）當時，，所以，可選，。對于，，所以，。

（2）當時，，所以，可選，。對于，，所以，。

（3）由（1）、（2）可知，取，，，當時，有，所以。

2-11.(1)當時，，所以，?？蛇x，。對于，，即。留神：是f(n)和g(n)的關(guān)系。

（2）當時，，所以，。可選，。對于，，即。

（3）由于，。當時，，。所以，可選，，對于，，即。

其次章2-17.證明：設(shè)，那么。

當時，。所以，。

第五章5-4.SolutionTypeDandC1(intleft,intright){while(!Small(left,right)elsereturnS(P)}}5-7.templateintSortableList::BSearch(constTelsereturnm;}return-1;}第五章9．證明：由于該算法在告成探尋的處境下，關(guān)鍵字之間的對比次數(shù)至少為，至多為。在不告成探尋的處境下，關(guān)鍵字之間的對比次數(shù)至少為，至多為。所以，算法的最好、最壞處境的時間繁雜度為。

假定查找表中任何一個元素的概率是相等的，為，那么，不告成探尋的平均時間繁雜度為，告成探尋的平均時間繁雜度為。

其中，是二叉判定樹的內(nèi)路徑長度，是外路徑長度，并且。

11.步數(shù)012345初始時111111[11]1[11]∞2[1]11[11]∞3111[11]∞4111[1]1∞排序結(jié)果11111∞步數(shù)01234567初始時5583432∞1[4233]5[85]∞2[323]45[85]∞3[32]345[85]∞4[2]3345[85]∞523345[5]8∞排序結(jié)果2334558∞12.（1）證明：當或或時，程序鮮明正確。

當n=right-left+1>2時，程序執(zhí)行下面的語句：

intk=(right-left+1)/3;StoogeSort(left,right-k);StoogeSort(left+k,right);StoogeSort(left,right-k);①首次遞歸StoogeSort(left,right-k);時，序列的前2/3的子序列有序。

②當遞歸執(zhí)行StoogeSort(left+k,right);時，使序列的后2/3的子序列有序，經(jīng)過這兩次遞歸排序，使原序列的后1/3的位置上是整個序列中較大的數(shù)，即序列后1/3的位置上數(shù)均大于前2/3的數(shù)，但此時，前2/3的序列并不確定是有序的。

③再次執(zhí)行StoogeSort(left,right-k);使序列的前2/3有序。

經(jīng)過三次遞歸，最終使序列有序。

所以，這一排序算法是正確的。

（2）最壞處境發(fā)生在序列按遞減次序排列。

，，。

設(shè)，那么。

冒泡排序最壞時間繁雜度為，隊排序最壞時間繁雜度為，快速排序最壞時間繁雜度為。所以，該算法不如冒泡排序，堆排序，快速排序。

13.templateselect(Tif(m+n0){do{mid=(left+right)/2;if(a[mid]b[i])right=mid;else{cnt=mid;break;}}while(leftcnt){if(cnt>0){for(j=0;j=c[i