算法设计期末复习题

《算法设计期末复习题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、算法分析与设计复习题1、对于下图，写出图着色算法得出一种着色方案的过程。2314解：K←1X[1]←1,返回trueX[2]←1,返回false;X[2]←X[2]+1=2,返回trueX[3]←1,返回false;X[3]←X[3]+1=2,返回false;X[3]←X[3]+1=3,返回trueX[4]←1,返回false;X[4]←X[4]+1=2,返回false;X[4]←X[4]+1=3,返回true找到一个解（1，2，3，3）2、写出多段图最短路经动态规划算法求解下列实例的过程，并求出最优值。52863174各边的代价如下：C(1,2)=3，C(1,3)=5，C(1,4)=2C(2

2、,6)=8，C(2,7)=4，C(3,5)=5，C(3,6)=4，C(4,5)=2，C(4,6)=1C(5,8)=4，C(6,8)=5，C(7,8)=6解：Cost(4,8)=0Cost(3,7)=C(7,8)+0=6，D[5]=8Cost(3,6)=C(6，8)+0=5,D[6]=8Cost(3,5)=C(5，8)+0=4D[7]=8Cost(2,4)=min{C(4，6)+Cost(3,6),C(4，5)+Cost(3,5)}=min{1+5,2+4}=6D[4]=6Cost(2,3)=min{C(3，6)+Cost(3,6)}=min{4+5}=9D[3]=5Cost(2,2)=min{

3、C(2，6)+Cost(3,6),C(2，7)+Cost(3,7)}=min{8+5,4+6}=10D[2]=7Cost(1,1)=min{C(1,2)+Cost(2,2),C(1,3)+Cost(2,3),C(1,4)+Cost(2,4)}=min{3+10,5+9,2+6}=8D[1]=41→4→6→83、写出maxmin算法对下列实例中找最大数和最小数的过程。数组A=(48,12,61,3,5,19,32,7)解：1、48,12,61,3,5,19,32,72、48,1261,35,1932,73、48～61,12～319～32，5～74、61～323～55、6134、归并排序算法对下列

4、实例排序，写出算法执行过程。A=(48,12,61,3,5,19,32,7)解：48,12,61,35,19,32,748,1261,35,1932,712,483,615,197,323,12,48,615,7,19，323,5,7,12，19，32，48,615、设计一个算法在一个向量A中找出最大数和最小数的元素解：Voidmaxmin(A,n)VectorA;intn;{intmax,min,i;max=A[1];min=A[1];for(i=2;i<=n;i++)if(A[i]>max)max=A[i];elseif(A[i]

5、in=%d”,max,min);}6、．快速排序算法对下列实例排序，算法执行过程中，写出数组A第一次被分割的过程。A=(65,70,75,80,85,55,50,2)解：(1)(2)(3)(4)(5)(6)(7)(8)ip657075808555502286527580855550703765250808555757046652505585807570465570758085655027、写出用背包问题贪心算法解决下列实例的过程。P=(18,12,4,1)W=(12,10,8,3)M=25解：实例符合P(i)/W(i)≥P(i+1)/W(i+1)的顺序。CU←25,X←0W[1]

6、[1]←1;CU←CU-W[1]=13;W[2]CU:x[3]←CU/W[3]=3/8;实例的解为：（1，1，3/8，0）8、procedurePARTITION(m,p)Integerm,p,i;globalA(m:p-1)v←A(m);i←mlooploopi←i+1untilA(i)≥vrepeatloopp←p-1untilA(p)≤vrepeatifi

7、多的查找次数是p-m+1次9、procedureBINSRCH(A,n,x,j)integerlow,high,mid,j,n;low←1;high←nwhilelow≤highdomid←

8、_(low+high)/2_

9、case:xA(mid):low←mid+1:else:j←mid;returnendcaserepeatj←0endBINSRCH时间