1、2008學年第一學期考試類型：(閉卷)華南農業大學期末考試試卷(A卷)考試科目： 算法分析與設計考試時間： 120分鐘學號 姓名 年級專業題號一二三四總分得分評閱人、選擇題(20分，每題2分)1. 下述表達不正確的是 。A. n2/2 + 2n的漸進表達式上界函數是O(2n)B. n2/2 + 2n的漸進表達式下界函數是Q(2n)C. logn3的漸進表達式上界函數是O(logn)D. logn3的漸進表達式下界函數是Q(n3)2 .當輸入規模為n時，算法增長率最大的是 。A. 5n B. 2010g2nC. 2n2D. 3nlog3n3 . T (n)表示當輸入規模為n時的算法效率，以下算法

2、效率最優的是 。A. T (n) = T (n -1) +1, T (1) =1B. T (n) = 2n2C. T (n) = T (n/2) +1, T (1) =1D . T (n) = 3n1og2n4.在棋盤覆蓋問題中，對于2kx 2k的特殊棋盤(有一個特殊方塊)，所需的L型骨牌的個數是。A. (4k -1) /3B. 2k /3C. 4k D. 2k 5.在尋找n個元素中第k小元素問題中，若使用快速排序算法思想，運用分治算法對n個元素進行劃分，應如何選擇劃分基準？下面 答案解釋最合理。A.隨機選擇一個元素作為劃分基準B.取子序列的第一個元素作為劃分基準C.用中位數的中位數方法尋找劃

3、分基準D.以上皆可行。但不同方法，算法復雜度上界可能不同6.有9個村莊，其坐標位置如下表所示:i123456789x(i)123456789y123456789現在要蓋一所郵局為這 9個村莊服務，請問郵局應該蓋在 才能使到郵局到這 9個村莊的總距離和最短。A. (4.5, 0)B. (4.5, 4.5)C. (5, 5)D. (5, 0)7 . n個人拎著水桶在一個水龍頭前面排隊打水，水桶有大有小，水桶必須打滿水， 水流恒定。如下 說法不正確？A.讓水桶大的人先打水，可以使得每個人排隊時間之和最小8 .讓水桶小的人先打水，可以使得每個人排隊時間之和最小C.讓水桶小的人先打水，在某個確定的時間t

4、內，可以讓盡可能多的人打上水D.若要在盡可能短的時間內，n個人都打完水，按照什么順序其實都一樣8 .分治法的設計思想是將一個難以直接解決的大問題分割成規模較小的子問題，分 別解決子問題，最后將子問題的解組合起來形成原問題的解。這要求原問題和子 問題。A.問題規模相同，問題性質相同B.問題規模相同，問題性質不同C.問題規模不同，問題性質相同D.問題規模不同，問題性質不同9 .對布線問題，以下是不正確描述。A.布線問題的解空間是一個圖B.可以對方格陣列四周設置圍墻，即增設標記的附加方格的預處理，使得算法簡化 對邊界的判定C.采用廣度優先的標號法找到從起點到終點的布線方案(這個方案如果存在的話)不一

5、定是最短的D.采用先入先出的隊列作為活結點表，以終點b為擴展結點或活結點隊列為空作為算法結束條件10.對于含有n個元素的子集樹問題，最壞情況下其解空間的葉結點數目為 nA. n!B. 2nC. 2n+1-1D.n!/i!i 1答案：DACAD CACCB二、填空題(10分，每題2分)1、一個算法復雜性的高低體現在計算機運行該算法所需的時間和存儲器資源上，因此算法的復雜性有時間 復雜性和空間復雜性之分。2、出自于“平衡子問題”的思想，通常分治法在分割原問題，形成若干子問題時，這些子問題的規模都大致 相同 。3、使用二分搜索算法在 n個有序元素表中搜索一個特定元素，在最佳情況下，搜索的時間復雜性為

