算法考試試題及答案

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

2、小題2分)1、分支限界法與回溯法都是在問(wèn)題的解空間樹(shù)A.求解目標(biāo)不同，搜索方式相同C.求解目標(biāo)相同，搜索方式不同2、回溯法在解空間樹(shù) T上的搜索方式是B.D.T上搜索問(wèn)題的解，二者()求解目標(biāo)不同，搜索方式也不同求解目標(biāo)相同，搜索方式也相同A.深度優(yōu)先B. 廣度優(yōu)先 C.()。最小耗費(fèi)優(yōu)先 D.活結(jié)點(diǎn)優(yōu)先3、在對(duì)問(wèn)題的解空間樹(shù)進(jìn)行搜索的方法中,一個(gè)活結(jié)點(diǎn)最多有一次機(jī)會(huì)成為活結(jié)點(diǎn)的是()。A.回溯法 B.分支限界法C.回溯法和分支限界法D.回溯法求解子集樹(shù)問(wèn)題4、 以下關(guān)于判定問(wèn)題難易處理的敘述中正確的是()。A. 可以由多項(xiàng)式時(shí)間算法求解的問(wèn)題是難處理的B. 需要超過(guò)多項(xiàng)式時(shí)間算法求解的問(wèn)題是

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

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

5、題四、算法填空(本題 30分，每空2分)1、Dijkstra算法是解單源最短路徑問(wèn)題的貪心算法。請(qǐng)你閱讀下面?zhèn)未a并在空白處填上適當(dāng)?shù)拇a。/ G是一個(gè)n個(gè)結(jié)點(diǎn)的有向圖，它由成本鄰接矩陣wu,v表示，Dv表示結(jié)點(diǎn)v到源結(jié)點(diǎn)s的最短路徑長(zhǎng)度，pv記錄結(jié)點(diǎn)v的父結(jié)點(diǎn)。Init-single-source(G,s)1. for each vertex v VG2. do dv=8 pv=NIL3. ds=0Relax(u,v,w)1.if _l2. then dv=du+wu,vPv=udijkstra(G,w,s)1. _22. S=3. Q=VG4. while Q<> _3do u

6、=min(Q)S=SU ufor each vertex vC adju / 所有 u 的鄰接點(diǎn) vdo4 2、某工廠預(yù)計(jì)明年有N個(gè)新建項(xiàng)目，每個(gè)項(xiàng)目的投資額 wk及其投資后的收益 vk已知。投資總額為C,問(wèn)如何選擇項(xiàng)目才能使總收益最大。Invest-Program() for (j=0;j<=C;j+)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 _jfor (j=wi;j<=C;j+) mij=max( 7);m1c=m

