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

第1页，共5页北京化工大学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’)参考答案如下：101::nnnkknfafaf即记0)(:nnnzfzg定义生成函数1101)(:nnnnnnzfazfazgza则010)()1(nnnnzzfzgaz111)(lim:0axaxaxniin由zznn110azBzAazzzg11)1)(1(1)(aaBaA1,11:由待定系数法可求得第2页，共5页000)(11,11:)(limnnnnniinazazzzax得又由0)()(nnnzaBAzg111111aaaaaaaBAfnnnn3.(15’)参考代码如下：intQuickSort(intL[],intn){stackintS;S.push(0);S.push(n-1);while(!S.empty()){intj=S.top();S.pop();inti=S.top();S.pop();if(st){intk=Partition(L,i,j);S.push(i);S.push(k-1);S.push(k+1);S.push(j);}}return1;}第3页，共5页4.(15’)参考答案如下：01234001358496136K=0K=0K=0K=310546690K=1K=2K=3203688K=2K=23016K=340((A0((A1A2)A3))A4)5.(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达到最大。贪心选择性质得证。最优子结构性质证明：当a4的值确定后，为了使a1+a2+a3+a4达到最小，须使a1+a2+a3达到最小，且由穷举可知，仍为同型的最优问题。第4页，共5页6.(15’)已知正整数集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}7.(15’)参考答案如下：{}sa=0su=19{}sa=0su=17{2}sa=2su=17{}sa=0su=14{3}sa=3su=14{2}sa=2su=14{2,3}sa=5su=14{}sa=0su=9{5}sa=5su=9{3}sa=3su=9{3,5}sa=8su=9{2}sa=2su=9{2,5}sa=7su=9{2,3}sa=5su=9{2,3,5}sa=10su=9{5}sa=5su=0{5,9}sa=14su=0{2,3}sa=5su=0{2,3,9}sa=14su=0第5页，共5页定义状态结点为(v1,v2,..vt)，表示已着色结点及其顺序。则解结点权值D(x)=∑vi*pvii=1..n可定义状态结点的下界为已着色结点的着色权值+可能的最小着色权值。如：~C(x)=∑vi*pvi+(t+1)*∑pji=1..t,j为其他未着色结点。可定义状态结点的上界为已着色结点的着色权值+可能的最大着色权值。如：U(x)=∑vi*pvi+n*∑pji=1..t,j为其他未着色结点。