算法設(shè)計(jì)與分析課程期末試卷a卷（自測(cè)）

1、精選優(yōu)質(zhì)文檔-傾情為你奉上華南農(nóng)業(yè)大學(xué)期末考試試卷（A卷）2008學(xué)年第一學(xué)期 考試科目：算法分析與設(shè)計(jì)考試類型：（閉卷）考試時(shí)間：120分鐘學(xué)號(hào) 姓名 年級(jí)專業(yè) 題號(hào)一二三四總分得分評(píng)閱人一、選擇題（20分，每題2分）1.下述表達(dá)不正確的是 。 An2/2 + 2n的漸進(jìn)表達(dá)式上界函數(shù)是O(2n)Bn2/2 + 2n的漸進(jìn)表達(dá)式下界函數(shù)是(2n)Clogn3的漸進(jìn)表達(dá)式上界函數(shù)是O(logn)Dlogn3的漸進(jìn)表達(dá)式下界函數(shù)是(n3)2.當(dāng)輸入規(guī)模為n時(shí)，算法增長率最大的是 。 A5nB20log2nC2n2 D3nlog3n3.T（n）表示當(dāng)輸入規(guī)模為n時(shí)的算法效率，以下算法效率最優(yōu)的是

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

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

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

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

6、)= O（ nlogn ）。5、動(dòng)態(tài)規(guī)劃算法有一個(gè)變形方法 備忘錄方法 。這種方法不同于動(dòng)態(tài)規(guī)劃算法“自底向上”的填充方向，而是“自頂向下”的遞歸方向，為每個(gè)解過的子問題建立了備忘錄以備需要時(shí)查看，同樣也可避免相同子問題的重復(fù)求解。參考解答：1、時(shí)間 2、相同 3、1 logn 4、 5、備忘錄方法三、簡答題（40分，每題8分）1、（8分）寫出下列復(fù)雜性函數(shù)的偏序關(guān)系（即按照漸進(jìn)階從低到高排序）：參考解答：2、（8分）現(xiàn)在有8位運(yùn)動(dòng)員要進(jìn)行網(wǎng)球循環(huán)賽，要設(shè)計(jì)一個(gè)滿足以下要求的比賽日程表：（1）每個(gè)選手必須與其他選手各賽一次；（2）每個(gè)選手一天只能賽一次；（3）循環(huán)賽一共進(jìn)行n 1天。請(qǐng)利用分治

7、法的思想，給這8位運(yùn)動(dòng)員設(shè)計(jì)一個(gè)合理的比賽日程。參考解答：12345678214365873412785643218765567812346587214378563412876543213、（8分）某體育館有一羽毛球場出租，現(xiàn)在總共有10位客戶申請(qǐng)租用此羽毛球場，每個(gè)客戶所租用的時(shí)間單元如下表所示，s(i)表示開始租用時(shí)刻，f(i)表示結(jié)束租用時(shí)刻，10個(gè)客戶的申請(qǐng)如下表所示：i12345678910s(i)03153511886f(i)65498713121110同一時(shí)刻，該羽毛球場只能租借給一位客戶，請(qǐng)?jiān)O(shè)計(jì)一個(gè)租用安排方案，在這10位客戶里面，使得體育館能盡可能滿足多位客戶的需求，并算出針

