1、選擇題：(每題2分，共30分)1. 衡量一個(gè)算法好壞的標(biāo)準(zhǔn)是（ C ）。A.運(yùn)行速度快 B.占用空間少 C.時(shí)間復(fù)雜度低 D.代碼短2. 當(dāng)輸入規(guī)模為n時(shí)，算法增長率最快的是（ C ）。 A.12n B. 100log2n C.2n2 D.3nlog3n3. 漸進(jìn)算法分析是指（ B ）。A. 算法在最好情況、最壞情況和平均情況下的代價(jià)B. 當(dāng)規(guī)模逐步往極限方向增大時(shí)，對(duì)算法資源開銷“增長率”上的簡化分析C. 數(shù)據(jù)結(jié)構(gòu)所占用的空間 D. 在最小輸入規(guī)模下算法的資源代價(jià)4. 當(dāng)上下限表達(dá)式相等時(shí)，我們使用下列（ C ）來描述算法代價(jià)？ A.大O 表示法 B.大 表示法C.表示法 D.小o表示法5.

2、 二分搜索算法是利用（A ）實(shí)現(xiàn)的算法。A.分治策略 B.動(dòng)態(tài)規(guī)劃法 C.貪心法 D.回溯法6. 下列不是動(dòng)態(tài)規(guī)劃算法基本步驟的是（A ）。A.找出最優(yōu)解的性質(zhì) B.構(gòu)造最優(yōu)解 C.算出最優(yōu)解 D.定義最優(yōu)解7. 動(dòng)態(tài)規(guī)劃算法的基本要素為（ C ）。A. 最優(yōu)子結(jié)構(gòu)性質(zhì)與貪心選擇性質(zhì)B重疊子問題性質(zhì)與貪心選擇性質(zhì)C最優(yōu)子結(jié)構(gòu)性質(zhì)與重疊子問題性質(zhì)D. 預(yù)排序與遞歸調(diào)用8. 能采用貪心算法求最優(yōu)解的問題，一般具有的重要性質(zhì)為（ A ）。A. 最優(yōu)子結(jié)構(gòu)性質(zhì)與貪心選擇性質(zhì)B重疊子問題性質(zhì)與貪心選擇性質(zhì)C最優(yōu)子結(jié)構(gòu)性質(zhì)與重疊子問題性質(zhì)D. 預(yù)排序與遞歸調(diào)用9. 備忘錄方法是那種算法的變形。（ B ）。

3、A分治法 B.動(dòng)態(tài)規(guī)劃法 C.貪心法 D.回溯法 10. 實(shí)現(xiàn)大整數(shù)乘法利用的算法是（A）。A.分治策略 B.動(dòng)態(tài)規(guī)劃法C.貪心法 D.回溯法11. 使用分治法求解不需要滿足的條件是（ A ）。A. 子問題必須是一樣的B. 子問題不能夠重復(fù)C. 子問題的解可以合并D. 原問題和子問題使用相同的方法解12. 貪心算法與動(dòng)態(tài)規(guī)劃算法的主要區(qū)別是（B ）。A.最優(yōu)子結(jié)構(gòu) B.貪心選擇性質(zhì) C.構(gòu)造最優(yōu)解 D.定義最優(yōu)解13. 實(shí)現(xiàn)最長公共子序列利用的算法是（B ）。A.分治策略B.動(dòng)態(tài)規(guī)劃法 C.貪心法 D.回溯法14. 使用二分搜索算法在1000個(gè)有序元素表中搜索一個(gè)特定元素，在最壞情況下，搜索總

4、共需要比較的次數(shù)是（ A ）。A.10 B.11 C.500 D.100015. 關(guān)于0-1背包問題以下描述正確的是（ D ）。A. 可以使用貪心算法找到最優(yōu)解B. 能找到多項(xiàng)式時(shí)間的有效算法C. 使用動(dòng)態(tài)規(guī)劃算法可求解任意0-1背包問題D. 對(duì)于同一背包與相同的物品，做背包問題取得的總價(jià)值一定大于等于做 0-1背包問題二、 填空題：(每空1分，共10分)1. 一個(gè)算法復(fù)雜性的高低體現(xiàn)在計(jì)算機(jī)運(yùn)行該算法所需的時(shí)間和存儲(chǔ)器資源上，因此算法的復(fù)雜性有 時(shí)間 復(fù)雜性和 空間 復(fù)雜性之分。2. 一個(gè)直接或間接調(diào)用自身的算法稱為 遞歸 算法。3. 出自于“平衡子問題”的思想，通常分治法在分割原問題，形成