6、O ( 1 ),在最壞情況下，搜索的時間復雜性為O ( logn )。4、已知一個分治算法耗費的計算時間T(n), T(n)滿足如下遞歸方程：T(n)O(1)n 22T(n/2) O(n) n 2解得此遞歸方可得T(n)= O ( nlogn )。5、動態規劃算法有一個變形方法備忘錄方法。這種方法不同于動態規劃算法 “自底向上”的填充方向，而是“自頂向下”的遞歸方向，為每個解過的子問題建立了備忘 錄以備需要時查看，同樣也可避免相同子問題的重復求解。參考解答：1、時間2、相同3、1 logn 4、nlog n 5、備忘錄方法三、簡答題(40分，每題8分)1、(8分)寫出下列復雜性函數的偏序關系(

7、即按照漸進階從低到高排序)：2n 3n log n n! n log n n2 nn 103參考解答：103 p log n p nlog n p n2 p 2np 3n p n! p nn2、(8分)現在有8位運動員要進行網球循環賽，要設計一個滿足以下要求的比賽日 程表：(1) 每個選手必須與其他選手各賽一次;(2) 每個選手一天只能賽一次；(3) 循環賽一共進行 n -1天。請利用分治法的思想，給這 8位運動員設計一個合理的比賽日程。 參考解答：12342143341243215678658778568765567865877856876512342143341243213、(8分)某體育

8、館有一羽毛球場出租，現在總共有10位客戶申請租用此羽毛球場，每個客戶所租用的時間單元如下表所示，s(i)表示開始租用時刻，f(i)表示結束租用時刻，10個客戶的申請如下表所示：i12345678910s(i)03153511886f(i)65498713121110同一時刻，該羽毛球場只能租借給一位客戶，請設計一個租用安排方案，在這 10位客戶里面，使得體育館能盡可能滿足多位客戶的需求，并算出針對上表的10個客戶申請，最多可以安排幾位客戶申請。參考解答：將這10位客戶的申請按照結束時間f(i)遞增排序，如下表：i12345678910s(i(i)45678910111

9、2131)選擇申請1 (1,4)2)依次檢查后續客戶申請，只要與已選擇的申請相容不沖突，則選擇該申請。直到所有申請檢查完畢。申請 4(5,7)、申請8 (8,11)、申請10(11,13)3)最后，可以滿足：申請 1 (1,4 )、申請4 (5,7 )、申請8 (8,11 )、申請10 (11,13 ) 共4個客戶申請。這已經是可以滿足的最大客戶人數。4、(8分)對于矩陣連乘所需最少數乘次數問題，其遞歸關系式為:mi, jminmi,k mk 1,j PiiPkPj i j i k j其中mi, j為計算矩陣連乘 AiAj所需的最少數乘次數，Pi-i為矩陣Ai的行，pi為矩陣Ai的列。現有四個

10、矩陣，其中各矩陣維數分別為：A1A2A3A450 1010 4040 3030 5p 0 p 1P 1 P 2P 2 p 3P 3 p 4請根據以上的遞歸關系，計算出矩陣連乘積A iA2 A3A 4所需要的最少數乘次數。參考解答：m11 m24 P0P1P4 0 8000 50 10 5 10500 m14 min m12 m34p0 p2 P4 20000 6000 50 40 5 36000m13 m44P0P3 P4 27000 0 50 30 5 34500105005、（8分）有這樣一類特殊 0-1背包問題：可選物品 重量越輕的物品價值越高。n=6, c=20, P= （4, 8,

11、15, 1 , 6, 3）, W= （5, 3, 2, 10, 4, 8）。其中n為物品個數，c為背包載重量，P表示物品白價值， W表示物品的重量。請問對于此0-1背包問題，應如何選擇放進去的物品，才能使到放進背包的物品總價值最大，能獲得的最大總價值多少？參考解答：因為該01背包問題比較特殊，恰好重量越輕的物品價值越高，所以優先取重量輕的物品放進背包。最終可以把重量分別為 2, 3,4,5的三個物品放進背包,得到的價值和為15 + 8 + 6 + 4 = 33,為最大值。四、算法設計題（30分，前三題每題8分，最后一題6分）1、【最優服務次序問題】（8分）一一提示：此題可采用貪心算法實現問題描

