軟件水平考試《程序員》習題及答案

軟件水平考試《程序員》習題及答案習題1在Word的編輯狀態(tài)打開了一個文檔，對文檔沒作任何修改，隨后單擊Word主窗口標題欄右側的“關閉"按鈕或者單擊“文件"菜單中的“退出”命令，則B僅文檔窗口被關閉文檔和Word主窗口全被關閉Word主窗口被關閉僅文檔和Word主窗口全未被關閉在Word的編輯狀態(tài)，文檔窗口顯示出水平標尺，拖動水平標尺上沿的“首行縮進"滑塊，則B文檔中各段落的首行起始位置都重新確定文檔中被選擇的各段落首行起始位置都重新確定文檔中各行的起始位置都重新確定插入點所在行的起始位置被重新確定3.在Word的編輯狀態(tài)，打開了“wl.doc"文檔，若要將經(jīng)過編輯后的文檔以“w2.doc”為名存盤，應當執(zhí)行“文件"菜單中的命令是C保存另存為HTML另存為版本

網(wǎng)關網(wǎng)橋計算機中對數(shù)據(jù)進行加工與處理的部件，通常稱為A運算器控制器顯示器存儲器微型計算機中內(nèi)存儲器比外存儲器A讀寫速度快存儲容量大運算速度慢以上三種都可以目前微型計算機中CPU進行算術運算和邏輯運算時，可以處理的二進制信息長度是DTOC\o"1-5"\h\z32位16位8位以上三種都可以微型計算機存儲器系統(tǒng)中的Cache是B只讀存儲器高速緩沖存儲器可編程只讀存儲器

可擦除可再編程只讀存儲器存儲容量1GB等于C1024B1024KB1024MB128MB習題2在從1到n的正數(shù)中1出現(xiàn)的次數(shù)題目：輸入一個整數(shù)n,求從1到n這n個整數(shù)的十進制表示中1出現(xiàn)的次數(shù)。例如輸入12,從1到12這些整數(shù)中包含1的數(shù)字有1,10,11和12,1一共出現(xiàn)了5次。分析：這是一道廣為流傳的google面試題。用最直觀的方法求解并不是很難，但遺憾的是效率不是很高；而要得出一個效率較高的算法，需要比較強的分析能力，并不是件很容易的事情。當然，google的面試題中簡單的也沒有幾道。首先我們來看最直觀的方法，分別求得1到n中每個整數(shù)中1出現(xiàn)的次數(shù)。而求一個整數(shù)的十進制表示中1出現(xiàn)的次數(shù)，就和本面試題系列的第22題很相像了。我們每次判斷整數(shù)的個位數(shù)字是不是lo如果這個數(shù)字大于10,除以10之后再判斷個位數(shù)字是不是lo基于這個思路，不難寫出如下的代碼：intNumberOf1(unsignedintn)；

///////////////////////////////////////////////////////////////////////////////Findthenumberof1intheintegersbetween1andn//Input：n-aninteger//Output:thenumberof1intheintegersbetween1andn/////////////////////////////////////////////////////////////////////////////intNumberOflBeforeBetweenlAndN_Solutionl(unsignedintn){intnumber=0；//Findthenumberof1ineachintegerbetween1andnfor(unsignedinti=1；i<=n；++i)number+=NumberOfl(i)；returnnumber；)/////////////////////////////////////////////////////////////////////////////

//Findthenumberof1inanintegerwithradix10//Input：n-aninteger//Output:thenumberof1innwithradix/////////////////////////////////////////////////////////////////////////////intNumberOf1(unsignedintn){intnumber=0；while(n)(if(n%10==1)number++；n=n/10；)returnnumber；)這個思路有一個非常明顯的缺點就是每個數(shù)字都要計算1在該數(shù)字中出現(xiàn)的次數(shù)，因此時間復雜度是0(n)。當輸入的n非常大的時候，需要大量的計算，運算效率很低。我們試著找出一些規(guī)律，來避免不必要的計算。我們用一個稍微大一點的數(shù)字21345作為例子來分析。我們把從

