l算法设计与分析试题A卷参.docVIP

北京化工大学 2004年《算法设计与分析》试题(A卷) 参考答案 考试日期：2004年11月24日 考试时间：2小时 (每段5’)参考答案如下： 段1：T(n) = n = O(n) 段2：T(n) = n2 = O(n2) 段3：T(n) = n(n+1)/2 = O(n2) (10’)参考答案如下： (15’)参考代码如下： int QuickSort( int L[], int n ) { stackint S; S.push(0); S.push(n-1); while (!S.empty()) { int j = S.top(); S.pop(); int i = S.top(); S.pop(); if (st) { int k = Partition(L, i, j); S.push(i); S.push(k-1); S.push(k+1); S.push(j); } } return 1; } (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) (15’)证明如下：设某种货币系统为(1, 5, 10, 25)四种币值（单位：元），要用最少的币数找出n元钱，问：能否用贪心算法进行求解，并证明。 贪心性质证明： 对n=25的情况，易由穷举得证。 当n25时，设n=1*a1+5*a2+10*a3+25*a4 为了使a1+a2+a3+a4最小，易知： a15，若a1=5，可将5个1元兑换为1个5元，币数减少。 a22，若a2=2，可将2个5元兑换为1个10元，币数减少。 当a2=0时，a33，若a3=3，可将3个10元兑换为1个5元和1个25元，币数减少。 当a20时，a32，若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达’)已知正整数集A={2, 3, 5, 9}，目标值M=14，用回溯法求解A的所有和等于M的子集，请画出状态空间树，并写出回溯求解的过程。 沿状态空间树深度优先有哪些信誉好的足球投注网站，左分枝表示放弃，右分枝表示选入。 在结点({}/sa=0/su=9)处，因sa+suM，回溯； 在结点({5}/sa=5/su=0)处，因sa+suM，回溯； 在结点({5,9}/sa=14/su=0)处，得解； 在结点({3}/sa=3/su=9)处，因sa+suM，回溯； 在结点({3,5}/sa=8/su=0)处，因sa+A[3]M，回溯； 在结点({2}/sa=2/su=9)处，因sa+suM，回溯； 在结点({2,5}/sa=7/su=9)处，因sa+A[3]M，回溯； 在结点({2,3}/sa=5/su=0)处，因sa+suM，回溯； 在结点({2,3,9}/sa=14/su=0)处，得解； 在结点({2,3,5}/sa=10/su=9)处，因sa+A[3]M，回溯。 最后得解：{5,9}, {2,3,9} (15’)参考答案如下： 定义状态结点为(v1,v2,..vt)，表示已着色结点及其顺序。 则解结点权值D(x)=∑vi*pvi i=1..n 可定义状态结点的下