《算法设计与分析》试题（A卷）参

北京化工大学

2004年《算法设计与分析》试题(A卷)

参考答案

考试日期：2004年11月24日

考试时间：2小时

1. (每段5’)参考答案如下：

段1：T(n) = n = O(n) 段2：T(n) = n2 = O(n2)

段3：T(n) = n(n+1)/2 = O(n2) 2. (10’)参考答案如下：

n记:fkn??a即:fn?1?a?fn?1

k?0?定义生成函数:g(z)??fnn?z

n?0??则:a?z?g(z)??a?fn?1n?z?n

n?0?a?fn?1?zn?1?n??(1?az)g(z)?f0??z??1?zn

nn?0n由:lim?(ax)i?1n??i?01?axax?1

???zn?1n?01?z ?g(z)?1(1?z)(1?az)?A1?z?B1?az

由待定系数法可求得:A?1?a1?a,B?1?a

第1页，共5页

n又由limin???(ax)得:1?i?01?z??zn,1???01?az?(az)n

nn?0??g(z)??(A?B?an)zn

n?0?fn1?anan?1?1n?A?B?a?1?a?1?a?a?a?1

3. (15’)参考代码如下：

int QuickSort( int L[], int n ) {

stack S;

S.push(0); S.push(n-1); while (!S.empty()) {

int j = S.top(); S.pop(); int i = S.top(); S.pop(); if (s

int k = Partition(L, i, j); S.push(i); S.push(k-1); S.push(k+1); S.push(j); } }

return 1; }

第2页，共5页

4. (15’)参考答案如下：

0 1 2 3 4 0 0 135 84 96 136 K=0 K=0 K=0 K=3 1 0 54 66 90 K=1 K=2 K=3 2 0 36 88 K=2 K=2 3 0 16 K=3 4 0

((A0((A1A2)A3))A4)

5. (15’)证明如下：设某种货币系统为(1, 5, 10, 25)四种币值（单

位：元），要用最少的币数找出n元钱，问：能否用贪心算法进行求解，并证明。 贪心性质证明：

对n<=25的情况，易由穷举得证。

当n>25时，设n=1*a1+5*a2+10*a3+25*a4 为了使a1+a2+a3+a4最小，易知：

a1<5，若a1>=5，可将5个1元兑换为1个5元，币数减少。 a2<2，若a2>=2，可将2个5元兑换为1个10元，币数减少。

当a2=0时，a3<3，若a3>=3，可将3个10元兑换为1个5元和1个25元，币数减少。

当a2>0时，a3<2，若a2>=2，可将1个5元和2个10元兑换为1个25元，币数减少。

即，为了使a1+a2+a3+a4最小，所使用的1、5、10元币的币数的上限为：

a1=4, a2=0, a3=2 或 a1=4, a2=1, a3=1 则所使用的1、5、10元币的币值上限为：

4*1+0*5+2*10 = 24 或 4*1+1*5+1*10 = 19

均不超过25，因此，为了使a1+a2+a3+a4最小，应使a4达到最大。贪心选择性质得证。 最优子结构性质证明：

当a4的值确定后，为了使a1+a2+a3+a4达到最小，须使a1+a2+a3达到最小，且由穷举可知，仍为同型的最优问题。

第3页，共5页

6. (15’)已知正整数集A={2, 3, 5, 9}，目标值M=14，用回溯法求

解A的所有和等于M的子集，请画出状态空间树，并写出回溯求解的过程。

{} sa=0 su=19 {} sa=0 su=17 {} sa=0 su=14 {} sa=0 su=9 {5} sa=5 su=9 {3} sa=3 su=14 {3} sa=3 su=9 {3,5} sa=8 su=9 {2} sa=2 su=14 {2} sa=2 su=9 {2} sa=2 su=17 {2,3} sa=5 su=14 {2,3} {2,3,5} sa=5 sa=10 su=9 su=9 {2,3,9} sa=14 su=0 {2,5} sa=7 su=9 {5} sa=5 su=0 {5,9} sa=14 su=0 {2,3} sa=5 su=0 沿状态空间树深度优先搜索，左分枝表示放弃，右分枝表示选入。 在结点({}/sa=0/su=9)处，因sa+su

在结点({3}/sa=3/su=9)处，因sa+su

在结点({3,5}/sa=8/su=0)处，因sa+A[3]>M，回溯； 在结点({2}/sa=2/su=9)处，因sa+su

在结点({2,5}/sa=7/su=9)处，因sa+A[3]>M，回溯； 在结点({2,3}/sa=5/su=0)处，因sa+su

在结点({2,3,5}/sa=10/su=9)处，因sa+A[3]>M，回溯。 最后得解：{5,9}, {2,3,9}

7. (15’)参考答案如下：

第4页，共5页

定义状态结点为(v1,v2,..vt)，表示已着色结点及其顺序。 则解结点权值D(x)=∑vi*pvi i=1..n

可定义状态结点的下界为已着色结点的着色权值+可能的最小着色权值。 如：~C(x)=∑vi*pvi + (t+1)*∑pj i=1..t, j为其他未着色结点。 可定义状态结点的上界为已着色结点的着色权值+可能的最大着色权值。 如：U(x)=∑vi*pvi + n*∑pj i=1..t, j为其他未着色结点。

第5页，共5页