20231算法設(shè)計與分析課程期末試卷

本文格式為Word版，下載可任意編輯——20231算法設(shè)計與分析課程期末試卷華南農(nóng)業(yè)大學(xué)期末考試試卷（A卷）

2023學(xué)年第一學(xué)期考試科目：算法分析與設(shè)計

考試類型：（閉卷）考試時間：120分鐘

學(xué)號姓名年級專業(yè)

題號得分評閱人一二三四總分一、選擇題（20分，每題2分）

1.下述表達不正確的是。D

A．n2/2+2n的漸進表達式上界函數(shù)是O(2n)B．n2/2+2n的漸進表達式下界函數(shù)是Ω(2n)C．logn3的漸進表達式上界函數(shù)是O(logn)D．logn的漸進表達式下界函數(shù)是Ω(n)

2.當(dāng)輸入規(guī)模為n時，算法增長率最大的是。AA．5n

B．20log2n

C．2n2D．3nlog3n

3.T（n）表示當(dāng)輸入規(guī)模為n時的算法效率，以下算法效率最優(yōu)的是。CA．T（n）=T（n–1）+1，T（1）=1B．T（n）=2nC．T（n）=T（n/2）+1，T（1）=1D．T（n）=3nlog2n

4.在棋盤覆蓋問題中，對于2k×2k的特別棋盤（有一個特別方塊），所需的L型骨

牌的個數(shù)是。AA．（4k–1）/3

B．2k/3C．4kD．2k

5.在尋覓n個元素中第k小元素問題中，若使用快速排序算法思想，運用分治算法

對n個元素進行劃分，應(yīng)如何選擇劃分基準(zhǔn)？下面答案解釋最合理。DA．隨機選擇一個元素作為劃分基準(zhǔn)

1

2

3

3

B．取子序列的第一個元素作為劃分基準(zhǔn)C．用中位數(shù)的中位數(shù)方法尋覓劃分基準(zhǔn)

D．以上皆可行。但不同方法，算法繁雜度上界可能不同

6.有9個村莊，其坐標(biāo)位置如下表所示：

ix（i）y（i）112233445566778899123456789現(xiàn)在要蓋一所郵局為這9個村莊服務(wù)，請問郵局應(yīng)當(dāng)蓋在才能使到郵局到這9個村莊的總距離和最短。C

A．（4.5，0）B．（4.5，4.5）C．（5，5）D．（5，0）

7.n個人拎著水桶在一個水龍頭前面排隊打水，水桶有大有小，水桶必需打滿水，水流恒定。如下說法不正確？A

A．讓水桶大的人先打水，可以使得每個人排隊時間之和最小

B．讓水桶小的人先打水，可以使得每個人排隊時間之和最小

C．讓水桶小的人先打水，在某個確定的時間t內(nèi)，可以讓盡可能多的人打上水D．若要在盡可能短的時間內(nèi)，n個人都打完水，依照什么順序其實都一樣

8.分治法的設(shè)計思想是將一個難以直接解決的大問題分割成規(guī)模較小的子問題，分

別解決子問題，最終將子問題的解組合起來形成原問題的解。這要求原問題和子問題。C

A．問題規(guī)模一致，問題性質(zhì)一致B．問題規(guī)模一致，問題性質(zhì)不同C．問題規(guī)模不同，問題性質(zhì)一致D．問題規(guī)模不同，問題性質(zhì)不同

9.對布線問題，以下是不正確描述。CA．布線問題的解空間是一個圖

B．可以對方格陣列四周設(shè)置圍墻，即增設(shè)標(biāo)記的附加方格的預(yù)處理，使得算法簡化對邊界的判定

C．采用廣度優(yōu)先的標(biāo)號法找到從起點到終點的布線方案（這個方案假使存在的話）不一定是最短的

D．采用先入先出的隊列作為活結(jié)點表，以終點b為擴展結(jié)點或活結(jié)點隊列為空作為算法終止條件

