北京大學算法設計與分析報告報告材料課09年期末試的題目

1、實用標準文案 北京大學信息科學技術學院考試試卷 考試科目：算法設計與分析姓名：學號: 考試時間：2009年6月9日 任課教師： 裝 訂 線 內 題號 一 二 三 四 五 六 七 八 總分 分數(shù) 閱卷人 精彩文檔 不 要 答 題 考場紀律 1 .請持學生證入場考試，并按指定座位就座；除必要的文具和教師指定的用 具用書外，其他所有物品包括手機、呼機、MP3、電子詞典、書籍、筆記、 紙張等嚴禁帶入座位，必須放在指定位置。凡有試題印制問題請向監(jiān)考教 師提出，不得向其他考生詢問。 2 .認真、誠實、獨立并在規(guī)定時間內完成答卷，嚴禁任何形式的違紀作弊行 為；否則，本答卷成績以 0分記，并根據(jù)北京大學本科考

2、試工作與學術 規(guī)范條例給予紀律處分。 3 .提前交卷的考生不要在考場逗留，不要在門口、窗外大聲喧嘩。考試結束 時間到，請停止答卷，在座位等候監(jiān)考教師收卷并清點完畢，方可離開考 場；考題和試卷不得帶出考場。 以下為試題和答題紙，共9 頁 一、填空題（選做5道，10分） 1 . 用矩陣冪的方法求斐波那契數(shù)，其運行時間為（ ）。 2 . 對于一個可以用動態(tài)規(guī)劃法求解的問題，要求問題既要滿足 （）的特性，又要具有大量的（ ）。 3. 對于一個可以用貪心法求解的問題，不僅要求問題滿足 （）的特性，還應證明其貪心策略的（） 4. 設有n個棧操作（PUSH、POP、MULTIPOP ）的序列，作用于初始為

3、空的棧S。不區(qū)分三種操作，則每個操作的最壞運行時間為 （），平攤運行時間為（）。 5. 三種平攤分析的方法分別為（ ）、（）、 （） 6. 四后問題的搜索空間為（）樹；0-1背包問題的搜索空間 為（）樹；巡回售貨員問題的搜索空間為（ ） 樹。 7 .（）法的求解目標是找出解空間樹中滿足約束條件的所 有解，而（）法的求解目標則是找出滿足約束條件的 一個解，或是在滿足約束條件的解中找出在某種意義下的最優(yōu)解。 8.回溯法一般以（ ）優(yōu)先的方式搜索解空間樹， 而分支限界法則一般以（ ）優(yōu)先或以最小耗費優(yōu)先的方 式搜索解空間樹。 、單項選擇題(10分) 1. 下列關于排序算法的敘述，不正確的是？ ( )

4、 A 堆排序的最差情形運行時間為(n lg n) B) 快速排序平均情形運行時間為(n lg n) C) 任何排序算法的最差情形運行時間都不可能比Q (nlg n)更小 D) 插入排序在最好情形下的運行時間為(n) 裝 訂 線 內 2. 對于課堂講解的線性時間內找第 i小的元素的算法， () 下列敘述中不正確的是？ A) 算法第一步中可以按每五個元素一組找中位數(shù)； B) 算法第一步中可以按每七個元素一組找中位數(shù)； B) 算法第一步中不能按每三個元素一組找中位數(shù)； D)如果要求的n個元素的中位數(shù)，則中位數(shù)一定是第一步中找到的中 不 要 答 題 位數(shù)中的某一個。 3. 主方法可以求解滿足形如下式的

