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

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