算法考試試題及答案

填空題（本題10分，每空1分）算法的復雜性是的度量，是評價算法優(yōu)劣的重要依據(jù)。設n為正整數(shù)，利用大“O(·)”記號，將下列程序段的執(zhí)行時間表示為n的函數(shù)，則下面程序段的時間復雜度為。i=1;k=0;while(i<n){k=k+10*i;i++;}

計算機的資源最重要的是和資源。因而，算法的復雜性有和之分。f(n)=6×2n+n2，f(n)的漸進性態(tài)f(n)=O(

)遞歸是指函數(shù)或者通過一些語句調用自身。分治法的基本思想是將一個規(guī)模為n的問題分解為k個規(guī)模較小的子問題，這些子問題互相且與原問題相同。二、選擇題（本題20分，每小題2分）1、分支限界法與回溯法都是在問題的解空間樹T上搜索問題的解,二者()。A.求解目標不同,搜索方式相同B.求解目標不同,搜索方式也不同C.求解目標相同,搜索方式不同D.求解目標相同,搜索方式也相同2、回溯法在解空間樹T上的搜索方式是()。A.深度優(yōu)先B.廣度優(yōu)先C.最小耗費優(yōu)先D.活結點優(yōu)先3、在對問題的解空間樹進行搜索的方法中,一個活結點最多有一次機會成為活結點的是()。A.回溯法B.分支限界法C.回溯法和分支限界法D.回溯法求解子集樹問題4、以下關于判定問題難易處理的敘述中正確的是()。A.可以由多項式時間算法求解的問題是難處理的B.需要超過多項式時間算法求解的問題是易處理的C.可以由多項式時間算法求解的問題是易處理的D.需要超過多項式時間算法求解的問題是不能處理的5、設f(N),g(N)是定義在正數(shù)集上的正函數(shù),如果存在正的常數(shù)C和自然數(shù)N0,使得當N≥N0時有f(N)≤Cg(N),則稱函數(shù)f(N)當N充分大時有上界g(N),記作f(N)=O(g(N)),即f(N)的階()g(N)的階。A.不高于B.不低于C.等價于D.逼近6、對于含有n個元素的子集樹問題,最壞情況下其解空間的葉結點數(shù)目為()。A.n!B.2nC.2n+1-1D.2n-17、程序可以不滿足以下()特征A.輸入B.輸出C.確定性D.有限性8、以下()不能在線性時間完成排序A.計數(shù)排序B.基數(shù)排序C.堆排序D.桶排序9、以下()不一定得到問題的最優(yōu)解A.貪心算法B.回溯算法C.分支限界法D.動態(tài)規(guī)劃法10、以下（）不包括在圖靈機結構中A.控制器B.讀寫磁頭C.計算器D.磁帶三、簡答題（本題20分，每小題5分）1、設有n=2k個運動員要進行循環(huán)賽，現(xiàn)設計一個滿足以下要求的比賽日程表：①每個選手必須與其他n-1名選手比賽各一次；②每個選手一天至多只能賽一次；③循環(huán)賽要在最短時間內完成。（1）如果n=2k，循環(huán)賽最少需要進行幾天；（2）當n=22=4時，請畫出循環(huán)賽日程表。2、簡述最優(yōu)子結構性質。3、簡單描述回溯法基本思想。4、何謂P、NP問題四、算法填空（本題30分，每空2分）1、Dijkstra算法是解單源最短路徑問題的貪心算法。請你閱讀下面?zhèn)未a并在空白處填上適當?shù)拇a。//G是一個n個結點的有向圖，它由成本鄰接矩陣w[u,v]表示，D[v]表示結點v到源結點s的最短路徑長度，p[v]記錄結點v的父結點。Init-single-source(G,s)1.foreachvertexv∈V[G]2.do{d[v]=∞p[v]=NIL}3.d[s]=0Relax(u,v,w)1.if12.then{d[v]=d[u]+w[u,v]p[v]=u}dijkstra(G,w,s)1.22.S=Φ3.Q=V[G]4.whileQ<>3dou=min(Q)S=S∪{u}foreachvertexv∈adj[u]//所有u的鄰接點vdo42、某工廠預計明年有N個新建項目，每個項目的投資額w[k]及其投資后的收益v[k]已知。投資總額為C，問如何選擇項目才能使總收益最大。Invest-Program(){for(j=0;j<=C;j++)5for(j=w[n];j<=C;j++)m[n][j]=v[n];for(i=n-1;i>1;i--){intjMax=min(w[i]-1,c);for(j=0;j<=jMax;j++)m[i][j]=6;for(j=w[i];j<=C;j++)m[i][j]=max(7);}m[1][c]=m[2][c];if(8)m[1][c]=max(m[1][c],m[2][c-w[1]]+v[1]);}3、N后問題(1)用二維數(shù)組A[N][N]存儲皇后位置,若第i行第j列放有皇后,則A[i][j]為非0值,否則值為0。(2)分別用一維數(shù)組M[N]、L[2*N-1]、R[2*N-1]表示豎列、左斜線、右斜線是否放有棋子，有則值為1,否則值為0。for(j=0;j<N;j++)if(9)/*安全檢查*/{A[i][j]=i+1;/*放皇后*/10；if(i==N-1)輸出結果；else11；;/*試探下一行*/12；/*去皇后*/13；;}4、通過鍵盤輸入一個高精度的正整數(shù)n(n的有效位數(shù)≤240)，去掉其中任意s個數(shù)字后，剩下的數(shù)字按原左右次序將組成一個新的正整數(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)&&(n[1]=‘0’)delete(n,1);//刪去串首可能產(chǎn)生的無用零輸出n;}五、請你闡述prim算法的基本思想。并給出下圖的最小生成樹（要求畫出生成樹，分析過程可以省略）（本題10分）六、算法分析題（本題10分）數(shù)字全排列問題：任意給出從1到N的N個連續(xù)的自然數(shù)的各種排列。如N=3時，共有以下6種排列方式：123，132，213，231，312，321。算法描述如下。畫出N=3時遞歸調用時堆棧變化情況,寫出相對應i,j的值。設數(shù)組b的初始值為1，2，3。perm(intb[],inti){intk,j;if(i==N)輸出；elsefor(j=i;j<=num;j++){swap(b[i],b[j]);perm(b,i+1);swap(b[j],b[i]);}}/*初始調用時i=1;*/答案：一、填空題（本題10分，每空1分）算法效率O(n)時間、空間時間復雜度、空間復雜度2n