1到21345的所有數(shù)字分成兩段，即1-1235和1346-21345。先來看1346-21345中1出現(xiàn)的次數(shù)。1的出現(xiàn)分為兩種情況：一種情況是1出現(xiàn)在最高位（萬位）。從1到21345的數(shù)字中，1出現(xiàn)在10000-19999這10000個數(shù)字的萬位中，一共出現(xiàn)了10000（104）次；另外一種情況是1出現(xiàn)在除了最高位之外的其他位中。例子中1346-21345,這20000個數(shù)字中后面四位中1出現(xiàn)的次數(shù)是2000次（2*103,其中2的第一位的數(shù)值，103是因為數(shù)字的后四位數(shù)字其中一位為1,其余的三位數(shù)字可以在0到9這10個數(shù)字任意選擇，由排列組合可以得出總次數(shù)是2*103）。至于從1到1345的所有數(shù)字中1出現(xiàn)的次數(shù)，我們就可以用遞歸地求得了。這也是我們?yōu)槭裁匆?-21345分為1-1235和1346-21345兩段的原因。因為把21345的最高位去掉就得到1345,便于我們采用遞歸的思路。分析到這里還有一種特殊情況需要注意：前面我們舉例子是最高位是一個比1大的數(shù)字，此時最高位1出現(xiàn)的次數(shù)104（對五位數(shù)而言）o但如果最高位是1呢？比如輸入12345,從10000到12345這些數(shù)字中，1在萬位出現(xiàn)的次數(shù)就不是104次，而是2346次了，也就是除去最高位數(shù)字之后剩下的數(shù)字再加上lo基于前面的分析，我們可以寫出以下的代碼。在參考代碼中，為了編程方便，我把數(shù)字轉換成字符串了。[include"string.h”^include"stdlib.h”

intNumberOf1(constchar*strN)；intPowerBaselO(unsignedintn)；///////////////////////////////////////////////////////////////////////////////Findthenumberof1inanintegerwithradix10//Input:n-aninteger//Output:thenumberof1innwithradix/////////////////////////////////////////////////////////////////////////////intNumberOfIBeforeBetweenlAndN_So1ution2(intn){if(n<=0)return0；//converttheintegerintoastringcharstrN[50]；sprintf(strN,"%d",n)；returnNumberOfl(strN)；)/////////////////////////////////////////////////////////////////////////////

習題3整數(shù)的二進制表示中1的個數(shù)題目：輸入一個整數(shù)，求該整數(shù)的二進制表達中有多少個1。例如輸入10,由于其二進制表示為1010,有兩個1,因此輸出2。分析：這是一道很基本的考查位運算的面試題。包括微軟在內(nèi)的很多公司都曾采用過這道題。一個很基本的想法是，我們先判斷整數(shù)的最右邊一位是不是lo接著把整數(shù)右移一位，原來處于右邊第二位的數(shù)字現(xiàn)在被移到第一位了，再判斷是不是lo這樣每次移動一位，直到這個整數(shù)變成0為止?，F(xiàn)在的問題變成怎樣判斷一個整數(shù)的最右邊一位是不是1了。很簡單，如果它和整數(shù)1作與運算。由于1除了最右邊一位以外，其他所有位都為0。因此如果與運算的結果為1,表示整數(shù)的最右邊一位是1,否則是0。得到的代碼如下：/////////////////////////////////////////////////////////////////////////GethowmanyIsinaninteger1sbinaryexpression///////////////////////////////////////////////////////////////////////intNumberOfl_Solutionl(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,而是OxCOOOOOOOo這是因為移位前是個負數(shù)，仍然要保證移位后是個負數(shù)，因此移位后的最高位會設為lo如果一直做右移運算，最終這個數(shù)字就會變成OxFFFFFFFF而陷入死循環(huán)。為了避免死循環(huán)，我們可以不右移輸入的數(shù)字i。首先i和1做

與運算，判斷i的最低位是不是為1。接著把1左移一位得到2,再和i做與運算，就能判斷i的次高位是不是1……這樣反復左移，每次都能判斷i的其中一位是不是1?；诖?，我們得到如下代碼：IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII///////////////GethowmanyIsinaninteger1sbinaryexpression///////////////////////////////////////////////////////////////////////intNumberOfl_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保持不變，因此得到結果是1011O我們發(fā)現(xiàn)減1的結果是把從最右邊一個1開始的所有位都取反了。這個時候如果我們再把原來的整數(shù)和減去1之后的結果做與運算，從原來整數(shù)最右邊一個1那一位開始所有位都會變成0。如1100&1011=1000o也就是說，把一個整數(shù)減去1,再和原整數(shù)做與運算，會把該整數(shù)最右邊一個1變成0。那么一個整數(shù)的二進制有多少個1,就可以進行多少次這樣的操作。這種思路對應的代碼如下：IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII///////////////GethowmanyIsinaninteger1sbinaryexpression///////////////////////////////////////////////////////////////////////intNumberOfl_Solution3(inti)

在word的編輯狀態(tài)，被編輯文檔中的文字有“四號”、“五號"、“16”磅、“18"磅四種，下列關于所設定字號大小的比較中,正確的是A“四號”大于“五號"“四號"小于“五號"“16"磅大于“18”磅字的大小一樣，字體不同0SI（開放系統(tǒng)互連）參考模型的最高層是C表不層網(wǎng)絡層應用層會話層微型計算機中使用最普遍的字符編碼是DEBCDIC碼國標碼BCD碼ASCII碼微型計算機中的內(nèi)存儲器，通常采用C光存儲器磁表面存儲器半導體存儲器磁芯存儲器

intcount=0；while(i)(++count；i=(i-1)&i;}returncount；)習題4棧的push、pop序列題目：輸入兩個整數(shù)序列。其中一個序列表示棧的push順序，判斷另一個序列有沒有可能是對應的pop順序。為了簡單起見，我們假設push序列的任意兩個整數(shù)都是不相等的。比如輸入的push序列是1、2、3、4、5,那么4、5、3、2、1就有可能是一個pop系列。因為可以有如下的push和pop序列：push1,push2,push3,push4,pop,push5,pop,pop,pop,pop,這樣得到的pop序列就是4、5、3、2、lo但序列4、3、5、1、2就不可能是push序列1、2、3、4、5的pop序列。分析：這到題除了考查對棧這一基本數(shù)據(jù)結構的理解，還能考查我們的分析能力。這道題的一個很直觀的想法就是建立一個輔助棧，每次push的時候就把一個整數(shù)push進入這個輔助棧，同樣需要pop的時候就把

