計(jì)算機(jī)09級(jí)《算法設(shè)計(jì)與分析》中考試卷1

1、計(jì)算機(jī)科學(xué)技術(shù)學(xué)院09級(jí)算法設(shè)計(jì)與分析中考試題一、 簡(jiǎn)答題（共3小題，第1小題2分，第2，3小題4分，總計(jì)10分）1.(2分) 請(qǐng)用英文寫(xiě)出兩種以上能求解0-1背包問(wèn)題的設(shè)計(jì)算法策略。2.(4分) 請(qǐng)敘述動(dòng)態(tài)規(guī)劃法的基本思想。3.(4分) 請(qǐng)說(shuō)明：(1)優(yōu)先隊(duì)列可用什么數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)？(2)優(yōu)先隊(duì)列插入算法基本思想？(3)優(yōu)先隊(duì)列插入算法時(shí)間復(fù)雜度？二、填空題 （共10個(gè)空，每空1分，總計(jì)10分）1遞歸的快速排序算法在最好情況下divide階段所花的時(shí)間是 ，conquer階段所花的時(shí)間是 ，算法的時(shí)間復(fù)雜度是 。3背包問(wèn)題可用 ， 等策略求解。4用動(dòng)態(tài)規(guī)劃算法計(jì)算矩陣連乘問(wèn)題的最優(yōu)值所花的時(shí)間

2、是 ， 子問(wèn)題空間大小是 。5n個(gè)物品的0-1背包問(wèn)題可用 法求解，其解空間樹(shù)中葉子結(jié)點(diǎn)個(gè)數(shù)是 ，解空間樹(shù)中每個(gè)內(nèi)結(jié)點(diǎn)的孩子數(shù)是 。三、計(jì)算題（共4小題，第1,2,3小題10分，第4小題15分，總計(jì)45分）1(10分) 給定兩個(gè)序列X=B,C,D,A，Y=A,B,C,B，請(qǐng)按下列動(dòng)態(tài)規(guī)劃算法求其最長(zhǎng)公共子序列。要求分別填寫(xiě)s矩陣和m矩陣，并標(biāo)示出怎樣求其最長(zhǎng)公共子序列。填空。 void LCSLength(int m, int n, char *x, char *y, int *m, Type *s) int i, j; for(i=0; i<=m; i+) mi0=0; for(j=0

3、; j<=n; j+) m0j=0; for(i=1; i<=m; i+) for(j=1; j<=n; j+) if (xi=yj) mij= mi-1 j-1+1; sij=; else if (mi-1j> mij-1) mij= mi-1j; sij=; else mij= mij-1; sij=; void LCS(int i, int j, char *x, Type *s) if( (i=0) | (j=0) ) return ; if (sij=) LCS(i-1, j-1, x, s); cout<< xi; else if (sij=)

4、LCS(i-1, j, x, s); else LCS(i, j-1, x, s); s矩陣 最長(zhǎng)公共子序列: m矩陣 2（10分）對(duì)下列各組函數(shù)f (n) 和g (n)，確定f (n) = O (g (n) 或f (n) =(g (n)或f(n) =(g(n)，并簡(jiǎn)要說(shuō)明理由。(1) f(n)= log n3； g (n)= (2) f(n)= n!； g(n)= 3n (3) f(n)=1000； g(n)=log100 (4) f(n)=5n； g(n)=7n(5) f(n)= 2n； g(n)= n53（10分）對(duì)下圖所示的連通網(wǎng)絡(luò)G，用克魯斯卡爾(Kruskal)算法求G的最小生成樹(shù)

5、T,請(qǐng)寫(xiě)出在算法執(zhí)行過(guò)程中，依次加入T的邊集TE中的邊。說(shuō)明該算法的基本思想及貪心策略，并簡(jiǎn)要分析算法的時(shí)間復(fù)雜度。123456181117151921266794考慮n=3的批處理作業(yè)調(diào)度實(shí)例：tji機(jī)器1機(jī)器2作業(yè)1111作業(yè)231作業(yè)321其中tji是作業(yè)Ji需要在機(jī)器j上處理的時(shí)間。對(duì)于給定的3個(gè)作業(yè)，制定一個(gè)最佳作業(yè)調(diào)度方案，使其完成時(shí)間和達(dá)到最小。要求：（1）畫(huà)出該問(wèn)題的解空間樹(shù)； （5分）（2）寫(xiě)出該問(wèn)題的剪枝策略(即限界條件)，要求只保留第一個(gè)最優(yōu)解； （2分）（3）按回溯法搜索解空間樹(shù)，并用剪枝策略對(duì)解空間樹(shù)中該剪枝的位置打´； （5分）（4）給出最優(yōu)解及最優(yōu)值。

6、（3分）四、算法填空題（共1小題，總計(jì)15分）（15分）用分治策略設(shè)計(jì)的求一維空間上點(diǎn)集S中最接近點(diǎn)對(duì)的算法如下。int Cpair(int S , int l, int r)/算法的功能是確定數(shù)組S中l(wèi), r區(qū)間的最近點(diǎn)對(duì)距離 if (l>=r) ruturn ; / 注釋?zhuān)篲 _ _int m=selec(S,l,r,(r-l)/2); / 找出中位數(shù)m，所花時(shí)間：_ _ _i= partition(a, l, r, m）;/ 用中位數(shù)m將數(shù)組分為兩段, 所花時(shí)間：_ _d1=Cpair(S, l, i) ; / 求數(shù)組S中l(wèi), i區(qū)間的最近點(diǎn)對(duì)距離,所花時(shí)間：_ _d2=_ _ ; p=max(S, l, i); / 求數(shù)組S中l(wèi), i區(qū)間的最大數(shù)，所花時(shí)間：_ _q= min(S, i+1, r); / 求數(shù)組S中i+1，r區(qū)間的最小數(shù)d=min1(d1,d2,q-p); / 求三者中最小數(shù)，所花時(shí)間：_ _ return d ; / 返回最近點(diǎn)對(duì)的距離divide階段所花的時(shí)間：_ _conquer階段所花的時(shí)間：_ _combine階段所花的時(shí)間：_ _算法時(shí)間復(fù)