程序員面試模擬試卷1（共93題）

程序員面試模擬試卷1（共9套）（共93題）程序員面試模擬試卷第1套一、面試題(本題共8題，每題1.0分，共8分。)1、將一整數(shù)逆序后放入一數(shù)組中（要求遞歸實(shí)現(xiàn)）標(biāo)準(zhǔn)答案：voidconvert(int*result,intn){if(n>=10)convert(result+1,n/10);*result=n%10;}intmain(intargc,char*argv[]){intn=123456789,result[20]={};convert(result,n);printf("%d:",n);for(inti=0;i<9;i++)printf("%d",result[i]);returngetchar();}知識(shí)點(diǎn)解析：暫無解析2、求高于平均分的學(xué)生學(xué)號(hào)及成績(jī)（學(xué)號(hào)和成績(jī)?nèi)斯ぽ斎耄?biāo)準(zhǔn)答案：doublefind(inttotal,intn){intnumber,score,average;scanf("%d",&number);if(number!=0){scanf("%d",&score);average=find(total+score,n+1);if(score>=average)printf("%d:%d\n",number,score);returnaverage;}else{printf("Average=%d\n",total/n);returntotal/n;}}intmain(intargc,char*argv[]){find(0,0);returngetchar();}知識(shí)點(diǎn)解析：暫無解析3、遞歸實(shí)現(xiàn)回文判斷（如：abcdedbca就是回文）標(biāo)準(zhǔn)答案：intfind(char*str,intn){if(n<=1)return1;elseif(str[0]==str[n-1])returnfind(str+1,n-2);elsereturn0;}intmain(intargc,char*argv[]){char*str="abcdedcba";printf("%s:%s\n",str,find(str,strlen(str))?"Yes":"No");returngetchar();}知識(shí)點(diǎn)解析：暫無解析4、組合問題（從M個(gè)不同字符中任取N個(gè)字符的所有組合）標(biāo)準(zhǔn)答案：voidfind(char*source,char*result,intn){if(n==1){while(*source)printf("%s%c\n",result,*source++);}else{inti,j;for(i=0;source[i]!=0;i++);for(j=0;result[j]!=0;j++);for(;i>=n;i--){result[j]=*source++;result[j+1]=’\0’;find(source,result,n-1);}}}intmain(intargc,char*argv[]){intconstn=3;char*source="ABCDE",result[n+1]={0};if(n>0&&strlen(source)>0&&n<=strlen(source))find(source,result,3);returngetchar();}知識(shí)點(diǎn)解析：暫無解析5、分解成質(zhì)因數(shù)(如435234=251*17*17*3*2)標(biāo)準(zhǔn)答案：voidprim(intm,intn){if(m>n){while(m%n!=0)n++;m/=n;prim(m,n);printf("%d*",n);}}intmain(intargc,char*argv[]){intn=435234;printf("%d=",n);prim(n,2);returngetchar();}知識(shí)點(diǎn)解析：暫無解析6、尋找迷宮的一條出路（o：通路；X障礙）標(biāo)準(zhǔn)答案：#defineMAX_SIZE8intH[4]={0,1,0,-1};intV[4]={-1,0,1,0};charMaze[MAX_SIZE][MAX_SIZE]={{’X’,’X’,’X’,’X’,’X’,’X’,’X’,’X’},{’o’,’o’,’o’,’o’,’o’,’X’,’X’,’X’},{’X’,’o’,’X’,’X’,’o’,’o’,’o’,’X’},{’X’,’o’,’X’,’X’,’o’,’X’,’X’,’o’},{’X’,’o’,’X’,’X’,’X’,’X’,’X’,’X’},{’X’,’o’,’X’,’X’,’o’,’o’,’o’,’X’},{’X’,’o’,’o’,’o’,’o’,’X’,’o’,’o’},{’X’,’X’,’X’,’X’,’X’,’X’,’X’,’X’}};voidFindPath(intX,intY){if(X==MAX_SIZE||Y==MAX_SIZE){for(inti=0;i<MAX_SIZE;i++)for(intj=0;j<MAX_SIZE;j++)printf("%c%c",Maze[i][j],j<MAX_SIZE-1?’’:’\n’);}elsefor(intk=0;k<4;k++)if(X>=0&&Y>=0&&Y<MAX_SIZE&&X<MAX_SIZE&&’o’==Maze[X][Y]){Maze[X][Y]=’’;FindPath(X+V[k],Y+H[k]);Maze[X][Y]=’o’;}}intmain(intargc,char*argv[]){FindPath(1,0);returngetchar();}知識(shí)點(diǎn)解析：暫無解析7、隨機(jī)分配座位，共50個(gè)學(xué)生，使學(xué)號(hào)相鄰的同學(xué)座位不能相鄰(早些時(shí)候用C#寫的，沒有用C改寫）。標(biāo)準(zhǔn)答案：staticvoidMain(string[]args){intTmp=0,Count=50;int[]Seats=newint[Count];bool[]Students=newbool[Count];System.RandomRandStudent=newSystem.Random();Students[Seats[0]=RandStudent.Next(0,Count)]=true;for(inti=1;i<Count;){Tmp=(int)RandStudent.Next(0,Count);if((!Students[Tmp])&&(Seats[i-1]-Tmp!=1)&&(Seats[i-1]-Tmp)!=-1){Seats[i++]=Tmp;Students[Tmp]=true;}}foreach(intStudentinSeats)System.Console.Write(Student+"");System.Console.Read();}知識(shí)點(diǎn)解析：暫無解析8、求網(wǎng)格中的黑點(diǎn)分布（有6*7的網(wǎng)格，在某些格子中有黑點(diǎn)，已知各行與各列中有黑點(diǎn)的點(diǎn)數(shù)之和）標(biāo)準(zhǔn)答案：#defineROWS6#defineCOLS7intiPointsR[ROWS]={2,0,4,3,4,0};//各行黑點(diǎn)數(shù)和的情況intiPointsC[COLS]={4,1,2,2,1,2,1};//各列黑點(diǎn)數(shù)和的情況intiCount,iFound;intiSumR[ROWS],iSumC[COLS],Grid[ROWS][COLS];intSet(intiRowNo){if(iRowNo==ROWS){for(intiColNo=0;iColNo<COLS&&iSumC[iColNo]==iPointsC[iColNo];iColNo++)if(iColNo==COLS-1){printf("\nNo.%d:\n",++iCount);for(inti=0;i<ROWS;i++)for(intj=0;j<COLS;j++)printf("%d%c",Grid[i][j],(j+1)%COLS?’’:’\n’);iFound=1;//iFound=1，有解}}else{for(intiColNo=0;iColNo<COLS;iColNo++){if(iPointsR[iRowNo]==0){Set(iRowNo+1);}elseif(Grid[iRowNo][iColNo]==0){Grid[iRowNo][iColNo]=1;iSumR[iRowNo]++;iSumC[iColNo]++;if(iSumR[iRowNo]知識(shí)點(diǎn)解析：暫無解析程序員面試模擬試卷第2套一、面試題(本題共10題，每題1.0分，共10分。)1、有4種面值（面值為1,4,12,21）的郵票很多枚，從中最多任取5張進(jìn)行組合，求郵票最大連續(xù)組合值標(biāo)準(zhǔn)答案：#defineN5#defineM5intk,Found,Flag[N];intStamp[M]={0,1,4,12,21};//在剩余張數(shù)n中組合出面值和ValueintCombine(intn,intValue){if(n>=0&&Value==0){Found=1;intSum=0;for(inti=0;i0;i++)if(Value-Stamp[i]>=0){Flag[k++]=i;Combine(n-1,Value-Stamp[i]);Flag[--k]=0;}returnFound;}intmain(intargc,char*argv[]){for(inti=1;Combine(N,i);i++,Found=0);returngetchar();}知識(shí)點(diǎn)解析：暫無解析2、大整數(shù)數(shù)相乘的問題。標(biāo)準(zhǔn)答案：voidMultiple(charA[],charB[],charC[]){intTMP,In=0,LenA=-1,LenB=-1;while(A[++LenA]!=’\0’);while(B[++LenB]!=’\0’);intIndex,Start=LenA+LenB-1;for(inti=LenB-1;i>=0;i--){Index=Start--;if(B[i]!=’0’){for(intIn=0,j=LenA-1;j>=0;j--){TMP=(C[Index]-’0’)+(A[j]-’0’)*(B[i]-’0’)+In;C[Index--]=TMP%10+’0’;In=TMP/10;}C[Index]=In+’0’;}}}intmain(intargc,char*argv[]){charA[]="21839244444444448880088888889";charB[]="38888888888899999999999999988";charC[sizeof(A)+sizeof(B)-1];for(intk=0;k知識(shí)點(diǎn)解析：暫無解析3、求最大連續(xù)遞增數(shù)字串（如“ads3sl456789DF3456ld345AA”中的“456789”）標(biāo)準(zhǔn)答案：intGetSubString(char*strSource,char*strResult){intiTmp=0,iHead=0,iMax=0;for(intIndex=0,iLen=0;strSource[Index];Index++){if(strSource[Index]>=’0’&&strSource[Index]<=’9’&&strSource[Index-1]>’0’&&strSource[Index]==strSource[Index-1]+1){iLen++;//連續(xù)數(shù)字的長(zhǎng)度增1}else{//出現(xiàn)字符或不連續(xù)數(shù)字if(iLen>iMax){iMax=iLen;iHead=iTmp;}//該字符是數(shù)字，但數(shù)字不連續(xù)if(strSource[Index]>=’0’&&strSource[Index]<=’9’){iTmp=Index;iLen=1;}}}for(iTmp=0;iTmp<iMax;iTmp++)//將原字符串中最長(zhǎng)的連續(xù)數(shù)字串賦值給結(jié)果串strResult[iTmp]=strSource[iHead++];strResult[iTmp]=’\0’;returniMax;//返回連續(xù)數(shù)字的最大長(zhǎng)度}intmain(intargc,char*argv[]){charstrSource[]="ads3sl456789DF3456ld345AA",charstrResult[sizeof(strSource)];printf("Len=%d,strResult=%s\nstrSource=%s\n",GetSubString(strSource,strResult),strResult,strSource);returngetchar();}知識(shí)點(diǎn)解析：暫無解析4、四個(gè)工人，四個(gè)任務(wù)，每個(gè)人做不同的任務(wù)需要的時(shí)間不同，求任務(wù)分配的最優(yōu)方案。（2005年5月29日全國(guó)計(jì)算機(jī)軟件資格水平考試——軟件設(shè)計(jì)師的算法題）。標(biāo)準(zhǔn)答案：#include"stdafx.h"#defineN4intCost[N][N]={{2,12,5,32},//行號(hào)：任務(wù)序號(hào)，列號(hào)：工人序號(hào){8,15,7,11},//每行元素值表示這個(gè)任務(wù)由不同工人完成所需要的時(shí)間{24,18,9,6},{21,1,8,28}};intMinCost=1000;intTask[N],TempTask[N],Worker[N];voidAssign(intk,intcost){if(k==N){MinCost=cost;for(inti=0;i知識(shí)點(diǎn)解析：暫無解析5、八皇后問題（輸出所有情況，不過有些結(jié)果只是旋轉(zhuǎn)了90度而已）。哈哈：）回溯算法的典型例題標(biāo)準(zhǔn)答案：#defineN8intBoard[N][N];intValid(inti,intj)//所下棋子有效性的嚴(yán)正{intk=1;for(k=1;i>=k&&j>=k;k++)if(Board[i-k][j-k])return0;for(k=1;i>=k;k++)if(Board[i-k][j])return0;for(k=1;i>=k&&j+k知識(shí)點(diǎn)解析：暫無解析6、實(shí)現(xiàn)strstr功能（尋找子串在父串中首次出現(xiàn)的位置）標(biāo)準(zhǔn)答案：char*strstring(char*ParentString,char*SubString){char*pSubString,*pPareString;for(char*pTmp=ParentString;*pTmp;pTmp++){pSubString=SubString;pPareString=pTmp;while(*pSubString==*pPareString&&*pSubString!=’\0’){pSubString++;pPareString++;}if(*pSubString==’\0’)returnpTmp;}returnNULL;}intmain(intargc,char*argv[]){char*ParentString="happybirthdaytoyou!";char*SubString="birthday";printf("%s",strstring(ParentString,SubString));returngetchar();}}知識(shí)點(diǎn)解析：暫無解析7、現(xiàn)在小明一家過一座橋，過橋的時(shí)候是黑夜，所以必須有燈。現(xiàn)在小明過橋要1秒，小明的弟弟要3秒，小明的爸爸要6秒，小明的媽媽要八秒，小明的爺爺要12秒。每次此橋最多可過兩人，而過橋的速度依過橋最慢者而定，而且燈在點(diǎn)燃后30秒就會(huì)熄滅。問小明一家如何過橋？（原本是個(gè)智力題，這里用程序來求解）標(biāo)準(zhǔn)答案：#include"stdafx.h"#defineN5#defineSIZE64//將人員編號(hào)：小明-0，弟弟-1，爸爸-2，媽媽-3，爺爺-4//每個(gè)人的當(dāng)前位置：0--在橋左邊，1--在橋右邊intPosition[N];//過橋臨時(shí)方案的數(shù)組下標(biāo)；臨時(shí)方案；最小時(shí)間方案；intIndex,TmpScheme[SIZE],Scheme[SIZE];//最小過橋時(shí)間總和，初始值100；每個(gè)人過橋所需要的時(shí)間intMinTime=100,Time[N]={1,3,6,8,12};//尋找最佳過橋方案。Remnant:未過橋人數(shù);CurTime:當(dāng)前已用時(shí)間;//Direction:過橋方向,1--向右,0--向左voidFind(intRemnant,intCurTime,intDirection){if(Remnant==0){//所有人已經(jīng)過橋，更新最少時(shí)間及方案MinTime=CurTime;for(inti=0;i=0;i++){Scheme[i]=TmpScheme[i];}}elseif(Direction==1){//過橋方向向右，從橋左側(cè)選出兩人過橋for(inti=0;iTime[j]?Time[i]:Time[j]);if(Position[j]==0&&CurTime+TmpMax=0;i+=3)printf("%d-%d%d",Scheme[i],Scheme[i+1],Scheme[i+2]);printf("\b\b");returngetchar();}知識(shí)點(diǎn)解析：暫無解析8、2005年11月金山筆試題。編碼完成下面的處理函數(shù)。函數(shù)將字符串中的字符’*’移到串的前部分，前面的非’*’字符后移，但不能改變非’*’字符的先后順序，函數(shù)返回串中字符’*’的數(shù)量。如原始串為：ab**cd**e*12，處理后為*****abcde12，函數(shù)并返回值為5。（要求使用盡量少的時(shí)間和輔助空間）標(biāo)準(zhǔn)答案：intchange(char*str)/*這個(gè)算法并不高效，從后向前搜索效率要高些*/{intcount=0;/*記錄串中字符’*’的個(gè)數(shù)*/for(inti=0,j=0;str[i];i++)/*重串首開始遍歷*/{if(str[i]==’*’){/*遇到字符’*’*/for(j=i-1;str[j]!=’*’&&j>=0;j--)/*采用類似插入排序的思想，將*前面*/str[j+1]=str[j];/*的非*字符逐個(gè)后移，直到遇到*字符*/str[j+1]=’*’;count++;}}returncount;}intmain(intargc,char*argv[]){charstr[]="ab**cd**e*12";printf("str1=%s\n",str);printf("str2=%s,count=%d",str,change(str));returngetchar();}//終于得到一個(gè)比較高效的算法，一個(gè)網(wǎng)友提供，應(yīng)該和金山面試官的想法一致。算法如下：intchange(char*str){inti,j=strlen(str)-1;for(i=j;j>=0;j--){if(str[i]!=’*’){i--;}elseif(str[j]!=’*’){str[i]=str[j];str[j]=’*’;i--;}}returni+1;}知識(shí)點(diǎn)解析：暫無解析9、2005年11月15日華為軟件研發(fā)筆試題。實(shí)現(xiàn)一單鏈表的逆轉(zhuǎn)。標(biāo)準(zhǔn)答案：#include"stdafx.h"typedefchareleType;//定義鏈表中的數(shù)據(jù)類型typedefstructlistnode//定義單鏈表結(jié)構(gòu){eleTypedata;structlistnode*next;}node;node*create(intn)//創(chuàng)建單鏈表，n為節(jié)點(diǎn)個(gè)數(shù){node*p=(node*)malloc(sizeof(node));node*head=p;head->data=’A’;for(inti=’B’;i<’A’+n;i++){p=(p->next=(node*)malloc(sizeof(node)));p->data=i;p->next=NULL;}returnhead;}voidprint(node*head)//按鏈表順序輸出鏈表中元素{for(;head;head=head->next)printf("%c",head->data);printf("\n");}node*reverse(node*head,node*pre)//逆轉(zhuǎn)單鏈表函數(shù)。這是筆試時(shí)需要寫的最主要函數(shù){node*p=head->next;head->next=pre;if(p)returnreverse(p,head);elsereturnhead;}intmain(intargc,char*argv[]){node*head=create(6);print(head);head=reverse(head,NULL);print(head);returngetchar();}知識(shí)點(diǎn)解析：暫無解析10、編碼實(shí)現(xiàn)字符串轉(zhuǎn)整型的函數(shù)（實(shí)現(xiàn)函數(shù)atoi的功能），據(jù)說是神州數(shù)碼筆試題。如將字符串”+123”-->123,”-0123”-->-123,“123CS45”-->123,“123.45CS”-->123,“CS123.45”-->0標(biāo)準(zhǔn)答案：#include"stdafx.h"intstr2int(constchar*str)//字符串轉(zhuǎn)整型函數(shù){inti=0,sign=1,value=0;if(str==NULL)returnNULL;//空串直接返回NULLif(str[0]==’-’||str[0]==’+’){//判斷是否存在符號(hào)位i=1;sign=(str[0]==’-’?-1:1);}for(;str[i]>=’0’&&str[i]<=’9’;i++)//如果是數(shù)字，則繼續(xù)轉(zhuǎn)換value=value*10+(str[i]-’0’);returnsign*value;}intmain(intargc,char*argv[]){char*str="-123.45CS67";intval=str2int(str);printf("str=%s\tval=%d\n",str,val);returngetchar();}知識(shí)點(diǎn)解析：暫無解析程序員面試模擬試卷第3套一、面試題(本題共10題，每題1.0分，共10分。)1、描述一下C#中索引器的實(shí)現(xiàn)過程，是否只能根據(jù)數(shù)字進(jìn)行索引？標(biāo)準(zhǔn)答案：索引器允許類或結(jié)構(gòu)的實(shí)例按照與數(shù)組相同的方式進(jìn)行索引。索引器不必根據(jù)整數(shù)值進(jìn)行索引，由您決定如何定義特定的查找機(jī)制。classSampleCollection{privateT[]arr=newT[100];publicTthis[inti]{get{returnarr[i];}set{arr[i]=value;}}}//ThisclassshowshowclientcodeusestheindexerclassProgram{staticvoidMain(string[]args){SampleCollectionstringCollection=newSampleCollection();stringCollection[0]="Hello,World";System.Console.WriteLine(stringCollection[0]);}}知識(shí)點(diǎn)解析：暫無解析2、下面的例子中usingSystem;classA{publicstaticintX;staticA(){X=B.Y+1;}}classB{publicstaticintY=A.X+1;staticB(){}staticvoidMain(){//主函數(shù)為程序的入口Console.WriteLine("X={0},Y={1}",A.X,B.Y);}}產(chǎn)生的輸出結(jié)果是什么？標(biāo)準(zhǔn)答案：x=1,y=2知識(shí)點(diǎn)解析：暫無解析3、常用的調(diào)用webservice方法有哪些？標(biāo)準(zhǔn)答案：訪問WebService的三種方法，GET,POST,和基于SOAP協(xié)議的Web代理的調(diào)用知識(shí)點(diǎn)解析：暫無解析4、大概描述一下ASP。NET頁(yè)面的生命周期標(biāo)準(zhǔn)答案：知識(shí)點(diǎn)解析：暫無解析5、在下面的例子里usingSystem;classA{publicA(){PrintFields();}publicvirtualvoidPrintFields(){}}classB:A{intx=1;inty;publicB(){y=-1;}publicoverridevoidPrintFields(){Console.WriteLine("x={0},y={1}",x,y);}}當(dāng)使用newB()創(chuàng)建B的實(shí)例時(shí)，產(chǎn)生什么輸出？標(biāo)準(zhǔn)答案：x=1,y=0知識(shí)點(diǎn)解析：暫無解析6、如何通過ADO.NET讀取數(shù)據(jù)庫(kù)中的圖片？標(biāo)準(zhǔn)答案：//AssumesthatconnectionisavalidSqlConnectionobject.SqlCommandcommand=newSqlCommand("SELECTpub_id,logoFROMpub_info",connection);//WritestheBLOBtoafile(*.bmp).FileStreamstream;//StreamstheBLOBtotheFileStreamobject.BinaryWriterwriter;//SizeoftheBLOBbuffer.intbufferSize=100;//TheBLOBbyte[]buffertobefilledbyGetBytes.byte[]outByte=newbyte[bufferSize];//ThebytesreturnedfromGetBytes.longretval;//ThestartingpositionintheBLOBoutput.longstartIndex=0;//Thepublisheridtouseinthefilename.stringpubID="";//OpentheconnectionandreaddataintotheDataReader.connection.Open();SqlDataReaderreader=command.ExecuteReader(CommandBehavior.SequentialAccess);while(reader.Read()){//Getthepublisherid,whichmustoccurbeforegettingthelogo.pubID=reader.GetString(0);//Createafiletoholdtheoutput.stream=newFileStream("logo"+pubID+".bmp",FileMode.OpenOrCreate,FileAccess.Write);writer=newBinaryWriter(stream);//ResetthestartingbyteforthenewBLOB.startIndex=0;//ReadbytesintooutByte[]andretainthenumberofbytesreturned.retval=reader.GetBytes(1,startIndex,outByte,0,bufferSize);//Continuewhiletherearebytesbeyondthesizeofthebuffer.while(retval==bufferSize){writer.Write(outByte);writer.Flush();//Repositionstartindextoendoflastbufferandfillbuffer.startIndex+=bufferSize;retval=reader.GetBytes(1,startIndex,outByte,0,bufferSize);}//Writetheremainingbuffer.writer.Write(outByte,0,(int)retval-1);writer.Flush();//Closetheoutputfile.writer.Close();stream.Close();}//Closethereaderandtheconnection.reader.Close();connection.Close();知識(shí)點(diǎn)解析：暫無解析7、請(qǐng)編程遍歷頁(yè)面上所有TextBox控件并給它賦值為string.Empty？標(biāo)準(zhǔn)答案：protectedvoidPage_Load(objectsender,EventArgse){foreach(ControlctlinPage.Controls[0].Controls){if(ctl.GetType().Name=="TextBox"){TextBoxtb=newTextBox();tb=(TextBox)this.FindControl(ctl.ID);tb.Text="";}}}知識(shí)點(diǎn)解析：暫無解析8、Remoting簡(jiǎn)介標(biāo)準(zhǔn)答案：.NETRemoting(下文簡(jiǎn)稱Remoting)是一種可用于開發(fā)分布式應(yīng)用程序的技術(shù)。其主要的結(jié)構(gòu)，分為：遠(yuǎn)程對(duì)象、提供遠(yuǎn)程對(duì)象的遠(yuǎn)程服務(wù)器，以及可以訪問何使用遠(yuǎn)程對(duì)象的客戶端。這三個(gè)部分，可以分布于同一臺(tái)計(jì)算機(jī)的同一個(gè)進(jìn)程，或者是不同的進(jìn)程，也可以是處于網(wǎng)絡(luò)上的不同的計(jì)算機(jī)。Remoting技術(shù)最大的特點(diǎn)，就是對(duì)遠(yuǎn)程通信的過程進(jìn)行了抽象和封裝，使開發(fā)人員不必去處理底層通信的細(xì)節(jié)，而可以把重點(diǎn)放在對(duì)業(yè)務(wù)邏輯的處理上。而且Remoting的通信協(xié)議也比較靈活，可以使用多個(gè)通信協(xié)議、不同的數(shù)據(jù)格式類型，以及不同類型的序列化機(jī)制。在某些情況下，Remoting還允許你使用自定義的數(shù)據(jù)格式。知識(shí)點(diǎn)解析：暫無解析9、重載與覆蓋的區(qū)別標(biāo)準(zhǔn)答案：1、方法的覆蓋是子類和父類之間的關(guān)系，是垂直關(guān)系；方法的重載是同一個(gè)類中方法之間的關(guān)系，是水平關(guān)系。2、覆蓋只能由一個(gè)方法，或只能由一對(duì)方法產(chǎn)生關(guān)系；方法的重載是多個(gè)方法之間的關(guān)系。3、覆蓋要求參數(shù)列表相同；重載要求參數(shù)列表不同。4、覆蓋關(guān)系中，調(diào)用那個(gè)方法體，是根據(jù)對(duì)象的類型（對(duì)象對(duì)應(yīng)存儲(chǔ)空間類型）來決定；重載關(guān)系，是根據(jù)調(diào)用時(shí)的實(shí)參表與形參表來選擇方法體的。知識(shí)點(diǎn)解析：暫無解析10、大概描述一下ASP。NET服務(wù)器控件的生命周期標(biāo)準(zhǔn)答案：知識(shí)點(diǎn)解析：暫無解析程序員面試模擬試卷第4套一、面試題(本題共9題，每題1.0分，共9分。)1、某隊(duì)列的聲明如下：templateclassCQueue{public:CQueue(){}~CQueue(){}voidappendTail(constT&node);//appendaelementtotailvoiddeleteHead();//removeaelementfromheadprivate:T>m_stack1;T>m_stack2;};標(biāo)準(zhǔn)答案：/////////////////////////////////////////////////////////////////////////Appendaelementatthetailofthequeue///////////////////////////////////////////////////////////////////////templatevoidCQueue::appendTail(constT&element){//pushthenewelementintom_stack1m_stack1.push(element);}/////////////////////////////////////////////////////////////////////////Deletetheheadfromthequeue///////////////////////////////////////////////////////////////////////templatevoidCQueue::deleteHead(){//ifm_stack2isempty,andtherearesome//elementsinm_stack1,pushtheminm_stack2if(m_stack2.size()<=0){while(m_stack1.size()>0){T&data=m_stack1.top();m_stack1.pop();m_stack2.push(data);}}//pushtheelementintom_stack2assert(m_stack2.size()>0);m_stack2.pop();}知識(shí)點(diǎn)解析：從上面的類的聲明中，我們發(fā)現(xiàn)在隊(duì)列中有兩個(gè)棧。因此這道題實(shí)質(zhì)上是要求我們用兩個(gè)棧來實(shí)現(xiàn)一個(gè)隊(duì)列。相信大家對(duì)棧和隊(duì)列的基本性質(zhì)都非常了解了：棧是一種后入先出的數(shù)據(jù)容器，因此對(duì)隊(duì)列進(jìn)行的插入和刪除操作都是在棧頂上進(jìn)行；隊(duì)列是一種先入先出的數(shù)據(jù)容器，我們總是把新元素插入到隊(duì)列的尾部，而從隊(duì)列的頭部刪除元素。我們通過一個(gè)具體的例子來分析往該隊(duì)列插入和刪除元素的過程。首先插入一個(gè)元素a，不妨把先它插入到m_stack1。這個(gè)時(shí)候m_stack1中的元素有{a}，m_stack2為空。再插入兩個(gè)元素b和c，還是插入到m_stack1中，此時(shí)m_stack1中的元素有{a,b,c}，m_stack2中仍然是空的。這個(gè)時(shí)候我們?cè)囍鴱年?duì)列中刪除一個(gè)元素。按照隊(duì)列先入先出的規(guī)則，由于a比b、c先插入到隊(duì)列中，這次被刪除的元素應(yīng)該是a。元素a存儲(chǔ)在m_stack1中，但并不在棧頂上，因此不能直接進(jìn)行刪除。注意到m_stack2我們還一直沒有使用過，現(xiàn)在是讓m_stack2起作用的時(shí)候了。如果我們把m_stack1中的元素逐個(gè)pop出來并push進(jìn)入m_stack2，元素在m_stack2中的順序正好和原來在m_stack1中的順序相反。因此經(jīng)過兩次pop和push之后，m_stack1為空，而m_stack2中的元素是{c,b,a}。這個(gè)時(shí)候就可以pop出m_stack2的棧頂a了。pop之后的m_stack1為空，而m_stack2的元素為{c,b}，其中b在棧頂。這個(gè)時(shí)候如果我們還想繼續(xù)刪除應(yīng)該怎么辦呢？在剩下的兩個(gè)元素中b和c，b比c先進(jìn)入隊(duì)列，因此b應(yīng)該先刪除。而此時(shí)b恰好又在棧頂上，因此可以直接pop出去。這次pop之后，m_stack1中仍然為空，而m_stack2為{c}。從上面的分析我們可以總結(jié)出刪除一個(gè)元素的步驟：當(dāng)m_stack2中不為空時(shí)，在m_stack2中的棧頂元素是最先進(jìn)入隊(duì)列的元素，可以pop出去。如果m_stack2為空時(shí)，我們把m_stack1中的元素逐個(gè)pop出來并push進(jìn)入m_stack2。由于先進(jìn)入隊(duì)列的元素被壓到m_stack1的底端，經(jīng)過pop和push之后就處于m_stack2的頂端了，又可以直接pop出去。接下來我們?cè)俨迦胍粋€(gè)元素d。我們是不是還可以把它push進(jìn)m_stack1？這樣會(huì)不會(huì)有問題呢？我們說不會(huì)有問題。因?yàn)樵趧h除元素的時(shí)候，如果m_stack2中不為空，處于m_stack2中的棧頂元素是最先進(jìn)入隊(duì)列的，可以直接pop；如果m_stack2為空，我們把m_stack1中的元素pop出來并push進(jìn)入m_stack2。由于m_stack2中元素的順序和m_stack1相反，最先進(jìn)入隊(duì)列的元素還是處于m_stack2的棧頂，仍然可以直接pop。不會(huì)出現(xiàn)任何矛盾。我們用一個(gè)表來總結(jié)一下前面的例子執(zhí)行的步驟：[16*]總結(jié)完push和pop對(duì)應(yīng)的過程之后，我們可以開始動(dòng)手寫代碼了。2、輸入一個(gè)鏈表的頭結(jié)點(diǎn)，反轉(zhuǎn)該鏈表，并返回反轉(zhuǎn)后鏈表的頭結(jié)點(diǎn)。鏈表結(jié)點(diǎn)定義如下：{intm_nKey;ListNode*m_pNext;};標(biāo)準(zhǔn)答案：/////////////////////////////////////////////////////////////////////////Reversealistiteratively//Input:pHead-theheadoftheoriginallist//Output:theheadofthereversedhead///////////////////////////////////////////////////////////////////////ListNode*ReverseIteratively(ListNode*pHead){ListNode*pReversedHead=NULL;ListNode*pNode=pHead;ListNode*pPrev=NULL;while(pNode!=NULL){//getthenextnode,andsaveitatpNextListNode*pNext=pNode->m_pNext;//ifthenextnodeisnull,thecurrectistheendoforiginal//list,andit’stheheadofthereversedlistif(pNext==NULL)pReversedHead=pNode;//reversethelinkagebetweennodespNode->m_pNext=pPrev;//moveforwardonthethelistpPrev=pNode;pNode=pNext;}returnpReversedHead;}知識(shí)點(diǎn)解析：這是一道廣為流傳的微軟面試題。由于這道題能夠很好的反應(yīng)出程序員思維是否嚴(yán)密，在微軟之后已經(jīng)有很多公司在面試時(shí)采用了這道題。為了正確地反轉(zhuǎn)一個(gè)鏈表，需要調(diào)整指針的指向。與指針操作相關(guān)代碼總是容易出錯(cuò)的，因此最好在動(dòng)手寫程序之前作全面的分析。在面試的時(shí)候不急于動(dòng)手而是一開始做仔細(xì)的分析和設(shè)計(jì)，將會(huì)給面試官留下很好的印象，因?yàn)樵趯?shí)際的軟件開發(fā)中，設(shè)計(jì)的時(shí)間總是比寫代碼的時(shí)間長(zhǎng)。與其很快地寫出一段漏洞百出的代碼，遠(yuǎn)不如用較多的時(shí)間寫出一段健壯的代碼。為了將調(diào)整指針這個(gè)復(fù)雜的過程分析清楚，我們可以借助圖形來直觀地分析。假設(shè)下圖中l(wèi)、m和n是三個(gè)相鄰的結(jié)點(diǎn)：a?b?…?lmànà…假設(shè)經(jīng)過若干操作，我們已經(jīng)把結(jié)點(diǎn)l之前的指針調(diào)整完畢，這些結(jié)點(diǎn)的m_pNext指針都指向前面一個(gè)結(jié)點(diǎn)?，F(xiàn)在我們遍歷到結(jié)點(diǎn)m。當(dāng)然，我們需要把調(diào)整結(jié)點(diǎn)的m_pNext指針讓它指向結(jié)點(diǎn)l。但注意一旦調(diào)整了指針的指向，鏈表就斷開了，如下圖所示：a?b?…l?mnà…因?yàn)橐呀?jīng)沒有指針指向結(jié)點(diǎn)n，我們沒有辦法再遍歷到結(jié)點(diǎn)n了。因此為了避免鏈表斷開，我們需要在調(diào)整m的m_pNext之前要把n保存下來。接下來我們?cè)囍业椒崔D(zhuǎn)后鏈表的頭結(jié)點(diǎn)。不難分析出反轉(zhuǎn)后鏈表的頭結(jié)點(diǎn)是原始鏈表的尾位結(jié)點(diǎn)。什么結(jié)點(diǎn)是尾結(jié)點(diǎn)？就是m_pNext為空指針的結(jié)點(diǎn)。3、如果字符串一的所有字符按其在字符串中的順序出現(xiàn)在另外一個(gè)字符串二中，則字符串一稱之為字符串二的子串。注意，并不要求子串（字符串一）的字符必須連續(xù)出現(xiàn)在字符串二中。請(qǐng)編寫一個(gè)函數(shù)，輸入兩個(gè)字符串，求它們的最長(zhǎng)公共子串，并打印出最長(zhǎng)公共子串。例如：輸入兩個(gè)字符串BDCABA和ABCBDAB，字符串BCBA和BDAB都是是它們的最長(zhǎng)公共子串，則輸出它們的長(zhǎng)度4，并打印任意一個(gè)子串。標(biāo)準(zhǔn)答案：#include"string.h"http://directionsofLCSgenerationenumdecreaseDir{kInit=0,kLeft,kUp,kLeftUp};///////////////////////////////////////////////////////////////////////////////Getthelengthoftwostrings’LCSs,andprintoneoftheLCSs//Input:pStr1-thefirststring//pStr2-thesecondstring//Output:thelengthoftwostrings’LCSs/////////////////////////////////////////////////////////////////////////////intLCS(char*pStr1,char*pStr2){if(!pStr1||!pStr2)return0;size_tlength1=strlen(pStr1);size_tlength2=strlen(pStr2);if(!length1||!length2)return0;size_ti,j;//initiatethelengthmatrixint**LCS_length;LCS_length=(int**)(newint[length1]);for(i=0;i<length1;++i)LCS_length[i]=(int*)newint[length2];for(i=0;i<length1;++i)for(j=0;j<length2;++j)LCS_length[i][j]=0;//initiatethedirectionmatrixint**LCS_direction;LCS_direction=(int**)(newint[length1]);for(i=0;i<length1;++i)LCS_direction[i]=(int*)newint[length2];for(i=0;i<length1;++i)for(j=0;j<length2;++j)LCS_direction[i][j]=kInit;for(i=0;i<length1;++i){for(j=0;j<length2;++j){if(i==0||j==0){if(pStr1[i]==pStr2[j]){LCS_length[i][j]=1;LCS_direction[i][j]=kLeftUp;}elseLCS_length[i][j]=0;}//acharofLCSisfound,//itcomesfromtheleftupentryinthedirectionmatrixelseif(pStr1[i]==pStr2[j]){LCS_length[i][j]=LCS_length[i-1][j-1]+1;LCS_direction[i][j]=kLeftUp;}//itcomesfromtheupentryinthedirectionmatrixelseif(LCS_length[i-1][j]>LCS_length[i][j-1]){LCS_length[i][j]=LCS_length[i-1][j];LCS_direction[i][j]=kUp;}//itcomesfromtheleftentryinthedirectionmatrixelse{LCS_length[i][j]=LCS_length[i][j-1];LCS_direction[i][j]=kLeft;}}}LCS_Print(LCS_direction,pStr1,pStr2,length1-1,length2-1);returnLCS_length[length1-1][length2-1];}///////////////////////////////////////////////////////////////////////////////PrintaLCSfortwostrings//Input:LCS_direction-a2dmatrixwhichrecordsthedirectionof//LCSgeneration//pStr1-thefirststring//pStr2-thesecondstring//row-therowindexinthematrixLCS_direction//col-thecolumnindexinthematrixLCS_direction/////////////////////////////////////////////////////////////////////////////voidLCS_Print(int**LCS_direction,char*pStr1,char*pStr2,size_trow,size_tcol){if(pStr1==NULL||pStr2==NULL)return;size_tlength1=strlen(pStr1);size_tlength2=strlen(pStr2);if(length1==0||length2==0||!(row<length1&&col<length2))return;//kLeftUpimpliesacharintheLCSisfoundif(LCS_direction[row][col]==kLeftUp){if(row>0&&col>0)LCS_Print(LCS_direction,pStr1,pStr2,row-1,col-1);//printthecharprintf("%c",pStr1[row]);}elseif(LCS_direction[row][col]==kLeft){//movetotheleftentryinthedirectionmatrixif(col>0)LCS_Print(LCS_direction,pStr1,pStr2,row,col-1);}elseif(LCS_direction[row][col]==kUp){//movetotheupentryinthedirectionmatrixif(row>0)LCS_Print(LCS_direction,pStr1,pStr2,row-1,col);}}知識(shí)點(diǎn)解析：求最長(zhǎng)公共子串（LongestCommonSubsequence,LCS）是一道非常經(jīng)典的動(dòng)態(tài)規(guī)劃題，因此一些重視算法的公司像MicroStrategy都把它當(dāng)作面試題。完整介紹動(dòng)態(tài)規(guī)劃將需要很長(zhǎng)的篇幅，因此我不打算在此全面討論動(dòng)態(tài)規(guī)劃相關(guān)的概念，只集中對(duì)LCS直接相關(guān)內(nèi)容作討論。如果對(duì)動(dòng)態(tài)規(guī)劃不是很熟悉，請(qǐng)參考相關(guān)算法書比如算法討論。先介紹LCS問題的性質(zhì)：記Xm={x0,x1,…xm-1}和Yn={y0,y1,…yn-1}為兩個(gè)字符串，而Zk={z0,z1,…zk-1}是它們的LCS，則：1.如果xm-1=yn-1，那么zk-1=xm-1=yn-1，并且Zk-1是Xm-1和Yn-1的LCS；2.如果xm-1≠yn-1，那么當(dāng)zk-1≠xm-1時(shí)Z是Xm-1和Y的LCS；3.如果xm-1≠yn-1，那么當(dāng)zk-1≠yn-1時(shí)Z是Yn-1和X的LCS；下面簡(jiǎn)單證明一下這些性質(zhì)：1.如果zk-1≠xm-1，那么我們可以把xn-1（yk-1）加到Z中得到Z’，這樣就得到X和Y的一個(gè)長(zhǎng)度為k+1的公共子串Z’。這就與長(zhǎng)度為k的Z是X和Y的LCS相矛盾了。因此一定有zk-1=xm-1=yn-1。既然zk-1=xm-1=yn-1，那如果我們刪除zk-1（xm-1、yn-1）得到的Zk-1，Xm-1和Yn-1，顯然Zk-1是Xm-1和Yn-1的一個(gè)公共子串，現(xiàn)在我們證明Zk-1是Xm-1和Yn-1的LCS。用反證法不難證明。假設(shè)有Xm-1和Yn-1有一個(gè)長(zhǎng)度超過k-1的公共子串W，那么我們把加到W中得到W’，那W’就是X和Y的公共子串，并且長(zhǎng)度超過k，這就和已知條件相矛盾了。2.還是用反證法證明。假設(shè)Z不是Xm-1和Y的LCS，則存在一個(gè)長(zhǎng)度超過k的W是Xm-1和Y的LCS，那W肯定也X和Y的公共子串，而已知條件中X和Y的公共子串的最大長(zhǎng)度為k。矛盾。3.證明同2。有了上面的性質(zhì)，我們可以得出如下的思路：求兩字符串Xm={x0,x1,…xm-1}和Yn={y0,y1,…yn-1}的LCS，如果xm-1=yn-1，那么只需求得Xm-1和Yn-1的LCS，并在其后添加xm-1（yn-1）即可；如果xm-1≠yn-1，我們分別求得Xm-1和Y的LCS和Yn-1和X的LCS，并且這兩個(gè)LCS中較長(zhǎng)的一個(gè)為X和Y的LCS。如果我們記字符串Xi和Yj的LCS的長(zhǎng)度為c[i,j]，我們可以遞歸地求c[i,j]：上面的公式用遞歸函數(shù)不難求得。但從前面求Fibonacci第n項(xiàng)的分析中我們知道直接遞歸會(huì)有很多重復(fù)計(jì)算，我們用從底向上循環(huán)求解的思路效率更高。為了能夠采用循環(huán)求解的思路，我們用一個(gè)矩陣（參考代碼中的LCS_length）保存下來當(dāng)前已經(jīng)計(jì)算好了的c[i,j]，當(dāng)后面的計(jì)算需要這些數(shù)據(jù)時(shí)就可以直接從矩陣讀取。另外，求取c[i,j]可以從c[i-1,j-1]、c[i,j-1]或者c[i-1,j]三個(gè)方向計(jì)算得到，相當(dāng)于在矩陣LCS_length中是從c[i-1,j-1]，c[i,j-1]或者c[i-1,j]的某一個(gè)各自移動(dòng)到c[i,j]，因此在矩陣中有三種不同的移動(dòng)方向：向左、向上和向左上方，其中只有向左上方移動(dòng)時(shí)才表明找到LCS中的一個(gè)字符。于是我們需要用另外一個(gè)矩陣（參考代碼中的LCS_direction）保存移動(dòng)的方向。4、定義字符串的左旋轉(zhuǎn)操作：把字符串前面的若干個(gè)字符移動(dòng)到字符串的尾部。如把字符串a(chǎn)bcdef左旋轉(zhuǎn)2位得到字符串cdefab。請(qǐng)實(shí)現(xiàn)字符串左旋轉(zhuǎn)的函數(shù)。要求時(shí)間對(duì)長(zhǎng)度為n的字符串操作的復(fù)雜度為O(n)，輔助內(nèi)存為O(1)。標(biāo)準(zhǔn)答案：#include"string.h"http://///////////////////////////////////////////////////////////////////////Movethefirstncharsinastringtoitsend///////////////////////////////////////////////////////////////////////char*LeftRotateString(char*pStr,unsignedintn){if(pStr!=NULL){intnLength=static_cast(strlen(pStr));if(nLength>0||n==0||n>nLength){char*pFirstStart=pStr;char*pFirstEnd=pStr+n-1;char*pSecondStart=pStr+n;char*pSecondEnd=pStr+nLength-1;//reversethefirstpartofthestringReverseString(pFirstStart,pFirstEnd);//reversethesecondpartofthestrintReverseString(pSecondStart,pSecondEnd);//reversethewholestringReverseString(pFirstStart,pSecondEnd);}}returnpStr;}/////////////////////////////////////////////////////////////////////////ReversethestringbetweenpStartandpEnd///////////////////////////////////////////////////////////////////////voidReverseString(char*pStart,char*pEnd){if(pStart==NULL||pEnd==NULL){while(pStart<=pEnd){chartemp=*pStart;*pStart=*pEnd;*pEnd=temp;pStart++;pEnd--;}}}知識(shí)點(diǎn)解析：如果不考慮時(shí)間和空間復(fù)雜度的限制，最簡(jiǎn)單的方法莫過于把這道題看成是把字符串分成前后兩部分，通過旋轉(zhuǎn)操作把這兩個(gè)部分交換位置。于是我們可以新開辟一塊長(zhǎng)度為n+1的輔助空間，把原字符串后半部分拷貝到新空間的前半部分，在把原字符串的前半部分拷貝到新空間的后半部分。不難看出，這種思路的時(shí)間復(fù)雜度是O(n)，需要的輔助空間也是O(n)。接下來的一種思路可能要稍微麻煩一點(diǎn)。我們假設(shè)把字符串左旋轉(zhuǎn)m位。于是我們先把第0個(gè)字符保存起來，把第m個(gè)字符放到第0個(gè)的位置，在把第2m個(gè)字符放到第m個(gè)的位置…依次類推，一直移動(dòng)到最后一個(gè)可以移動(dòng)字符，最后在把原來的第0個(gè)字符放到剛才移動(dòng)的位置上。接著把第1個(gè)字符保存起來，把第m+1個(gè)元素移動(dòng)到第1個(gè)位置…重復(fù)前面處理第0個(gè)字符的步驟，直到處理完前面的m個(gè)字符。該思路還是比較容易理解，但當(dāng)字符串的長(zhǎng)度n不是m的整數(shù)倍的時(shí)候，寫程序會(huì)有些麻煩，感興趣的朋友可以自己試一下。由于下面還要介紹更好的方法，這種思路的代碼我就不提供了。我們還是把字符串看成有兩段組成的，記位XY。左旋轉(zhuǎn)相當(dāng)于要把字符串XY變成YX。我們先在字符串上定義一種翻轉(zhuǎn)的操作，就是翻轉(zhuǎn)字符串中字符的先后順序。把X翻轉(zhuǎn)后記為XT。顯然有(XT)T=X。我們首先對(duì)X和Y兩段分別進(jìn)行翻轉(zhuǎn)操作，這樣就能得到XTYT。接著再對(duì)XTYT進(jìn)行翻轉(zhuǎn)操作，得到(XTYT)T=(YT)T(XT)T=YX。正好是我們期待的結(jié)果。分析到這里我們?cè)倩氐皆瓉淼念}目。我們要做的僅僅是把字符串分成兩段，第一段為前面m個(gè)字符，其余的字符分到第二段。再定義一個(gè)翻轉(zhuǎn)字符串的函數(shù)，按照前面的步驟翻轉(zhuǎn)三次就行了。時(shí)間復(fù)雜度和空間復(fù)雜度都合乎要求。5、輸入一個(gè)整數(shù)，求該整數(shù)的二進(jìn)制表達(dá)中有多少個(gè)1。例如輸入10，由于其二進(jìn)制表示為1010，有兩個(gè)1，因此輸出2。標(biāo)準(zhǔn)答案：/////////////////////////////////////////////////////////////////////////Gethowmany1sinaninteger’sbinaryexpression///////////////////////////////////////////////////////////////////////intNumberOf1_Solution1(inti){intcount=0;while(i){if(i&1)count++;i=i>>1;}returncount;}可能有讀者會(huì)問，整數(shù)右移一位在數(shù)學(xué)上是和除以2是等價(jià)的。那可不可以把上面的代碼中的右移運(yùn)算符換成除以2呢？答案是最好不要換成除法。因?yàn)槌ǖ男时纫莆贿\(yùn)算要低的多，在實(shí)際編程中如果可以應(yīng)盡可能地用移位運(yùn)算符代替乘除法。這個(gè)思路當(dāng)輸入i是正數(shù)時(shí)沒有問題，但當(dāng)輸入的i是一個(gè)負(fù)數(shù)時(shí)，不但不能得到正確的1的個(gè)數(shù)，還將導(dǎo)致死循環(huán)。以負(fù)數(shù)0x80000000為例，右移一位的時(shí)候，并不是簡(jiǎn)單地把最高位的1移到第二位變成0x40000000，而是0xC0000000。這是因?yàn)橐莆磺笆莻€(gè)負(fù)數(shù)，仍然要保證移位后是個(gè)負(fù)數(shù)，因此移位后的最高位會(huì)設(shè)為1。如果一直做右移運(yùn)算，最終這個(gè)數(shù)字就會(huì)變成0xFFFFFFFF而陷入死循環(huán)。為了避免死循環(huán)，我們可以不右移輸入的數(shù)字i。首先i和1做與運(yùn)算，判斷i的最低位是不是為1。接著把1左移一位得到2，再和i做與運(yùn)算，就能判斷i的次高位是不是1……這樣反復(fù)左移，每次都能判斷i的其中一位是不是1。基于此，我們得到如下代碼：/////////////////////////////////////////////////////////////////////////Gethowmany1sinaninteger’sbinaryexpression///////////////////////////////////////////////////////////////////////intNumberOf1_Solution2(inti){intcount=0;unsignedintflag=1;while(flag){if(i&flag)count++;flag=flag<<1;}returncount;}另外一種思路是如果一個(gè)整數(shù)不為0，那么這個(gè)整數(shù)至少有一位是1。如果我們把這個(gè)整數(shù)減去1，那么原來處在整數(shù)最右邊的1就會(huì)變成0，原來在1后面的所有的0都會(huì)變成1。其余的所有位將不受到影響。舉個(gè)例子：一個(gè)二進(jìn)制數(shù)1100，從右邊數(shù)起的第三位是處于最右邊的一個(gè)1。減去1后，第三位變成0，它后面的兩位0變成1，而前面的1保持不變，因此得到結(jié)果是1011。我們發(fā)現(xiàn)減1的結(jié)果是把從最右邊一個(gè)1開始的所有位都取反了。這個(gè)時(shí)候如果我們?cè)侔言瓉淼恼麛?shù)和減去1之后的結(jié)果做與運(yùn)算，從原來整數(shù)最右邊一個(gè)1那一位開始所有位都會(huì)變成0。如1100&1011=1000。也就是說，把一個(gè)整數(shù)減去1，再和原整數(shù)做與運(yùn)算，會(huì)把該整數(shù)最右邊一個(gè)1變成0。那么一個(gè)整數(shù)的二進(jìn)制有多少個(gè)1，就可以進(jìn)行多少次這樣的操作。這種思路對(duì)應(yīng)的代碼如下：/////////////////////////////////////////////////////////////////////////Gethowmany1sinaninteger’sbinaryexpression///////////////////////////////////////////////////////////////////////intNumberOf1_Solution3(inti){intcount=0;while(i){++count;i=(i-1)&i;}returncount;}知識(shí)點(diǎn)解析：這是一道很基本的考查位運(yùn)算的面試題。包括微軟在內(nèi)的很多公司都曾采用過這道題。一個(gè)很基本的想法是，我們先判斷整數(shù)的最右邊一位是不是1。接著把整數(shù)右移一位，原來處于右邊第二位的數(shù)字現(xiàn)在被移到第一位了，再判斷是不是1。這樣每次移動(dòng)一位，直到這個(gè)整數(shù)變成0為止。現(xiàn)在的問題變成怎樣判斷一個(gè)整數(shù)的最右邊一位是不是1了。很簡(jiǎn)單，如果它和整數(shù)1作與運(yùn)算。由于1除了最右邊一位以外，其他所有位都為0。因此如果與運(yùn)算的結(jié)果為1，表示整數(shù)的最右邊一位是1，否則是0。6、一個(gè)臺(tái)階總共有n級(jí)，如果一次可以跳1級(jí)，也可以跳2級(jí)。求總共有多少總跳法，并分析算法的時(shí)間復(fù)雜度。標(biāo)準(zhǔn)答案：首先我們考慮最簡(jiǎn)單的情況。如果只有1級(jí)臺(tái)階，那顯然只有一種跳法。如果有2級(jí)臺(tái)階，那就有兩種跳的方法了：一種是分兩次跳，每次跳1級(jí)；另外一種就是一次跳2級(jí)?，F(xiàn)在我們?cè)賮碛懻撘话闱闆r。我們把n級(jí)臺(tái)階時(shí)的跳法看成是n的函數(shù)，記為f(n)。當(dāng)n>2時(shí)，第一次跳的時(shí)候就有兩種不同的選擇：一是第一次只跳1級(jí)，此時(shí)跳法數(shù)目等于后面剩下的n-1級(jí)臺(tái)階的跳法數(shù)目，即為f(n-1)；另外一種選擇是第一次跳2級(jí)，此時(shí)跳法數(shù)