該棧的棧頂整數(shù)pop出來。我們以前面的序列4、5、3、2、1為例。第一個希望被pop出來的數(shù)字是4,因此4需要先push到棧里面。由于push的順序已經(jīng)由push序列確定了，也就是在把4push進棧之前，數(shù)字1,2,3都需要push到棧里面。此時棧里的包含4個數(shù)字，分別是1,2,3,4,其中4位于棧頂。把4pop出棧后，剩下三個數(shù)字1,2,3o接下來希望被pop的是5,由于仍然不是棧頂數(shù)字，我們接著在push序列中4以后的數(shù)字中尋找。找到數(shù)字5后再一次push進棧，這個時候5就是位于棧頂，可以被pop出來。接下來希望被pop的三個數(shù)字是3,2,lo每次操作前都位于棧頂，直接pop即可。再來看序列4、3、5、1、2opop數(shù)字4的情況和前面一樣。把4pop出來之后，3位于棧頂，直接pop0接下來希望pop的數(shù)字是5,由于5不是棧頂數(shù)字，我們到push序列中沒有被push進棧的數(shù)字中去搜索該數(shù)字，幸運的時候能夠找到5,于是把5push進入棧。此時pop5之后，棧內(nèi)包含兩個數(shù)字1、2,其中2位于棧頂。這個時候希望pop的數(shù)字是1,由于不是棧頂數(shù)字，我們需要到push序列中還沒有被push進棧的數(shù)字中去搜索該數(shù)字。但此時push序列中所有數(shù)字都已被push進入棧，因此該序列不可能是一個pop序列。也就是說，如果我們希望pop的數(shù)字正好是棧頂數(shù)字，直接pop出棧即可;如果希望pop的數(shù)字目前不在棧頂，我們就到push序列中還沒有被push到棧里的數(shù)字中去搜索這個數(shù)字，并把在它之前的所有數(shù)字都push進棧。如果所有的數(shù)字都被push進棧仍然沒有找到這

個數(shù)字，表明該序列不可能是一個pop序列。習題5最長公共子串題目：如果字符串一的所有字符按其在字符串中的順序出現(xiàn)在另外一個字符串二中，則字符串一稱之為字符串二的子串。注意，并不要求子串(字符串一)的字符必須連續(xù)出現(xiàn)在字符串二中。請編寫一個函數(shù)，輸入兩個字符串，求它們的最長公共子串，并打印出最長公共子串。例如：輸入兩個字符串BDCABA和ABCBDAB,字符串BCBA和BDAB都是是它們的最長公共子串，則輸出它們的長度4,并打印任意一個子串。分析：求最長公共子串(LongestCommonSubsequence,LCS)是一道非常經(jīng)典的動態(tài)規(guī)劃題，因此一些重視算法的公司像MicroStrategy都把它當作面試題。完整介紹動態(tài)規(guī)劃將需要很長的篇幅，因此我不打算在此全面討論動態(tài)規(guī)劃相關的概念，只集中對LCS直接相關內(nèi)容作討論。如果對動態(tài)規(guī)劃不是很熟悉，請參考相關算法書比如算法討論。先介紹LCS問題的性質：記Xm={xO,xl,…xm-1}和Yn={yO,yl,…，yn-1}為兩個字符串,而Zk={zO,zl,???zkT}是它們的LCS,則：如果xm~l=yn-l,那么zk-l=xm-l=yn-l,并且ZkT是Xm-1和Yn-1的LCS；

如果xm-l^yn-1,那么當zk-l^xm-1時Z是Xm-1和Y的LCS；如果xm-l^yn-1,那么當zk-l^yn-1時Z是Yn-1和X的LCS；下面簡單證明一下這些性質：如果泳-l^xm-l,那么我們可以把xm-1(yn-1)加到Z中得到V,這樣就得到X和Y的一個長度為k+1的公共子串Z，o這就與長度為k的Z是X和Y的LCS相矛盾了。因此一定有zk-l=xm-l=yn-lo既然zk-l=xm-l=yn-l,那如果我們刪除zkT(xmT、ynT)得到的Zk-1,Xm-l和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'就是X和Y的公共子串，并且長度超過k,這就和已知條件相矛盾了。還是用反證法證明。假設Z不是Xm-l和Y的LCS,則存在一個長度超過k的W是Xm-1和Y的LCS,那W肯定也X和Y的公共子串，而已知條件中X和Y的公共子串的最大長度為k。矛盾。證明同2。有了上面的性質，我們可以得出如下的思路：求兩字符串Xm=(xO,xl,???xm-1)和Yn={yO,yl,…,ynT}的LCS,如果xm-l=yn-l,那么只需求得XmT和Yn-1的LCS,并在其后添加xm-1(yn~l)即可;如果xmT尹yn-1,我們分別求得Xm-1和Y的LCS和Yn-1和X的LCS,并且這兩個LCS中較長的一個為X和Y的LCS。如果我們記字符串Xi和Yj的LCS的長度為c[i,j],我們可以

