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

《《算法设计与分析》试题(A卷)参.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、北京化工大学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’)参考答案如下：1.(15’)参考代码如下：intQuickSort(intL[],intn){stackS;S.push(0);S.push(n-1);while(!S.empty()){intj=S.top();S.pop();inti=S.top();S.po

2、p();if(s

3、：对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

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达到最小，且由穷举可知，仍为同型的最优问题。1.(15’)已知正整数集A={2,3,5,9}，目标值M=14，用回溯法求解A的所有和等于M的子集，请画出状态空间树，并写出回溯求解的过程。{}s

5、a=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沿状态空间树深度优先搜索，左分枝表示放弃，右分枝表示选入。在结点(

6、{}/sa=0/su=9)处，因sa+suM，回溯；在结点({2}/sa=2/su=9)处，因sa+suM，回溯；在结点({2,3}/sa=5/su=0)处，因sa+su

7、}/sa=14/su=0)处，得解；在结点({2,3,5}/sa=10/su=9)处，因sa+A[3]>M，回溯。最后得解：{5,9},{2,3,9}2.(15’)参考答案如下：定义状态结点为(v1,v2,..vt)，表示已着色结点及其顺序。则解结点权值D(x)=∑vi*pvii=1..n可定义状态结点的下界为已着色结点的着色权值+可能的最小着色权值。如：~C(x)=∑vi*pvi+(t+1)*∑pji=1..t,j为其他未着色结点。可定义状态结点的上界为已着色结点的着色权值+可能的最大着色权值。如：U(x)=∑vi*pvi

8、+n*∑pji=1..t,j为其他未着色结点。