華南農(nóng)業(yè)大學(xué)大三計(jì)算機(jī)專業(yè)算法設(shè)計(jì)與分析期末試卷及答案

PAGEPAGE6華南農(nóng)業(yè)大學(xué)期末考試試卷（A卷）20XX學(xué)年第二學(xué)期(20xx.6) 考試科目：算法設(shè)計(jì)與分析（開卷）考試時(shí)間：120分鐘學(xué)號(hào)題號(hào)一姓名二三年級(jí)專業(yè)四 總分得分評(píng)閱人一、選擇題（30分，每題2分）1、一個(gè)算法應(yīng)該包含如下幾條性質(zhì)，除了A 。（A）二義性 （B）有限性 （C） 正確性 可終止性2、解決一個(gè)問題通常有多種方法。若說一個(gè)算法“有效”是指 D 。這個(gè)算法能在一定的時(shí)間和空間資源限制內(nèi)將問題解決這個(gè)算法能在人的反應(yīng)時(shí)間內(nèi)將問題解決這個(gè)算法比其他已知算法都更快地將問題解決（D）A和C3、當(dāng)輸入規(guī)模為n時(shí)，算法增長率最小的是 B 。3（A）5n （B）20log2n （C）2n2 （D）3nlogn34、漸進(jìn)算法分析是指 B 。算法在最佳情況、最差情況和平均情況下的代價(jià)當(dāng)規(guī)模逐步往極限方向增大時(shí)，對(duì)算法資源開銷“增長率”上的簡(jiǎn)化分析數(shù)據(jù)結(jié)構(gòu)所占用的空間在最小輸入規(guī)模下算法的資源代價(jià)5、當(dāng)上下限表達(dá)式相等時(shí)，我們使用下列哪種表示法來描述算法代價(jià)？C（A）大O表示法 （B）大Ω表示法（C）Θ表示法 （D）小o表示法6、采用“順序搜索法”從一個(gè)長度為N的隨機(jī)分布數(shù)組中搜尋值為K的元素。以下順序搜索法分析正確的是 B 。最佳情況、最差情況和平均情況下，順序搜索法的漸進(jìn)代價(jià)都相同最佳情況的漸進(jìn)代價(jià)要好于最差情況和平均情況的漸進(jìn)代價(jià)最佳情況和平均情況的漸進(jìn)代價(jià)要好于最差情況的漸進(jìn)代價(jià)7、遞歸通常用 C 來實(shí)現(xiàn)。（A）有序的線性表 （B）隊(duì)列 （C）棧 （D）數(shù)組8、分治法的設(shè)計(jì)思想是將一個(gè)難以直接解決的大問題分割成規(guī)模較小的子問題，分別決子問題，最后將子問題的解組合起來形成原問題的解。這要求原問題和子問題 C問題規(guī)模相同，問題性質(zhì)相同問題規(guī)模相同，問題性質(zhì)不同問題規(guī)模不同，問題性質(zhì)相同問題規(guī)模不同，問題性質(zhì)不同9、在尋找n個(gè)元素中第k小元素問題中，如快速排序算法思想，運(yùn)用分治算法對(duì)n個(gè)素進(jìn)行劃分，如何選擇劃分基準(zhǔn)？下面 D 答案解釋最合理。隨機(jī)選擇一個(gè)元素作為劃分基準(zhǔn)取子序列的第一個(gè)元素作為劃分基準(zhǔn)用中位數(shù)的中位數(shù)方法尋找劃分基準(zhǔn)以上皆可行。但不同方法，算法復(fù)雜度上界可能不同10、對(duì)于0－1背包問題和背包問題的解法，下面 C 答案解釋正確。0－1背包問題和背包問題都可用貪心算法求解0－1背包問題可用貪心算法求解，但背包問題則不能用貪心算法求解0－1包問題則可以用貪心算法求解0－1背包問題不具有最優(yōu)子結(jié)構(gòu)性質(zhì)，所以不能用貪心算法求解、關(guān)于回溯搜索法的介紹，下面 D是不正確描述?；厮莘ㄓ小巴ㄓ媒忸}法”之稱，它可以系統(tǒng)地搜索一個(gè)問題的所有解或任意解回溯法是一種既帶系統(tǒng)性又帶有跳躍性的搜索算法改：樹結(jié)構(gòu)回溯法，又被稱為通用解題法，用它可以系統(tǒng)地搜索問題的所有解?；厮莘ㄊ且粋€(gè)既帶有系統(tǒng)性又帶有跳躍性的搜索算法。它在問題的解空間中按深度優(yōu)先策略，從根結(jié)點(diǎn)出發(fā)搜索解空間樹。算法搜索到解空間樹的任意結(jié)點(diǎn)時(shí)，首先判斷該結(jié)點(diǎn)是否包含問題的解。如果不包含則跳過對(duì)以該結(jié)點(diǎn)為根的子樹的搜索，逐層向其祖先結(jié)點(diǎn)回溯；否則進(jìn)入這棵子樹繼續(xù)按深度優(yōu)先搜索。如收費(fèi)公路重建問題。12、關(guān)于回溯算法和分支限界法，以下 A是不正確描述?；厮莘ㄖ校總€(gè)活結(jié)點(diǎn)只有一次機(jī)會(huì)成為擴(kuò)展結(jié)點(diǎn)兒子結(jié)點(diǎn)中，那些導(dǎo)致不可行解或?qū)е路亲顑?yōu)解的兒子結(jié)點(diǎn)被舍棄，其余兒子加入活結(jié)點(diǎn)表中回溯法采用深度優(yōu)先的結(jié)點(diǎn)生成策略分支限界法采用廣度優(yōu)先或最小耗費(fèi)優(yōu)先（最大效益優(yōu)先）的結(jié)點(diǎn)生成策略13、優(yōu)先隊(duì)列通常用以下 B數(shù)據(jù)結(jié)構(gòu)來實(shí)現(xiàn)。棧堆隊(duì)列二叉查找樹14、在分支限界算法中，根據(jù)從活結(jié)點(diǎn)表中選擇下一擴(kuò)展結(jié)點(diǎn)的不同方式可有幾種常分類，以下 D 描述最為準(zhǔn)確采用FIFO隊(duì)列的隊(duì)列式分支限界法采用最小值堆的優(yōu)先隊(duì)列式分支限界法采用最大值堆的優(yōu)先隊(duì)列式分支限界法以上都常用，針對(duì)具體問題可以選擇采用其中某種更為合適的方式15、對(duì)布線問題，以下C 是不正確描述布線問題的解空間是一個(gè)圖（這個(gè)方案如果存在的話）b法結(jié)束條件二、填空題（20分，每空2分）1、一個(gè)算法復(fù)雜性的高低體現(xiàn)在計(jì)算機(jī)運(yùn)行該算法所需的時(shí)間和存儲(chǔ)器資源上，因此法的復(fù)雜性有 時(shí)間 復(fù)雜性和 空間 復(fù)雜性之分。2、一個(gè)直接或間接調(diào)用自身的算法稱為遞歸 算法。出自于“平衡子問題”的思想，通常分治法在分割原問題，形成若干子問題時(shí)，些子問題的規(guī)模都大致 相等 。3、使用二分搜索算法在n個(gè)有序元素表中搜索一個(gè)特定元素，在最佳情況下，搜索的間復(fù)雜性為（ 1，在最壞情況下，搜索的時(shí)間復(fù)雜性為（logn （ 或log2n） 。4、動(dòng)態(tài)規(guī)劃算法的基本要素是最優(yōu)子結(jié)構(gòu)性質(zhì)和子問題重疊質(zhì) 。5“自底向上”的填充方向，而是“自頂向下”的遞歸方向，為每個(gè)解過的子問題建立了備忘錄以備需要時(shí)查看，同樣也可避免相同子問題的重復(fù)求解。6、貪心算法的基本要素是貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì)。三、簡(jiǎn)答題（32分，五題任選四題，每題8分）1、有4個(gè)矩陣{A,A1 2

,,4

，連乘積為AA1 2

。其中Ai

與Ai1

是可乘的，A1，A2，A3，A4A1A2，A2A3，A3A4A1A2A3，A2A3A4A1A2A3A4n個(gè)C(n,2)個(gè)i1,2,A1，A2，A3，A4A1A2，A2A3，A3A4A1A2A3，A2A3A4A1A2A3A4n個(gè)C(n,2)個(gè)2、最大子段和問題：?jiǎn)栴}描述：給定由n個(gè)整數(shù)（其中可能有負(fù)數(shù)組成的序列aa,a，求該序列1 2 n形如jakki