5、若干子問題時(shí)，這些子問題的規(guī)模都大致 相等 。4. 大整數(shù)乘積算法是用 分治法 來設(shè)計(jì)的。5. 快速排序算法的性能取決于 劃分的對(duì)稱性 。6. 已知一個(gè)分治算法耗費(fèi)的計(jì)算時(shí)間T(n)，T(n)滿足如下遞歸方程：解此遞歸方程可得T(n)=O（ nlogn ）。7. 遞歸通常用 棧 來實(shí)現(xiàn)。8. 最優(yōu)二叉搜索樹即是 最小平均路長 二叉搜索樹。9. 任何可用計(jì)算機(jī)求解的問題所需的時(shí)間都與其 規(guī)模 有關(guān)。三、 簡答題：（每小題10分，共30分）1. 簡述歸動(dòng)態(tài)規(guī)劃算法的基本步驟，以及動(dòng)態(tài)規(guī)劃算法與分治法的異同。設(shè)計(jì)動(dòng)態(tài)規(guī)劃算法的主要步驟為：（4分）（1）找出最優(yōu)解的性質(zhì)，并刻劃其結(jié)構(gòu)特征。（2）遞歸地

6、定義最優(yōu)值。（3）以自底向上的方式計(jì)算出最優(yōu)值。（4）根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息，構(gòu)造最優(yōu)解。分治法與動(dòng)態(tài)規(guī)劃法的相同點(diǎn)是：將待求解的問題分解成若干個(gè)子問題，先求解子問題，然后從這些子問題的解得到原問題的解。（3分）兩者的不同點(diǎn)是：適合于用動(dòng)態(tài)規(guī)劃法求解的問題，經(jīng)分解得到的子問題往往不是互相獨(dú)立的。而用分治法求解的問題，經(jīng)分解得到的子問題往往是互相獨(dú)立的。（3分）2. 與順序查找算法相比，二分查找算法的時(shí)間復(fù)雜性有多大程度的降低？它是如何提高算法的效率的？有一個(gè)有序表為1，3，9，12，32，41，45，62，75，77，82，95，100，當(dāng)使用二分查找值為82的結(jié)點(diǎn)時(shí)，經(jīng)過多少次比較后查找

7、成功？ 答：順序查找的時(shí)間是O(n)，折半查找O(log n) 降低了一個(gè)數(shù)量級(jí)。采用分治策略，每一次比較可以排除一半的數(shù)據(jù)。共需要比較4次才能找到82.3. 簡述歸并排序算法和快速排序算法的分治方法。并對(duì)下列實(shí)例數(shù)據(jù)A=(38,27,55,50,13,49,65)排序，寫出采用快速排序算法，數(shù)組A第一次被分割的過程。答：歸并排序的分治是將數(shù)組從中間分開，分別對(duì)前后來那個(gè)部分進(jìn)行排序，將排序后的兩個(gè)數(shù)組合并成整個(gè)數(shù)組的排序。這樣分治為遞歸過程，直到一個(gè)元素時(shí)返回。快速排序的分治是選取分割元素，以分割元素為界，將數(shù)組分成兩部分，一部分小于分割元素，一部分大于分割元素，分別對(duì)兩部分排序。數(shù)組A第一

8、次被分割的過程如下：38 27 55 50 13 49 6513 27 55 50 38 49 6513 7 38 50 55 49 65四、 算法分析題：（每題10分，共30分）1. 有16個(gè)選手參加循環(huán)賽，循環(huán)賽一共進(jìn)行15天，每個(gè)選手必須與其他的 15個(gè)選手各賽一場，每個(gè)選手一天只比賽一次；設(shè)計(jì)一個(gè)滿足上述要求的比賽日程表，并簡述采用的算法基本思路。 2. 對(duì)于矩陣連乘所需最少數(shù)乘次數(shù)問題，其遞歸關(guān)系式為：其中mi,j為計(jì)算矩陣連乘AiAj所需的最少數(shù)乘次數(shù)，pi-1為矩陣Ai的行，pi為矩陣的列。現(xiàn)有四個(gè)矩陣，其中各矩陣位數(shù)分別為：A1A2A3A4501010404030305p0p1

