算法設計與分析復習題目及答案-資料下載頁
2025-08-05 10:30本頁面
【正文】 ht）。 Merge(a, b, left, right)。 Copy(a, b, left, right)。 } } Divide 階段的時間復雜性： O(1) Conquer階段的時間復雜性： 2T(n) Combine階段的時間復雜性： Θ(n) 用套用公式法：a=2, b=2, nlog ba = n , f(n)=n, 因為f(n)與nlog ba 同階， ∴T(n) =Θ(nlogn) 設有n=2k個運動員要進行循環(huán)賽,現(xiàn)設計一個滿足以下要求的比賽日程表:每個選手必須與其他n1名選手比賽各一次。每個選手一天至多只能賽一次。循環(huán)賽要在最短時間內(nèi)完成.(1)（4分）循環(huán)賽最少需要進行( n1 )天.(2)（6分）當n=23=8時,請畫出循環(huán)賽日程表: 234567821436587341278564321876556781234658721437856341287654321123456782143658734127856432187655678123465872143785634128765432112345678214365873412785643218765567812346587214378563412876543211234567821436587341278564321876556781234658721437856341287654321 1 2 3 4 5 6 7 考慮用哈夫曼算法來找字符a,b,c,d,e,f 的最優(yōu)編碼。這些字符出現(xiàn)在文件中的頻數(shù)之比為 20:10:6:4:44:16。要求：（1）（4 分）簡述使用哈夫曼算法構(gòu)造最優(yōu)編碼的基本步驟；（2）（5 分）構(gòu)造對應的哈夫曼樹，并據(jù)此給出a,b,c,d,e,f 的一種最優(yōu)編碼。解：1）、哈夫曼算法是構(gòu)造最優(yōu)編碼樹的貪心算法。其基本思想是，首先所有字符對應n 棵樹構(gòu)成的森林，每棵樹只有一個結(jié)點，根權(quán)為對應字符的頻率。然后，重復下列過程n1 次：將森林中的根權(quán)最小的兩棵樹進行合并產(chǎn)生一個新樹，該新樹根的兩個子樹分別是參與合并的兩棵子樹，根權(quán)為兩個子樹根權(quán)之和。2）、根據(jù)題中數(shù)據(jù)構(gòu)造哈夫曼樹如下圖所示。由此可以得出 a,b,c,d,e,f 的一組最優(yōu)的編碼：01,0000,00010,00011, 1,001。[1..n]中找最大最小元素的問題。一個分治算法描述如下：如果n≤2 就直接求解。否則，將序列等分成兩個子序列A[1..n/2]和A[n/2+1..n]，分別找出這兩子序列的最大最小元素x1,y1 和x2,y2；然后據(jù)此求出A[1..n]的最大元素x=max{x1,x2}及最小元素y=min{y1,y2}。請給出該算法計算時間T(n)滿足的遞歸方程，并解方程來確定算法的時間復雜度。假定n=2k（k 為正整數(shù)）。答：算法時間復雜度滿足如下遞歸方程：T(n)=2T(n/2)+2（n2）；T(2)=1。因為 n=2 k（k 為正整數(shù)），所以，T(n)= T(2 k)= 2T(2 k1)+2= 22T(2 k2)+ 22+2?= 2k1T(2)+ 2k2+?+23+22+2= 2k1+?+23+22+2。因此，T(n)=Q(n)。8. 考慮使用動態(tài)規(guī)劃方法求解下列問題：01背包數(shù)據(jù)如下表，求：能夠放入背包的最有價值的物品集合。物品i重量 wi價值 vi承重量 W1w1=2v1=12W=52w2=1v2=103w3=3v3=204w4=2v4=15如設： V(i, j) —— 前 i 個物品中能夠裝入承重量 j 的背包中的最大總價值。請將如下遞推式填寫完整：V(0, j) = 0（0個物品），V(i, 0) = 0（承重量0） V(i, j) = V(i1, j) 第 i 個物品不能裝入， j wi （超重） V(i, j) = max { , } j wi （不超重） i在最優(yōu)子集中 i不在最優(yōu)子集中自底向上：按行或列填寫下表。Vj=012345i=000000010203040Vj=012345i=000000010203040答：V(0, j) = 0（0個物品），V(i, 0) = 0（承重量0）V(i, j) = V(i1, j) 第 i 個物品不能裝入， j wi （超重）V(i, j) = max { vi + V(i1,jwj) , V(i1, j) } j wi （不超重） i在最優(yōu)子集中 i不在最優(yōu)子集中Vj=012345i=000000010203040Vj=012345i=000000010012121212201012222222301012223032401015253037：解空間樹：用回溯法的搜索空間樹：給定n種物品和一背包。物品i的重量是wi，其價值為vi，背包的容量為C。問應如何選擇裝入背包的物品，使得裝入背包中物品的總價值最大?示例：n=3, C=30, w={16, 15, 15}, v={45, 25, 25}求：問題的解空間樹 約束條件如何剪枝？解：問題的解空間樹：約束條件：如何剪枝？： 設r是當前尚未考慮的剩余物品價值總和；Cv是當前價值；bestv是當前最優(yōu)價值。當r＋Cv≤bestv時，可剪去右子樹。11，請畫出用回溯法解n=3的01背包問題的解空間樹和當三個物品的重量為{20, 15, 10}，價值為{20, 30, 25}，背包容量為25時搜索空間樹。答：解空間樹：1111110000000112345781112141531069搜索空間樹：1不可行解價值=20價值=55價值=30價值=25價值=01111000000112811121415131069
教學課件相關(guān)推薦
鄂ICP備17016276號-1