2009.1算法設(shè)計與分析課程期末試卷-A卷(自測)課案

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

2、n-1)+1,T(1)=1B.T(n)=2n2C.T(n)=T(n/2)+1，T(1)=1D.T(n)=3nlog2n4. 在棋盤覆蓋問題中，對于2kX2k的特殊棋盤(有一個特殊方塊)，所需的L型骨牌的個數(shù)是。A.(4k1)/3B.2k/3C.4kD.2k5. 在尋找n個元素中第k小元素問題中，若使用快速排序算法思想，運用分治算法對n個元素進行劃分，應(yīng)如何選擇劃分基準？下面答案解釋最合理。A. 隨機選擇一個元素作為劃分基準B. 取子序列的第一個元素作為劃分基準C. 用中位數(shù)的中位數(shù)方法尋找劃分基準D. 以上皆可行。但不同方法，算法復(fù)雜度上界可能不同6.有9個村莊，其坐標位置如下表所示：i123

3、456789x(i)123456789y(i)123456789現(xiàn)在要蓋一所郵局為這9個村莊服務(wù)，請問郵局應(yīng)該蓋在能使到郵局到這9個村莊的總距離和最短。A（4.5，0）B（4.5，4.5）C（5，5）D（5，0）7. n個人拎著水桶在一個水龍頭前面排隊打水，水桶有大有小，水桶必須打滿水，水流恒定。如下說法不正確？A. 讓水桶大的人先打水，可以使得每個人排隊時間之和最小B. 讓水桶小的人先打水，可以使得每個人排隊時間之和最小C. 讓水桶小的人先打水，在某個確定的時間t內(nèi)，可以讓盡可能多的人打上水D. 若要在盡可能短的時間內(nèi)，n個人都打完水，按照什么順序其實都一樣8. 分治法的設(shè)計思想是將一個難以

4、直接解決的大問題分割成規(guī)模較小的子問題，分別解決子問題，最后將子問題的解組合起來形成原問題的解。這要求原問題和子問題。A. 問題規(guī)模相同，問題性質(zhì)相同B.問題規(guī)模相同，問題性質(zhì)不同C.問題規(guī)模不同，問題性質(zhì)相同D.問題規(guī)模不同，問題性質(zhì)不同9. 對布線問題，以下是不正確描述。A. 布線問題的解空間是一個圖B. 可以對方格陣列四周設(shè)置圍墻，即增設(shè)標記的附加方格的預(yù)處理，使得算法簡化對邊界的判定C. 采用廣度優(yōu)先的標號法找到從起點到終點的布線方案（這個方案如果存在的話）不一定是最短的D. 采用先入先出的隊列作為活結(jié)點表，以終點b為擴展結(jié)點或活結(jié)點隊列為空作為算法結(jié)束條件10. 對于含有n個元素的子

5、集樹問題，最壞情況下其解空間的葉結(jié)點數(shù)目為。A.n!B.2nC.2皿1D.n!/i!i=1答案：DACADCACCB二、填空題（10分，每題2分）1、一個算法復(fù)雜性的高低體現(xiàn)在計算機運行該算法所需的時間和存儲器資源上，因此算法的復(fù)雜性有時迴復(fù)雜性和空間復(fù)雜性之分。2、出自于“平衡子問題”的思想，通常分治法在分割原問題，形成若干子問題時，這些子問題的規(guī)模都大致相同_。3、使用二分搜索算法在n個有序元素表中搜索一個特定元素，在最佳情況下，搜索的時間復(fù)雜性為O（丄），在最壞情況下，搜索的時間復(fù)雜性為O（logn）。4、已知一個分治算法耗費的計算時間T（n）,T（n）滿足如下遞歸方程：O(1)n<

6、;22T(n/2)+O(n)n>2解得此遞歸方可得T（n）=O（nlogn）。5、動態(tài)規(guī)劃算法有一個變形方法備忘錄方法。這種方法不同于動態(tài)規(guī)劃算法“自底向上”的填充方向，而是“自頂向下”的遞歸方向，為每個解過的子問題建立了備忘錄以備需要時查看，同樣也可避免相同子問題的重復(fù)求解。參考解答：1、時間2、相同3、1logn4、nlogn5、備忘錄方法三、簡答題（40分，每題8分）1、（8分）寫出下列復(fù)雜性函數(shù)的偏序關(guān)系（即按照漸進階從低到高排序）：2n3nlognn!nlognn2nn103參考解答：103lognnlognn22n3nn!nnYYYYYYY2、（8分）現(xiàn)在有8位運動員要進行網(wǎng)