9、p1p2P2p3p3p4(1) 在這個(gè)四矩陣連乘積問題中，請(qǐng)問不同子問題的個(gè)數(shù)總共有多少個(gè)？并請(qǐng)把所有的子問題列出來。(2) 請(qǐng)根據(jù)以上的遞歸關(guān)系，計(jì)算出矩陣連乘積A1A2A3A4所需要的最少數(shù)乘次數(shù)。要求寫出求解過程，并將結(jié)果填入m44。3. 請(qǐng)用動(dòng)態(tài)規(guī)劃解下列0-1背包問題，寫出遞歸式及求解過程。共有4個(gè)物品，背包重量C=5，下表中列出每個(gè)物品的重量和價(jià)值。物品重量（公斤）價(jià)值（美元）12122110332142152013-2014學(xué)年第1學(xué)期算法分析期中參考答案一、選擇題：(每題2分，共30分)1 C2 C3 B4 C5 A6 A7 C8 A9 B10 A11 A12 B13 B14

10、A15 D二、填空題：(每空1分，共10分)1 時(shí)間2 空間3 遞歸4 相等5 分治法6 劃分的對(duì)稱性7 nlogn8 棧9 最小平均路長（或最小搜索代價(jià)）10 規(guī)模三、簡答題：（每題10分，共30分）1. 答：設(shè)計(jì)動(dòng)態(tài)規(guī)劃算法的主要步驟為：（4分）（1）找出最優(yōu)解的性質(zhì)，并刻劃其結(jié)構(gòu)特征。（2）遞歸地定義最優(yōu)值。（3）以自底向上的方式計(jì)算出最優(yōu)值。（4）根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息，構(gòu)造最優(yōu)解。分治法與動(dòng)態(tài)規(guī)劃法的相同點(diǎn)是：將待求解的問題分解成若干個(gè)子問題，先求解子問題，然后從這些子問題的解得到原問題的解。（3分）兩者的不同點(diǎn)是：適合于用動(dòng)態(tài)規(guī)劃法求解的問題，經(jīng)分解得到的子問題往往不是互相獨(dú)立

11、的。而用分治法求解的問題，經(jīng)分解得到的子問題往往是互相獨(dú)立的。（3分）2. 答：順序查找的時(shí)間是O(n)，折半查找O(log n) 降低了一個(gè)數(shù)量級(jí)。采用分治策略，每一次比較可以排除一半的數(shù)據(jù)。共需要比較4次才能找到82.3. 答：歸并排序的分治是將數(shù)組從中間分開，分別對(duì)前后來那個(gè)部分進(jìn)行排序，將排序后的兩個(gè)數(shù)組合并成整個(gè)數(shù)組的排序。這樣分治為遞歸過程，直到一個(gè)元素時(shí)返回。快速排序的分治是選取分割元素，以分割元素為界，將數(shù)組分成兩部分，一部分小于分割元素，一部分大于分割元素，分別對(duì)兩部分排序。數(shù)組A第一次被分割的過程如下：38 27 55 50 13 49 6513 27 55 50 38 4

12、9 6513 7 38 50 55 49 65四、算法分析題：（每題10分，共30分）1. 答：可采用分治策略，將所有的選手分為兩半，n個(gè)選手的比賽日程表就可以通過為n/2個(gè)選手設(shè)計(jì)的比賽日程表來決定。遞歸地用一分為二的策略對(duì)選手進(jìn)行分割，直到只剩下2個(gè)選手時(shí)，比賽日程表的制定就變得很簡單。這時(shí)只要讓這2個(gè)選手進(jìn)行比賽就可以了。設(shè)計(jì)的比賽日程表如下所示：天數(shù) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15123456789101112131415162143658710912111413161534127856111291015161314432187651211109

13、161514135678123413141516910111265872143141316151091211785634121516131411129108765432116151413121110991011121314151612345678109121114131615214365871112910151613143412785612111091615141343218765131415169101112567812341413161510912116587214315161314111291078563412161514131211109876543212. 答：（1）共有10個(gè)子問題。 n+C(n,2)個(gè)A1,A2,A3,A4 4個(gè)A1A2, A2A3, A3A4 A1A2A3，A2A3A4A1A2A3A4A5（2）最少數(shù)乘次數(shù)即m1,4=1050