10.對于含有n個元素的子集樹問題，最壞狀況下其解空間的葉結(jié)點數(shù)目為。

B

2

A．n!

B．2C．2

nn+1

n-1D．?n!/i!

i?1二、填空題（10分，每題2分）

1、一個算法繁雜性的高低表達在計算機運行該算法所需的時間和存儲器資源上，因此算法的繁雜性有繁雜性和空間繁雜性之分。

參考解答：時間

2、出自于“平衡子問題〞的思想，尋常分治法在分割原問題，形成若干子問題時，這些子問題的規(guī)模都大致。

參考解答：一致

3、使用二分探尋算法在n個有序元素表中探尋一個特定元素，在最正確狀況下，探尋的時間繁雜性為O（），在最壞狀況下，探尋的時間繁雜性為O（）。參考解答：1logn

4、已知一個分治算法花費的計算時間T(n)，T(n)滿足如下遞歸方程：

n?2?O(1)T(n)??

2T(n/2)?O(n)n?2?解得此遞歸方可得T(n)=O（）。參考解答：nlogn

5、動態(tài)規(guī)劃算法有一個變形方法。這種方法不同于動態(tài)規(guī)劃算法“自底向

上〞的填充方向，而是“自頂向下〞的遞歸方向，為每個解過的子問題建立了備忘錄以備需要時查看，同樣也可避免一致子問題的重復(fù)求解。參考解答：備忘錄方法

三、簡答題（40分，每題8分）

1、（8分）寫出以下繁雜性函數(shù)的偏序關(guān)系（即依照漸進階從低到高排序）：

23n3nlognn!2nlognnnn2nn10

n3參考解答：10?logn?nlogn?n

?2?3?n!?n

3

2、（8分）現(xiàn)在有8位運動員要進行網(wǎng)球循環(huán)賽，要設(shè)計一個滿足以下要求的比賽日程表：（1）（2）

每個選手必需與其他選手各賽一次；每個選手一天只能賽一次；

（3）循環(huán)賽一共進行n–1天。

請利用分治法的思想，給這8位運動員設(shè)計一個合理的比賽日程。參考解答：

12345678

3、（8分）某體育館有一羽毛球場出租，現(xiàn)在總共有10位客戶申請租用此羽毛球場，每個客戶所租用的時間單元如下表所示，s(i)表示開始租用時刻，f(i)表示終止租用時刻，10個客戶的申請如下表所示：is(i)102331455365711889810621436587341278564321876556781234658721437856341287654321f(i)65498713121110同一時刻，該羽毛球場只能租借給一位客戶，請設(shè)計一個租用安排方案，在這10位客戶里面，使得體育館能盡可能滿足多位客戶的需求，并算出針對上表的10個客戶申請，最多可以安排幾位客戶申請。

參考解答：將這10位客戶的申請依照終止時間f(i)遞增排序，如下表：

is(i)f(i)1142353064575386597610881198121011131）選擇申請1（1,4）2）依次檢查后續(xù)客戶申請，只要與已選擇的申請相容不沖突，則選擇該申請。直到

所有申請檢查完畢。申請4（5,7）、申請8（8,11）、申請10（11,13）3）最終，可以滿足：申請1（1,4）、申請4（5,7）、申請8（8,11）、申請10（11,13）共4個客戶申請。這已經(jīng)是可以滿足的最大客戶人數(shù)。

4

4、（8分）對于矩陣連乘所需最少數(shù)乘次數(shù)問題，其遞歸關(guān)系式為：

0??m[i,j]??min{m[i,k]?m[k?1,j]?pi?1pkpj}??i?k?ji?ji?j

其中m[i，j]為計算矩陣連乘Ai…Aj所需的最少數(shù)乘次數(shù)，pi-1為矩陣Ai的行，pi為矩陣Ai的列?，F(xiàn)有四個矩陣，其中各矩陣維數(shù)分別為：

A150?10p0?p1參考解答：

