曲阜師范大學計算機-算法分析與設計期末復習題

PAGE13/3《算法分析與設計》復習資料（一）一、填空題1.算法的復雜性有復雜性和復雜性之分。2.動態(tài)規(guī)劃算法的基本要素是__________和_________。3.最小生成樹問題中，Prim算法是保證__________的前提下，依次選出權(quán)重較小的邊；Kruskal算法是保證__________的前提下，依次選出權(quán)重較小的邊。4.圓排列問題構(gòu)造的狀態(tài)空間樹是________。5.解決0-1背包問題可以使用動態(tài)規(guī)劃、回溯法和分支限界法，其中不需要排序的是__________，需要排序的是__________和__________。二、簡答題1.簡述算法的一般性質(zhì)。2.簡述分治法的基本思想3.分支限界法設計算法的步驟4.說明貪心選擇性質(zhì)與最優(yōu)子結(jié)構(gòu)性質(zhì)的關(guān)系?！端惴ǚ治雠c設計》復習資料（一）答案一、填空題1.時間空間2.最優(yōu)子結(jié)構(gòu)重疊子問題3.連通無回路4.排列樹 5.動態(tài)規(guī)劃回溯法分支限界法二、簡答題1.簡述算法的一般性質(zhì)。答：（1）輸入：有零個或多個外部量作為算法的輸入。（2）輸出：算法產(chǎn)生至少一個量作為輸出。（3）確定性：組成算法的每條指令清晰、無歧義。（4）有限性：每條指令的執(zhí)行次數(shù)與執(zhí)行時間有限。2.分治法的基本思想是將一個規(guī)模為n的問題分解為k個規(guī)模較小的子問題，這些子問題互相獨立且與原問題相同。遞歸地解這些子問題，然后將各個子問題的解合并得到原問題的解。3.用分支限界法設計算法的步驟是：(1)針對所給問題，定義問題的解空間（對解進行編碼）；(2)確定易于搜索的解空間結(jié)構(gòu)（按樹或圖組織解）；(3)以廣度優(yōu)先或以最小耗費（最大收益）優(yōu)先的方式搜索解空間，并在搜索過程中用剪枝函數(shù)避免無效搜索。4. 貪心選擇性質(zhì)與最優(yōu)子結(jié)構(gòu)性質(zhì)的關(guān)系：（1）滿足貪心選擇性質(zhì)必滿足最優(yōu)子結(jié)構(gòu)性質(zhì)：貪心算法和動態(tài)規(guī)劃算法都要求問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)，這是兩類算法的共同點。雖然能夠應用貪心算法一定能夠應用動態(tài)規(guī)劃法，但是一般來說，貪心算法的效率高于動態(tài)規(guī)劃法。（2）滿足最優(yōu)子結(jié)構(gòu)性質(zhì)未必滿足貪心選擇性質(zhì)：因為原問題盡管滿足最優(yōu)子結(jié)構(gòu)性質(zhì)，即它的最優(yōu)解是由子問題的最優(yōu)解構(gòu)成的，但子問題的最優(yōu)解不一定是用貪心選擇可以做出的。因此，能夠用動態(tài)規(guī)劃法的不一定能夠應用貪心算法?！端惴ǚ治雠c設計》復習資料（二）一、選擇題1.衡量一個算法好壞的標準是().A.運行速度快B.時間復雜度低C.占用空間少D.代碼短2.二分搜索算法是利用（

）實現(xiàn)的算法。A、分治策略

B、動態(tài)規(guī)劃法

C、貪心法

D、回溯法3.下列算法中通常以自頂向下的方式求解最優(yōu)解的是（）。A、分治法B、動態(tài)規(guī)劃法C、貪心法D、回溯法4.FIFO是（）的一搜索方式。A、分支界限法B、動態(tài)規(guī)劃法C、貪心法D、回溯法5.應用Johnson法則的流水作業(yè)調(diào)度采用的算法是（）。A.貪心算法 B.分支限界法 C.分治法 D.動態(tài)規(guī)劃算法6.下面哪種函數(shù)是回溯法中為避免無效搜索采取的策略（）。A.遞歸函數(shù)B.剪枝函數(shù)C.隨機數(shù)函數(shù)D.搜索函數(shù)7.一個算法應該包含如下幾條性質(zhì)，除了________。A．有窮性 B.二義性C.確定性 D.可行性8.分支限界法解裝載問題時，活結(jié)點表的組織形式是（）。A.棧B.最小堆C.最大堆D.數(shù)組9.棋牌覆蓋問題是利用（）實現(xiàn)的算法。A.分治策略B.動態(tài)規(guī)劃法C.貪心算法D.回溯法10.回溯法的效率不依賴于以下哪一個因素？（）。A．產(chǎn)生x[k]的時間； B．滿足顯約束的x[k]值的個數(shù)；C．問題的解空間的形式；D．計算上界函數(shù)bound的時間；11.下面不屬于Java基本數(shù)據(jù)類型的是（）。A、floatB、IntegerC、byteD、long12.常見的兩種分支限界法為（）。A、廣度優(yōu)先分支限界法與深度優(yōu)先分支限界法；B、隊列式（FIFO）分支限界法與堆棧式分支限界法；C、排列樹法與子集樹法；D、隊列式（FIFO）分支限界法與優(yōu)先隊列式分支限界法；13.下列是貪心算法基本步驟的是（）。A、重疊子問題性質(zhì)B、構(gòu)造最優(yōu)解C、貪心選擇性質(zhì)D、定義最優(yōu)解14.優(yōu)先隊列式分支限界法選取擴展結(jié)點的原則是（

