算法設(shè)計(jì)與分析2007試卷答案

1、1、 2、 3、 4、 5、二、填空題（每空 1 分，共 20 分）1、（1）輸出2、（3）輾轉(zhuǎn)相除法3、（5）尾遞歸 4、（7） (logn)5、（11）（2） 確定性 （4） 最大公約數(shù) （6） 迭代 （8） O(logn) （9） (logn) （10） (logn) 3、Kruskal 算法每次選取一條邊 e=(u,v)，加入到正在構(gòu)造中的最小代價(jià)生成樹 F=(U,S)時(shí)，是否必須要判斷邊 e 加入邊集S 后S e 是否包含回路？為什么？如果包含回路，應(yīng)該如何處理？（共 5 分）必須判斷。（2 分）因?yàn)?Kruskal 算法構(gòu)造最小代價(jià)生成樹的過程中，是按邊權(quán)值的非減次序，從原圖中選擇

2、一條代價(jià)最小的邊e=(u,v)加入到正在構(gòu)建的生成樹邊集S 中。為了確保最終得到生成樹，每選擇一條邊時(shí)，都需要判定邊集Se 是否包含回路。如果形成回路，則應(yīng)該舍棄該邊，繼續(xù)選下一條邊。（直到 S 中包含n-1 條邊時(shí)，得到原圖的一棵最小代價(jià)生成樹。）（3 分）4、若用dkij表示從結(jié)點(diǎn) i 到結(jié)點(diǎn) j 的路徑上，只允許包含結(jié)點(diǎn)不大于 k 的結(jié)點(diǎn)時(shí)，所有可能路徑中的最短路徑長度。請(qǐng)寫出(Floyd)算法的求解遞推表達(dá)式。（共 5 分）d-1ij=（2）當(dāng) n=4 時(shí)，該顯式約束條件下的狀態(tài)空間樹如下圖。請(qǐng)畫出回溯法求解得到第一個(gè)可行解時(shí)，實(shí)際生成的狀態(tài)空間樹部分。（共 6 分）解空間大小為 n!

3、。實(shí)際生成的狀態(tài)空間樹為：（2 分）（4 分）1x0=0 x0=12x1=1x1=218x1=0 x1=2x1=3x1=33B8BB16BBB215B2ans五、證明題（10 分）證明：求多段圖中從源點(diǎn) s 到匯點(diǎn) t 的最短路徑問題，具有最優(yōu)子結(jié)構(gòu)特性。（反證法：）假定(s,v2,v3,.,vk-1,t)是一條從 s 到 t 的最短路徑，并假定在初始狀態(tài)（源點(diǎn) s）已經(jīng)作出達(dá)到 v2 的決策，即 v2 是從初始狀態(tài) s 由初始決策所到達(dá)的狀態(tài)。則v2 是原問題的一個(gè)子問題的初始狀態(tài)，求解此子問題就是尋找一條從 v2 到 t 的最短路徑。如果(s,v2,v3,.,vk-1,t)是一條從 s 到 t 的最短路徑，那么(v2,v3,.,vk-1,t)必定是一條從 v2 到 t 的最短路徑。若不然，另有(v2,q3,.,qk-1,t)是從 v2 到 t 的最短路徑，那么路徑(s,v2,q3,.,qk-1,t)顯然比(s,v2,v3,vk-1,t)更短，與假設(shè)。因此，多段圖問題的最優(yōu)子結(jié)構(gòu)性質(zhì)成立。六、算法程序題（每空 2 分，共 10 分）1、 （1）RandomizedPartition(left,right)（2）Partition (left,