7、球循環(huán)賽，要設(shè)計一個滿足以下要求的比賽日程表：（1）每個選手必須與其他選手各賽一次；（2）每個選手一天只能賽一次；（3）循環(huán)賽一共進行n-1天。請利用分治法的思想，給這8位運動員設(shè)計一個合理的比賽日程參考解答：12345678214365873412785643218765567812346587214378563412876543213、（8分）某體育館有一羽毛球場出租，現(xiàn)在總共有10位客戶申請租用此羽毛球場，每個客戶所租用的時間單元如下表所示，s（i）表示開始租用時刻，f（i）表示結(jié)束租用時刻，10個客戶的申請如下表所示：i12345678910s(i)03153511886f(i)654

8、98713121110同一時刻，該羽毛球場只能租借給一位客戶，請設(shè)計一個租用安排方案，在這10位客戶里面，使得體育館能盡可能滿足多位客戶的需求，并算出針對上表的10個客戶申請，最多可以安排幾位客戶申請。參考解答：將這10位客戶的申請按照結(jié)束時間f（i）遞增排序，如下表：i12345678910s(i(i)456789101112131）選擇申請1（1,4）2）依次檢查后續(xù)客戶申請，只要與已選擇的申請相容不沖突，則選擇該申請。直到所有申請檢查完畢。申請4（5,7）、申請8（8,11）、申請10（11,13）3）最后，可以滿足：申請1（1,4）、申請4（5,7）、申請8（

9、8,11）、申請10（11,13）共4個客戶申請。這已經(jīng)是可以滿足的最大客戶人數(shù)。4、（8分）對于矩陣連乘所需最少數(shù)乘次數(shù)問題，其遞歸關(guān)系式為：J0i=jmi,刀'minmi,k+mk+1,j+pppi<jIi<k<jIkj其中mi,j為計算矩陣連乘AiAj所需的最少數(shù)乘次數(shù)，環(huán)為矩陣Ai的行，P.為矩陣Ai的列。現(xiàn)有四個矩陣，其中各矩陣維數(shù)分別為：A1AA3A450x1010x4040x3030x5P0xP.P/P2P2xP3P/P4請根據(jù)以上的遞歸關(guān)系，計算出矩陣連乘積axa2a3a4所需要的最少數(shù)乘次數(shù)。參考解答：'m11>m24+ppp二0+80

10、00+50x10x5二10500J014ml4=minm12+m34+ppp=20000+6000+50x40x5=36000024m13+m44+ppp二27000+0+50x30x5二34500034二105005、（8分）有這樣一類特殊0-1背包問題：可選物品重量越輕的物品價值越高。n=6，c=20，P=（4，8，15，1，6，3），W=（5，3，2，10，4，8）。其中n為物品個數(shù)，c為背包載重量，P表示物品的價值，W表示物品的重量。請問對于此0-1背包問題，應(yīng)如何選擇放進去的物品，才能使到放進背包的物品總價值最大，能獲得的最大總價值多少？參考解答：因為該01背包問題比較特殊，恰好重量

11、越輕的物品價值越高，所以優(yōu)先取重量輕的物品放進背包。最終可以把重量分別為2，3，4，5的三個物品放進背包，得到的價值和為15+8+6+4=33，為最大值。四、算法設(shè)計題（30分，前三題每題8分，最后一題6分）1、【最優(yōu)服務(wù)次序問題】（8分）提示：此題可采用貪心算法實現(xiàn)問題描述:設(shè)有n個顧客同時等待一項服務(wù)，顧客i需要的服務(wù)時間為ti，1v=iv=n。應(yīng)該如何安排n個顧客的服務(wù)次序才能使平均等待時間達到最??？（平均等待時間是n個顧客等待服務(wù)時間的總和除以n）。參考解答：貪心策略：最短服務(wù)時間優(yōu)先。將n個顧客的服務(wù)時間ti按照由小到大排序，n個顧客的服務(wù)調(diào)度方案即為排序后的順序，即可使得平均等待時

12、間最小。評分準則：1) 答到使用貪心算法，并且說明貪心的策略是短服務(wù)優(yōu)先，本題即可得滿分；2) 僅說明使用貪心算法，但未說明貪心策略，答題不完整，扣2分以上；3) 其它情況酌情考慮。2【Gray碼構(gòu)造問題(8分)一一提示：此題可采用分治遞歸算法實現(xiàn)問題描述：“格雷碼”是一個長度為2n的序列，滿足：(a) 每個元素都是長度為n比特的串(b) 序列中無相同元素(c) 連續(xù)的兩個元素恰好只有1個比特不同例如：n=2時，格雷碼為00,01，11，10。Gray碼是一種編碼，這種編碼可以避免在讀取時，因各數(shù)據(jù)位時序上的差異造成的誤讀。格雷碼在工程上有廣泛應(yīng)用。但格雷碼不便于運算，請你設(shè)計一種構(gòu)造方法，輸

