1、PAGE 福建師范大學 數學與計算機科學學院 2009 2010 學年第 2 學期考試 C 卷考生信息欄學院系 專業 年級姓名 學號裝 訂 線 專 業： 計算機科學與技術（非師） 年 級： 2008 課程名稱: 算法設計與分析 任課教師： 翁 彬 試卷類別：開卷（ ）閉卷（ ） 考試用時： 120 分鐘考試時間: 2010 年 6 月 29 日 上 午 9 點 分題號一二三四五總得分評卷人得分題號六七八九十得分一計算題（共25分）1. 計算下面算法中count=count+1的執行次數，并用符號表示出它的階。 （5分）算法 COUNTcount=0for i=1 to for j=i to i

2、+5 for k=1 to i2 count=count+1 end for end forend for end COUNT2. 用兩種方法證明 = (n log n)。 （共10分，每小題5分）(1)用代數方法(2)用積分方法3. 求解遞推關系式 f(n)=-6f(n-1)-9f(n-2),當n2;f(0)=3,f(1)=-3。 （5分）4. 一個旅行商問題的耗費矩陣如下，要求用分支限界法解該問題，給出最優巡回路徑。（5分）二簡答題（共20分）1. 分治算法的基本思想是什么？有哪些基本步驟？（8分）2. 回溯法的基本思想是什么？回溯算法的時間復雜性主要取決于哪些因素？（8分）3貪心法與動態

3、規劃有何根本區別？（4分）三算法填空題（共45分，每空3分） 1. 下面是求一個序列的多數元素的遞歸算法算法 MAJORITY輸入：n個元素的數組A1.n。輸出：若A1.n存在多數元素，則輸出；否則輸出none。 c=candidate ( 1 ) / 求A1.n中的候選多數元素。count=0 /以下驗證c是否為A1.n中的多數元素。 for j=1 to n if Aj=c then count=count+1 end for考生信息欄學院系 專業 年級姓名 學號裝 訂 線 if _（1）_ then return c else return noneend MAJORITY過程 cand

4、idate ( m )/求Am.n中的候選多數元素并返回。j=m; c=Am; count=1while j0 j=j+1 if Aj=c then _（2）_ else _（3）_ /除去兩個不同的元素。end whileif j=n then return c /此時序列已掃描完畢。else return _（4）_ end candidate2. 以下是分數背包問題的貪心算法算法 GREEDY_KANPSACK輸入：表示背包容量的實數C, 物品數n, 表示n個物品的體積和價值的實數數組s1.n和v1.n。輸出：裝入背包物品的最大總價值maxv和相應的最優解x1.n。 for i=1 to

5、 n yi=vi/si /求n個物品的單位體積價值y1.n。 end for /對y1.n按降序地址排序，排序結果返回到數組d1.n /中, 使得yd1=yd2=ydn。 d=sort(y, n) for i=1 to n xi=0 /對x1.n初始化。 i=1; maxv=0; rc=C /以下rc表示當前背包的剩余容量。while _(1)_ and i=nj=di / uj為當前考慮選擇的物品 if sj=0 and cvmaxv then /找到更優的解，更新當前最優值。 maxv=_(1)_; x0=x end if if rsmaxv then maxv=cv+rv; x01.k=x1.k; x0k+1.n=1; end if else if r0 and cv+rvmaxv then /可繼續往下搜索。 rv=_(2)_; rs=_(3)_ xk+1=0 knapsack_(4)_/搜索左子樹（對應xk+1=0） xk+1=1 knapsack_(5)_ /搜索右子樹end if考生信息欄學院系 專業 年級姓名 學號裝 訂 線 end if end knapsack四算法設計題（10分）1. 考慮金錢兌換問題。有一個貨幣系統，它有n種硬幣，它們