算法復雜度習題

一、選擇題1.個算法應該是（）。A.程序B.問題求解步驟的描述C.要滿足五個基本特性D.A和C2.某算法的時間復雜度為O(n2)，表明該算法的（）。A.問題規(guī)模是n2B.執(zhí)行時間等于n2C.執(zhí)行時間與n2成正比D.問題規(guī)模與n2成正比3.以下算法的時間復雜度為（）。voidfun(intn){inti=l;while(i<=n)i=i*2;}A.O(n)B.O(n2)C.O(nlog2n)D.O(log2n)4.【2011年計算機聯(lián)考真題】設n是描述問題規(guī)模的非負整數(shù)，下面程序片段的時間復雜度是（）。x=2;while(x<n/2)x=2*x;A.O(log2n)B.O(n)C.O(nlog2n)D.O(n2)5.【2012年計算機聯(lián)考真題】求整數(shù)n(n>=0)階乘的算法如下，其時間復雜度是（）。intfact(intn){if(n<=l)return1;returnn*fact(n-1);}A.O(log2n)B.O(n)C.O(nlog2n)D.O(n2)6.有以下算法，其時間復雜度為（）。voidfun(intn){inti=0;while(i*i*i<=n)i++;}A.O(n)B.O(nlogn)C.D.7.程序段for(i=n-l;i>l;i--)for(j=1;j<i;j++)if(A[j]>A[j+l])A[j]與A[j+1]對換;其中n為正整數(shù)，則最后一行的語句頻度在最壞情況下是（）。A.O(n)B.O(nlogn)C.O(n3)D.O(n2)8.以下算法中加下劃線語句的執(zhí)行次數(shù)為（）。intm=0,i,j;for(i=l;i<=n;i++)for(j=1;j<=2*i;j++)m++;A.n(n+1)B.nC.n+1D.n29.下面說法錯誤的是（）。Ⅰ.算法原地工作的含義是指不需要任何額外的輔助空間Ⅱ.在相同的規(guī)模n下，復雜度O(n)的算法在時間上總是優(yōu)于復雜度O(2n)的算法Ⅲ.所謂時間復雜度是指最壞情況下，估算算法執(zhí)行時間的一個上界Ⅳ.同一個算法，實現(xiàn)語言的級別越高，執(zhí)行效率就越低.A.ⅠB.Ⅰ、ⅡC.Ⅰ、ⅣD.Ⅲ二、綜合應用題1.一個算法所需時間由下述遞歸方程表示，試求出該算法的時間復雜度的級別（或階)。式中，n是問題的規(guī)模，為簡單起見，設n是2的整數(shù)冪。2.分析以下各程序段，求出算法的時間復雜度。01.//程序段①02.i=l;k=0;03.while(i<n-l){04.k=k+10*i;05.i++;06.}07.08.//程序段②09.y=0;10.while((y+1)*(y+1)<=n)11.y=y+1;12.13.//程序段③14.for(i=l;i<=n;i++)15.for(j=1;j<=i;j++)16.for(k=l;k<=j;k++)17.x++;18