）。A、先進先出 B、后進先出 C、結(jié)點的優(yōu)先級 D、隨機15．回溯法在解空間樹T上的搜索方式是().

A.深度優(yōu)先B.廣度優(yōu)先C.最小耗費優(yōu)先D.活結(jié)點優(yōu)先二、填空題1.算法的復雜性有復雜性和復雜性之分。2．程序是

用某種程序設計語言的具體實現(xiàn)。3.動態(tài)規(guī)劃算法的基本要素是__________和_________。4.貪心算法的基本要素是性質(zhì)和性質(zhì)。5.分支限界法主要有分支限界法和分支限界法。6.以深度優(yōu)先方式系統(tǒng)搜索問題解的算法稱為。三、分析計算題如下描述的背包問題，請計算最終裝入背包的最大價值和以及各個物品裝入背包的數(shù)量。背包容量：C=50千克。3件物品。物品1重20千克，價值是100元；物品2重20千克，價值是120元；物品3重30千克，價值是90元?！端惴ǚ治雠c設計》復習資料（二）答案選擇題1-5BACAD6-10BBCAC11-15BDCCA二、填空題1.時間空間2.算法3.最優(yōu)子結(jié)構(gòu)重疊子問題4.貪心選擇最優(yōu)子結(jié)構(gòu)5.隊列式（FIFO）優(yōu)先隊列式6.回溯法三．分析計算題：物品1的單位重量價值為5元/千克，物品2的單位重量價值為6元/千克，物品3的單位重量價值為3元/千克。采用貪心算法解此背包問題。此時，貪心的策略是：每次選擇單位重量價值最大的物品。因此，首先選擇物品2，然后是物品1，最后是物品3，直至將背包裝滿。物品2全部裝入背包，當前背包中價值120元，背包占用20千克，剩余30千克；物品1全部裝入背包，當前背包中價值220元（120元+100元），背包占用40千克，剩余10千克；物品3的1/3被裝入背包，當前背包中價值250元（120元+100元+90元）×1/3，背包占用50千克（裝滿）。因此，最終裝入背包的最大價值為250元，物品1和物品2都全部裝入，分別是20千克和20千克，物品3裝入1/3，是10千克?！端惴ǚ治雠c設計》復習資料（三）一、分析計算題有一個有序表為{1，5，9，10，38，43，57，62，71，80，85，99，100}，當使用二分查找值為85的結(jié)點時，經(jīng)過多少次比較后查找成功并給出過程。二、填空題算法由若干條指令組成的又窮序列，且滿足輸入、、和四個特性。2.分支限界法的兩種搜索方式有、，用一個隊列來存儲結(jié)點的表叫。3.調(diào)用自身的方法叫。4.大整數(shù)乘積算法是用來設計的。5.以廣度優(yōu)先或以最小耗費方式搜索問題解的算法稱為。三、簡答題1.簡述分支限界法的搜索策略2.簡述回溯法解題的通常步驟。3.簡述最優(yōu)子結(jié)構(gòu)性質(zhì)《算法分析與設計》復習資料（三）答案一．分析計算題：有一個有序表為{1，5，9，10，38，43，57，62，71，80，85，99，100}，當使用二分查找值為85的結(jié)點時，經(jīng)過多少次比較后查找成功并給出過程。答：一共要要執(zhí)行四次才能找到值為85的數(shù)。第一次：下限l=1,上限h=13,中點m=(l+h)/2=7，因為85大于中點位置元素值57，所以到后半段繼續(xù)查找；第二次：下限l=8,上限h=13，中點m=10,因為85在于現(xiàn)在中點位置的元素值80，所以到現(xiàn)在的后半段繼續(xù)查找；第三次：下限l=11,上限h=13，中點m=12,因為85小于現(xiàn)在的中點位置的元素值99，所以到前半段繼續(xù)查找；第四次：下限l=11,上限h=11，中點m=11，中點位置元素值正好為85，說明找到了元素85。二、填空題1.輸出確定性有限性2.隊列式(FIFO)分支限界法優(yōu)先隊列式分支限界法活節(jié)點表3.直接或間接遞歸算法4.分治算法5.分支限界法三簡答題1.分支限界法的搜索策略是：在擴展結(jié)點處，先生成其所有的兒子結(jié)點（分支），然后再從當前的活結(jié)點表中選擇下一個擴展結(jié)點。為了有效地選擇下一擴展結(jié)點，加速搜索的進程，在每一個活結(jié)點處，計算一個函數(shù)值（限界），并根據(jù)函數(shù)值，從當前活結(jié)點表中選擇一個最有利的結(jié)點作