/0ifi<0orj<0c[i,j]=c[i-l,j-l]+lifi,j>=0andxi=xj\max（c[i,j]ifi,j>=0andxiKxj上面的公式用遞歸函數(shù)不難求得。但從前面求Fibonacci第n項（本面試題系列第16題）的分析中我們知道直接遞歸會有很多重復計算，我們用從底向上循環(huán)求解的思路效率更高。為了能夠采用循環(huán)求解的思路，我們用一個矩陣（參考代碼中的LCS_length）保存下來當前已經(jīng)計算好了的當后面的計算需要這些數(shù)據(jù)時就可以直接從矩陣讀取。另外，求取c[i,j]可以從c[iT,jT]、c[i,jT]或者c[iT,j]三個方向計算得到,相當于在矩陣LCS_length中是從c[iT,jT],c[i,jT]或者c[iT,j]的某一個各自移動到c[i,j],因此在矩陣中有三種不同的移動方向：向左、向上和向左上方，其中只有向左上方移動時才表明找到LCS中的一個字符。于是我們需要用另外一個矩陣（參考代碼中的LCS_direction）保存移動的方向。參考代碼如下：ttinclude"string.hM//directionsofLCSgenerationenumdecreaseDir（klnit=0,kLeft,kUp,kLeftUp｝；//////////////////////////////////////////////////////////

/////////////////////GetthelengthoftwostringsrLCSs,andprintoneoftheLCSs//Input：pStrl-thefirststring//pStr2-thesecondstring//Output:thelengthoftwostrings1LCSs/////////////////////////////////////////////////////////////////////////////intLCS(char*pStrl,char*pStr2)(if(IpStrl||!pStr2)return0；size_tlengthl=strlen(pStrl)；size_tlength2=strlen(pStr2)；if(!lengthl||!Iength2)return0；size_ti,j；//initiatethelengthmatrixint**LCS_length；LCS_length=(int**)(newint[lengthl])；for(i=0；i<lengthl；++i)

LCS_length[i]=(int*)newint[length2]；for(i=0；i<lengthl；++i)for(j=0；j<length2；++j)LCS_length[i][j]=0；//initiatethedirectionmatrixint**LCS_direction；LCS_direction=(int**)(newint[lengthl])；for(i=0；i<lengthl；++i)LCS_direction[i]=(int*)newint[length2]；for(i=0；i<lengthl；++i)for(j=0；j<length2；++j)LCS_direction[i][j]=klnit；for(i=0；i<lengthl；++i)(for(j=0；j<length2；++j){if(i==0||j==0)(if(pStrlEi]==pStr2[j]){LCS_length[i][j]=1;LCS_direction[i][j]=kLeftUp；

)elseLCS_length[i][j]=0；)習題6反轉鏈表題目：輸入一個鏈表的頭結點，反轉該鏈表，并返回反轉后鏈表的頭結點。鏈表結點定義如下：structListNode(intm_nKey；ListNode*mjpNext；);分析：這是一道廣為流傳的微軟面試題。由于這道題能夠很好的反應出程序員思維是否嚴密，在微軟之后已經(jīng)有很多公司在面試時采用了這道題。為了正確地反轉一個鏈表，需要調(diào)整指針的指向。與指針操作相關代碼總是容易出錯的，因此最好在動手寫程序之前作全面的分析。在面試的時候不急于動手而是一開始做仔細的分析和設計，將會給面試官留下很好的印象，因為在實際的軟件開發(fā)中，設計的時間總是比寫代碼的時間長。與其很快地寫出一段漏洞百出的代碼，遠不如用較多的時間寫出一段健壯的代碼。

