算法課件試卷及答案

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

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

3、則對于1in,Vi0=0, 算法設計與分 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回溯算法來求解acfd解向量的eb8回溯算法來求解acfd解向量的形式為（x1x2 ,，xn 剪枝，否則剪枝（即搜索跳過對子樹X的搜索（5分2所得解為 (1,2,3,2,1,1)（5 分三、算法分析題（10分1下面是使用C語言表示的一個遞歸算法：求出FA(n)嗎？簡述你的改進辦法。if (n= if (n= return return 5*A(n-1)6*A(n-else 解答

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

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

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

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