算法分析復(fù)習(xí)題1(gai)

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