发布时间 : 星期五 文章算法分析与设计考试复习题及参考答案jing更新完毕开始阅读
4 7
各边的代价如下：
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
2、 写出maxmin算法对下列实例中找最大数和最小数的过程。
数组 A=(48,12,61,3,5,19,32,7) 写出maxmin算法对下列实例中找最大数和最小数的过程。
数组 A=()
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
9.给出5个数(3,6,9,1,7),M=13，用递归树描述sumofsub算法求和数=M的一个子集的过程。
1，28，0
2，25，3 3，19，3 4，10，12 5
1、 快速排序算法对下列实例排序，算法执行过程中，写出数组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
2、 归并排序算法对下列实例排序，写出算法执行过程。 A=(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
3、 对于下图，写出图着色算法得出一种着色方案的过程。
2
3 1 4
4、 写出归并排序算法对下列实例排序的过程。
(6,2,9,3,5,1,8,7)
调用第一层次 6,2,9,3 5,1,8,7 分成两个子问题 调用第二层次 6,2 9,3 5,1 8,7 分成四个子问题
调用第三层次 6 2 9 3 5 1 8 7 分成八个子问题 调用第四层次 只有一个元素返回上一层
第三层归并 2 ,6 3, 9 1,5 7,8 返回上一层 第二层归并 2 ,3,6, 9 1,5,7,8 返回上一层
第一层归并 1, 2 ,3, 5 ,6, 7, 8,9 排序结束，返回主函数
5、 写出用背包问题贪心算法解决下列实例的过程。 P=(18,12,4,1)
W=(12,10,8,3) M=25
实例符合P(i)/W(i)≥P(i+1)/W(i+1)的顺序。
6
CU←25,X←0
W[1]< CU: x[1]←1; CU←CU-W[1]=13; W[2]< CU: x[2]←1; CU←CU-W[2]=3;
W[3]>CU: x[3]←CU/ W[3]=3/8; 实例的解为：（1，1，3/8，0）
11、有一个有序表为{1，3，9，12，32，41，45，62，75，77，82，95，100}，当使用二分查找值为82的结点时，经过多少次比较后查找成功并给出过程。 一共要要执行四次才能找到值为82的数
12、使用prim算法构造出如下图G的一棵最小生成树。
1 2 3 4 5 6
dist(1,2)=6;dist(2,5)=3;dist(5,6)=6;dist(6,4)=2;dist(4,1)=5; dist(1,3)=1;dist(2,3)=5;dist(3,4)=5;dist(3,6)=4;dist(5,3)=6
1 1 1 4 3 3 3 6 6 1 2 4 2 3 3 6
13、有如下函数说明
5 6
1 4 7
int f(int x,int y)
{
f=x Mod y +1; }
已知a=10,b=4,c=5 则执行k=f(f(a+c,b),f(b,c))后，k的值是多少并写出详细过程。
int f(int x,int y) {
f=x Mod y +1; }
已知a=10,b=4,c=5 则执行k=f(f(a+c,b),f(b,c))后，k的值是多少并写出详细过程。
}
K的值是5
14、McCathy函数定义如下：
当x>100时 m(x)=x-10;
当x<=100时 m(x)=m(m(x+11));
编写一个递归函数计算给定x的m(x)值。 int m(int x) {
int y;
if(x>100) return(x-100); else {
y=m(x+11);
return (m(y)); } }
15、 设计一个算法在一个向量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] printf(“max=%d,min=%d\\n”,max,min); } 8