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

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

,,4

，連乘積為AA1 2

。其中Ai

與Ai1

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

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

ak

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

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

d(Xi

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

k

Lk

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

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

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

d(Xi

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