課程名稱： 算法分析與設計 課程編號： 課程類型： 非學位課 考試方式： 開卷
學科專業、領域： 計算機應用技術 所在學院： 信電學院 任課教師： 劉建國
河北工程大學研究生2010～ 2011 學年第 1 學期考試試卷（ A ）卷
一、填空題（20分，每空2分）
1. 假設某算法在輸入規模為n 時的計算時間為T(n)=3×2n
。在某臺計算機上實現并完成該算法的時間為t 秒。現有另一臺計算機算法的時間復雜性tn，其運行速度為第一臺的64倍，那么在這臺計算機上用同一算法在t 秒內能解決輸入規模為的問題。若上述算法的計算時間改進為T(n)=n 2
，其余條件不變，則在新機器上用t 秒事件能解輸入規模為的問題；若算法計算時間進一步改進為T(n)=8新機器可解輸入規模。
2. 按照漸近階從低到高的順序排列下列表達式：20n ，4n 2，logn ，3n ，2，n 2/3，n!，2n 。 。
3. 動態規劃算法的主要步驟包括刻畫最優解的性質和結構、遞歸定義最優值、以自底向上的方式計算最優值、根據計算最優值的相關信息構造最優解，在分析了最優解的性質和結構之后，一個比較至關重要的步驟是給出最優值的遞歸定義，請給出下面問題的最優值的遞歸定義：
最長公共子序列問題中，c[i ，j]表示序列X i 和Y j 的最長公共子序列的長度，則c[i ，j]可遞歸定義為：
4. 在使用回溯法考慮求解一個具體問題時，往往需要設計出約束條件和限界條件。0-1背包問題的約束條件是；限界條件是bound>，其中，bound=。
5. 用貪心算法求解單源最短路徑的時間復雜度為。 二、解答下列問題（40分，每題8分） 1. 求解遞歸方程
2. 求解下列遞歸方程F(n)的通解
j j
i i y y x x j i j i j i j i c ≠==>>=??
??=0;0,;0,,
?>+==1
)
4(2)3(5)2(3)1(322
11001
F(n)n n F n F n F n F n n n n
課程名稱：算法分析與設計課程編號： 課程類型：非學位課考試方式：開卷
學科專業、領域：計算機應用技術所在學院：信電學院任課教師：劉建國
3. 用貪心算法求下圖頂點1到其它頂點的的最短路徑。
4. 有0-1背包問題如下：n=5，c=16算法的時間復雜性tn，P=（8，15，18，12，6），W=（3，2，10，4，2）。畫出用回溯法求解時的搜索樹，并指明約束條件、限界條件。
5.設有5個矩陣A1,A2,A3,A4，A5它們的維數分別是：
用動態規劃方法計算矩陣連乘的最優次數m[i][j]。
三、算法設計題（共40分，1題10分，2、3題15分）
1.設n個不同的整數排好序后存放于T[0:n-1]中。若存在一個下標0≤i
2.最優分解問題
設n是一個整數，現將n分解為若干互不相同的自然數的和，使這些自然數的乘積最大。
3.最優裝載問題，可采用下面的策略改進，使算法的計算時間復雜度為O(2n)
首先只運行計算最優值的算法，計算出最優裝載量W，由于該算法不記錄最優解，故所需要的計算時間為O(2n)，然后再運行改進后的算法，并在算法中將bestw置為W。這樣一來，在首次到達的葉子結點處（即首次遇到i>n時）終止算法。此時返回的bestw即為最優解。