算法分析復習題1(gai)

《算法設計與分析》復習題1一、填空：算法是指解決問題的方法或過程，算法所描述的指令序列必須滿足下列性質(zhì)eq\o\ac(○,1)、eq\o\ac(○,2)、eq\o\ac(○,3)、eq\o\ac(○,4)、eq\o\ac(○,5)。程序是算法用某種程序設計語言的具體實現(xiàn)，程序可以不滿足算法的eq\o\ac(○,1)性質(zhì)。所以像操作系統(tǒng)這樣的軟件eq\o\ac(○,2)(是/不是)算法。抽象數(shù)據(jù)類型是算法設計的重要概念。嚴格地講，它是算法的一個eq\o\ac(○,1)連同定義在該模型上并作為eq\o\ac(○,2)的一組運算。算法的復雜性是算法運行所需要的計算機資源的量。這個量集中反映算法的效率，通常用C=F(N、I、A)表示，其中C、N、I、A所代表的含義是什么？設f(N)和g(N)是定義在正數(shù)集上的正函數(shù)，當N充分大時，f(N)=O(g(N))表示g(N)是f(N)的一個eq\o\ac(○,1)；f(N)=Ω(g(N))表示g(N)是f(N)的一個eq\o\ac(○,2)；f(N)=θ(g(N))表示g(N)是f(N)=3\*GB3③。直接或間接地調(diào)用自身的算法稱為eq\o\ac(○,1)，在定義該算法時，除了提供必須的計算公式外，還必須提供eq\o\ac(○,2)初始值。動態(tài)規(guī)劃算法與分治法的基本思想都是將待求解問題分解成若干個子問題，先求解子問題，然后從這些子問題的解得到原問題的解。它們的主要區(qū)別是分治法求解時，對有些子問題會eq\o\ac(○,1)，而動態(tài)規(guī)劃法采用eq\o\ac(○,2)避免子問題重復計算。貪心算法與動態(tài)規(guī)劃算法都要求問題具有最優(yōu)子結構性質(zhì)，這是兩類算法的一個共同點。但是否具有最優(yōu)子結構的問題，用貪心算法和動態(tài)規(guī)劃算法都可以得到最優(yōu)解？舉例說明。下面的說法錯誤的是________。算法原地工作的含義是指不需要任何額外的輔助空間；在相同的規(guī)模n下，時間復雜度為O(n)的算法在時間上總是優(yōu)于時間復雜度為O(2n)的算法。所謂時間復雜度是指最壞情況下，估算算法執(zhí)行時間的一個上界；同一算法，實現(xiàn)語言的級別越高，執(zhí)行效率越低。10．回朔法的求解目標是找出解空間中滿足約束條件的eq\o\ac(○,1)，而分支限界法的求解目標則是找出滿足約束條件的eq\o\ac(○,2)或在某種意義下的最優(yōu)解。11．回朔法以eq\o\ac(○,1)優(yōu)先的方式搜索解空間樹，而分支限界法則以eq\o\ac(○,2)優(yōu)先或以eq\o\ac(○,3)優(yōu)先的方式搜索解空間樹。12．按從活結點表中選擇下一擴展結點的不同方式，可將分支限界法分為eq\o\ac(○,1)分支限界法和eq\o\ac(○,2)分支限界法。13．eq\o\ac(○,1)假設某算法在輸入規(guī)模為n時的計算時間為T(n)=3×2n，在某臺計算機上實現(xiàn)并完成該算法的時間為t秒，現(xiàn)另有一臺計算機，其運行速度為第一臺的64倍，那么在這臺新機器上用同一算法在t秒內(nèi)能輸入規(guī)模多大的問題？eq\o\ac(○,2)若上述算法的計算時間改進為T(n)=n2，其余條件不變，則在新機器上用t秒時間能解輸入規(guī)模多大的問題？eq\o\ac(○,3)在上述算法的計算時間進一步改進為T(n)=8，其余條件不變，那么在新機器上用t秒時間能解輸入規(guī)模多大的問題？二、設n是偶數(shù)，試計算運行下列程序段后m的值，并給出該程序的時間復雜度。intm=0for(inti=1;i<=n;i++)for(intj=2*i;j<=n;j++)m=m+1;2．計算機執(zhí)行下面的語句時，語句s的執(zhí)行次數(shù)為多少？for(inti=1;i<n-1;i++)for(j=n;j>=i;j--)s;3．給出下列程序段中帶標號的語句eq\o\ac(○,1)~eq\o\ac(○,5)執(zhí)行的頻度，利用O記號將以下程序段在最壞情況下的運行時間表示為n的函數(shù)。for(inti=1;i<=n;i++)eq\o\ac(○,1)for(intj=1;j<=n;j++)eq\o\ac(○,2){c[i][j]=0;eq\o\ac(○,3)for(intk=1;k<=n;k++)eq\o\ac(○,4)c[i][j]=c[i][j]+a[i][k]*b[k][j];eq\o\ac(○,5)}4．a(chǎn).{if((Q.rear+1)%Maxsize==Q.front)returnERROR;Q.base[Q.rear]=e;Q.rear=(Q.rear+1)%Maxsize;returnok;}該算法實現(xiàn)什么功能？b.{if(S.top-S.base>=S.stacksize){S.base=追加分配空間；S.top=S.base+S.stacksize；S.stacksize+=stackincrement；｝*S.tope++=e;returnok;}該算法實現(xiàn)什么功能？c.{for(inti=0;i<S.length&&i<T.length;++i)if(S.ch[i]!=T.ch[i]return(S.ch[i]-T.ch[i])；return(S.length-T.length);}該算法實現(xiàn)什么功能？5.說明下列程序的功能：privatestaticintpartion(intp,intr){inti=p,j=r+1;Comparablex=a[p];while(true){while(a[++i]compareTo(x)<0;while(a[--j]compareTo(x)>0;if(i>=j)break;Mymath.swap(a,i,j)}a[p]=a[j];a[j]=x;returnj;}6.已知Fibonacci數(shù)列如下：1，1，2，3，5，8，13，21，……請寫出其遞歸關系式。三、1．假設合并排序算法的抽象定義為：PublicstaticvoidmergeSort(Comparablea[],intleft,intright){}其中使用的合并及拷貝方法分別定義為：Publicstaticvoidmerge(Comparable[]c,Comparable[]d,intl,intm,intr){}Publicstaticvoidcopy(Comparable[]c,Comparable[]d,inti,intj){}請補充完善遞歸方式實現(xiàn)的合并排序的細節(jié)。2．已知整數(shù)劃分問題的遞歸式如下：1n=1或m=1q(n,m)=q(n,n)n<m1+q(n,n-1)n=mq(n,m-1)+q(n-m,m)n>m>1請設計計算q(n,m)的遞歸算法。四、1．設所給0-1背包問題的子問題（其中物品i的重量是wi，其價值為vi）的最優(yōu)值為m(i，j)，即m(i，j)是背包容量為j，可選擇物品為i，i+1，…，n時0-1背包問題的最優(yōu)值。請建立m(i,j)的遞歸式。2．已知有7個獨立作業(yè){1,2,3,4,5,6,7}由3臺機器M1，M2和M3加工處理。各作業(yè)所需的處理時間分別為{2,14,4,16,6,5,3}。請給出利用貪心算法實現(xiàn)多機調(diào)度問題的步驟。3．假設有n=3時，0-1背包問題的一個實例為：w=[16,15,15]，p=[45,25,25]，c=30。請畫出解空間樹，利用隊列式分支限界法表示活結點進出隊列的過程并給出最優(yōu)值。4．請完善下面用回溯法搜索子集樹和排列樹的一般算法描述：子集樹：Voidbacktrack(intt){If(t>n)output(x)ElseFor(inti=____;__________;i++){___________;If(constra