算法考試試題及答案

1、一、 填空題（本題10分，每空1分）1、 算法的復(fù)雜性是 的度量，是評價算法優(yōu)劣的重要依據(jù)。2、 設(shè)n為正整數(shù)，利用大“O(·)”記號，將下列程序段的執(zhí)行時間表示為n的函數(shù)，則下面程序段的時間復(fù)雜度為 。i=1; k=0;while(i<n) k=k+10*i;i+;  3、 計算機(jī)的資源最重要的是 和 資源。因而，算法的復(fù)雜性有 和 之分。4、 f(n)= 6×2n+n2，f(n)的漸進(jìn)性態(tài)f(n)= O(    )5、 遞歸是指函數(shù) 或者 通過一些語句調(diào)用自身。6、 分治法的基本思想是將一個規(guī)模為n的問題分解為k個規(guī)模較小的

2、子問題，這些子問題互相 且與原問題相同。二、選擇題（本題20分，每小題2分）1、分支限界法與回溯法都是在問題的解空間樹T上搜索問題的解,二者( )。A.求解目標(biāo)不同,搜索方式相同 B.求解目標(biāo)不同,搜索方式也不同C.求解目標(biāo)相同,搜索方式不同 D.求解目標(biāo)相同,搜索方式也相同2、回溯法在解空間樹T上的搜索方式是( )。A.深度優(yōu)先 B.廣度優(yōu)先 C.最小耗費優(yōu)先 D.活結(jié)點優(yōu)先3、在對問題的解空間樹進(jìn)行搜索的方法中,一個活結(jié)點最多有一次機(jī)會成為活結(jié)點的是( )。A.回溯法 B.分支限界法 C.回溯法和分支限界法 D.回溯法求解子集樹問題4、以下關(guān)于判定問題難易處理的敘述中正確的是( )。A.可

3、以由多項式時間算法求解的問題是難處理的B.需要超過多項式時間算法求解的問題是易處理的C.可以由多項式時間算法求解的問題是易處理的D.需要超過多項式時間算法求解的問題是不能處理的5、設(shè)f(N),g(N)是定義在正數(shù)集上的正函數(shù),如果存在正的常數(shù)C和自然數(shù)N0,使得當(dāng)NN0時有f(N)Cg(N),則稱函數(shù)f(N)當(dāng)N充分大時有上界g(N),記作f(N)=O(g(N),即f(N)的階( )g(N)的階。A.不高于 B.不低于 C.等價于 D.逼近6、對于含有n個元素的子集樹問題,最壞情況下其解空間的葉結(jié)點數(shù)目為( )。A.n! B.2n C.2n+1-1 D. 2n-17、程序可以不滿足以下( )特

4、征A.輸入 B.輸出 C.確定性 D.有限性8、以下( )不能在線性時間完成排序A.計數(shù)排序 B.基數(shù)排序 C.堆排序 D.桶排序9、以下( )不一定得到問題的最優(yōu)解A.貪心算法 B.回溯算法 C.分支限界法 D.動態(tài)規(guī)劃法10、以下（）不包括在圖靈機(jī)結(jié)構(gòu)中A. 控制器 B. 讀寫磁頭 C.計算器 D. 磁帶三、簡答題（本題20分，每小題5分）1、設(shè)有n=2k個運動員要進(jìn)行循環(huán)賽，現(xiàn)設(shè)計一個滿足以下要求的比賽日程表：每個選手必須與其他n-1名選手比賽各一次；每個選手一天至多只能賽一次；循環(huán)賽要在最短時間內(nèi)完成。（1）如果n=2k ，循環(huán)賽最少需要進(jìn)行幾天；（2）當(dāng)n=22=4時，請畫出循環(huán)賽日

5、程表。2、簡述最優(yōu)子結(jié)構(gòu)性質(zhì)。3、簡單描述回溯法基本思想。4、何謂P、NP問題四、算法填空（本題30分，每空2分）1、Dijkstra算法是解單源最短路徑問題的貪心算法。請你閱讀下面?zhèn)未a并在空白處填上適當(dāng)?shù)拇a。/ G是一個n個結(jié)點的有向圖，它由成本鄰接矩陣wu,v表示，Dv表示結(jié)點v到源結(jié)點s的最短路徑長度，pv記錄結(jié)點v的父結(jié)點。Init-single-source(G,s)1.for each vertex vVG2.do dv= pv=NIL3. ds=0Relax(u,v,w)1.if 1 2.then dv=du+wu,v pv=u dijkstra(G,w,s)1. 2 2.

6、S= 3. Q=VG4.while Q<> 3 do u=min(Q) S=Su for each vertex vadju /所有u的鄰接點 v do 4 2、某工廠預(yù)計明年有N個新建項目，每個項目的投資額 wk及其投資后的收益 vk已知。投資總額為C，問如何選擇項目才能使總收益最大。Invest-Program( ) for (j=0;j<=C;j+) 5 for (j=wn;j<=C;j+) mnj=vn; for (i=n-1;i>1;i-) int jMax=min(wi-1,c); for(j=0;j<=jMax;j+) mij= 6 ; for

