1、內部資料，轉載請注明出處，謝謝合作北京大學信息科學技術學院考試試卷考試科目：算法設計與分析 姓名： 學號： 考試時間：2009年6月9日 任課教師：題號一二三四五六七八總分分數閱卷人考場紀律1. 請持學生證入場考試，并按指定座位就座；除必要的文具和教師指定的用具用書外，其他所有物品包括手機、呼機、 MP3電子詞典、書籍、筆記、 紙張等嚴禁帶入座位，必須放在指定位置。凡有試題印制問題請向監考教 師提出，不得向其他考生詢問。2. 認真、誠實、獨立并在規定時間內完成答卷，嚴禁任何形式的違紀作弊行為；否則，本答卷成績以 0分記，并根據北京大學本科考試工作與學術 規范條例給予紀律處分。3. 提前交卷的考

2、生不要在考場逗留，不要在門口、窗外大聲喧嘩。考試結束 時間到，請停止答卷，在座位等候監考教師收卷并清點完畢，方可離開考 場；考題和試卷不得帶出考場 。以下為試題和答題紙，共9 頁。、填空題（選做5道，10分）1. 用矩陣冪的方法求斐波那契數，其運行時間為（ ）。2. 對于一個可以用動態規劃法求解的問題，要求問題既要滿足（）的特性，又要具有大量的（ ）3. 對于一個可以用貪心法求解的問題，不僅要求問題滿足（）的特性，還應證明其貪心策略的（）4. 設有n個棧操作（PUSH、POP、MULTIPOP ）的序列，作用于初始為空的棧S。不區分三種操作，則每個操作的最壞運行時間為 （）,平攤運行時間為（）

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

4、)C) 任何排序算法的最差情形運行時間都不可能比Q (nlgn)更小D) 插入排序在最好情形下的運行時間為O (n)2. 對于課堂講解的線性時間內找第i小的元素的算法， ()下列敘述中不正確的是？A) 算法第一步中可以按每五個元素一組找中位數；B) 算法第一步中可以按每七個元素一組找中位數；裝訂線內B) 算法第一步中不能按每三個元素一組找中位數；D)如果要求的n個元素的中位數，則中位數一定是第一步中找到的中 位數中的某一個。3. 主方法可以求解滿足形如下式的遞推方程，()= aT 住)+ f(n)則下列關于方程中的約束中不準確的是？A) 對于系數a,必須滿足a 1B) 對于系數b,必須滿足b

5、1C) 若對于常數 0, f(n)=O(nlogba-)，則 T(n)=対喈)D) 若 f(n)=O(nlogba),則 T(n)= O(nlogbalogn)4. 下列哪些問題不能用貪心法求解？()A) 霍夫曼編碼問題B)單源最短路徑問題C) 0-1背包問題D)最小生成樹問題5 可合并堆上可以不包含下列哪個操作？A) DECREASE-KEY( H, x, k) B) UNION( H1, H2)C) INSERT( H , x)D) EXTRACT-MIN( H)6 不同堆上插入操作最差情形下的開銷或平攤開銷， ( ) 對二叉堆、二項堆和斐波那契堆，下列選項中描述錯誤的是？A)二叉堆為O

6、( n)B) 二項堆為 O(lg n)C)斐波那契堆為O (1)D) 三種堆的開銷都是O(lg n)7 關于網絡流的割，下列選項中錯誤的是？割(S,T)是流網絡 G=(V,E)的一個劃分，其中s S, t T。如果f是G上的 流，那么流經割的凈流量為f(S,T),割(S,T)上的容量定義為c(S,T)。A) I f| S, T)C) f(s, V-s) = | f |B) f(S, T) = | f |D) f(S-s, V) = | f |8 下列隨機算法一定有解但解不一定正確的是？()A) SherwoodB) LasVegasC) MonteCarloD) 三者都不是9 在快速排序算法中

7、引入隨機過程的主要目的是什么？ ()A) 改善確定性算法的平均運行時間B) 保證算法總能在 O(nlgn)時間內結束C) 避免了算法最壞情況下的發生D) 改善了確定性算法最壞情形下的平均運行時間10用 Monte Carlo 方法估計四后問題回溯算法的效率。()五次實驗結果分別為 1,4,2、 2,4,1,3、4,2、 3,1,4,2、1,3，則 解空間中的結點數估計為？A) 16B) 16.2 C) 17D) 16.5裝訂線內三、社會名流（20分）在n個人中，一個被所有人知道但卻不知道別人的人，被定義為社會名流。現在的問題是如果存在，試找出該社會名流。你可以使用的唯一方式是詢問：“請問你知道

8、那個人嗎？ ”請給出提問次數為O（n）的算法，寫出偽代碼，分析算法的正確性，并給出算法運行時間的精確分析（即O（n）中隱藏的系數）。（提示：當你問 A是否認識B時，如果A認識B,則A不是社會名流；如 果A不認識B,則B不是社會名流）四、地板覆蓋（20分）用2*1的地板塊覆蓋3*n的地面有多少種方案？如下圖是一個覆蓋的例子， 函數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;

9、j -= 2) fi += fj*2;return fn;不要答題五、田忌賽馬 （20分）你一定聽過田忌賽馬的故事吧？如果 3匹馬變成n匹，齊王仍然讓他的馬 按從優到劣的順序出賽，田忌可以按任意順序選擇他的賽馬出賽。贏一局，田 忌可以得到200兩銀子，輸一局，田忌就要輸掉 200兩銀子。已知國王和田忌 的所有馬的奔跑速度，并且所有馬奔跑的速度均不相同，現已經對兩人的馬分 別從快到慢排好序，請設計一個算法，幫助田忌贏得最多的銀子。 寫出偽代碼, 證明算法的正確性，并分析算法的復雜度。（提示：可以設計一個貪心策略的算法，面對國王每匹順序出場的馬，女口 果田忌的馬快，就派最快的出場；否則派最慢的馬出場）裝訂線內六、（20分）給出n項作業JJz-Jn，對應每項作業有一個運行時間 ti，在m個處理器上調度這些作業，使完成的時間最小。完成的時間定義為在所有的處 理器中運行時間最長的處理器運行的時間。采用如下的近似算法：即，按照原始給定的