算法导论答案

《算法导论答案》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、《算法导论》参考答案第2章第3章第4章第5章第6章第7章第8章第9章第15章第16章第24章第25章第2章2.1-12.1-22.1-32.1-42.2-12.2-22.2-32.2-42.3-12.3-2voidMerge(int*A,intp,intq,intr){//构建左半部分和右半部分的辅助数组intn1=q-p+1;intn2=r-q;int*L=newint[n1];int*R=newint[n2];for(inti=0;i

2、tk=p-1;while((i<=n1-1)&&(j<=n2-1)){if(L[i]<=R[j]){A[k]=L[i];i++;}else{A[k]=R[j];j++;}k++;}while(i<=n1-1){A[k]=L[i];i++;k++;}while(j<=n2-1){A[k]=R[j];j++;k++;}delete[]L;delete[]R;}2.3-32.3-42.3-52.3-62.3-7第3章3.1-13.1-23.1-33.1-43.1-53.1-63.1-73.1-83.2-13.2-23.2-33.2-43.2-5后者大3.2-6数学归纳法易证3.2-7用数学

3、归纳法证明第4章4.1-14.1-24.1-3T(n)=cnlgn+n4.1-44.1-54.1-64.2-14.2-24.2-34.2-44.2-54.3-14.3-24.3-34.3-4不能运用主方法4.3-5第5章5.1-1因为本身就是一个排序过程5.2-15.2-25.2-35.2-45.2-55.3-15.3-25.3-35.3-45.3-53n令mn=，生成的全排列个数有m，其中不重复的有Pmn(,)=−mm*(1)**(?mn−+1),n所以，所有元素唯一概率为Pmnm(,)/n要证Pmnm(,)/≥−11/nnn由于Pmnm(,)/≥−[(mnm)/]n故需证：[(m

4、nm−≥)/]11/−n易证5.3-6第6章6.1-16.1-26.1-36.1-46.1-56.1-66.1-76.2-1见图6-26.2-26.2-36.2-46.2-5对以i为根结点的子树上每个点用循环语句实现6.2-66.3-1见图6-36.3-26.3-36.4-1见图6-46.4-2HEAPSORT仍然正确，因为每次循环的过程中还是会运行MAX-HEAP的过程。6.4-36.4-46.4-56.5-1据图6-56.5-26.5-36.5-46.5-56.5-66.5-76.5-8第七章7.1-1见图7-17.1-27.1-37.1-47.2-17.2-27.2-37.2-

5、47.2-57.2-67.3-17.3-27.4-17.4-27.4-3纯数学问题，对式子求导即可得。7.4-4见RANDOMIZED-QUICKSORT.ppt7.4-5见快速排序改进算法(7.4-5).pdf7.4-6第八章8.1-18.1-28.1-38.1-48.2-1见图8-28.2-2和8.2-38.2-48.3-1见图8-38.3-28.3-38.3-48.3-5(*)8.4-1见图8-48.4-28.4-33/2，1/28.4-4(*)8.4-5(*)第九章9.1-19.1-29.2-19.3-19.3-29.3-39.3-49.3-59.3-69.3-79.3-89

6、.3-9第15章15.1-115.1-215.1-32nnnj−+nn1fji[]===∑∑rij()2(2)2(21)2∑−=−1ij==11j=115.1-415.1-515.2-1最终答案：((A1A2)((A3A4)(A5A6)))15.2-215.2-315.2-415.2-5用递归15.3-115.3-215.3-315.3-415.3-515.4-115.4-215.4-315.4-415.4-515.4-6#includeusingnamespacestd;intfind(int*a,intlen,intn)//修改后的二分查找，若返回值为x，则a

7、[x]>=n{intleft=0,right=len,mid=(left+right)/2;while(left<=right){if(n>a[mid])left=mid+1;elseif(n