《算法分析与设计》期末试题及参考答案

if A(i)>xmax then xmax←A(i); j←i;endif repeat

end MAX 答案 5、

xmax←A(1);j←1 时间为：O(1) for i←2 to n do 循环最多n-1次

所以 总时间为:

T(n)=O(1)+ (n-1)O(1)= O(n)

6.procedure BINSRCH(A,n,x,j) integer low,high,mid,j,n; low←1;high←n while low≤high do

mid←|_(low+high)/2_| case

:x

:x>A(mid):low←mid+1 :else:j←mid; return

endcase repeat j←0 end BINSRCH 答案

6、log2n+1

三、算法理解

1、写出多段图最短路经动态规划算法求解下列实例的过程，并求出最优值。 2 5 1 3 6 8 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 答案：

1、

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)

答案

2、 写出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 3

3、 给出5个数(3,6,9,1,7),M=13，用递归树描述sumofsub算法求和数=M的一个子集

的过程。

4、 快速排序算法对下列实例排序，算法执行过程中，写出数组A第一次被分割的过程。

A=(65,70,75,80,85,55,50,2)

5、 归并排序算法对下列实例排序，写出算法执行过程。 A=(48,12,61,3,5,19,32,7)

5、

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

6、 写出图着色问题的回溯算法的判断X[k]是否合理的过程。 6、 i←0

while i

if G[k,i]=1 and X[k]= X[i] then return false i←i+1 repeat

if i= k then return true

7、 对于下图，写出图着色算法得出一种着色方案的过程。

2

3 1 4

7、

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） 8、 写出第7题的状态空间树。

9、 写出归并排序算法对下列实例排序的过程。

(6,2,9,3,5,1,8,7) 9、

调用第一层次 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 排序结束，返回主函数

10、 写出用背包问题贪心算法解决下列实例的过程。 P=(18,12,4,1) W=(12,10,8,3) M=25

10、实例符合P(i)/W(i)≥P(i+1)/W(i+1)的顺序。 CU←25,X←0

W[1]< CU: x[1]←1; CU←CU-W[1]=13;