8、對(duì)上表的10個(gè)客戶申請(qǐng)，最多可以安排幾位客戶申請(qǐng)。參考解答：將這10位客戶的申請(qǐng)按照結(jié)束時(shí)間f(i)遞增排序，如下表：i12345678910s(i(i)456789101112131）選擇申請(qǐng)1（1,4）2）依次檢查后續(xù)客戶申請(qǐng)，只要與已選擇的申請(qǐng)相容不沖突，則選擇該申請(qǐng)。直到所有申請(qǐng)檢查完畢。申請(qǐng)4（5,7）、申請(qǐng)8（8,11）、申請(qǐng)10（11,13）3）最后，可以滿足：申請(qǐng)1（1,4）、申請(qǐng)4（5,7）、申請(qǐng)8（8,11）、申請(qǐng)10（11,13）共4個(gè)客戶申請(qǐng)。這已經(jīng)是可以滿足的最大客戶人數(shù)。4、（8分）對(duì)于矩陣連乘所需最少數(shù)乘次數(shù)問題，其遞歸關(guān)系式為：其中mi

9、，j為計(jì)算矩陣連乘AiAj所需的最少數(shù)乘次數(shù)，pi-1為矩陣Ai的行，為矩陣Ai的列?，F(xiàn)有四個(gè)矩陣，其中各矩陣維數(shù)分別為：A1A2A3A450?1010?4040?3030?5p 0? p 1p 1? p 2p 2? p 3p 3? p 4請(qǐng)根據(jù)以上的遞歸關(guān)系，計(jì)算出矩陣連乘積A1A2A3A4所需要的最少數(shù)乘次數(shù)。參考解答：5、（8分）有這樣一類特殊0-1背包問題：可選物品重量越輕的物品價(jià)值越高。n=6，c=20，P=（4，8，15，1，6，3），W=（5，3，2，10，4，8）。其中n為物品個(gè)數(shù)，c為背包載重量，P表示物品的價(jià)值，W表示物品的重量。請(qǐng)問對(duì)于此0-1背包問題，應(yīng)如何選擇放進(jìn)去的

10、物品，才能使到放進(jìn)背包的物品總價(jià)值最大，能獲得的最大總價(jià)值多少？參考解答：因?yàn)樵?1背包問題比較特殊，恰好重量越輕的物品價(jià)值越高，所以優(yōu)先取重量輕的物品放進(jìn)背包。最終可以把重量分別為2，3，4，5的三個(gè)物品放進(jìn)背包，得到的價(jià)值和為15 + 8 + 6 + 4 = 33，為最大值。四、算法設(shè)計(jì)題（30分，前三題每題8分，最后一題6分）1、【最優(yōu)服務(wù)次序問題】（8分） 提示：此題可采用貪心算法實(shí)現(xiàn)問題描述：設(shè)有n個(gè)顧客同時(shí)等待一項(xiàng)服務(wù)，顧客i需要的服務(wù)時(shí)間為ti，1=i1時(shí)，格雷碼的長度為，即共有個(gè)碼序列。此時(shí)，將問題一分為二，即上半部分和下半部分。上半部分最高位設(shè)為0，下半部分最高位設(shè)為1。剩下

11、n-1位的格雷碼的構(gòu)造采用遞歸的思路。評(píng)分準(zhǔn)則：1)答到使用分治算法，并且推導(dǎo)出分治算法的過程，邊界設(shè)定清晰（即當(dāng)僅輸出1位的格雷碼如何處理），本題即可得滿分；2)說明使用分治算法，但漏邊界條件，扣2分以上；3)其它情況酌情考慮。3、【最長上升子序列問題】（8分） 提示：此題可采用動(dòng)態(tài)規(guī)劃算法實(shí)現(xiàn)對(duì)于給定的一個(gè)序列，。我們可以得到一些遞增上升的子序列，這里。比如，對(duì)于序列(1, 7, 3, 5, 9, 4, 8)，有它的一些上升子序列，如(1, 7), (3, 4, 8)等等。這些子序列中最長的長度是4，比如子序列(1, 3, 5, 8)。你的任務(wù)：就是對(duì)于給定的序列，求出最長上升子序列的長度

12、。要求寫出你設(shè)計(jì)的算法思想及遞推函數(shù)的公式表達(dá)。參考解答：設(shè)表示：從左向右掃描過來直到以元素結(jié)尾的序列，獲得的最長上升子序列的長度，且子序列包含元素（）。即，是從，到中找最大的一個(gè)值，再加1?；蛘呔褪?。主要是看ai這個(gè)元素能否加入到之前已經(jīng)獲得的最長上升子序列，如果能加入，是之前已獲得的最長上升子序列長度加一；如果不能加入，就取這最后一個(gè)元素作為一個(gè)單獨(dú)子序列，長度為1。最后，所要求的整個(gè)序列的最長公共子序列長度為maxf(i): 1=i=n例如，對(duì)于序列：4 2 6 3 1 5 2i1234567array4263152f(i)1122132評(píng)分準(zhǔn)則：1) 答到使用動(dòng)態(tài)規(guī)劃算法，并且推導(dǎo)出

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

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