13、入長度序列n，輸出格雷碼(你只要做出一種構(gòu)造方案即可，格雷碼并不唯一)。參考解答：此題可用分治法解決。當(dāng)n=1時，輸出格雷碼0,1當(dāng)n>1時，格雷碼的長度為2n，即共有2n個碼序列。此時，將問題一分為二，即上半部分和下半部分。上半部分最高位設(shè)為0，下半部分最高位設(shè)為1。剩下n-1位的格雷碼的構(gòu)造采用遞歸的思路。評分準則：1) 答到使用分治算法，并且推導(dǎo)出分治算法的過程，邊界設(shè)定清晰(即當(dāng)僅輸出1位的格雷碼如何處理)，本題即可得滿分；2) 說明使用分治算法，但漏邊界條件，扣2分以上；3) 其它情況酌情考慮。3、【最長上升子序列問題(8分)提示：此題可采用動態(tài)規(guī)劃算法實現(xiàn)對于給定的一個序列(

14、a,a,a)，1<N<1000。我們可以得到一些遞增上12N升的子序列(a,a,a)，這里1<i<i<<i<N。比如，對于序列(1,7,3,5,訂i2iK.12K9,4,8)，有它的一些上升子序列，如(1,7),(3,4,8)等等。這些子序列中最長的長度是4,比如子序列(1,3,5,8)。你的任務(wù)：就是對于給定的序列，求出最長上升子序列的長度。要求寫出你設(shè)計的算法思想及遞推函數(shù)的公式表達。參考解答：設(shè)f(i)表示：從左向右掃描過來直到以ai元素結(jié)尾的序列，獲得的最長上升子序列的長度，且子序列包含ai元素(1<i<n)。'1i二1f(

15、i)二<maxf(j)+1:當(dāng)ai>aj;1<j<ii>1、1i>1;Vj(1<j<i),都有ai<aj即，f(i)是從f(1)，f到f(i-1)中找最大的一個值，再加1?；蛘呔褪?。主要是看ai這個元素能否加入到之前已經(jīng)獲得的最長上升子序列，如果能加入，是之前已獲得的最長上升子序列長度加一；如果不能加入，就取這最后一個元素作為一個單獨子序列，長度為1。最后，所要求的整個序列的最長公共子序列長度為maxf(i):1<=i<=n例如，對于序列：4263152i1234567array4263152f(i)1122132評分準則：1

16、) 答到使用動態(tài)規(guī)劃算法，并且推導(dǎo)出動態(tài)規(guī)劃算法的遞推函數(shù)公式表達，邊界設(shè)定清晰，本題即可得滿分；(閱卷時仔細看遞推公式表達，公式表達含義正確即可，因其表達形式可能不唯一)2) 說明使用動態(tài)規(guī)劃算法，但對遞推函數(shù)表達錯誤或含糊，扣2分以上；3) 其它情況酌情考慮。4、【騎士問題】(6分)提示：此題可采用廣度優(yōu)先搜索算法實現(xiàn)在一個標準8x8的國際象棋棋盤上，棋盤中有些格子是可能有障礙物的。已知騎士的初始位置和目標位置，你的任務(wù)是計算出騎士最少需要多少步可以從初始位置到達目標位置，若無法到達目標位置，輸出“iotreachable”。請用文字或偽代碼說明你的算法。注意：騎士只能進行“日”字行對角跳

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