為了將調(diào)整指針這個復雜的過程分析清楚，我們可以借助圖形來直觀地分析。假設下圖中1、m和n是三個相鄰的結點：aBbB???(?1mdnd???假設經(jīng)過若干操作，我們已經(jīng)把結點1之前的指針調(diào)整完畢，這些結點的mjpNext指針都指向前面一個結點?，F(xiàn)在我們遍歷到結點mo當然，我們需要把調(diào)整結點的m_pNext指針讓它指向結點1。但注意一旦調(diào)整了指針的指向，鏈表就斷開了，如下圖所示：aBbB???IBmnd…因為已經(jīng)沒有指針指向結點n,我們沒有辦法再遍歷到結點n了o因此為了避免鏈表斷開，我們需要在調(diào)整m的m_pNext之前要把n保存下來。接下來我們試著找到反轉后鏈表的頭結點。不難分析出反轉后鏈表的頭結點是原始鏈表的尾位結點。什么結點是尾結點？就是m_pNext為空指針的結點?；谏鲜龇治?，我們不難寫出如下代碼：/////////////////////////////////////////////////////////////////////////Reversealistiteratively//Input：pHead-theheadoftheoriginallist//Output:theheadofthereversedhead

///////////////////////////////////////////////////////////////////////ListNode*Reverselteratively(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；

微型計算機鍵盤上的Tab鍵是D退格鍵控制鍵交替換檔鍵制表定位鍵下列四種軟件中，屬于系統(tǒng)軟件的是CWPSWordTOC\o"1-5"\h\zDOSExcel3“計算機輔助制造”的常用英文縮寫是DCADCAICATCAM在Word的編輯狀態(tài)，選擇了一個段落并設置段落的“首行縮進"設置為1厘米，則A該段落的首行起始位置距頁面的左邊距1厘米文檔中各段落的首行只由“首行縮進"確定位置該段落的首行起始位置距段落的“左縮進"位置的右邊1厘米該段落的首行起始位置在段落“左縮進”位置的左邊1厘米在Word的編輯狀態(tài)，打開了“wl.doc"文檔，把當前文檔以

returnpReversedHead；擴展：本題也可以遞歸實現(xiàn)。習題7用兩個棧實現(xiàn)隊列題目：某隊列的聲明如下：templateclassCQueue{public：CQueue(){)~CQueue()(}voidappendTail(constT&node)；//appendaelementtotailvoiddeleteHeadO；//removeaelementfromheadprivate：T>m_stackl；T>m_stack2；);分析：從上面的類的聲明中，我們發(fā)現(xiàn)在隊列中有兩個棧。因此這道題實質上是要求我們用兩個棧來實現(xiàn)一個隊列。相信大家對棧和隊列的基本性質都非常了解了：棧是一種后入先出的數(shù)據(jù)容器，因此對隊列進行的插入和刪除操作都是在棧頂上進行；隊列是一種先入先出的數(shù)據(jù)容器，我們總是把新元素插入到隊列的尾部，而從隊列的頭

部刪除元素。我們通過一個具體的例子來分析往該隊列插入和刪除元素的過程。首先插入一個元素a,不妨把先它插入到m.stacklo這個時候m_stackl中的元素有｛a｝,m_stack2為空。再插入兩個元素b和c,還是插入到m_stackl中，此時m_stackl中的元素有｛a,b,c｝,m_stack2中仍然是空的。這個時候我們試著從隊列中刪除一個元素。按照隊列先入先出的規(guī)則，由于a比b、c先插入到隊列中，這次被刪除的元素應該是a。元素a存儲在m_stackl中，但并不在棧頂上，因此不能直接進行刪除。注意到m_stack2我們還一直沒有使用過，現(xiàn)在是讓m_stack2起作用的時候了。如果我們把m_stackl中的元素逐個pop出來并push進入m_stack2,元素在m_stack2中的順序正好和原來在m_stackl中的順序相反。因此經(jīng)過兩次pop和push之后，m_stackl為空，而m_stack2中的元素是｛c,b,a｝。這個時候就可以pop出m_stack2的棧頂a了。pop之后的m_stackl為空，而m_stack2的元素為｛c,b｝,其中b在棧頂。這個時候如果我們還想繼續(xù)刪除應該怎么辦呢?在剩下的兩個元素中b和c,b比c先進入隊列，因此b應該先刪除。而此時b恰好又在棧頂上，因此可以直接pop出去。這次pop之后，m_stackl中仍然為空，而m_stack2為｛c｝。從上面的分析我們可以總結出刪除一個元素的步驟：當m_stack2中不為空時，在m_stack2中的棧頂元素是最先進入隊列的

元素，可以pop出去。如果m_stack2為空時，我們把m_stackl中的元素逐個pop出來并push進入m_stack2o由于先進入隊列的元素被壓到m_stackl的底端，經(jīng)過pop和push之后就處于m_stack2的頂端了，又可以直接pop出去。接下來我們再插入一個元素do我們是不是還可以把它push進m.stackl?這樣會不會有問題呢?我們說不會有問題。因為在刪除元素的時候，如果m_stack2中不為空，處于m_stack2中的棧頂元素是最先進入隊列的，可以直接pop；如果m_stack2為空，我們把m_stackl中的元素pop出來并push進入m_stack2o由于m_stack2中元素的順序和m_stackl相反，最先進入隊列的元素還是處于m_stack2的棧頂，仍然可以直接pop。不會出現(xiàn)任何矛盾。習題8把字符串轉換成整數(shù)題目：輸入一個表示整數(shù)的字符串，把該字符串轉換成整數(shù)并輸出。例如輸入字符串”345”，則輸出整數(shù)345。分析：這道題盡管不是很難，學過C/C++語言一般都能實現(xiàn)基本功能，但不同程序員就這道題寫出的代碼有很大區(qū)別，可以說這道題能夠很好地反應出程序員的思維和編程習慣，因此已經(jīng)被包括微軟在內(nèi)的多家公司用作面試題。建議讀者在往下看之前自己先編寫代碼,再比較自己寫的代碼和下面的參考代碼有哪些不同。首先我們分析如何完成基本功能，即如何把表示整數(shù)的字符串正確地轉換成整數(shù)。還是以”345”作為例子。當我們掃描到字符串的第

一個字符'3'時，我們不知道后面還有多少位，僅僅知道這是第一位,因此此時得到的數(shù)字是3O當掃描到第二個數(shù)字'4'時，此時我們已經(jīng)知道前面已經(jīng)一個3了，再在后面加上一個數(shù)字4,那前面的3相當于30,因此得到的數(shù)字是3*10+4=34o接著我們又掃描到字符'5',我們已經(jīng)知道了'5'的前面已經(jīng)有了34,由于后面要加上一個5,前面的34就相當于340了，因此得到的數(shù)字就是34*10+5=345o分析到這里，我們不能得出一個轉換的思路：每掃描到一個字符,我們把在之前得到的數(shù)字乘以10再加上當前字符表示的數(shù)字。這個思路用循環(huán)不難實現(xiàn)。由于整數(shù)可能不僅僅之含有數(shù)字，還有可能以'+'或者開頭,表示整數(shù)的正負。因此我們需要把這個字符串的第一個字符做特殊處理。如果第一個字符是'+'號，則不需要做任何操作;如果第一個字符是'-'號，則表明這個整數(shù)是個負數(shù)，在最后的時候我們要把得到的數(shù)值變成負數(shù)。接著我們試著處理非法輸入。由于輸入的是指針，在使用指針之前，我們要做的第一件是判斷這個指針是不是為空。如果試著去訪問空指針，將不可避免地導致程序崩潰。另外，輸入的字符串中可能含有不是數(shù)字的字符。每當碰到這些非法的字符，我們就沒有必要再繼續(xù)轉換。最后一個需要考慮的問題是溢出問題。由于輸入的數(shù)字是以字符串的形式輸入，因此有可能輸入一個很大的數(shù)字轉換之后會超過能夠表示的最大的整數(shù)而溢出?，F(xiàn)在已經(jīng)分析的差不多了，開始考慮編寫代碼。首先我們考慮如

何聲明這個函數(shù)。由于是把字符串轉換成整數(shù)，很自然我們想到：intStrToInt(constchar*str)；這樣聲明看起來沒有問題。但當輸入的字符串是一個空指針或者含有非法的字符時，應該返回什么值呢?0怎么樣?那怎么區(qū)分非法輸入和字符串本身就是”0”這兩種情況呢？接下來我們考慮另外一種思路。我們可以返回一個布爾值來指示輸入是否有效，而把轉換后的整數(shù)放到參數(shù)列表中以引用或者指針的形式傳入。于是我們就可以聲明如下：boolStrToInt(constchar*str,int&num)；這種思路解決了前面的問題。但是這個函數(shù)的用戶使用這個函數(shù)的時候會覺得不是很方便，因為他不能直接把得到的整數(shù)賦值給其他整形變臉，顯得不夠直觀。前面的第一種聲明就很直觀。如何在保證直觀的前提下當碰到非法輸入的時候通知用戶呢?一種解決方案就是定義一個全局變量，每當碰到非法輸入的時候，就標記該全局變量。用戶在調(diào)用這個函數(shù)之后，就可以檢驗該全局變量來判斷轉換是不是成功。下面我們寫出完整的實現(xiàn)代碼。參考代碼：enumStatus(kValid=0,klnvalid｝；intg_nStatus=kValid；///////////////////////////////////////////////////////////////////////

//Convertastringintoaninteger///////////////////////////////////////////////////////////////////////intStrToInt(constchar*str)(g_nStatus=klnvalid；longlongnum=0；if(str!=NULL)(constchar*digit=str；//thefirstcharinthestringmaybeorboolminus=false；if(*digit=='+')digit++;elseif(*digit==(digit++；minus=true；)//theremainingcharsinthestringwhile(*digit!=*\0r)

if(*digit>='O'&&*digit<=‘9’)num=num*10+(*digit-'0');//overflowif(num>std：:numeric_limits：:max()){num=0；break；)digit++；)//ifthecharisnotadigit,invalidinputelse(num=0；break；))if(*digit==1\0f)g_nStatus=kValid；

if(minus)num=0-num；))returnstatic_cast(num)；}討論：在參考代碼中，我選用的是第一種聲明方式。不過在面試時，我們可以選用任意一種聲明方式進行實現(xiàn)。但當面試官問我們選擇的理由時，我們要對兩者的優(yōu)缺點進行評價。第一種聲明方式對用戶而言非常直觀，但使用了全局變量，不夠優(yōu)雅；而第二種思路是用返回值來表明輸入是否合法，在很多API中都用這種方法，但該方法聲明的函數(shù)使用起來不夠直觀。習題9求二元查找樹的鏡像題目：輸入一顆二元查找樹，將該樹轉換為它的鏡像，即在轉換后的二元查找樹中，左子樹的結點都大于右子樹的結點。用遞歸和循環(huán)兩種方法完成樹的鏡像轉換。例如輸入：8/\610