m[1][1]?m[2][4]?p0p1p4?0?8000?50?10?5?10500??m[1][4]?min?m[1][2]?m[3][4]?p0p2p4?20000?6000?50?40?5?36000

?m[1][3]?m[4][4]?ppp?27000?0?50?30?5?34500034??10500A210?40p1?p2A340?30p2?p3A430?5p3?p4請根據(jù)以上的遞歸關(guān)系，計算出矩陣連乘積A1A2A3A4所需要的最少數(shù)乘次數(shù)。

5、（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)如何選擇放進去的物品，才能使到放進背包的物品總價值最大，能獲得的最大總價值多少？

參考解答：由于該0－1背包問題比較特別，恰好重量越輕的物品價值越高，所以優(yōu)先取重量輕的物品放進背包。最終可以把重量分別為2，3，4，5的三個物品放進背包，得到的價值和為15+8+6+4=33，為最大值。

四、算法設(shè)計題（30分，前三題每題8分，最終一題6分）

1、（8分）——提醒：此題可采用貪心算法實現(xiàn)

問題描述：設(shè)有n個顧客同時等待一項服務(wù)，顧客i需要的服務(wù)時間為ti，1將n個顧客的服務(wù)時間ti依照由小到大排序，n個顧客的服務(wù)調(diào)度方案即為排序后的順序，即可使得平均等待時間最小。

評分準(zhǔn)則：

1)答到使用貪心算法，并且說明貪心的策略是短服務(wù)優(yōu)先，此題即可得總分值；2)僅說明使用貪心算法，但未說明貪心策略，答題不完整，扣2分以上；3)其它狀況酌情考慮。

2、（8分）——提醒：此題可采用分治遞歸算法實現(xiàn)問題描述：“格雷碼〞是一個長度為2n的序列，滿足：

（a）每個元素都是長度為n比特的串

（b）序列中無一致元素

（c）連續(xù)的兩個元素恰好只有1個比特不同例如：n=2時，格雷碼為{00，01，11，10}。

Gray碼是一種編碼，這種編碼可以避免在讀取時，因各數(shù)據(jù)位時序上的差異造成的誤讀。格雷碼在工程上有廣泛應(yīng)用。但格雷碼不便于運算，請你設(shè)計一種構(gòu)造方法，輸入長度序列n，輸出格雷碼（你只要做出一種構(gòu)造方案即可，格雷碼并不唯一）。

參考解答：此題可用分治法解決。當(dāng)n＝1時，輸出格雷碼{0,1}

當(dāng)n>1時，格雷碼的長度為2n，即共有2n個碼序列。此時，將問題一分為二，即上半部分和下半部分。上半部分最高位設(shè)為0，下半部分最高位設(shè)為1。剩下n-1位的格雷碼的構(gòu)造采用遞歸的思路。

評分準(zhǔn)則：

1)答到使用分治算法，并且推導(dǎo)出分治算法的過程，邊界設(shè)定明了（即當(dāng)僅輸出1位的格雷碼如何處理），此題即可得總分值；2)說明使用分治算法，但漏邊界條件，扣2分以上；3)其它狀況酌情考慮。

3、（8分）——提醒：此題可采用動態(tài)規(guī)劃算法實現(xiàn)

6

對于給定的一個序列(a1,a2,?,aN)，1?N?1000。我們可以得到一些遞增上升的子序列(ai1,ai2,?,aiK)，這里1?i1?i2???iK?N。譬如，對于序列(1,7,3,5,9,4,8)，有它的一些上升子序列，如(1,7),(3,4,8)等等。這些子序列中最長的長度是4，譬如子序列(1,3,5,8)。你的任務(wù)：就是對于給定的序列，求出最長上升子序列的長度。要求寫出你設(shè)計的算法思想及遞推函數(shù)的公式表達。

參考解答：設(shè)f(i)表示：從左向右掃描過來直到以a[i]元素結(jié)尾的序列，獲得的最長上升子序列的長度，