12、述：設有n個顧客同時等待一項服務， 顧客i需要的服務時間為ti, 1=i1時，格雷碼的長度為 2n,即共有2n個碼序列。此時，將問題一分為二，即上半部分和下半部分。上半部分最高位設為0，下半部分最高位設為1。 剩下 n-1 位的格雷碼的構造采用遞歸的思路。評分準則：4) 答到使用分治算法，并且推導出分治算法的過程，邊界設定清晰(即當僅輸出 1 位的格雷碼如何處理)，本題即可得滿分；5) 說明使用分治算法，但漏邊界條件，扣2 分以上；6) 其它情況酌情考慮。3、 【最長上升子序列問題】( 8 分) 提示：此題可采用動態規劃算法實現對于給定的一個序列(a1, a2,L ,aN )， 1 N 100

13、0。我們可以得到一些遞增上升的子序列(ai1,ai2,L ,aiK)， 這里 1 i1 i2 L iK N 。 比如， 對于序列(1, 7, 3, 5,9, 4, 8)， 有它的一些上升子序列，如 (1, 7), (3, 4, 8)等等。 這些子序列中最長的長度是4，比如子序列(1,3, 5, 8)。你的任務：就是對于給定的序列，求出最長上升子序列的長度。要求寫出你設計的算法思想及遞推函數的公式表達。參考解答：設f(i)表示：從左向右掃描過來直到以ai元素結尾的序列，獲得的最長上升子序列的長度，且子序列包含ai元素(1 i n)。1i 1f(i) maxf(j) 1:當 ai aj;1 j i

14、 i 11 i 1; j (1 j i),都有 ai aj即，f (i)是從f(1), f(2)到f(i 1)中找最大的一個值，再加1。或者就是1。主要是看ai這個元素能否加入到之前已經獲得的最長上升子序列，如果能加 入，是之前已獲得的最長上升子序列長度加一；如果不能加入，就取這最后一個元素 作為一個單獨子序列，長度為 1。最后，所要求的整個序列的最長公共子序列長度為maxf(i): 1=i=n例如，對于序列：4 2 6 3 1 5 2i1234567array4263152f(i)1122132評分準則：1)答到使用動態規劃算法，并且推導出動態規劃算法的遞推函數公式表達，邊 界設定清晰，本題

15、即可得滿分；(閱卷時仔細看遞推公式表達，公式表達含義正確即可，因其表達形式可能不唯一)2) 說明使用動態規劃算法，但對遞推函數表達錯誤或含糊，扣2分以上；3)其它情況酌情考慮。4、【騎士問題】(6分)一一提示：此題可采用廣度優先搜索算法實現 在一個標準8X8的國際象棋棋盤上，棋盤中有些格子是可能有障礙物的。已知騎 士的初始位置和目標位置，你的任務是計算出騎士最少需要多少步可以從初始位置到 達目標位置，若無法到達目標位置，輸出“ not reachable”。請用文字或偽代碼說明你 的算法。注意：騎士只能進行“日”字行對角跳，棋盤上有障礙物的格子不能到達。9 / 9圖（a） ：騎士能進行的“日”

16、字行對角跳， n 為騎士當前位置，x 為騎士下一步可以跳到的格子圖（b）:騎士從初始位置 n到目標位置N,最小需要7步的實例。b為棋盤障礙參考解答：這也是一個搜索的題目，非常類似于書上的“布線問題”，可參考書上此例。用一個二維數組board1212 來記錄棋盤的狀況。為何大小是12*12 呢？棋盤大小8*8 ，為了減少對周圍邊界的判斷，在上下左右四邊各加上2 行 2 列做“圍墻”（障礙） ，因此 board 棋盤的大小12*12。有如下幾個步驟需要解決：1) 障礙格子：將輸入的障礙格子填寫到board 當中對應格上，設置為-1 ；2) 起始格子和結束格子：將起始點start和結束點end,這兩個點記錄下來，在 board 中這兩個格子設置為0；3) 圍墻： 在 8*8 的棋盤外面，上下左右各加2 行 2 列做圍墻，圍墻和障礙一樣，設置為 -1 ；4) 除障礙圍墻起始結束格子這些格子特殊對待輸入之外，其余格子全部初始化為0；5) 隊列初始為空。隊列是用來在騎士做 “日字型”對角跳的時候，候選位置放入隊列中的一個輔助的數據結構，以便于“廣度優先搜索”。6) 從起點開始，將這個位置所能跳的周圍8 個位置都檢查一下：只要未標記，就標記為前一個位置值加1 ，并將該格子