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

PAGEPAGE13華南農(nóng)業(yè)大學(xué)期末考試試卷（A卷）2004學(xué)年第二學(xué)期(2005.6)考試科目：算法設(shè)計與分析考試類型：（開卷）考試時間：120分鐘學(xué)號姓名年級專業(yè)題號一二三四總分得分評閱人一、選擇題（30分，每題2分）1、一個算法應(yīng)該包含如下幾條性質(zhì)，除了。（A）二義性 （B）有限性 （C） 正確性 （D）可終止性2、解決一個問題通常有多種方法。若說一個算法“有效”是指。（A）這個算法能在一定的時間和空間資源限制內(nèi)將問題解決（B）這個算法能在人的反應(yīng)時間內(nèi)將問題解決（C）這個算法比其他已知算法都更快地將問題解決（D）A和C3、當(dāng)輸入規(guī)模為n時，算法增長率最小的是。（A）5n （B）20log2n （C）2n2 （D）3nlog3n4、漸進(jìn)算法分析是指。（A）算法在最佳情況、最差情況和平均情況下的代價（B）當(dāng)規(guī)模逐步往極限方向增大時，對算法資源開銷“增長率”上的簡化分析（C）數(shù)據(jù)結(jié)構(gòu)所占用的空間（D）在最小輸入規(guī)模下算法的資源代價5、當(dāng)上下限表達(dá)式相等時，我們使用下列哪種表示法來描述算法代價？（A）大O表示法 （B）大Ω表示法（C）Θ表示法 （D）小o表示法6、采用“順序搜索法”從一個長度為N的隨機(jī)分布數(shù)組中搜尋值為K的元素。以下對順序搜索法分析正確的是。（A）最佳情況、最差情況和平均情況下，順序搜索法的漸進(jìn)代價都相同（B）最佳情況的漸進(jìn)代價要好于最差情況和平均情況的漸進(jìn)代價（C）最佳情況和平均情況的漸進(jìn)代價要好于最差情況的漸進(jìn)代價（D）最佳情況的漸進(jìn)代價要好于平均情況的漸進(jìn)代價，而平均情況的漸進(jìn)代價要好于最差情況的漸進(jìn)代價7、遞歸通常用來實現(xiàn)。（A）有序的線性表 （B）隊列 （C）棧 （D）數(shù)組8、分治法的設(shè)計思想是將一個難以直接解決的大問題分割成規(guī)模較小的子問題，分別解決子問題，最后將子問題的解組合起來形成原問題的解。這要求原問題和子問題。（A）問題規(guī)模相同，問題性質(zhì)相同（B）問題規(guī)模相同，問題性質(zhì)不同（C）問題規(guī)模不同，問題性質(zhì)相同（D）問題規(guī)模不同，問題性質(zhì)不同9、在尋找n個元素中第k小元素問題中，如快速排序算法思想，運用分治算法對n個元素進(jìn)行劃分，如何選擇劃分基準(zhǔn)？下面答案解釋最合理。（A）隨機(jī)選擇一個元素作為劃分基準(zhǔn)（B）取子序列的第一個元素作為劃分基準(zhǔn)（C）用中位數(shù)的中位數(shù)方法尋找劃分基準(zhǔn)（D）以上皆可行。但不同方法，算法復(fù)雜度上界可能不同10、對于0－1背包問題和背包問題的解法，下面答案解釋正確。（A）0－1背包問題和背包問題都可用貪心算法求解（B）0－1背包問題可用貪心算法求解，但背包問題則不能用貪心算法求解（C）0－1背包問題不能用貪心算法求解，但可以使用動態(tài)規(guī)劃或搜索算法求解，而背包問題則可以用貪心算法求解（D）因為0－1背包問題不具有最優(yōu)子結(jié)構(gòu)性質(zhì)，所以不能用貪心算法求解11、關(guān)于回溯搜索法的介紹，下面是不正確描述。（A）回溯法有“通用解題法”之稱，它可以系統(tǒng)地搜索一個問題的所有解或任意解（B）回溯法是一種既帶系統(tǒng)性又帶有跳躍性的搜索算法（C）回溯算法在生成解空間的任一結(jié)點時，先判斷該結(jié)點是否可能包含問題的解，如果肯定不包含，則跳過對該結(jié)點為根的子樹的搜索，逐層向祖先結(jié)點回溯（D）回溯算法需要借助隊列這種結(jié)構(gòu)來保存從根結(jié)點到當(dāng)前擴(kuò)展結(jié)點的路徑12、關(guān)于回溯算法和分支限界法，以下是不正確描述。（A）回溯法中，每個活結(jié)點只有一次機(jī)會成為擴(kuò)展結(jié)點（B）分支限界法中，活結(jié)點一旦成為擴(kuò)展結(jié)點，就一次性產(chǎn)生其所有兒子結(jié)點，在這些兒子結(jié)點中，那些導(dǎo)致不可行解或?qū)е路亲顑?yōu)解的兒子結(jié)點被舍棄，其余兒子加入活結(jié)點表中（C）回溯法采用深度優(yōu)先的結(jié)點生成策略（D）分支限界法采用廣度優(yōu)先或最小耗費優(yōu)先（最大效益優(yōu)先）的結(jié)點生成策略13、優(yōu)先隊列通常用以下數(shù)據(jù)結(jié)構(gòu)來實現(xiàn)。（A）棧（B）堆（C）隊列（D）二叉查找樹14、在分支限界算法中，根據(jù)從活結(jié)點表中選擇下一擴(kuò)展結(jié)點的不同方式可有幾種常用分類，以下描述最為準(zhǔn)確（A）采用FIFO隊列的隊列式分支限界法（B）采用最小值堆的優(yōu)先隊列式分支限界法（C）采用最大值堆的優(yōu)先隊列式分支限界法（D）以上都常用，針對具體問題可以選擇采用其中某種更為合適的方式15、對布線問題，以下是不正確描述（A）布線問題的解空間是一個圖（B）可以對方格陣列四周設(shè)置圍墻，即增設(shè)標(biāo)記的附加方格的預(yù)處理，使得算法簡化對邊界的判定（C）采用廣度優(yōu)先的標(biāo)號法找到從起點到終點的布線方案（這個方案如果存在的話）不一定是最短的（D）采用先入先出的隊列作為活結(jié)點表，以終點b為擴(kuò)展結(jié)點或活結(jié)點隊列為空作為算法結(jié)束條件二、填空題（20分，每空2分）1、一個算法復(fù)雜性的高低體現(xiàn)在計算機(jī)運行該算法所需的時間和存儲器資源上，因此算法的復(fù)雜性有復(fù)雜性和復(fù)雜性之分。2、一個直接或間接調(diào)用自身的算法稱為算法。出自于“平衡子問題”的思想，通常分治法在分割原問題，形成若干子問題時，這些子問題的規(guī)模都大致。3、使用二分搜索算法在n個有序元素表中搜索一個特定元素，在最佳情況下，搜索的時間復(fù)雜性為O（），在最壞情況下，搜索的時間復(fù)雜性為O（）。4、動態(tài)規(guī)劃算法的基本要素是和。5、動態(tài)規(guī)劃算法有一個變形方法。這種方法不同于動態(tài)規(guī)劃算法“自底向上”的填充方向，而是“自頂向下”的遞歸方向，為每個解過的子問題建立了備忘錄以備需要時查看，同樣也可避免相同子問題的重復(fù)求解。6、貪心算法的基本要素是和最優(yōu)子結(jié)構(gòu)性質(zhì)。三、簡答題（32分，五題任選四題，每題8分）1、有4個矩陣，連乘積為。其中與是可乘的，。在這個四矩陣連乘積問題中，不同子問題的個數(shù)為4＋C(4,2)＝10個。請寫出這10個子問題。2、最大子段和問題：問題描述：給定由n個整數(shù)（其中可能有負(fù)數(shù)）組成的序列，求該序列形如的子段和的最大值。當(dāng)所有整數(shù)均為負(fù)整數(shù)時定義其最大子段和為0。依此定義，所求的最優(yōu)值為：動態(tài)規(guī)劃解決方案：記，則對于n個整數(shù)序列的最大子段和問題，即為所求。動態(tài)規(guī)劃遞歸式：問：對于實例：（）＝（－2，11，－4，13，－5，－2），按照前述動態(tài)規(guī)劃遞歸式填充b數(shù)組，算法運行完畢后，請寫出b數(shù)組中的數(shù)值，和最大子段和的值。3、對于如下描述的背包問題，請計算最終裝入背包的最大價值和以及各個物品裝入背包的數(shù)量。背包容量：C＝50千克。3件物品。物品1重20千克，價值100元；物品2重20千克，價值120元；物品3重30千克，價值94、對于符號三角問題，符號三角形的第一行有n個符號。符號可以為“＋”或“－”，以下每一行的符號由上行得到，2個同號下面都是“+”，2個異號下面都是“－”。如下圖所示（第一行有4個符號的符號三角中的其中的一個）：++-+++-++---+-請畫出使用回溯法求解第一行有4個符號（即n＝4）時，解空間樹的形狀。5、在最接近點對問題中，用一條垂直線L：x=m將平面點集分為大致相等的兩個子集S1和S2。設(shè)P1和P2分別表示直線L的左邊和右邊的寬為d的兩個垂直長條區(qū)域，d1和d2分別是S1和S2中最小距離，且設(shè)d=min{d1,d2}。對于P1中任意一個點p，可能和在P2中點q構(gòu)成全平面點集的最接近點對的候選點對，請證明：P2中最多有6對這樣的候選點對。四、算法設(shè)計題（18分，五題任選三題，每題6分）1、【主油管最佳位置】（6分）Olay教授正在為一家石油公司咨詢，該公司正在計劃建造一條由東向西的石油主管道，該管道要穿過一片有n口井的油田，從每口井中都有一條噴油管沿最短路徑與主管道直接相連（噴油管道為南北方向）。給定各個井的X坐標(biāo)和Y坐標(biāo)，Olay教授要如何才能選擇最佳主管道的位置（即：使各噴油管長度之和最?。?、【特殊的0-1背包問題】（6分）在0-1背包問題中，若各物品依重量遞增序排列時，其價值恰好依遞減序排列，對這個特殊的0-1背包問題，設(shè)計一個有效的算法找出最優(yōu)解。（描述你的算法即可，無需證明算法的正確性）3、【Gray碼構(gòu)造問題】（6分）問題描述：“格雷碼”是一個長度為2的n次方的序列，滿足：（a）每個元素都是長度為n比特的串（b）序列中無相同元素（c）連續(xù)的兩個元素恰好只有1個比特不同例如：n=2時，格雷碼為{00，01，11，10}。Gray碼是一種編碼，這種編碼可以避免在讀取時，因各數(shù)據(jù)位時序上的差異造成的誤讀。格雷碼在工程上有廣泛應(yīng)用。但格雷碼不便于運算，請你設(shè)計一種構(gòu)造方法，輸入長度序列n，輸出格雷碼（只要做出一種構(gòu)造方案即可，格雷碼并不唯一）。4、【男女運動員最佳搭配問題】（6分）問題描述：羽毛球隊有男女運動員各n人。給定兩個n×n的矩陣P和Q。P[i][j]是男運動員i和女運動員j配合組成混合雙打的競賽優(yōu)勢，Q[i][j]是女運動員i和男運動員j配合的競賽優(yōu)勢。由于技術(shù)配合或心理狀況等各種因素的影響，P[i][j]并不一定等于Q[j][i]。采用回溯法設(shè)計一個算法，計算男女運動員最佳搭配的配對法，使得各組男女雙方競賽優(yōu)勢乘積的總和達(dá)到最大。5、【優(yōu)美打印問題】（6分）問題描述：考慮在一臺打印機(jī)上優(yōu)美地打印一段文章的問題。輸入的文章正文是由長度為L1，L2，…，Ln的n個英文單詞構(gòu)成的序列。我們希望將這段文章分若干行打印出來，每行的最大長度為m，且“優(yōu)美度”的標(biāo)準(zhǔn)如下：如果某一行包含從單詞i到單詞j，且每兩個單詞間留一空格，行首無空格，則在行末多余的空格數(shù)為：（解釋：這個公式如何得到呢？由于某一行包含單詞i到單詞j，且每兩個單詞間留一空格，因此單詞間的空格數(shù)為j－i，又由于從第i個單詞到第j個單詞的長度和為，因此行末多余的空格為。）不同的斷行（即切斷從單詞i到單詞j形成一行）的方式，將可能產(chǎn)生不同的“優(yōu)美度”（即除最后一行的所有行的行末多余空格總和）。我們希望除最后一行的所有行中，行末多余空格的總和最小。請用動態(tài)規(guī)劃算法設(shè)計出一個優(yōu)美的打印出一段有n個單詞的文章的方案。解題思路提示：由于必須打印完n個單詞且每行打印的單詞是連續(xù)的，因此，我們從第n個單詞開始，依次考慮填一個單詞（單詞n），填兩個單詞（單詞n-1，單詞n），……，填n個單詞（單詞1，單詞2，…，單詞n）的打印方案。由于單詞填入的方式是按單詞序號遞減的順序進(jìn)行的，因此填入單詞i到單詞n后的行末空格數(shù)的總和應(yīng)為當(dāng)前行的行末空格數(shù)加后面行的行末空格數(shù)的和。我們的目標(biāo)是使它最小。設(shè)r[i]——填入單詞i到單詞n后，所有被填行的行末空格數(shù)總和的最小值。顯然，r[i]的動態(tài)規(guī)劃遞歸式可以由以上思路得到。另外，我們專門設(shè)置了一張記憶表k[i]（1≤i≤n+1），記下使得r[i]最小的j值，表示填單詞i到單詞n的最佳方案中，第一行應(yīng)填單詞i到單詞j（j即是k[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+l]，…，r[n+l]這些子問題。要使r[i]最小，必須使這些子問題的值最小，因此符合動態(tài)規(guī)劃程序設(shè)計要求的“最優(yōu)子結(jié)構(gòu)”和“重疊子問題”兩個要素。我們可以按自下而上的方式求解，充分利用了重疊子問題。最后求出的r[1]即為最優(yōu)“優(yōu)美打印方案”中行末空格數(shù)的總和；從單詞1出發(fā)，順著記憶表K的指示，可順序打印出文章的各行。問題和任務(wù)：根據(jù)以上的算法提示，請寫出r[i]的動態(tài)規(guī)劃遞歸式，并定義遞歸的邊界。2004學(xué)年第一學(xué)期考試科目：算法設(shè)計與分析考試類型：（開卷）考試時間：120分鐘學(xué)號姓名年級專業(yè)題號一二三四總分得分評閱人一、選擇題（30分，每題2分）1A2D3B4B5C6B7C8C9D10C11D12A13B14D15C二、填空題（20分，每空2分）1、時間 空間2、遞歸 相等3、1 logn （或）4、最優(yōu)子結(jié)構(gòu)性質(zhì) 子問題重疊性質(zhì)5、備忘錄方法6、貪心選擇性質(zhì)三、簡答題（32分，五題任選四題，每題8分）1、子問題如下所列：2、最大子段和值：3、物品1的單位重量價值為50元/千克；物品2的單位重量價值為60元/千克；物品3的單位重量價值為30元/千克。采用貪心算法解此背包問題。此時，貪心的策略是：每次選擇單位重量價值最大的物品。因此，首先選擇物品2，然后是物品1，最后是物品3，直至將背包裝滿。物品2全部裝入背包，當(dāng)前背包中價值120元，背包占用20千克，剩余30千克；物品1全部裝入背包，當(dāng)前背包中價值220元（120元＋100元），背包占用40千克，剩余1物品3的1/3被裝入背包，當(dāng)前背包中價值250元（120元＋100元＋90元×1/3），背包占用50千克因此，最終裝入背包的最大價值為250元，物品1和物品2都全部裝入，分別是20千克和20千克，物品3裝入1/3，是10千克。4、第一行4個符號（即n＝4）時，解空間樹是一棵完全二叉樹。5、證明：根據(jù)鴿籠原理：如果n+1只鴿子飛入n個籠子中，那么至少有一個籠子里包含兩只或兩只以上的鴿子。將矩形R的長為2d的邊3等分，將它的長為d的邊2等分，由此導(dǎo)出6個(d/2)×(2d/3)的矩形（如下圖a所示）。若矩形R中有多于6個S中的點，則由鴿籠原理易知至少有一個(d/2)×(2d/3)的小矩形中有2個以上S中的點。設(shè)u，v是位于同一小矩形中的2個點，則：distance(u,v)≤5d/6<d。這與d的意義相矛盾。即，矩形R中最多只有6個S中的點。上圖b中就是矩形R中恰有6個S中的點的極端情形。四、算法設(shè)計題（18分，五題任選三題，每題6分）1、【主油管最佳位置】（6分）參考解答：這是中位數(shù)的應(yīng)用問題。在順序統(tǒng)計的問題中，中位數(shù)的應(yīng)用最廣，例如在X軸上有n個點，由左到右依次排列為X1，X2，…，Xn。我們希望在x軸上尋找一點Xp，使得Xp與各點距離之和最小。這個問題可以歸結(jié)為中位數(shù)問題。即：當(dāng)n為奇數(shù)時，Xp為，否則，Xp為。從這個例子出發(fā)，本題求主油管道的問題也是類似的。由于主管道由東向西，因此，要使連接油井和主油管道的噴井管道最短，噴井管道必須南北走向，與主管道垂直，即主管道的最優(yōu)位置應(yīng)為一條Y＝Y(jié)k的水平線，問題是Yk如何確定。為了使Yk與各油井的Y坐標(biāo)Y1，Y2，…，Yn間的距離和最短，我們將Y1，…，Yn由小到大排序，選擇最中間的那個點作為Yk，（若油井為奇數(shù)，則取第(n+1)/2小的Y坐標(biāo)作為Yk，若油井為偶數(shù)，則取第n/2小的Y坐標(biāo)值與第(n/2+1)小的Y坐標(biāo)值的平均數(shù)作為Yk的值。顯然，確定主油管道的最佳位置，實際上就是求n個油井的Y坐標(biāo)的中位數(shù)。評分準(zhǔn)則：答到求n個油井Y坐標(biāo)的中位數(shù)，本題即可得滿分；僅說明求中位數(shù)，但未提到是對Y坐標(biāo)求取，扣2分；其它情況酌情考慮。2、【特殊的0-1背包問題】（6分）參考解答：對于0－1背包問題本來是無法用貪心算法得到最優(yōu)解的，但對于這類特殊的0－1背包問題，則可以用貪心算法去解。貪心策略如下：首先將各物品依重量遞增序（即也是價值遞減序）排列，然后依照價值遞減順序選擇物品裝入背包，直到背包裝不下下一件物品為止。這里貪心算法的貪心選擇策略是：每次總是選擇價值最大（同時重量也最小）的