的子段和的最大值。當(dāng)所有整數(shù)均為負(fù)整數(shù)時(shí)定義其最大子段和為0。依此定義，所求的最優(yōu)值為：max, maxja}1ijn ki[j]maj1ijki

ak

1ijnn個(gè)整數(shù)序列的最大子段和問題，maxb[j]即為所求。1jnj]jj],j]}

j11j問：對(duì)于實(shí)例（a,a, ,a）＝（21，13，5，2，按照前述動(dòng)態(tài)1 2 6a規(guī)劃遞歸式填充b數(shù)組，算法運(yùn)行完畢后，請(qǐng)寫出。aa1a2a3a4a5a6－211－413－5－2bb1b2b3b4b5b60117201513最大子段和值：maxb[j]201jn3、對(duì)于如下描述的背包問題，請(qǐng)計(jì)算最終裝入背包的．．．．．。背包容量：C＝50千克。3件物品。物品1重20千克，價(jià)值100元；物品2重20千克，價(jià)值120元；物品3重30千克，價(jià)值90元。150元/260元/30元千克。采用貪心算法解此背包問題。此時(shí)，貪心的策略是：每次選擇單位重量價(jià)值最大的物品。因此，首先選擇物品13，直至將背包裝滿。21202030千克；物品1全部裝入背包，當(dāng)前背包中價(jià)值220元120100元，背包占用40千克，剩余10千克；物品3的1/3250（120元＋10090×1/，50千克（裝滿。250122031/310千克。4符號(hào)三角形的第一行有n“＋”或“－”，以下“+”，2“－”++-++ - - +-++-++ - - +-4個(gè)符號(hào)（即n＝4）的形狀。－－＋－＋－＋－＋－＋－＋－＋－＋－＋－＋－＋－＋－＋－＋5將平面點(diǎn)集分為大致相等的兩個(gè)子集S2P1P2Ld和d2分別是S1S2中最小距離，且設(shè)d=min{d1,d2}。P1pP2q構(gòu)成全平面點(diǎn)集的最接近點(diǎn)對(duì)的候選6證明：鴿籠原理n+1n或兩只以上的鴿子。將矩形R的長為2d3d的邊26個(gè)(d/2)×(2d/3)（a所示R6個(gè)S鴿籠原理易知至少有一個(gè)(d/2)×(2d/3)2個(gè)以上S中的點(diǎn)。設(shè)2則：(x(u)x(v))2(y(u)y(v))2(d/2)2(2d/3)225d236distance(u,v)≤5d/6<ddR6SbR6S中的點(diǎn)的極端情形。四、算法設(shè)計(jì)題（18分，五題任選三題，每題6分）1、【主油管最佳位置】（6分）Olay教授正在為一家石油公司咨詢，該公司正在計(jì)劃建造一條由東向西的石油主管道，該管道要穿過一片有n。給定各個(gè)井的X坐標(biāo)和Y坐標(biāo)，Olay教授要如何才能選擇最佳主管道的位置（使各噴油管長度之和最?。?？7PAGEPAGE14噴油管噴油管主油管參考解答：這是中位數(shù)的應(yīng)用問題。在順序統(tǒng)計(jì)的問題中，中位數(shù)的應(yīng)用最廣，例如在X軸上有n個(gè)點(diǎn)，由左到右依次排列為X1，X2，…，Xn。XXX1X2…Xn-1 Xn我們希望在x軸上尋找一點(diǎn)Xp與各點(diǎn)距離之和i1