57911輸出：8/\6/\/\975定義二元查找樹的結點為：structBSTreeNode//anodeinthebinarysearchtree(BST)(intm_nValue；//valueofnodeBSTreeNode*m_pLeft；//leftchildofnodeBSTreeNode*mjpRight；//rightchildofnode};分析：盡管我們可能一下子不能理解鏡像是什么意思，但上面的例子給我們的直觀感覺，就是交換結點的左右子樹。我們試著在遍歷例子中的二元查找樹的同時來交換每個結點的左右子樹。遍歷時首先訪問頭結點8,我們交換它的左右子樹得到：8/\106

91157我們發(fā)現(xiàn)兩個結點6和10的左右子樹仍然是左結點的值小于右結點的值，我們再試著交換他們的左右子樹，得到：8/\6/\/\975剛好就是要求的輸出。上面的分析印證了我們的直覺：在遍歷二元查找樹時每訪問到一個結點，交換它的左右子樹。這種思路用遞歸不難實現(xiàn)，將遍歷二元查找樹的代碼稍作修改就可以了。參考代碼如下：IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII///////////////MirroraBST(swaptheleftrightchildofeachnode)recursively//theheadofBSTininitialcall///////////////////////////////////////////////////////////////////////voidMirrorRecursively(BSTreeNode*pNode)

“w.doc"為名進行“另存為”操作，則D當前文檔是wl.doc當前文檔是w.doc當前文檔是wl.doc與w.docwl.doc與w.doc全被關閉在Word的編輯狀態(tài)，選擇了文檔全文，若在“段落"對話框中設置行距為0磅的格式，應當選擇“行距”列表框中的C單倍行距1.5倍行距固定值多倍行距下列設備中，多媒體計算機所特有的設備是C打印機視頻卡鼠標器鍵盤下列四項中不屬于微型計算機主要性能指標的是A字長內(nèi)存容量重量時鐘脈沖目前各部門廣泛使用的人事檔案管理.財務管理等軟件，按計