7、2c;if( 8_J_m1c=max(m1c,m2c-w1+v1);3、N后問(wèn)題用二維數(shù)組ANN存儲(chǔ)皇后位置，若第i行第j列放有皇后，則Aij 為非0值，否則 值為0。 分別用一維數(shù)組MN、L2*N-1、R2*N-1表示豎列、左斜線、右斜線是否放有棋子,有則值為1,否則值為0。安全檢查*/放皇后*/for(j=0;j<N;j+)if( 9 ) /* Aij=i+1; /*輸出結(jié)果； ; /* 試探下一彳T */；/* 去皇后*/10;if(i=N-1)12else 11134、通過(guò)鍵盤(pán)輸入一個(gè)高精度的正整數(shù)n(n的有效位數(shù)< 240)，去掉其中任意 s個(gè)數(shù)字后，剩下的數(shù)字按原左右次

8、序?qū)⒔M成一個(gè)新的正整數(shù)。編程對(duì)給定的n和s,尋找一種方案，使得剩下的數(shù)字組成的新數(shù)最小。delete (n ,s)輸入s, n;while ( s > 0)14 / 從串首開(kāi)始找while ( 15)刪除串n的第i個(gè)字符i+;delete(n,i); /s-;'0')while (length(n)>1)&& (n1=delete(n,1); /刪去串首可能產(chǎn)生的無(wú)用零輸出n;五、請(qǐng)你闡述prim算法的基本思想。并給出下圖的最小生成樹(shù)(要求畫(huà)出生成樹(shù)，分析過(guò)程 可以省略)(本題10分)六、算法分析題(本題10分)數(shù)字全排列問(wèn)題：任意給出從1到N的N個(gè)

9、連續(xù)的自然數(shù)的各種排列。如 N=3時(shí)，共有以下6種排列方式：123, 132, 213, 231, 312, 321。算法描述如下。畫(huà)出N=3時(shí)遞歸調(diào)用時(shí)堆棧變化情況，寫(xiě)出相對(duì)應(yīng)i,j的值。設(shè)數(shù)組b的初始值為1 , 2, 3。perm(int b, int i)(int k,j;if(i=N)輸出；elsefor(j=i;j<=num;j+)(swap(bi,bj);perm(b,i+1);swap(bj,bi);/*初始調(diào)用時(shí)i = 1;*/答案：、填空題(本題 10分，每空1分)1、算法效率2、O(n)3、 時(shí)間、空間時(shí)間復(fù)雜度、空間復(fù)雜度4、2n5、直接 間接6、獨(dú)立、選擇題(本題

10、 20分，每小題2分)1-5 : BABCA 6-10 : BDCAC三、簡(jiǎn)答題(本題20分，每小題5分) 1、(1) 2k-1 天(2 分)；(2)當(dāng)n=22=4時(shí)，循環(huán)賽日程表 (3分)。23414341232112342、某個(gè)問(wèn)題的最優(yōu)解包含著其子問(wèn)題的最優(yōu)解。這種性質(zhì)稱為最優(yōu)子結(jié)構(gòu)性質(zhì)3、回溯法的基本思想是在一棵含有問(wèn)題全部可能解的狀態(tài)空間樹(shù)上進(jìn)行深度優(yōu)先搜索，解為葉子結(jié)點(diǎn)。搜索過(guò)程中，每到達(dá)一個(gè)結(jié)點(diǎn)時(shí)，貝峋斷該結(jié)點(diǎn)為根的子樹(shù)是否含有問(wèn)題的解，如果可以確 定該子樹(shù)中不含有問(wèn)題的解，貝U放棄對(duì)該子樹(shù)的搜索，退回到上層父結(jié)點(diǎn)，繼續(xù)下一步深度 優(yōu)先搜索過(guò)程。在回溯法中，并不是先構(gòu)造出整棵狀態(tài)

11、空間樹(shù)，再進(jìn)行搜索，而是在搜索過(guò) 程，逐步構(gòu)造出狀態(tài)空間樹(shù)，即邊搜索，邊構(gòu)造。4、P(Polynomial問(wèn)題)：也即是多項(xiàng)式復(fù)雜程度的問(wèn)題。NP就是Non-deterministic Polynomial的問(wèn)題，也即是多項(xiàng)式復(fù)雜程度的非確定性問(wèn)題。四、算法填空(本題 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+1田(7) mi+1j,mi+1j-wi+vi(8) c>=w13、(9) !Mj&&!Li+j&&

12、!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=04、(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的真子集，就作如下的貪心選擇：選取滿足條件i £ U,j V-U,且cij 最小的邊，將頂點(diǎn)j添加到U中。這個(gè)過(guò)程一直進(jìn)行到U=V時(shí)為止。在這個(gè)過(guò)程中選取到的所有邊恰好構(gòu)成G的一棵最小生成樹(shù)。(5分)最小生成樹(shù)如下:10分)（本題六、算法設(shè)計(jì)題perm(int b, int i)(int k,j;if(i=N)輸出b數(shù)組各元素值；elsefor(j=i;j<=N;j+)(swap(bi,bj);perm(b,i+1);(2)(3)