d(Xi

X p個(gè)問題可以歸結(jié)為中位數(shù)問題。即：當(dāng)n為奇數(shù)時(shí)為X ，否則為(X X )/2。(n1)/2 n/2 n/21從這個(gè)例子出發(fā)，本題求主油管道的問題也是類似的。由于主管道由東向西，因此，要使連接油井和主油管道的噴井管道最短，噴井管道必須南北走向，與主管道垂直，即主管道的最優(yōu)位置應(yīng)為一條Y＝Y(jié)kYk如何確定。為了使Yk與各油井的Y坐標(biāo)Y1，Y2，…，Yn間的距離和最短，我們將YnYk（(n+1)/2小的Y坐標(biāo)作為n/2小的Y(n/2+1)小的Y坐標(biāo)值的平均數(shù)作為Yk的值。顯然，確定主油管道的最佳位置，實(shí)際上就是求n個(gè)油井的Y坐標(biāo)的中位數(shù)。評(píng)分準(zhǔn)則：答到求n個(gè)油井Y坐標(biāo)的中位數(shù)，本題即可得滿分；僅說明求中位數(shù)，但未提到是對(duì)Y2分；其它情況酌情考慮。2、【特殊的0-1背包問題】（6分）在0-10-1背包問題，設(shè)計(jì)一個(gè)有效的算法找出最優(yōu)解（描述你的算法即可，算法的正確性）參考解答：對(duì)于0－1背包問題本來是無法用貪心算法得到最優(yōu)解的，但對(duì)于這類特殊的0－1背包問題，則可以用貪心算法去解。貪心策略如下：首先將各物品依重量遞增序（即也是價(jià)值遞減序）排列，然后依照價(jià)值遞減順序選擇物品裝入背包，直到背包裝不下下一件物品為止。這里貪心算法的貪心選擇策略是：每次總是選擇價(jià)值最大（同時(shí)重量也最?。┑奈锲?，然后檢查是否可以裝入背包。評(píng)分準(zhǔn)則：答到使用貪心算法，并且貪心策略描述清晰，本題即可得滿分；僅說明使用貪心算法，但貪心策略描述含糊，扣1～2分；其它情況酌情考慮。3Gray（6分）問題描述：“格雷碼”是一個(gè)長度為2的n次方的序列，滿足：每個(gè)元素都是長度為n比特的串序列中無相同元素1個(gè)比特不同例如：n=2{00，01，11，10}Gray誤讀。格雷碼在工程上有廣泛應(yīng)用。但格雷碼不便于運(yùn)算，請(qǐng)你設(shè)計(jì)一種構(gòu)造方法，輸入長度序列n，輸出格雷碼（只要做出一種構(gòu)造方案即可，格雷碼并不唯一）。參考解答：此題也可用分治法解決。當(dāng)n＝1時(shí)，輸出格雷碼{0,1}當(dāng)n>1時(shí)，格雷碼的長度為2n，即共有2n個(gè)碼序列。此時(shí)，將問題一分為二，即上半部分和下半部分。上半部分最高位設(shè)為0，下半部分最高位設(shè)為1。剩下n-1位的格雷碼的構(gòu)造采用遞歸的思路。評(píng)分準(zhǔn)則：（即當(dāng)僅輸出位的格雷碼如何處理，本題即可得滿分；說明使用分治算法，但漏邊界條件，扣1分；其它情況酌情考慮。4、【男女運(yùn)動(dòng)員最佳搭配問題】（6分）n人。給定兩個(gè)n×n的矩陣P和QP[i][j]動(dòng)員i和女運(yùn)動(dòng)員jQ[i][j是女運(yùn)動(dòng)員i和男運(yùn)動(dòng)員j并不一定等于Q[j][i]。采用回溯法設(shè)計(jì)一個(gè)算法，計(jì)算男女運(yùn)動(dòng)員最佳搭配的配對(duì)法，使得各組男女雙方競(jìng)賽優(yōu)勢(shì)乘積的總和達(dá)到最大。對(duì)于這個(gè)問題，解空間如下：男男1男n女1女…女n男…女1女…女n女1女…女n在這個(gè)解空間中采用回溯方法，由于一個(gè)男隊(duì)員只能和一個(gè)女隊(duì)員搭檔，反之也同理，因此，對(duì)于搜索的第一步選定某男和某女，那么第二個(gè)男隊(duì)員就不能和第一個(gè)男隊(duì)員的女搭檔組合，因此，剪去改女隊(duì)員的分枝。將男女隊(duì)員的競(jìng)賽優(yōu)勢(shì)乘積計(jì)算出來，然后將各組男女的優(yōu)勢(shì)乘積進(jìn)行相加。找出最大值。評(píng)分準(zhǔn)則：滿分；說明使用回溯算法，但解空間含糊，扣2～3分；其它情況酌情考慮。5、【優(yōu)美打印問題】（6分）問題描述：考慮在一臺(tái)打印機(jī)上優(yōu)美地打印一段文章的問題。輸入的文章正文是由長度Ln個(gè)英文單詞構(gòu)成的序列。我們希望將這段文章分若干行打印出來，1 2 n每行的最大長度為m，且“優(yōu)美度”的標(biāo)準(zhǔn)如下：如果某一行包含從單詞i到單詞j，且每兩個(gè)單詞間留一空格，行首無空格，則在行末多余的空格數(shù)為：mjij Lkki（這個(gè)公式如何得到呢？由于某一行包含單詞i到單詞一空格因此單詞間的空格數(shù)為－又由于從第i個(gè)單詞到第j個(gè)單詞的長度和為j L ，kki因此行末多余的空格為mjij L 。）kki不同的斷行（即切斷從單詞i到單詞j形成一行）度”（即除最后一行的所有行的行末多余空格總和）。計(jì)出一個(gè)優(yōu)美的打印出一段有n個(gè)單詞的文章的方案。參考解答：此題的題目已經(jīng)指定了動(dòng)態(tài)規(guī)劃算法，而且算法思路也已較為清晰，所需要做的只是寫出狀態(tài)轉(zhuǎn)移方程和邊界設(shè)定。ijnr[i]j(mjijn0

k

Lk

(1in)(in1)解題思路提示：由于必須打印完n個(gè)單詞且每行打印的單詞是連續(xù)的，因此，我們從第n個(gè)單詞開始，依次考慮填一個(gè)單詞（單詞n），填兩個(gè)單詞（單詞n-1，單詞n），……，填n個(gè)單詞（單詞1，單詞2，…，單詞n）的打印方案。由于單詞填入的方式是按單詞序號(hào)遞減的順序進(jìn)行的．．．設(shè)r[i]——填入單詞i到單詞n后，所有被填行的行末空格數(shù)總和的最小值。顯然，r[i]的動(dòng)態(tài)規(guī)劃遞歸式可以由以上思路得到。另外，我們專門設(shè)置了一張記憶表k[i]（1≤i≤n+1），記下使得r[i]j示填單詞i到單詞n的最佳方案中，第一行應(yīng)填單詞i到單詞j（jk[i]）。r的遞歸的邊界可定義為：r[n+1]＝0；k[n+1]＝n+1；表示不填任何單詞時(shí)的行末空格數(shù)為0。我們從r[n+1]出發(fā)，依次求r[n]，r[n-1]，…，r[1]。由r[i]的遞歸式的由來可以看出，求r[i]最小值的子問題，包含了求這些子問題。要使r[i]最小，必須使這兩個(gè)要素。我們可以按自下而上的方式求解，充分利用了重疊子問題。最后求出的r[1]即為最優(yōu)“優(yōu)美打印方案”中行末空格數(shù)的總和；從單詞1出發(fā)，順著記憶表K的指示，可順序打印出文章的各行。問題和任務(wù)：根據(jù)以上的算法提示，請(qǐng)寫出r[i]的動(dòng)態(tài)規(guī)劃遞歸式，并定義遞歸的邊界。20XX學(xué)年第一學(xué)期 考試科目：算法設(shè)計(jì)與分析考試類型（開卷） 考試時(shí)間：120 分鐘學(xué)號(hào)姓名年級(jí)專業(yè)題號(hào)得分一二三四 總分評(píng)閱人一、選擇題（302分）1A2D3B4B5C6B7C8C9D10C11D12A13B14D15C二、填空題（202分）1、時(shí)間2、遞歸3、1

空間相等logn（或log2n）4、最優(yōu)子結(jié)構(gòu)性質(zhì)5、備忘錄方法6、貪心選擇性質(zhì)

子問題重疊性質(zhì)三、簡(jiǎn)答題（32分，五題任選四題，每題8分）1、子問題如下所列：A1A1，A2，A3，A4A1A2，A2A3，A3A4A1A2A3，A2A3A4A1A2A3A4n個(gè)C(n,2)個(gè)2、aa1a2a3a4a5a6－211－413－5－2bb1b2b3b4b5b60117201513最大子段和值：maxb[j]201jn3、物品1的單位重量價(jià)值為50元/千克；物品2的單位重量價(jià)值為60元/千克；物品3的單位重量價(jià)值為30元/千克。采用貪心算法解此背包問題。此時(shí)，貪心的策略是：每次選擇單位重量價(jià)值最大的物品。因此，首先選擇物品13，直至將背包裝滿。21202030千克；物品1全部裝入背包，當(dāng)前背包中價(jià)值220元120100元，背包占用40千克，剩余10千克；物品3的1/3250（120元＋10090×1/，50千克（裝滿。250122031/310千克。4、4個(gè)符號(hào)（即n＝4）時(shí)，解空間樹是一棵完全二叉樹。－ ＋－ ＋ － ＋－＋ － ＋ － ＋ － ＋－＋－＋－＋－＋－＋－＋－＋－＋5、證明：鴿籠原理n+1n或兩只以上的鴿子。將矩形R的長為2d3d的邊26個(gè)(d/2)×(2d/3)（a所示R6個(gè)S鴿籠原理易知至少有一個(gè)(d/2)×(2d/3)2個(gè)以上S中的點(diǎn)。設(shè)2則：(x(u)x(v))2(y(u)y(v))2(d/2)2(2d/3)225d236distance(u,v)≤5d/6<ddR6SbR6S中的點(diǎn)的極端情形。四、算法設(shè)計(jì)題（18分，五題任選三題，每題6分）1、【主油管最佳位置】（6分）參考解答：這是中位數(shù)的應(yīng)用問題。在順序統(tǒng)計(jì)的問題中，中位數(shù)的應(yīng)用最廣，例如在X軸上有n個(gè)點(diǎn)，由左到右依次排列為X1，X2，…，Xn。15PAGEPAGE18XXX1X2…Xn-1 Xn我們希望在x軸上尋找一點(diǎn)Xp與各點(diǎn)距離之和i1

d(Xi

X p個(gè)問題可以歸結(jié)為中位數(shù)問題。即：當(dāng)n為奇數(shù)時(shí)為X ，否則為(X X )/2。(n1)/2 n/2 n/21從這個(gè)例子出發(fā)，本題求主油管道的問題也是類似的。由于主管道由東向西，因此，要使連接油井和主油管道的噴井管道最短，噴井管道必須南北走向，與主管道垂直，即主管道的最優(yōu)位置應(yīng)為一條Y＝Y(jié)kYk如何確定。為了使Yk與各油井的Y坐標(biāo)Y1，Y2，…，Yn間的距離和最短，我們將YnYk（(n+1)/2小的Y坐標(biāo)作為n/2小的Y(n/2+1)小的Y坐標(biāo)值的平均數(shù)作為Yk的值。顯然，確定主油管道的最佳位置，實(shí)際上就是求n個(gè)油井的Y坐標(biāo)的中位數(shù)。評(píng)分準(zhǔn)則：答到求n個(gè)油井Y坐標(biāo)的中位數(shù)，本題即可得滿分；僅說明求中位數(shù)，但未提到是對(duì)Y2分；其它情況酌情考慮。2、【特殊的0-1背包問題】（6分）參考解答：對(duì)于0－1背包問題本來是無法用貪心算法得到最優(yōu)解的，但對(duì)于這類特殊的0－1背包問題，則可以用貪心算法去解。貪心策略如下：首先將各物品依重量遞增序（