1、計(jì)算機(jī)學(xué)院 2005 /2006 學(xué)年（下）學(xué)期期算法設(shè)計(jì)與分析試卷（A 卷試專(zhuān)年班學(xué)1. 使用記號(hào)表示下列函數(shù)f2 (n)=1in f1 (n)=n3+計(jì)算機(jī)學(xué)院 2005 /2006 學(xué)年（下）學(xué)期期算法設(shè)計(jì)與分析試卷（A 卷試專(zhuān)年班學(xué)1. 使用記號(hào)表示下列函數(shù)f2 (n)=1in f1 (n)=n3+（其中答：(1)f(n（2 分(2) g(n)=(nan)（3分 答：主要區(qū)別如下：圖的深度優(yōu)先搜索是每當(dāng)檢測(cè)一個(gè)結(jié)點(diǎn)u時(shí)到一個(gè)新結(jié)點(diǎn)v，則 的u 的鄰接點(diǎn)，即一次對(duì)u 檢測(cè)完（2 分. ？答：一種隨機(jī)算法的基本思路是Ai=i，1in；然后隨機(jī)地在A中選兩個(gè)元素出來(lái)交換，此操作執(zhí)行n 次。顯

2、然，這種算法的時(shí)間復(fù)雜度為(n)（5分）算法設(shè)計(jì)與分一、簡(jiǎn)答二、解答三、分析四、設(shè)計(jì) (1) 請(qǐng)用文字描述其描述算法的基本思路bd2(2) 用表格展示出主要計(jì)算過(guò)程。計(jì)算的關(guān)鍵步驟2 假定結(jié)18始 (1) 請(qǐng)用文字描述其描述算法的基本思路bd2(2) 用表格展示出主要計(jì)算過(guò)程。計(jì)算的關(guān)鍵步驟2 假定結(jié)18始結(jié)點(diǎn) 1af 6 某點(diǎn)（這里是結(jié)點(diǎn)a）到其它所有點(diǎn)之間的最短路其貪心準(zhǔn)則是，按照路長(zhǎng)由短到長(zhǎng)依次構(gòu)造這n-1條路ce令u表示結(jié)a只經(jīng)過(guò)X中的結(jié)點(diǎn)到達(dá)u的最短路每次選擇u最小的u加入到X中，即結(jié)點(diǎn)a 到u 的最短路長(zhǎng)為u。 令Vij表示在物品1,2,i中挑選物品裝入容量是j的背包中的最大價(jià)值。

3、則對(duì)于1in,Vi0=0, 算法設(shè)計(jì)與分 234迭代次集合X中的元a b e 最短路初始12345 a，b，c a，b， c，e a，b，c，e， 0 2 3 2 3 10 7 2 3 107 0 2 39 7 eb8回溯算法來(lái)求解acfd解向量的eb8回溯算法來(lái)求解acfd解向量的形式為（x1x2 ,，xn 剪枝，否則剪枝（即搜索跳過(guò)對(duì)子樹(shù)X的搜索（5分2所得解為 (1,2,3,2,1,1)（5 分三、算法分析題（10分1下面是使用C語(yǔ)言表示的一個(gè)遞歸算法：求出FA(n)嗎？簡(jiǎn)述你的改進(jìn)辦法。if (n= if (n= return return 5*A(n-1)6*A(n-else 解答

4、解得 （5分（2）算法的特點(diǎn)：子問(wèn)題的求解有大量的重復(fù)。可以改進(jìn)如下：時(shí)算法用(n)時(shí)間即可求出A(n)（5分）算法設(shè)計(jì)與分解答 較即可在三個(gè)元素x1，x2An中找出2大元素，該元素即為A1.n中的2大元素。（5分解得T(n)=2n-3（5分11某廠根據(jù)計(jì)劃安排，擬將n臺(tái)相同的設(shè)備分配給m個(gè)車(chē)間，各車(chē)間獲得這種設(shè)備后，Cij(ij號(hào)車(chē)間將得到的利潤(rùn)，1in，1jm) ?？紤]（1）令Vij表示給車(chē)間1,2,i分配j臺(tái)設(shè)備的最大利潤(rùn)。則0im0jn，有 Vi0=0，V0j=0，Vij=max0 xjVi-1j-x+Cxi（5分）為(mn)（2分）（3）用 i+1，m號(hào)項(xiàng)目的資源總和，1in（3分）

5、算法設(shè)計(jì)與分計(jì)算機(jī)學(xué)院 2005 /2006 學(xué)年（下）學(xué)期期算法設(shè)計(jì)與分析試卷（B 卷試專(zhuān)年班學(xué) 計(jì)算機(jī)學(xué)院 2005 /2006 學(xué)年（下）學(xué)期期算法設(shè)計(jì)與分析試卷（B 卷試專(zhuān)年班學(xué) 計(jì)算時(shí)g(n)= 2n+100n+n!2n3+ 100nlog10n+n。請(qǐng)使用記號(hào)分別表f (n)和g(n)f(n)=（3 分g(n)=(n!)（2分答：其基是，通過(guò)不斷地對(duì)序列進(jìn)行劃分而達(dá)到排序的目標(biāo)。所謂對(duì)序列進(jìn)行劃分就是在序列中選定一個(gè)標(biāo)準(zhǔn)元素v，然后將序列進(jìn)行一遍梳理v的元素放在v之前vv之后，此時(shí)v所在的位置就是序列最終排序后元素v所在的位（2分） 快速排序算法的最好、 及平均情況時(shí)間復(fù)雜度分別是

6、(nlogn)、(n2)(nlogn)（3 分 ) 間復(fù)雜度O(n2)（3分）算MERGERSORT 的時(shí)間復(fù)雜度為(nlogn), 所以，很可能算法MERGERSORT 更快。（2分）如果圖用鄰接表來(lái)表示，則圖的深度優(yōu)先遍歷算法的時(shí)間復(fù)雜度為(n+m)（2分） 策T 。算法設(shè)計(jì)與分一、簡(jiǎn)答二、解答三、分析四、設(shè)計(jì)A9 64CFE5B8 A9 64CFE5B8 873GD解答 75H依次最小生成樹(shù)的n-1每次添加能讓樹(shù)生長(zhǎng)的權(quán)最短的邊。令u表示表示部分已經(jīng)生成的樹(shù)T上的點(diǎn)與T外的點(diǎn)u 7考慮a,b,c,d,e,f 的最優(yōu)編碼。這些字符出現(xiàn)在文件中的頻數(shù) 是，首先所有字符對(duì)應(yīng)n 棵樹(shù)棵子樹(shù)，根權(quán)

7、為（5分）樹(shù)如下（7分 算法設(shè)計(jì)與分c:迭次部分生成樹(shù)T 中點(diǎn)部分生成樹(shù)T 中邊B C D E F G 初始1234567 10 6 7 6 (2) 搜索到一個(gè)解所產(chǎn)生的部分搜索樹(shù)如下圖所示（7分這個(gè)解為(2,4,1,3)（3 分21343431423三、算法分析題（10分10考慮在序列A1.n中找最大最小。一個(gè)分治算法描述如下：如果n2 就直求解。否則，將序列等分成兩個(gè)子序列A1.n/2An/2+1.n，分別找出這兩子序列的最大最小元素x1,y1和x2,y2然后據(jù)此可求出A1.n的最大元素x=maxx1,x2及最小元素y=miny1,y2。試給出該算法計(jì)算時(shí)間T(n)滿足的遞歸方程，并解方程來(lái)確定算法的時(shí)間（k為正整數(shù)。T(n)=T(2k)= 2T(2k-= 22T(2k- （5 分（5 分算法設(shè)計(jì)與分 的算法來(lái)確定在A 中是否有兩x（1）算法的基如下：考慮序列A1.n的最大和最重復(fù)上述過(guò)程，直到找到問(wèn)題的解答，或者縮短的序列長(zhǎng)1 為止（此時(shí)表示原序列中有兩數(shù)之積為 （7 分）*注：只要方法可行，酌情給分故時(shí)間復(fù)雜度為O(n)（3 分）11n個(gè)資源可以投資m個(gè)項(xiàng)目，且已知i個(gè)資源投資到j(luò)的回報(bào)為rij?？紤](a)Vij表示給項(xiàng)目1,2,i