5、遞推方程，() T(n) = aT (?) + f(n) 門則下列關于方程中的約束中不準確的是？ A) 對于系數(shù)a，必須滿足a 1 B) 對于系數(shù)b，必須滿足b 1 C) 若對于常數(shù) 0 , f(n)=0(nlogba-9，則 T(n)= (nlog ba) D) 若 f(n)= O(nlog ba)，則 T(n)= (nlog balog n) 4 .下列哪些問題不能用貪心法求解？ ( ) A)霍夫曼編碼冋題 B) 單源最短路徑問題 C) 0-1背包問題 D) 最小生成樹問題 5. 可合并堆上可以不包含下列哪個操作? B) UNI0N( H1, H2) A) DECREASE-KEY( H,

6、 x, k) C) INSERT(H, x) D) EXTRACT-MIN( H) 6. 不同堆上插入操作最差情形下的開銷或平攤開銷，() 對二叉堆、二項堆和斐波那契堆，下列選項中描述錯誤的是？ A) 二叉堆為 (lg n)B) 二項堆為 O(lg n) C) 斐波那契堆為 (1)D)三種堆的開銷都是 (lg n) 關于網(wǎng)絡流的割，下列選項中錯誤的是？( 割(S,T)是流網(wǎng)絡G=(V,E)的一個劃分，其中s S, t T。如果 ) f是G上 c(S,T)。 的流，那么流經割的凈流量為 f(S,T)，割(S,T)上的容量定義為 A) I f I 宅(S, T) C) f(s, V-s) = |

7、f | B) f(S, T) = | f | D) f(S-s, V) = | f | 8. 下列隨機算法一定有解但解不一定正確的是？( A) SherwoodB) LasVegas C) MonteCarloD)三者都不是 在快速排序算法中引入隨機過程的主要目的是什么？( A) 改善確定性算法的平均運行時間 B) 保證算法總能在O(n lg n)時間內結束 C) 避免了算法最壞情況下的發(fā)生 D) 改善了確定性算法最壞情形下的平均運行時間 10 . 用Monte Carlo方法估計四后問題回溯算法的效率。( 五次實驗結果分別為 1,4,2、 2,4,1,3 則解空間中的結點數(shù)估計為？ 、4,2

8、、 3,1,4,2、1,3 ， D) 16.5 A) 16B) 16.2C) 17 裝 訂 線 內 不 要 答 題 三、社會名流（20分） 在n個人中，一個被所有人知道但卻不知道別人的人，被定義為社會名流。 現(xiàn)在的問題是如果存在，試找出該社會名流。你可以使用的唯一方式是詢問： “請問你知道那個人嗎？ ”請給出提問次數(shù)為O（n）的算法，寫出偽代碼，分析 算法的正確性，并給出算法運行時間的精確分析（即O（n）中隱藏的系數(shù)）。 （提示：當你問 A是否認識B時，如果A認識B,則A不是社會名流； 如果A不認識B,則B不是社會名流） 四、地板覆蓋（20分） 用2*1的地板塊覆蓋 3*n的地面有多少種方案？

9、如下圖是一個覆蓋的例 子，函數(shù)fn可用于求解這個問題，請說明fn算法的正確性，并說明算法運行 時間的上界和下界。 int fn (i nt n) 裝 訂 線 內 if (n % 2 = 1) return 0; in t f = new in t n+1; f0 = 1； for (i nt i = 2; i = 0; j -= 2) 不 要 答 題 fi += fj*2; return fn; 五、田忌賽馬 （20分） 你一定聽過田忌賽馬的故事吧？如果3匹馬變成n匹，齊王仍然讓他的馬 按從優(yōu)到劣的順序出賽，田忌可以按任意順序選擇他的賽馬出賽。贏一局，田 忌可以得到200兩銀子，輸一局，田忌就

10、要輸?shù)?00兩銀子。已知國王和田 忌的所有馬的奔跑速度，并且所有馬奔跑的速度均不相同，現(xiàn)已經對兩人的馬 分別從快到慢排好序，請設計一個算法，幫助田忌贏得最多的銀子。寫出偽代 碼，證明算法的正確性，并分析算法的復雜度。 裝 訂 線 內 （提示：可以設計一個貪心策略的算法，面對國王每匹順序出場的馬，女口 果田忌的馬快，就派最快的出場；否則派最慢的馬出場） 不 要 答 題 六、（20分）給出n項作業(yè)Ji, J2.Jn ,對應每項作業(yè)有一個運行時間 ti，在m 個處理器上調度這些作業(yè)，使完成的時間最小。完成的時間定義為在所有的處 理器中運行時間最長的處理器運行的時間。采用如下的近似算法：即，按照原 始給定的作業(yè)順序：