算法設(shè)計(jì)與分析復(fù)習(xí)試題

一、選擇題（5題/3分，總15分）循環(huán)賽日程表問(wèn)題的相關(guān)敘述。每個(gè)人與n-1個(gè)選手比賽，每天只能比賽一場(chǎng)，比賽一共進(jìn)行n-1天算法運(yùn)行時(shí)所需要占用的存儲(chǔ)空間有？算法本身占有的存儲(chǔ)空間，輸入輸出占有的數(shù)據(jù)，運(yùn)行時(shí)輔助變量占有的存儲(chǔ)空間。動(dòng)態(tài)規(guī)劃法的求解步驟分析最優(yōu)解得性質(zhì)，規(guī)劃定義最優(yōu)值，從底向上計(jì)算最優(yōu)值。解空間樹(shù)是排列樹(shù)的問(wèn)題有?；屎髥?wèn)題，旅行商問(wèn)題，批處理作業(yè)調(diào)度問(wèn)題，圓排列問(wèn)題，電路板排列問(wèn)題。分治法的步驟分解治理（求解各個(gè)子問(wèn)題）合并就會(huì)場(chǎng)安排問(wèn)題，貪心法的最佳貪心策略每次從剩下未安排的會(huì)議中選擇開(kāi)始時(shí)間最早的會(huì)議安排。每次從剩下的未安排的中選擇時(shí)間最短的會(huì)議安排。選擇最早結(jié)束時(shí)間。快速排序法基準(zhǔn)元素的選取方法第一個(gè)元素，中間位置的元素，取最后一個(gè)元素，三者取中原則，取位于lowhigh之間的隨機(jī)數(shù)k。滿足滿m叉樹(shù)的問(wèn)題有？n皇后問(wèn)題，圖的m著色問(wèn)題，最小重量機(jī)器設(shè)計(jì)問(wèn)題。分支限界法的解題步驟定義問(wèn)題的解空間，確定問(wèn)題解空間的組織結(jié)構(gòu)，收索解空間。事前分析法相關(guān)的影響因素有算法本身，問(wèn)題規(guī)模，輸入序列用分治法求解的問(wèn)題一般需要具備一些特征，主要有？問(wèn)題的規(guī)?？s小到一定程度就可以輕易解決，問(wèn)題可以分為若干規(guī)模較小的相同子問(wèn)題，問(wèn)題分解的子問(wèn)題相互獨(dú)立，子問(wèn)題不包含公共的子問(wèn)題。二、填空題（5題/3分，總15分）1．給定一個(gè)有向帶權(quán)圖G=(V，E)，其中每條邊的權(quán)是一個(gè)非負(fù)實(shí)數(shù)，另外，給定V中的一個(gè)頂點(diǎn)，稱為源點(diǎn)?，F(xiàn)在要計(jì)算從源點(diǎn)到所有其它各個(gè)頂點(diǎn)的最短路徑長(zhǎng)度，這里的路徑長(zhǎng)度是指路徑上經(jīng)過(guò)的所有邊上的權(quán)值之和，這個(gè)問(wèn)題通常稱為單源最短路徑問(wèn)題。2．采用回溯法可以求解0-1背包問(wèn)題，其解空間的形式為：（x1,x2,…,xn）或n元組。3．當(dāng)所給的問(wèn)題是從n個(gè)元素的排列中找出滿足某種性質(zhì)的一個(gè)排列時(shí)，相應(yīng)的解空間樹(shù)稱為排列樹(shù)。4．一個(gè)正在生成孩子的結(jié)點(diǎn)稱為擴(kuò)展結(jié)點(diǎn)。5．子集樹(shù)是用回溯法解題時(shí)經(jīng)常遇到的一種典型的解空間樹(shù)。當(dāng)所給的問(wèn)題是從n個(gè)元素組成的集合S中找出滿足某種性質(zhì)的一個(gè)子集時(shí)，相應(yīng)的解空間樹(shù)稱為子集樹(shù)。6．當(dāng)所給問(wèn)題的n個(gè)元素中每一個(gè)元素均有m種選擇，要求確定其中的一種選擇，使得對(duì)這n個(gè)元素的選擇結(jié)果組成的向量滿足某種性質(zhì)，即尋找滿足某種特性的n個(gè)元素取值的一種組合，這類問(wèn)題的解空間樹(shù)稱為滿m叉樹(shù)。7．一個(gè)自身已生成但其孩子還沒(méi)有全部生成的結(jié)點(diǎn)稱為活結(jié)點(diǎn)8．回溯法中，對(duì)于問(wèn)題的一個(gè)實(shí)例，解向量滿足顯約束的所有n元組構(gòu)成了該實(shí)例的一個(gè)解空間9．分支限界法有兩種：隊(duì)列式分支限界法和優(yōu)先隊(duì)列式分支限界法。10．分支限界法采用的是寬度優(yōu)先搜索。11．時(shí)間復(fù)雜性的度量方法通常有兩種：事后統(tǒng)計(jì)法和事前分析估算法12．一個(gè)所有孩子已經(jīng)生成的結(jié)點(diǎn)稱做死結(jié)點(diǎn)13．在最小生成樹(shù)的生成方法中，Kruskal算法從邊的角度出發(fā)，每一次將圖中的權(quán)值最小的邊取出來(lái)，在不構(gòu)成環(huán)的情況下，將該邊加入最小生成樹(shù)。三、判斷題（10題/2分，總20分）1．分治法字面上的解釋是分而治之，就是把一個(gè)復(fù)雜的問(wèn)題分成兩個(gè)或更多的相同子問(wèn)題，子問(wèn)題相互獨(dú)立，如果子問(wèn)題還是不容易解決，再把子問(wèn)題分成更小的子問(wèn)題…，直到最后各個(gè)子問(wèn)題可以簡(jiǎn)單地直接求解，對(duì)各個(gè)子問(wèn)題遞歸求解，將子問(wèn)題的解進(jìn)行合并即得原問(wèn)題的解。Y2．動(dòng)態(tài)規(guī)劃法要求將大問(wèn)題分解成規(guī)模較小的子問(wèn)題，經(jīng)分解得到的各個(gè)子問(wèn)題往往不是相互獨(dú)立的。在求解過(guò)程中，將已解決的子問(wèn)題的解進(jìn)行保存，在需要時(shí)可以輕松找出。采用自底向上的遞歸，由子問(wèn)題的解得到原問(wèn)題的解。Y3．貪心法可以理解為以逐步的局部最優(yōu)，達(dá)到最終的全局最優(yōu)，而且不一定能達(dá)到全局最優(yōu)。Y4．子集樹(shù)中的所有非葉子結(jié)點(diǎn)均有左右兩個(gè)分支，左分支為1，右分支為0。Y5．回溯法是一種“能進(jìn)則進(jìn)，進(jìn)不了則換，換不了則退”的搜索方法。Y6．最長(zhǎng)公共子序列問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。）Y7．凸多邊形最優(yōu)三角剖分問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。Y8．時(shí)間復(fù)雜性是對(duì)算法運(yùn)行時(shí)間的長(zhǎng)短的度量。N9．貪心法是根據(jù)貪心策略來(lái)逐步構(gòu)造問(wèn)題的解，該算法的好壞關(guān)鍵在于正確地選擇貪心策略。Y10．當(dāng)所給的問(wèn)題是從n個(gè)元素的排列中找出滿足某種性質(zhì)的一個(gè)排列時(shí)，相應(yīng)的解空間樹(shù)稱為排列樹(shù)。Y11．子集樹(shù)的深度等于問(wèn)題的規(guī)模Y12．隱約束也叫剪枝函數(shù)，一般有兩種：約束條件和限界條件。Y13．加工順序問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。Y14．包含元素最多的公共子序列即為最長(zhǎng)公共子序列。Y15．回溯法問(wèn)題的解是一個(gè)n元組(x1,x2,…,xn)。Y16．子集樹(shù)中，從根結(jié)點(diǎn)到葉子結(jié)點(diǎn)的路徑表示一個(gè)可行解。Y17．針對(duì)問(wèn)題的可能解是有限種的情況，逐一檢查所有可能的情況，從中找到問(wèn)題真正的解。Y18．子集樹(shù)是用回溯法解題時(shí)經(jīng)常遇到的一種典型的解空間樹(shù)。當(dāng)所給的問(wèn)題是從n個(gè)元素組成的集合S中找出滿足某種性質(zhì)的一個(gè)子集時(shí)，相應(yīng)的解空間樹(shù)稱為子集樹(shù)。Y19．動(dòng)態(tài)規(guī)劃法與分治法和貪心法類似，都是把待求解的問(wèn)題分解為更小的、相同的子問(wèn)題，然后對(duì)子問(wèn)題進(jìn)行求解，最終產(chǎn)生一個(gè)整體最優(yōu)解。N20．快速排序法通過(guò)一趟掃描將待排序的元素分成獨(dú)立的三個(gè)序列。N四、簡(jiǎn)答題（5題/10分，總50分）1會(huì)場(chǎng)安排問(wèn)題。設(shè)有n個(gè)會(huì)議的集合C={1,2,…,n}，其中每個(gè)會(huì)議都要求使用同一個(gè)資源（如會(huì)議室），而在同一時(shí)間內(nèi)只能有一個(gè)會(huì)議使用該資源。每個(gè)會(huì)議i都有要求使用該資源的起始時(shí)間bi和結(jié)束時(shí)間ei，且bi<ei。如果選擇了會(huì)議i使用會(huì)議室，則它在半開(kāi)區(qū)間[bi,ei)內(nèi)占用該資源。如果[bi,ei)與[bj,ej)不相交，則稱會(huì)議i與會(huì)議j是相容的。也就是說(shuō)，當(dāng)biej或bjei時(shí)，會(huì)議i與會(huì)議j相容。會(huì)場(chǎng)安排問(wèn)題要求在所給的會(huì)議集合中選出最大的相容活動(dòng)子集，也即盡可能地選擇更多的會(huì)議來(lái)使用資源。設(shè)有11個(gè)會(huì)議等待安排，如下表所示，用貪心法找出滿足要求的會(huì)議集合（用箭頭畫出即可）。會(huì)議i1234567891011開(kāi)始時(shí)間bi130535688212結(jié)束時(shí)間ei45678910111213141設(shè)G=(V，E)是無(wú)向連通帶權(quán)圖，V={1,2,…,6}，如下圖所示，根據(jù)貪心策略寫出用Prim算法求解最小生成樹(shù)的過(guò)程。（1）（2）（3）（4）（5）（6）4.圖的m著色問(wèn)題。給定無(wú)向連通圖G=(V，E)和3種不同的顏色。用這些顏色為圖G的各頂點(diǎn)著色，每個(gè)頂點(diǎn)著一種顏色。要求有邊相連的兩個(gè)頂點(diǎn)著不同顏色，找出所有不同的著色方法。要求給出最終的搜索樹(shù)。2．用分治法求解循環(huán)賽安排問(wèn)題。設(shè)有4個(gè)運(yùn)動(dòng)員要進(jìn)行乒乓球循環(huán)賽，現(xiàn)要設(shè)計(jì)一個(gè)滿足以下要求的比賽日程表：（1）每個(gè)選手必須與其它3個(gè)選手各賽一次；（2）每個(gè)選手一天只能比賽一次；（3）循環(huán)賽一共需要進(jìn)行7天。要求：安排4個(gè)選手的比賽日程表。4．有7個(gè)工件，它們?cè)诘谝慌_(tái)機(jī)器和第二臺(tái)機(jī)器上的處理時(shí)間分別為：[t11,t12,t13,t14,t15,t16,t17]=[3,8,10,12,6,9,15][t21,t22,t23,t24,t25,t26,t27]=[7,2,6,18,3,10,4]求7個(gè)工件的最優(yōu)加工順序。要求：用動(dòng)態(tài)規(guī)劃法按照算法步驟，求出問(wèn)題的解。（1）N1={1,4,6}，N2={2,3,5,7}（2）將N1中工件按t1i非減序排序N1={1,6,4}，將N2中工件按t2i非增序排序N2={3,7,5,2}（3）N1中工件接N2中工件N1N2={1,6,4,3,7,5,2}。5．布線問(wèn)題。布線問(wèn)題就是在N×M的方格陣列中，指定一個(gè)方格的中點(diǎn)為a，另一個(gè)方格的中點(diǎn)為b，如圖所示，問(wèn)題要求找出a到b的最短布線方案（即最短路徑）。布線時(shí)只能沿直線或直角，不能走斜線，黑色的單元格代表不可以通過(guò)的封鎖方格。ab要求給出搜索結(jié)果，并構(gòu)造問(wèn)題的最優(yōu)解。5．用優(yōu)先隊(duì)列式分支限界法求解0-1背包問(wèn)題：n=4，W=[3，5，2，1]，v=[9，10，7，4]，C=7。要求給出最終的搜索結(jié)果。3用二分查找算法在有序序列（6，12，15，18，22，25，28，35，46，58，60）中查找元素12，畫出每次劃分的示意圖。3.已知待排序序列A=<8，3，2，9，7，1，5，4>，采用合并排序法進(jìn)行排序，畫出合并排序的過(guò)程示意圖。6.用分支限界法求解旅行商問(wèn)題。如圖所示，n=4，城市1為售貨員所在的住地城市，畫出最終的搜索樹(shù)。2．已知某系統(tǒng)在通信聯(lián)絡(luò)中只可能出現(xiàn)8種字符，分別為a，b，c，d，e，f，g