if(IpNode)return；//swaptherightandleftchildsub-treeBSTreeNode*pTemp=pNode->mjpLeft；pNode->m_pLeft=pNode->m_pRight;pNode->m_pRight=pTemp；//mirrorleftchildsub-treeifnotnullif(pNode->m_pLeft)MirrorRecursively(pNode->m_pLeft)；//mirrorrightchildsub-treeifnotnullif(pNode->mjpRight)MirrorRecursively(pNode->m_pRight)；)由于遞歸的本質是編譯器生成了一個函數(shù)調(diào)用的棧，因此用循環(huán)來完成同樣任務時最簡單的辦法就是用一個輔助棧來模擬遞歸。首先我們把樹的頭結點放入棧中。在循環(huán)中，只要棧不為空，彈出棧的棧頂結點，交換它的左右子樹。如果它有左子樹，把它的左子樹壓入棧中；如果它有右子樹，把它的右子樹壓入棧中。這樣在下次循環(huán)中就能交換它兒子結點的左右子樹了。參考代碼如下：//////////////////////////////////////////////////////////

///////////////MirroraBST(swaptheleftrightchildofeachnode)Iteratively//Input：pTreeHead：theheadofBST///////////////////////////////////////////////////////////////////////voidMirrorlteratively(BSTreeNode*pTreeHead)(if(!pTreeHead)return；std：:stackstackTreeNode；stackTreeNode.push(pTreeHead)；while(stackTreeNode.sizeO)(BSTreeNode*pNode=stackTreeNode.top()；stackTreeNode.pop()；//swaptherightandleftchildsub-treeBSTreeNode*pTemp=pNode->m_pLeft；pNode->m_pLeft=pNode-〉mjpRight；pNode->m_pRight=pTemp；//pushleftchildsub-treeintostackifnotnull

if(pNode->m_pLeft)stackTreeNode.push(pNode->m_pLeft)；//pushrightchildsub-treeintostackifnotnullif(pNode->m_pRight)stackTreeNode.push(pNode->mjpRight)；})習題10翻轉句子中單詞的順序［折疊］題目：輸入一個英文句子，翻轉句子中單詞的順序，但單詞內(nèi)字符的順序不變。句子中單詞以空格符隔開。為簡單起見，標點符號和普通字母一樣處理。例如輸入“Iamastudent.",則輸出ustudent,aamI"。分析：由于編寫字符串相關代碼能夠反映程序員的編程能力和編程習慣，與字符串相關的問題一直是程序員筆試、面試題的熱門題目。本題也曾多次受到包括微軟在內(nèi)的大量公司的青睞。由于本題需要翻轉句子，我們先顛倒句子中的所有字符。這時,不但翻轉了句子中單詞的順序，而且單詞內(nèi)字符也被翻轉了。我們再顛倒每個單詞內(nèi)的字符。由于單詞內(nèi)的字符被翻轉兩次，因此順序仍然和輸入時的順序保持一致。還是以上面的輸入為例子。翻轉"Iamastudent.w中所有字符得到\tnedutsamaI”，再翻轉每個單詞中字符的順序得到

“students,aamI",正是符合要求的輸出。參考代碼：/////////////////////////////////////////////////////////////////////////Reverseastringbetweentwopointers//Input：pBegin-thebeginpointerinastring//pEnd-theendpointerinastring///////////////////////////////////////////////////////////////////////voidReverse(char*pBegin,char*pEnd){if(pBegin=NULL||pEnd==NULL)return；while(pBegin<pEnd)(chartemp=*pBegin；?pBegin=*pEnd；?pEnd=temp；pBegin++,pEnd—；/////////////////////////////////////////////////////////////////////////Reversethewordorderinasentence,butmaintainthecharacter//orderinsideaword//Input：pData-thesentencetobereversed///////////////////////////////////////////////////////////////////////char*ReverseSentence(char*pData){if(pData==NULL)returnNULL；char*pBegin=pData；char*pEnd=pData；while(*pEnd!='\0f)pEnd++；pEnd—；//ReversethewholesentenceReverse(pBegin,pEnd)；//ReverseeverywordinthesentencepBegin=pEnd=pData；while(*pBegin!=’\0‘)if(*pBegin==**)(pBegin++；pEnd++；continue；)//AwordisbetweenwithpBeginandpEnd,reverseitelseif(*pEnd==1'||*pEnd=='\0'){Reverse(pBegin,―pEnd)；pBegin=++pEnd；)else(pEnd++；))returnpData；習題11求1+2+..?+n題目：求l+2+???+n,要求不能使用乘除法、for、while、if、else、switch、case等關鍵字以及條件判斷語句(A?B：C)o分析：這道題沒有多少實際意義，因為在軟件開發(fā)中不會有這么變態(tài)的限制。但這道題卻能有效地考查發(fā)散思維能力，而發(fā)散思維能力能反映出對編程相關技術理解的深刻程度。通常求l+2+???+n除了用公式n(n+l)/2之外，無外乎循環(huán)和遞歸兩種思路。由于已經(jīng)明確限制for和while的使用，循環(huán)已經(jīng)不能再用了。同樣，遞歸函數(shù)也需要用if語句或者條件判斷語句來判斷是繼續(xù)遞歸下去還是終止遞歸，但現(xiàn)在題目已經(jīng)不允許使用這兩種語句了。我們?nèi)匀粐@循環(huán)做文章。循環(huán)只是讓相同的代碼執(zhí)行n遍而已，我們完全可以不用for和while達到這個效果。比如定義一個類,我們new一含有n個這種類型元素的數(shù)組，那么該類的構造函數(shù)將確定會被調(diào)用n次。我們可以將需要執(zhí)行的代碼放到構造函數(shù)里。如下代碼正是基于這個思路：classTemp{public：TempO{++N；Sum+=N；)staticvoidResetO{N=0；Sum=0；)staticintGetSumO(returnSum；}private：staticintN；staticintSum；};intTemp：:N=0；intTemp：:Sum=0；intsolutionl_Sum(intn)(Temp：:Reset()；Temp*a=newTemp[n]；delete[]a；a=0；returnTemp：:GetSumO；)習題12在排序數(shù)組中查找和為給定值的兩個數(shù)字題目：輸入一個已經(jīng)按升序排序過的數(shù)組和一個數(shù)字，在數(shù)組中查找兩個數(shù)，使得它們的和正好是輸入的那個數(shù)字。要求時間復雜度是0(n)。如果有多對數(shù)字的和等于輸入的數(shù)字，輸出任意一對即可。例如輸入數(shù)組1、2、4、7、11、15和數(shù)字15。由于4+11=15,

