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

程序員面試模擬試卷1（共9套）（共93題）程序員面試模擬試卷第1套一、面試題(本題共8題，每題1.0分，共8分。)1、將一整數(shù)逆序后放入一數(shù)組中（要求遞歸實現(xià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();}知識點解析：暫無解析2、求高于平均分的學生學號及成績（學號和成績人工輸入）標準答案：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();}知識點解析：暫無解析3、遞歸實現(xiàn)回文判斷（如：abcdedbca就是回文）標準答案：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();}知識點解析：暫無解析4、組合問題（從M個不同字符中任取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();}知識點解析：暫無解析5、分解成質因數(shù)(如435234=251*17*17*3*2)標準答案：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();}知識點解析：暫無解析6、尋找迷宮的一條出路（o：通路；X障礙）標準答案：#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();}知識點解析：暫無解析7、隨機分配座位，共50個學生，使學號相鄰的同學座位不能相鄰(早些時候用C#寫的，沒有用C改寫）。標準答案：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();}知識點解析：暫無解析8、求網格中的黑點分布（有6*7的網格，在某些格子中有黑點，已知各行與各列中有黑點的點數(shù)之和）標準答案：#defineROWS6#defineCOLS7intiPointsR[ROWS]={2,0,4,3,4,0};//各行黑點數(shù)和的情況intiPointsC[COLS]={4,1,2,2,1,2,1};//各列黑點數(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]知識點解析：暫無解析程序員面試模擬試卷第2套一、面試題(本題共10題，每題1.0分，共10分。)1、有4種面值（面值為1,4,12,21）的郵票很多枚，從中最多任取5張進行組合，求郵票最大連續(xù)組合值標準答案：#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();}知識點解析：暫無解析2、大整數(shù)數(shù)相乘的問題。標準答案：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知識點解析：暫無解析3、求最大連續(xù)遞增數(shù)字串（如“ads3sl456789DF3456ld345AA”中的“456789”）標準答案：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ù)字的長度增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++)//將原字符串中最長的連續(xù)數(shù)字串賦值給結果串strResult[iTmp]=strSource[iHead++];strResult[iTmp]=’\0’;returniMax;//返回連續(xù)數(shù)字的最大長度}intmain(intargc,char*argv[]){charstrSource[]="ads3sl456789DF3456ld345AA",charstrResult[sizeof(strSource)];printf("Len=%d,strResult=%s\nstrSource=%s\n",GetSubString(strSource,strResult),strResult,strSource);returngetchar();}知識點解析：暫無解析4、四個工人，四個任務，每個人做不同的任務需要的時間不同，求任務分配的最優(yōu)方案。（2005年5月29日全國計算機軟件資格水平考試——軟件設計師的算法題）。標準答案：#include"stdafx.h"#defineN4intCost[N][N]={{2,12,5,32},//行號：任務序號，列號：工人序號{8,15,7,11},//每行元素值表示這個任務由不同工人完成所需要的時間{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知識點解析：暫無解析5、八皇后問題（輸出所有情況，不過有些結果只是旋轉了90度而已）。哈哈：）回溯算法的典型例題標準答案：#defineN8intBoard[N][N];intValid(inti,intj)//所下棋子有效性的嚴正{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知識點解析：暫無解析6、實現(xiàn)strstr功能（尋找子串在父串中首次出現(xià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();}}知識點解析：暫無解析7、現(xiàn)在小明一家過一座橋，過橋的時候是黑夜，所以必須有燈?，F(xiàn)在小明過橋要1秒，小明的弟弟要3秒，小明的爸爸要6秒，小明的媽媽要八秒，小明的爺爺要12秒。每次此橋最多可過兩人，而過橋的速度依過橋最慢者而定，而且燈在點燃后30秒就會熄滅。問小明一家如何過橋？（原本是個智力題，這里用程序來求解）標準答案：#include"stdafx.h"#defineN5#defineSIZE64//將人員編號：小明-0，弟弟-1，爸爸-2，媽媽-3，爺爺-4//每個人的當前位置：0--在橋左邊，1--在橋右邊intPosition[N];//過橋臨時方案的數(shù)組下標；臨時方案；最小時間方案；intIndex,TmpScheme[SIZE],Scheme[SIZE];//最小過橋時間總和，初始值100；每個人過橋所需要的時間intMinTime=100,Time[N]={1,3,6,8,12};//尋找最佳過橋方案。Remnant:未過橋人數(shù);CurTime:當前已用時間;//Direction:過橋方向,1--向右,0--向左voidFind(intRemnant,intCurTime,intDirection){if(Remnant==0){//所有人已經過橋，更新最少時間及方案MinTime=CurTime;for(inti=0;i=0;i++){Scheme[i]=TmpScheme[i];}}elseif(Direction==1){//過橋方向向右，從橋左側選出兩人過橋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();}知識點解析：暫無解析8、2005年11月金山筆試題。編碼完成下面的處理函數(shù)。函數(shù)將字符串中的字符’*’移到串的前部分，前面的非’*’字符后移，但不能改變非’*’字符的先后順序，函數(shù)返回串中字符’*’的數(shù)量。如原始串為：ab**cd**e*12，處理后為*****abcde12，函數(shù)并返回值為5。（要求使用盡量少的時間和輔助空間）標準答案：intchange(char*str)/*這個算法并不高效，從后向前搜索效率要高些*/{intcount=0;/*記錄串中字符’*’的個數(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];/*的非*字符逐個后移，直到遇到*字符*/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();}//終于得到一個比較高效的算法，一個網友提供，應該和金山面試官的想法一致。算法如下：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;}知識點解析：暫無解析9、2005年11月15日華為軟件研發(fā)筆試題。實現(xiàn)一單鏈表的逆轉。標準答案：#include"stdafx.h"typedefchareleType;//定義鏈表中的數(shù)據(jù)類型typedefstructlistnode//定義單鏈表結構{eleTypedata;structlistnode*next;}node;node*create(intn)//創(chuàng)建單鏈表，n為節(jié)點個數(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)//逆轉單鏈表函數(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();}知識點解析：暫無解析10、編碼實現(xiàn)字符串轉整型的函數(shù)（實現(xiàn)函數(shù)atoi的功能），據(jù)說是神州數(shù)碼筆試題。如將字符串”+123”-->123,”-0123”-->-123,“123CS45”-->123,“123.45CS”-->123,“CS123.45”-->0標準答案：#include"stdafx.h"intstr2int(constchar*str)//字符串轉整型函數(shù){inti=0,sign=1,value=0;if(str==NULL)returnNULL;//空串直接返回NULLif(str[0]==’-’||str[0]==’+’){//判斷是否存在符號位i=1;sign=(str[0]==’-’?-1:1);}for(;str[i]>=’0’&&str[i]<=’9’;i++)//如果是數(shù)字，則繼續(xù)轉換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();}知識點解析：暫無解析程序員面試模擬試卷第3套一、面試題(本題共10題，每題1.0分，共10分。)1、描述一下C#中索引器的實現(xiàn)過程，是否只能根據(jù)數(shù)字進行索引？標準答案：索引器允許類或結構的實例按照與數(shù)組相同的方式進行索引。索引器不必根據(jù)整數(shù)值進行索引，由您決定如何定義特定的查找機制。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]);}}知識點解析：暫無解析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);}}產生的輸出結果是什么？標準答案：x=1,y=2知識點解析：暫無解析3、常用的調用webservice方法有哪些？標準答案：訪問WebService的三種方法，GET,POST,和基于SOAP協(xié)議的Web代理的調用知識點解析：暫無解析4、大概描述一下ASP。NET頁面的生命周期標準答案：知識點解析：暫無解析5、在下面的例子里usingSystem;classA{publicA(){PrintFields();}publicvirtualvoidPrintFields(){}}classB:A{intx=1;inty;publicB(){y=-1;}publicoverridevoidPrintFields(){Console.WriteLine("x={0},y={1}",x,y);}}當使用newB()創(chuàng)建B的實例時，產生什么輸出？標準答案：x=1,y=0知識點解析：暫無解析6、如何通過ADO.NET讀取數(shù)據(jù)庫中的圖片？標準答案：//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();知識點解析：暫無解析7、請編程遍歷頁面上所有TextBox控件并給它賦值為string.Empty？標準答案：protectedvoidPage_Load(objectsender,EventArgse){foreach(ControlctlinPage.Controls[0].Controls){if(ctl.GetType().Name=="TextBox"){TextBoxtb=newTextBox();tb=(TextBox)this.FindControl(ctl.ID);tb.Text="";}}}知識點解析：暫無解析8、Remoting簡介標準答案：.NETRemoting(下文簡稱Remoting)是一種可用于開發(fā)分布式應用程序的技術。其主要的結構，分為：遠程對象、提供遠程對象的遠程服務器，以及可以訪問何使用遠程對象的客戶端。這三個部分，可以分布于同一臺計算機的同一個進程，或者是不同的進程，也可以是處于網絡上的不同的計算機。Remoting技術最大的特點，就是對遠程通信的過程進行了抽象和封裝，使開發(fā)人員不必去處理底層通信的細節(jié)，而可以把重點放在對業(yè)務邏輯的處理上。而且Remoting的通信協(xié)議也比較靈活，可以使用多個通信協(xié)議、不同的數(shù)據(jù)格式類型，以及不同類型的序列化機制。在某些情況下，Remoting還允許你使用自定義的數(shù)據(jù)格式。知識點解析：暫無解析9、重載與覆蓋的區(qū)別標準答案：1、方法的覆蓋是子類和父類之間的關系，是垂直關系；方法的重載是同一個類中方法之間的關系，是水平關系。2、覆蓋只能由一個方法，或只能由一對方法產生關系；方法的重載是多個方法之間的關系。3、覆蓋要求參數(shù)列表相同；重載要求參數(shù)列表不同。4、覆蓋關系中，調用那個方法體，是根據(jù)對象的類型（對象對應存儲空間類型）來決定；重載關系，是根據(jù)調用時的實參表與形參表來選擇方法體的。知識點解析：暫無解析10、大概描述一下ASP。NET服務器控件的生命周期標準答案：知識點解析：暫無解析程序員面試模擬試卷第4套一、面試題(本題共9題，每題1.0分，共9分。)1、某隊列的聲明如下：templateclassCQueue{public:CQueue(){}~CQueue(){}voidappendTail(constT&node);//appendaelementtotailvoiddeleteHead();//removeaelementfromheadprivate:T>m_stack1;T>m_stack2;};標準答案：/////////////////////////////////////////////////////////////////////////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();}知識點解析：從上面的類的聲明中，我們發(fā)現(xiàn)在隊列中有兩個棧。因此這道題實質上是要求我們用兩個棧來實現(xiàn)一個隊列。相信大家對棧和隊列的基本性質都非常了解了：棧是一種后入先出的數(shù)據(jù)容器，因此對隊列進行的插入和刪除操作都是在棧頂上進行；隊列是一種先入先出的數(shù)據(jù)容器，我們總是把新元素插入到隊列的尾部，而從隊列的頭部刪除元素。我們通過一個具體的例子來分析往該隊列插入和刪除元素的過程。首先插入一個元素a，不妨把先它插入到m_stack1。這個時候m_stack1中的元素有{a}，m_stack2為空。再插入兩個元素b和c，還是插入到m_stack1中，此時m_stack1中的元素有{a,b,c}，m_stack2中仍然是空的。這個時候我們試著從隊列中刪除一個元素。按照隊列先入先出的規(guī)則，由于a比b、c先插入到隊列中，這次被刪除的元素應該是a。元素a存儲在m_stack1中，但并不在棧頂上，因此不能直接進行刪除。注意到m_stack2我們還一直沒有使用過，現(xiàn)在是讓m_stack2起作用的時候了。如果我們把m_stack1中的元素逐個pop出來并push進入m_stack2，元素在m_stack2中的順序正好和原來在m_stack1中的順序相反。因此經過兩次pop和push之后，m_stack1為空，而m_stack2中的元素是{c,b,a}。這個時候就可以pop出m_stack2的棧頂a了。pop之后的m_stack1為空，而m_stack2的元素為{c,b}，其中b在棧頂。這個時候如果我們還想繼續(xù)刪除應該怎么辦呢？在剩下的兩個元素中b和c，b比c先進入隊列，因此b應該先刪除。而此時b恰好又在棧頂上，因此可以直接pop出去。這次pop之后，m_stack1中仍然為空，而m_stack2為{c}。從上面的分析我們可以總結出刪除一個元素的步驟：當m_stack2中不為空時，在m_stack2中的棧頂元素是最先進入隊列的元素，可以pop出去。如果m_stack2為空時，我們把m_stack1中的元素逐個pop出來并push進入m_stack2。由于先進入隊列的元素被壓到m_stack1的底端，經過pop和push之后就處于m_stack2的頂端了，又可以直接pop出去。接下來我們再插入一個元素d。我們是不是還可以把它push進m_stack1？這樣會不會有問題呢？我們說不會有問題。因為在刪除元素的時候，如果m_stack2中不為空，處于m_stack2中的棧頂元素是最先進入隊列的，可以直接pop；如果m_stack2為空，我們把m_stack1中的元素pop出來并push進入m_stack2。由于m_stack2中元素的順序和m_stack1相反，最先進入隊列的元素還是處于m_stack2的棧頂，仍然可以直接pop。不會出現(xiàn)任何矛盾。我們用一個表來總結一下前面的例子執(zhí)行的步驟：[16*]總結完push和pop對應的過程之后，我們可以開始動手寫代碼了。2、輸入一個鏈表的頭結點，反轉該鏈表，并返回反轉后鏈表的頭結點。鏈表結點定義如下：{intm_nKey;ListNode*m_pNext;};標準答案：/////////////////////////////////////////////////////////////////////////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;}知識點解析：這是一道廣為流傳的微軟面試題。由于這道題能夠很好的反應出程序員思維是否嚴密，在微軟之后已經有很多公司在面試時采用了這道題。為了正確地反轉一個鏈表，需要調整指針的指向。與指針操作相關代碼總是容易出錯的，因此最好在動手寫程序之前作全面的分析。在面試的時候不急于動手而是一開始做仔細的分析和設計，將會給面試官留下很好的印象，因為在實際的軟件開發(fā)中，設計的時間總是比寫代碼的時間長。與其很快地寫出一段漏洞百出的代碼，遠不如用較多的時間寫出一段健壯的代碼。為了將調整指針這個復雜的過程分析清楚，我們可以借助圖形來直觀地分析。假設下圖中l(wèi)、m和n是三個相鄰的結點：a?b?…?lmànà…假設經過若干操作，我們已經把結點l之前的指針調整完畢，這些結點的m_pNext指針都指向前面一個結點。現(xiàn)在我們遍歷到結點m。當然，我們需要把調整結點的m_pNext指針讓它指向結點l。但注意一旦調整了指針的指向，鏈表就斷開了，如下圖所示：a?b?…l?mnà…因為已經沒有指針指向結點n，我們沒有辦法再遍歷到結點n了。因此為了避免鏈表斷開，我們需要在調整m的m_pNext之前要把n保存下來。接下來我們試著找到反轉后鏈表的頭結點。不難分析出反轉后鏈表的頭結點是原始鏈表的尾位結點。什么結點是尾結點？就是m_pNext為空指針的結點。3、如果字符串一的所有字符按其在字符串中的順序出現(xiàn)在另外一個字符串二中，則字符串一稱之為字符串二的子串。注意，并不要求子串（字符串一）的字符必須連續(xù)出現(xiàn)在字符串二中。請編寫一個函數(shù)，輸入兩個字符串，求它們的最長公共子串，并打印出最長公共子串。例如：輸入兩個字符串BDCABA和ABCBDAB，字符串BCBA和BDAB都是是它們的最長公共子串，則輸出它們的長度4，并打印任意一個子串。標準答案：#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);}}知識點解析：求最長公共子串（LongestCommonSubsequence,LCS）是一道非常經典的動態(tài)規(guī)劃題，因此一些重視算法的公司像MicroStrategy都把它當作面試題。完整介紹動態(tài)規(guī)劃將需要很長的篇幅，因此我不打算在此全面討論動態(tài)規(guī)劃相關的概念，只集中對LCS直接相關內容作討論。如果對動態(tài)規(guī)劃不是很熟悉，請參考相關算法書比如算法討論。先介紹LCS問題的性質：記Xm={x0,x1,…xm-1}和Yn={y0,y1,…yn-1}為兩個字符串，而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，那么當zk-1≠xm-1時Z是Xm-1和Y的LCS；3.如果xm-1≠yn-1，那么當zk-1≠yn-1時Z是Yn-1和X的LCS；下面簡單證明一下這些性質：1.如果zk-1≠xm-1，那么我們可以把xn-1（yk-1）加到Z中得到Z’，這樣就得到X和Y的一個長度為k+1的公共子串Z’。這就與長度為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的一個公共子串，現(xiàn)在我們證明Zk-1是Xm-1和Yn-1的LCS。用反證法不難證明。假設有Xm-1和Yn-1有一個長度超過k-1的公共子串W，那么我們把加到W中得到W’，那W’就是X和Y的公共子串，并且長度超過k，這就和已知條件相矛盾了。2.還是用反證法證明。假設Z不是Xm-1和Y的LCS，則存在一個長度超過k的W是Xm-1和Y的LCS，那W肯定也X和Y的公共子串，而已知條件中X和Y的公共子串的最大長度為k。矛盾。3.證明同2。有了上面的性質，我們可以得出如下的思路：求兩字符串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，并且這兩個LCS中較長的一個為X和Y的LCS。如果我們記字符串Xi和Yj的LCS的長度為c[i,j]，我們可以遞歸地求c[i,j]：上面的公式用遞歸函數(shù)不難求得。但從前面求Fibonacci第n項的分析中我們知道直接遞歸會有很多重復計算，我們用從底向上循環(huán)求解的思路效率更高。為了能夠采用循環(huán)求解的思路，我們用一個矩陣（參考代碼中的LCS_length）保存下來當前已經計算好了的c[i,j]，當后面的計算需要這些數(shù)據(jù)時就可以直接從矩陣讀取。另外，求取c[i,j]可以從c[i-1,j-1]、c[i,j-1]或者c[i-1,j]三個方向計算得到，相當于在矩陣LCS_length中是從c[i-1,j-1]，c[i,j-1]或者c[i-1,j]的某一個各自移動到c[i,j]，因此在矩陣中有三種不同的移動方向：向左、向上和向左上方，其中只有向左上方移動時才表明找到LCS中的一個字符。于是我們需要用另外一個矩陣（參考代碼中的LCS_direction）保存移動的方向。4、定義字符串的左旋轉操作：把字符串前面的若干個字符移動到字符串的尾部。如把字符串abcdef左旋轉2位得到字符串cdefab。請實現(xiàn)字符串左旋轉的函數(shù)。要求時間對長度為n的字符串操作的復雜度為O(n)，輔助內存為O(1)。標準答案：#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--;}}}知識點解析：如果不考慮時間和空間復雜度的限制，最簡單的方法莫過于把這道題看成是把字符串分成前后兩部分，通過旋轉操作把這兩個部分交換位置。于是我們可以新開辟一塊長度為n+1的輔助空間，把原字符串后半部分拷貝到新空間的前半部分，在把原字符串的前半部分拷貝到新空間的后半部分。不難看出，這種思路的時間復雜度是O(n)，需要的輔助空間也是O(n)。接下來的一種思路可能要稍微麻煩一點。我們假設把字符串左旋轉m位。于是我們先把第0個字符保存起來，把第m個字符放到第0個的位置，在把第2m個字符放到第m個的位置…依次類推，一直移動到最后一個可以移動字符，最后在把原來的第0個字符放到剛才移動的位置上。接著把第1個字符保存起來，把第m+1個元素移動到第1個位置…重復前面處理第0個字符的步驟，直到處理完前面的m個字符。該思路還是比較容易理解，但當字符串的長度n不是m的整數(shù)倍的時候，寫程序會有些麻煩，感興趣的朋友可以自己試一下。由于下面還要介紹更好的方法，這種思路的代碼我就不提供了。我們還是把字符串看成有兩段組成的，記位XY。左旋轉相當于要把字符串XY變成YX。我們先在字符串上定義一種翻轉的操作，就是翻轉字符串中字符的先后順序。把X翻轉后記為XT。顯然有(XT)T=X。我們首先對X和Y兩段分別進行翻轉操作，這樣就能得到XTYT。接著再對XTYT進行翻轉操作，得到(XTYT)T=(YT)T(XT)T=YX。正好是我們期待的結果。分析到這里我們再回到原來的題目。我們要做的僅僅是把字符串分成兩段，第一段為前面m個字符，其余的字符分到第二段。再定義一個翻轉字符串的函數(shù)，按照前面的步驟翻轉三次就行了。時間復雜度和空間復雜度都合乎要求。5、輸入一個整數(shù)，求該整數(shù)的二進制表達中有多少個1。例如輸入10，由于其二進制表示為1010，有兩個1，因此輸出2。標準答案：/////////////////////////////////////////////////////////////////////////Gethowmany1sinaninteger’sbinaryexpression///////////////////////////////////////////////////////////////////////intNumberOf1_Solution1(inti){intcount=0;while(i){if(i&1)count++;i=i>>1;}returncount;}可能有讀者會問，整數(shù)右移一位在數(shù)學上是和除以2是等價的。那可不可以把上面的代碼中的右移運算符換成除以2呢？答案是最好不要換成除法。因為除法的效率比移位運算要低的多，在實際編程中如果可以應盡可能地用移位運算符代替乘除法。這個思路當輸入i是正數(shù)時沒有問題，但當輸入的i是一個負數(shù)時，不但不能得到正確的1的個數(shù)，還將導致死循環(huán)。以負數(shù)0x80000000為例，右移一位的時候，并不是簡單地把最高位的1移到第二位變成0x40000000，而是0xC0000000。這是因為移位前是個負數(shù)，仍然要保證移位后是個負數(shù)，因此移位后的最高位會設為1。如果一直做右移運算，最終這個數(shù)字就會變成0xFFFFFFFF而陷入死循環(huán)。為了避免死循環(huán)，我們可以不右移輸入的數(shù)字i。首先i和1做與運算，判斷i的最低位是不是為1。接著把1左移一位得到2，再和i做與運算，就能判斷i的次高位是不是1……這樣反復左移，每次都能判斷i的其中一位是不是1?；诖耍覀兊玫饺缦麓a：/////////////////////////////////////////////////////////////////////////Gethowmany1sinaninteger’sbinaryexpression///////////////////////////////////////////////////////////////////////intNumberOf1_Solution2(inti){intcount=0;unsignedintflag=1;while(flag){if(i&flag)count++;flag=flag<<1;}returncount;}另外一種思路是如果一個整數(shù)不為0，那么這個整數(shù)至少有一位是1。如果我們把這個整數(shù)減去1，那么原來處在整數(shù)最右邊的1就會變成0，原來在1后面的所有的0都會變成1。其余的所有位將不受到影響。舉個例子：一個二進制數(shù)1100，從右邊數(shù)起的第三位是處于最右邊的一個1。減去1后，第三位變成0，它后面的兩位0變成1，而前面的1保持不變，因此得到結果是1011。我們發(fā)現(xiàn)減1的結果是把從最右邊一個1開始的所有位都取反了。這個時候如果我們再把原來的整數(shù)和減去1之后的結果做與運算，從原來整數(shù)最右邊一個1那一位開始所有位都會變成0。如1100&1011=1000。也就是說，把一個整數(shù)減去1，再和原整數(shù)做與運算，會把該整數(shù)最右邊一個1變成0。那么一個整數(shù)的二進制有多少個1，就可以進行多少次這樣的操作。這種思路對應的代碼如下：/////////////////////////////////////////////////////////////////////////Gethowmany1sinaninteger’sbinaryexpression///////////////////////////////////////////////////////////////////////intNumberOf1_Solution3(inti){intcount=0;while(i){++count;i=(i-1)&i;}returncount;}知識點解析：這是一道很基本的考查位運算的面試題。包括微軟在內的很多公司都曾采用過這道題。一個很基本的想法是，我們先判斷整數(shù)的最右邊一位是不是1。接著把整數(shù)右移一位，原來處于右邊第二位的數(shù)字現(xiàn)在被移到第一位了，再判斷是不是1。這樣每次移動一位，直到這個整數(shù)變成0為止。現(xiàn)在的問題變成怎樣判斷一個整數(shù)的最右邊一位是不是1了。很簡單，如果它和整數(shù)1作與運算。由于1除了最右邊一位以外，其他所有位都為0。因此如果與運算的結果為1，表示整數(shù)的最右邊一位是1，否則是0。6、一個臺階總共有n級，如果一次可以跳1級，也可以跳2級。求總共有多少總跳法，并分析算法的時間復雜度。標準答案：首先我們考慮最簡單的情況。如果只有1級臺階，那顯然只有一種跳法。如果有2級臺階，那就有兩種跳的方法了：一種是分兩次跳，每次跳1級；另外一種就是一次跳2級?，F(xiàn)在我們再來討論一般情況。我們把n級臺階時的跳法看成是n的函數(shù)，記為f(n)。當n>2時，第一次跳的時候就有兩種不同的選擇：一是第一次只跳1級，此時跳法數(shù)目等于后面剩下的n-1級臺階的跳法數(shù)目，即為f(n-1)；另外一種選擇是第一次跳2級，此時跳法數(shù)