7、 (j=wi;j<=C;j+) mij=max( 7 ); m1c=m2c;if( 8 )m1c=max(m1c,m2c-w1+v1);3、N后問題(1)用二維數(shù)組ANN存儲皇后位置,若第i行第j列放有皇后,則Aij為非0值,否則值為0。(2)分別用一維數(shù)組MN、L2*N-1、R2*N-1表示豎列、左斜線、右斜線是否放有棋子，有則值為1,否則值為0。for(j=0;j<N;j+) if( 9 ) /*安全檢查*/ Aij=i+1; /*放皇后*/ 10 ； if(i=N-1) 輸出結(jié)果； else 11 ；; /*試探下一行*/ 12 ； /*去皇后*/ 13 ；; 4、通過鍵盤輸

8、入一個高精度的正整數(shù)n(n的有效位數(shù)240)，去掉其中任意s個數(shù)字后，剩下的數(shù)字按原左右次序?qū)⒔M成一個新的正整數(shù)。編程對給定的n 和s，尋找一種方案，使得剩下的數(shù)字組成的新數(shù)最小。delete（n ,s)輸入s, n; while（ s > 0 ） 14 /從串首開始找while ( 15 ) i+; delete(n,i); /刪除串n的第i個字符 s-;while (length(n)>1)&& (n1=0) delete(n,1); /刪去串首可能產(chǎn)生的無用零輸出n; 五、請你闡述prim算法的基本思想。并給出下圖的最小生成樹（要求畫出生成樹，分析過程可以省略

9、）（本題10分）六、算法分析題（本題10分）數(shù)字全排列問題：任意給出從1到N的N個連續(xù)的自然數(shù)的各種排列。如N=3時，共有以下6種排列方式：123，132，213，231，312，321。算法描述如下。畫出N=3時遞歸調(diào)用時堆棧變化情況,寫出相對應(yīng)i,j的值。設(shè)數(shù)組b的初始值為1，2，3。perm(int b, int i)int k,j;if(i=N)輸出；else for(j=i;j<=num;j+) swap(bi,bj); perm(b,i+1); swap(bj,bi); /*初始調(diào)用時i = 1;*/ 答案：一、填空題（本題10分，每空1分）1、 算法效率2、 O(n)3、

10、時間、空間 時間復(fù)雜度、空間復(fù)雜度4、 2n 5、 直接 間接6、 獨立二、選擇題（本題20分，每小題2分）1-5：BABCA 6-10：BDCAC三、簡答題（本題20分，每小題5分）1、（1）2k-1天（2分）； （2）當(dāng)n=22=4時，循環(huán)賽日程表（3分）。12342143341243212、某個問題的最優(yōu)解包含著其子問題的最優(yōu)解。這種性質(zhì)稱為最優(yōu)子結(jié)構(gòu)性質(zhì)。3、回溯法的基本思想是在一棵含有問題全部可能解的狀態(tài)空間樹上進(jìn)行深度優(yōu)先搜索，解為葉子結(jié)點。搜索過程中，每到達(dá)一個結(jié)點時，則判斷該結(jié)點為根的子樹是否含有問題的解，如果可以確定該子樹中不含有問題的解，則放棄對該子樹的搜索，退回

11、到上層父結(jié)點，繼續(xù)下一步深度優(yōu)先搜索過程。在回溯法中，并不是先構(gòu)造出整棵狀態(tài)空間樹，再進(jìn)行搜索，而是在搜索過程，逐步構(gòu)造出狀態(tài)空間樹，即邊搜索，邊構(gòu)造。4、P(Polynomial問題)：也即是多項式復(fù)雜程度的問題。 NP就是Non-deterministic Polynomial的問題，也即是多項式復(fù)雜程度的非確定性問題。四、算法填空（本題30分，每空2分）1、（1）dv>du+w(u,v) （2）Init-single-source(G,s) （3） （4）Relax(u,v,w)2、（5）mnj=0; （6）mi+1j （7）mi+1j,mi+1j-wi+vi （8）c&

12、gt;=w13、(9) !Mj&&!Li+j&&!Ri-j+N(10) Mj=Li+j=Ri-j+N=1;(11) try(i+1,M,L,R,A) (12) Aij=0 (13) Mj=Li+j=Ri-j+N=0 4、（14）i=1;（15）(i<length(n)&&(ni<ni+1)五、闡述prim算法的基本思想（本題10分）(5分) prim算法的基本思想是：設(shè)G=(V,E)是連通帶權(quán)圖，V=1,2,n。首先置U=1，然后，只要U是V的真子集，就作如下的貪心選擇：選取滿足條件iU，jV-U，且cij最小的邊，將頂點j添加到U中。這個過程一直進(jìn)行到U=V時為止。在這個過程中選取到的所有邊恰好構(gòu)成G的一棵最小生成樹。（5分）最小生成樹如下：輸出2，1，3(5)i=3,j=2(4)i=1,j=2(3) i=3,j=3(1) i=1,j=1彈出、清空輸出1，3，2輸出1，2，3(2) i=3,j=2(7)i=1,j=3輸出2，3，1(6)i=3,j=3