因此輸出4和llo分析：如果我們不考慮時間復雜度，最簡單想法的莫過去先在數(shù)組中固定一個數(shù)字，再依次判斷數(shù)組中剩下的n-1個數(shù)字與它的和是不是等于輸入的數(shù)字?？上н@種思路需要的時間復雜度是0(n2)o我們假設現(xiàn)在隨便在數(shù)組中找到兩個數(shù)。如果它們的和等于輸入的數(shù)字，那太好了，我們找到了要找的兩個數(shù)字；如果小于輸入的數(shù)字呢?我們希望兩個數(shù)字的和再大一點。由于數(shù)組已經(jīng)排好序了，我們是不是可以把較小的數(shù)字的往后面移動一個數(shù)字？因為排在后面的數(shù)字要大一些，那么兩個數(shù)字的和也要大一些，就有可能等于輸入的數(shù)字了；同樣，當兩個數(shù)字的和大于輸入的數(shù)字的時候，我們把較大的數(shù)字往前移動，因為排在數(shù)組前面的數(shù)字要小一些，它們的和就有可能等于輸入的數(shù)字了。我們把前面的思路整理一下：最初我們找到數(shù)組的第一個數(shù)字和最后一個數(shù)字。當兩個數(shù)字的和大于輸入的數(shù)字時，把較大的數(shù)字往前移動；當兩個數(shù)字的和小于數(shù)字時，把較小的數(shù)字往后移動；當相等時，打完收工。這樣掃描的順序是從數(shù)組的兩端向數(shù)組的中間掃描。問題是這樣的思路是不是正確的呢?這需要嚴格的數(shù)學證明。感興趣的讀者可以自行證明一下。參考代碼：IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII/////////////

//Findtwonumberswithasuminasortedarray//Output:tureisfoundsuchtwonumbers,otherwisefalse///////////////////////////////////////////////////////////////////////boolFindTwoNumbersWithSum(intdata[],//asortedarrayunsignedintlength,//thelengthofthesortedarrayintsum,//thesumint&numl,//thefirstnumber,outputint&num2//thesecondnumber,output)(boolfound=false；if(length<1)returnfound；intahead=length一1；intbehind=0；while(ahead>behind)longlongcurSum=data[ahead]+data[behind]；

算機應用分類，應屬于A實時控制科學計算計算機輔助工程數(shù)據(jù)處理T列關于計算機病毒的四條敘述中，有錯誤的一條是A計算機病毒是一個標記或一個命令計算機病毒是人為制造的一種程序計算機病毒是一種通過磁盤.網(wǎng)絡等媒介傳播.擴散，并能傳染其它程序的程序計算機病毒是能夠實現(xiàn)自身復制，并借助一定的媒體存的具有潛伏性?傳染性和破壞性計算機硬件能直接識別并執(zhí)行的語言是D高級語言算法語言機器語言符號語言按照操作方式，Windows98系統(tǒng)相當于B實時系統(tǒng)批處理系統(tǒng)分布式系統(tǒng)分時系統(tǒng)

//ifthesumoftwonumbersisequaltotheinput//wehavefoundthemif(curSum==sum)numl=data[behind]；num2=data[ahead]；found=true;break；)//ifthesumoftwonumbersisgreaterthantheinput//decreasethegreaternumberelseif(curSum>sum)ahead—；//ifthesumoftwonumbersislessthantheinput//increasethelessnumberelsebehind++；)returnfound；)查找鏈表中倒數(shù)第k個結點題目：輸入一個單向鏈表，輸出該鏈表中倒數(shù)第k個結點。鏈表

的倒數(shù)第0個結點為鏈表的尾指針。鏈表結點定義如下：structListNode(intm_nKey；ListNode*mjpNext；};分析：為了得到倒數(shù)第k個結點，很自然的想法是先走到鏈表的尾端，再從尾端回溯k步?？?/p>