算法設计期末复习题.docVIP

算法分析与设计复习题 1、对于下图，写出图着色算法得出一种着色方案的过程。 解： K←1 X[1] ←1 , 返回 true X[2]←1,返回false; X[2]←X[2]+1=2, 返回 true X[3]←1 ,返回false; X[3]←X[3]+1=2, 返回false;X[3]←X[3]+1=3, 返回 true X[4]←1, 返回false; X[4]←X[4]+1=2, 返回false;X[4]←X[4]+1=3, 返回 true 找到一个解 （1，2，3，3） 2、写出多段图最短路经动态规划算法求解下列实例的过程，并求出最优值。 各边的代价如下： C(1,2)=3， C(1,3)=5 ，C(1,4)=2 C(2,6)=8 ，C(2,7)=4 ，C(3,5)=5 ，C(3,6)=4， C(4,5)=2，C(4,6)=1 C(5,8)=4， C(6,8)=5 ，C(7,8)=6 解： Cost(4,8)=0 Cost(3,7)= C(7,8)+0=6 ，D[5]=8 Cost(3,6)= C(6，8)+0=5, D[6]=8 Cost(3,5)= C(5，8)+0=4 D[7]=8 Cost(2,4)= min{C(4，6)+ Cost(3,6), C(4，5)+ Cost(3,5)} = min{1+ 5, 2+4}=6 D[4]=6 Cost(2,3)= min{C(3，6)+ Cost(3,6) } = min{4+5}=9 D[3]=5 Cost(2,2)= min{C(2，6)+ Cost(3,6), C(2，7)+ Cost(3,7)} = min{8+5, 4+6}=10 D[2]=7 Cost(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}= 8 D[1]=4 1→4→6→8 3、写出maxmin算法对下列实例中找最大数和最小数的过程。 数组 A=(48,12,61,3,5,19,32,7) 解： 1、 48,12,61,3, 5,19,32,7 2、48,12 61,3 5,19 32,7 3、 48～61, 12～3 19～32，5～7 4、 61～32 3～5 5、 61 3 4、归并排序算法对下列实例排序，写出算法执行过程。 A=(48,12,61,3,5,19,32,7) 解： 48,12,61,3 5,19,32,7 48,12 61,3 5,19 32,7 12,48 3,61 5,19 7,32 3, 12, 48, 61 5, 7, 19，32 3,5, 7,12，19，32，48,61 5、设计一个算法在一个向量A中找出最大数和最小数的元素 解： Void maxmin(A,n) Vector A; int n; { int max,min,i; max=A[1];min=A[1]; for(i=2;i=n;i++) if(A[i]max)max=A[i]; else if(A[i]min)min=A[i]; printf(“max=%d,min=%d\n”,max,min); } 6、．快速排序算法对下列实例排序，算法执行过程中，写出数组A第一次被分割的过程。 A=(65,70,75,80,85,55,50,2) 解： (1) (2) (3) (4) (5) (6) (7) (8) i p 65 70 75 80 85 55 50 2 2 8 65 2 75 80 85 55 50 70 3 7 65 2 50 80 85 55 75 70 4 6 65 2 50 55 85 80 75 70 4 6 55 70 75 80 85 65 50 2 7、写出用背包问题贪心算法解决下列实例的过程。 P=(18,12,4,1) W=(12,10,8,3) M=25 解： 实例