湖南中醫藥大學 2009—2010 學年第一學期
《演算法設計與分析》期末考試試卷
班級姓名學號
一、 選擇題（10題*2分=20分）
1. 我們常用演算法的最壞時間來估計演算法的時間複雜性，下面（ ）不是這樣做的原因：
a、 在實際問題中，演算法的執行時間常常達到這個上界。
b、 平均執行時間難以計算。
c、 假設每乙個輸入具有相同的概率有時沒有意義。
d、 平均執行時間與最壞執行時間有相同的數量級。
2. 合併排序演算法是利用（ ）實現的演算法。
a、分治策略 b、動態規劃法 c、貪心法 d、回溯法
3. 下列是動態規劃演算法基本要素的是（ ）。
a、最優子結構 b、構造最優解 c、算出最優解 d、定義最優解
4. 下列演算法中通常以自頂向下的方式求解最優解的是（ ）。
a、分治法 b、動態規劃法 c、貪心法 d、回溯法
5. 廣度優先是（ ）的一搜尋方式。
a、分支界限法 b、動態規劃法 c、貪心法 d、回溯法
6. 設q（n，m）是將正整數n劃分成最大加數不大於m的若干不同正整數之和的劃分數，則q（n，m）為
a1n=1 || m=1）
q(n, nn < m）
q（n，m）= 1 + q(n, n-1n = m）
q(n, m-2) + q(n-m,m)（n > m > 1）
b、1n=1 || m=1）
q(n, nn < m）
q（n，m）= 1 + q(n, n-1n = m）
q(n, m-1) + q(n-m,m)（n > m > 1）
c、1n=1 || m=1）
q(n, nn < m）
q（n，m）= 1 + q(n, n-1n = m）
q(n, m-1) + q(n-m,m-1)（n > m > 1）
d、0n > 1 && m = 1）
1n=1）
q（n，m）= q(n, nn < m）
1 + q(n, n-1n = m）
q(n, m-1) + q(n-m,m-1)（n > m > 1）
7. 計算機演算法指的是解決問題的步驟序列，它必須具備（ ）這三個主要特性。
a、可行性、正確性、可讀性
b、可行性、確定性、有窮性
c、確定性、有窮性、穩定性
d、易讀性、健壯性、安全性
8. 當乙個確定性演算法在最壞情況下的計算複雜性與其在平均情況下的計算複雜性有較大差別時，可以使用（ ）來消除或減少問題的好壞例項間的這種差別。
a、數值概率演算法b、舍伍德演算法
c、蒙特卡羅演算法d、拉斯維加斯演算法
9. 對於0-1揹包問題和揹包問題的解法，下面答案解釋正確的是（ ）。
a、0-1揹包問題和揹包問題都可以用貪心演算法求解
b、0-1揹包問題可以用貪心演算法求解，但揹包問題則不能用貪心演算法求解。
c、0-1揹包問題問題不能用貪心演算法求解，但可以用動態規劃和回溯法求解，而揹包問題可以用貪心演算法求解。
d、因為0-1揹包問題不具有最優子結構性質，所以不能用貪心演算法求解。
10. 在分支限界演算法中，根據從活結點表中選擇下一擴充套件點的不同方式可以有幾種常用的分類，以下描述最準確的是（ ）。
a、 採用fifo佇列的佇列式分支限界法。
b、 採用最小堆的優先佇列式分支限界法。
c、 採用最大堆的優先佇列式分支限界法。
d、 以上都常用，針對具體問題可以選擇其中某種更為合適的方式。
二、 填空題(10題×2分=20分)
1. 演算法執行所需要的計算機資源的量，稱為演算法複雜性，主要包括
和2. f(n)=o(g(n))表示當且僅當存在正的常數c和n0，使得對於所有的n ， 有f(n
3. 對於函式，如果存在，使得當時有，就說是當時的
4. 多項式的上界為
5. 直接或間接地呼叫自身的演算法稱為用函式自身給出定義的函式稱為
6. 動態規劃演算法的子問題重疊性質是指：每次產生的子問題並不是有些子問題會被
7. 貪心演算法的兩個基本要素是和
8. 按照活結點表的組織方式的不同，分支限界法包括和兩種形式。
9. 回溯法中的解空間樹結構通常有兩種，分別是
10. 用分支限界法解旅行售貨員問題時，對空間樹搜尋結束的標誌是
三、 判斷題(10題×2分=20分)
1. 如果g(n)=o(f(n))，則o(f)+o(g)=o(f)。 （ ）
2. 所有的遞迴函式都能找到對應的非遞迴定義。（ ）
3. 動態規劃演算法中，通常不同子問題的個數隨問題規模呈指數級增長。（ ）
4. 備忘錄方法求解時採用與遞迴定義一致的自上而下的方式。（ ）
5. 用貪心演算法解0-1揹包問題時，總能得到整體最優解。（ ）
6. 利用貪心演算法求解問題時，往往需要事先把問題集合按照一定原則進行排序，而活動安排問題即按活動結束時間的非減序進行排列的。（ ）
7. 使用回溯法搜尋問題的解空間樹時，按照深度優先方式進行搜尋，其間不受其他條件限制。（ ）
8. 動態規劃演算法與分治法類似，其基本思想是將待求解問題分解成若干個子問題，先求解子問題，然後從這些子問題的解得到原問題的解，二者採用的都是自底向上的計算方式（ ）
9. 每個優化問題都是由目標函式和約束條件組成。（ ）
10. 解空間樹中，只有展開了所有子結點的結點才稱為死結點。（ ）
四、 簡答題（4題×5分=20分）
1. 按漸高階從低到高的順序排列以下表示式：n!，4n2，logn，3n，20n，2，n2/3。
2. 已知矩陣a1，a2，a3，a4，a5，a6的維數分別是：5×10，10×3，3×12，12×5，5×50，50×6，求矩陣連乘a1×a2×a3×a4×a5×a6的最佳求積順序。
3. 寫出貪心演算法的基本設計思想。
4. 分析說明分治法與動態規劃法的聯絡與區別。
五、 演算法分析與設計題（2題*10分=20分）
1. 對於下圖使用dijkstra演算法求由頂點a到其他各個頂點的最短路徑。並給出求各個頂點對之間的最短路徑的演算法思想。（12分）
2. 對於如下圖所示的旅行售貨員問題，使用優先佇列式分支限界法進行求解，試構造出描述其搜尋過程的狀態空間樹，並說明活結點表的變化情況。
演算法設計與分析課程設計報告簡單示例1
演算法設計與分析課程設計 題目 模擬實現穩定婚姻問題的gale shapley演算法 設計分析測試報告 姓名 鄭展圖 學號 3100608010 班級 軟體1001 指導教師 蔣麗萍 2013年 1 月 9 日 程式演算法設計說明書 一 前言 1.問題描述 穩定婚姻問題 有n男n女，每人都按他對 異...
演算法設計技巧與分析答案
參 第1章演算法分析基本概念 1.1 a 6 b 5 c 6 d 6 1.4演算法執行了7 6 5 4 3 2 1 28次比較 1.5 a 演算法modselectionsort執行的元素賦值的最少次數是0,元素已按非降序排列的時候達到最小值。b 演算法modselectionsort執行的元素賦值...
演算法設計與分析期末試題
總題一 記得哪些演算法複雜性的知識？用自己的話簡述。例如最壞時間複雜性 複雜性漸進性態的階 二 演算法的時間複雜性分析 1 如何根據演算法的結構分析演算法的時間複雜性？例如選擇基本運算步驟 依據演算法的結構統計。2 分析遞迴演算法的方法，歸方程方法和遞迴樹。姐遞迴方程有迭代法 遞推 法解遞迴方程，或...