直接間接獨立二、選擇題（本題20分，每小題2分）1-5：BABCA6-10：BDCAC三、簡答題（本題20分，每小題5分）1、（1）2k-1天（2分）；（2）當n=22=4時，循環(huán)賽日程表（3分）。12342143341243212、某個問題的最優(yōu)解包含著其子問題的最優(yōu)解。這種性質稱為最優(yōu)子結構性質。3、回溯法的基本思想是在一棵含有問題全部可能解的狀態(tài)空間樹上進行深度優(yōu)先搜索，解為葉子結點。搜索過程中，每到達一個結點時，則判斷該結點為根的子樹是否含有問題的解，如果可以確定該子樹中不含有問題的解，則放棄對該子樹的搜索，退回到上層父結點，繼續(xù)下一步深度優(yōu)先搜索過程。在回溯法中，并不是先構造出整棵狀態(tài)空間樹，再進行搜索，而是在搜索過程，逐步構造出狀態(tài)空間樹，即邊搜索，邊構造。4、P(Polynomial問題)：也即是多項式復雜程度的問題。NP就是Non-deterministic

Polynomial的問題，也即是多項式復雜程度的非確定性問題。四、算法填空（本題30分，每空2分）1、（1）d[v]>d[u]+w(u,v)（2）Init-single-source(G,s)（3）Φ（4）Relax(u,v,w)2、（5）m[n][j]=0;（6）m[i+1][j]（7）m[i+1][j],m[i+1][j-w[i]]+v[i]（8）c>=w[1]3、(9)!M[j]&&!L[i+j]&&!R[i-j+N](10)M[j]=L[i+j]=R[i-j+N]=1;(11)try(i+1,M,L,R,A)(12)A[i][j]=0(13)M[j]=L[i+j]=R[i-j+N]=04、（14）i=1;（15）(i<length(n))&&(n[i]<n[i+1])五、闡述prim算法的基本思想（本題10分）(5分)prim算法的基本思想是：設G=(V,E)是連通帶權圖，V={1,2,…,n}。首先置U={1}，然后，只要U是V的真子集，就作如下的貪心選擇：選取滿足條件i∈U，j∈V-U，且c[i][j]最小的邊，將頂點j添加到U中。這個過程一直進行到U=V時為止。在這個過程中選取到的所有邊恰好構成G的一棵最小生成樹。（5分）最小生成樹如下：輸出2，1，3(5)i=3,j=2輸出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(9)i=3,j=3輸出