算法設(shè)計與分析c卷及答案

1、算法設(shè)計與分析試題C及答案一 .填空題：（每題4分，共20分）實例特征是指決定問題規(guī)模的那些因素.如兩個nxn矩陣的相乘，則n為實例特征.估算程序運(yùn)行時間的方法通常有兩種，分別為和 （操作計數(shù)方法，統(tǒng)計程序的執(zhí)行步數(shù)）遞歸函數(shù)的兩大基本要素是和 （遞歸方程和邊界條件）給定如下順序搜索算法，則最壞時間復(fù)雜性是O（n）最好時間復(fù)雜性是0（1）int seqSearch（Type *a, int n, Type k）（for（int i=0;in;i+） if （ai=k） return i; return -1;采用回溯法求解問題時，通常采用兩種策略（即兩種剪枝函數(shù)）避免無效的搜索，它們分別是 和

2、。（約束函數(shù)，限界函數(shù)）二.簡答題：（每小題6分，共18分）描述由分治法產(chǎn)生的子問題的基本特征往往是原問題的較小模式，這就為使用遞歸技術(shù)提供了方便。在這種情況下，反復(fù)應(yīng) 用分治手段，可以使子問題與原問題類型一致而其規(guī)模卻不斷縮小，最終使子問題縮小到 很容易直接求出其解。這自然導(dǎo)致遞歸過程的產(chǎn)生。在什么情況下可以應(yīng)用貪心方法獲得問題的最優(yōu)解？a）問題滿足貪心選擇性質(zhì)。即所求問題的整體最優(yōu)解可以通過一系列局部最優(yōu)的選擇， 即貪心選擇來達(dá)到。b）問題滿足最優(yōu)子結(jié)構(gòu)性質(zhì)。即所求問題的最優(yōu)解包含其子問題的最優(yōu)解算法設(shè)計通常有哪些方法？（至少列出4種）并指出哪些算法具有的某個共有性質(zhì)。答：算法設(shè)計方法有分

3、治算法，貪心算法，動態(tài)規(guī)劃算法，歸納算法，回溯算法，分支 限界算法等。分治算法，貪心算法，動態(tài)規(guī)劃算法等算法都具有最優(yōu)子結(jié)構(gòu)性質(zhì)。對下圖中的有向圖，應(yīng)用Dijkstra算法計算從源頂點4到其它頂點間最短路 徑的過程。Sudist1dist2dist3dist5初始4maxintmaxint6161(4,3336maxint61624,3,5536416163(4,3,5,1136416164(1,2,4,3,521641616三.算法分析解答題：（每題20分，共60分）設(shè)有n個活動的集合E=1,2，,n,其中每個活動都要求使用同一資源，并且在同一 時間內(nèi)只有一個活動能使用這一資源。每個活動i都

4、有一個要求使用該資源的起始時 間s和一個結(jié)束時間f ,且s f。如果選擇了活動i，則它在半開時間區(qū)間s , f）iii ii i內(nèi)占用資源。若區(qū)間s, f）與區(qū)間s, f）不相交，則稱活動i與活動j是相容的。i ij ja）給出活動i與活動j是相容的定義。b）描述求解活動安排問題的貪心算法，并分析算法的時間復(fù)雜性。若區(qū)間s, f)與區(qū)間s, f)不相交，則稱活動i與活動j是相容的。iijjvoid GreedySelector(int n, Type s, Type f, bool A) sort(s,f,n);/按照活動的結(jié)束時間的非降序排列。A1=true;int j=1;for (int

5、 i=2;i=fj) Ai=true; j=i; else Ai=false;算法中，如果活動按照其結(jié)束時間的非降序排列，則其時間復(fù)雜性是O(n)；如果沒有 排序，則要考慮為n個活動排序所需要的時間，則其時間復(fù)雜性是O (nlogn)。簡述0-1背包問題和背包問題的差別，描述求解背包問題的貪心算法。給定n種物品和一個背包。物品i的重量是Wi,其價值為Vi，背包的容量為C。應(yīng) 如何選擇裝入背包的物品，使得裝入背包中物品的總價值最大？0-1背包問題：在選擇裝入背包的物品時，對每種物品1只有2種選擇，即裝入背包或 不裝入背包。不能將物品1裝入背包多次，也不能只裝入部分的物品i。背包問題：與0-1背包

6、問題所不同的是在選擇物品i裝入背包時，可以選擇物品i的 一部分，而不一定要全部裝入背包。這2類問題都具有最優(yōu)子結(jié)構(gòu)性質(zhì)，極為相似，但背包問題可以用貪心算法求解，而 0-1背包問題卻不能用貪心算法求解。用貪心算法解背包問題的基本：首先計算每種物品單位重量的價值Vi/Wi，然后，依貪 心選擇策略，將盡可能多的單位重量價值最高的物品裝入背包。若將這種物品全部裝入背 包后，背包內(nèi)的物品總重量未超過C，則選擇單位重量價值次高的物品并盡可能多地裝入背 包。依此策略一直地進(jìn)行下去，直到背包裝滿為止。void Knapsack(int n,float M,float v,float w,float x)(So

7、rt(n,v,w); /按物品單位重量的價值降序排序。int i;for (i=1;i=n;i+) xi=0;float c=M;for (i=1;ic) break;xi=1;c-=wi;if (i=n) xi=c/wi;/部分裝入物品 i。在用回溯法求解0/1背包問題時，假設(shè)n=4,畫出該問題的解空間樹；用偽代碼描述用于剪枝的限界函數(shù)。假設(shè)n=5,物品的重量是W=10,8,9,12,11，價值P=18,12,3,8,20，背包的容量 是40。試用你給出的限界函數(shù)計算i=3時的上界。解答:1）這個問題的解可以表示成0/1數(shù)組住1, x2xn ），依據(jù)wi是否屬于S, xi分別取值1或0。故解空間中共有2n個元素。解空間的結(jié)構(gòu)是一棵完全二叉樹。解空間樹2)限界函數(shù)：double bound(int i)/計算子樹i的上界double cleft = c - cw; / 剩余容量double bound = cp;/以物品單位重量價值遞減序裝入物品while (i = n & wi = cleft) cleft -= wi;bound += pi;i+;/裝滿背包if (i = n) bound += p