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

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