程序員面試題精選100題

1、程序員面試題精選100 題前言隨著高校的持續(xù)擴張，每年應(yīng)屆畢業(yè)生的數(shù)目都在不斷增長，伴隨而來的是應(yīng)屆畢業(yè)生的就業(yè)壓力也越來越大。在這樣的背景下， 就業(yè)變成一個買方市場的趨勢越來越明顯。為了找到一個稱心的工作，絕大多數(shù)應(yīng)屆畢業(yè)生都必須反復(fù)經(jīng)歷簡歷篩選、電話面試、筆試、面試等環(huán)節(jié)。在這些環(huán)節(jié)中，面試無疑起到最為重要的作用，因為通過面試公司能夠最直觀的了解學(xué)生的能力。為了有效地準(zhǔn)備面試，面經(jīng)這個新興概念應(yīng)運而生。筆者在當(dāng)初找工作階段也從面經(jīng)中獲益匪淺并最終找到滿意的工作。為了方便后來者，筆者花費大量時間收集并整理散落在茫茫網(wǎng)絡(luò)中的面經(jīng)。不同行業(yè)的面經(jīng)全然不同，筆者從自身專業(yè)出發(fā)，著重關(guān)注程序員面試的

2、面經(jīng)，并從精選出若干具有代表性的技術(shù)類的面試題展開討論，希望能給讀者帶來一些啟發(fā)。由于筆者水平有限，給各面試題提供的思路和代碼難免會有錯誤，還請讀者批評指正。另外，熱忱歡迎讀者能夠提供更多、更好的面試題，本人將感激不盡。(1) 把二元查找樹轉(zhuǎn)變成排序的雙向鏈表題目：輸入一棵二元查找樹， 將該二元查找樹轉(zhuǎn)換成一個排序的雙向鏈表。 要求不能創(chuàng)建任何新的結(jié)點，只調(diào)整指針的指向。比如將二元查找樹10/ 614/481216轉(zhuǎn)換成雙向鏈表4=6=8=10=12=14=16。分析：本題是微軟的面試題。 很多與樹相關(guān)的題目都是用遞歸的思路來解決， 本題也不例外。下面我們用兩種不同的遞歸思路來分析。思路一：

3、當(dāng)我們到達某一結(jié)點準(zhǔn)備調(diào)整以該結(jié)點為根結(jié)點的子樹時， 先調(diào)整其左子樹將左子樹轉(zhuǎn)換成一個排好序的左子鏈表， 再調(diào)整其右子樹轉(zhuǎn)換右子鏈表。 最近鏈接左子鏈表的最右結(jié)點（左子樹的最大結(jié)點）、當(dāng)前結(jié)點和右子鏈表的最左結(jié)點（右子樹的最小結(jié)點）。從樹的根結(jié)點開始遞歸調(diào)整所有結(jié)點。思路二：我們可以中序遍歷整棵樹。按照這個方式遍歷樹，比較小的結(jié)點先訪問。如果我們每訪問一個結(jié)點，假設(shè)之前訪問過的結(jié)點已經(jīng)調(diào)整成一個排序雙向鏈表，我們再把調(diào)整當(dāng)前結(jié)點的指針將其鏈接到鏈表的末尾。 當(dāng)所有結(jié)點都訪問過之后， 整棵樹也就轉(zhuǎn)換成一個排序雙向鏈表了。參考代碼：首先我們定義二元查找樹結(jié)點的數(shù)據(jù)結(jié)構(gòu)如下：structBSTree

4、Nodeprint the pathbool isLeaf = (!pTreeNode->m_pLeft && !pTreeNode->m_pRight); if (currentSum = expectedSum && isLeaf)std:vector<int >:iterator iter =();for (; iter != (); + iter)std:cout<<*iter<<'t'std:cout<<std:endl;，則輸出“ student. a am I”。分析：由于

5、編寫字符串相關(guān)代碼能夠反映程序員的編程能力和編程習(xí)慣，與字符串相關(guān)的問題一直是程序員筆試、面試題的熱門題目。本題也曾多次受到包括微軟在內(nèi)的大量公司的青睞。由于本題需要翻轉(zhuǎn)句子，我們先顛倒句子中的所有字符。這時，不但翻轉(zhuǎn)了句子中單詞的順序，而且單詞內(nèi)字符也被翻轉(zhuǎn)了。我們再顛倒每個單詞內(nèi)的字符。由于單詞內(nèi)的字符被翻轉(zhuǎn)兩次，因此順序仍然和輸入時的順序保持一致。還是以上面的輸入為例子。翻轉(zhuǎn)“I am a student.”中所有字符得到“.tnedutsa ma I ”，再翻轉(zhuǎn)每個單詞中字符的順序得到“students. a am I”，正是符合要求的輸出。參考代碼：.+n題目：求 1+2+ +n，要

6、求不能使用乘除法、for 、 while 、 if 、 else 、 switch 、 case 等關(guān)鍵字以及條件判斷語句（ A?B:C）。分析： 這道題沒有多少實際意義，因為在軟件開發(fā)中不會有這么變態(tài)的限制。但這道題卻能有效地考查發(fā)散思維能力，而發(fā)散思維能力能反映出對編程相關(guān)技術(shù)理解的深刻程度。通常求 1+2+ +n 除了用公式 n(n+1)/2 之外，無外乎循環(huán)和遞歸兩種思路。由于已經(jīng)明確限制 for 和 while 的使用，循環(huán)已經(jīng)不能再用了。同樣，遞歸函數(shù)也需要用if 語句或者條件判斷語句來判斷是繼續(xù)遞歸下去還是終止遞歸，但現(xiàn)在題目已經(jīng)不允許使用這兩種語句了。我們?nèi)匀粐@循環(huán)做文章。循

7、環(huán)只是讓相同的代碼執(zhí)行n 遍而已，我們完全可以不用for和 while 達到這個效果。 比如定義一個類， 我們 new一含有 n 個這種類型元素的數(shù)組，那么該類的構(gòu)造函數(shù)將確定會被調(diào)用n 次。我們可以將需要執(zhí)行的代碼放到構(gòu)造函數(shù)里。如下代碼正是基于這個思路：classTemppublic:Temp() + N; Sum += N; staticvoidReset() N = 0; Sum = 0; staticintGetSum() returnSum; private:staticintN;staticintSum;intTemp:N = 0;intTemp:Sum = 0;intsolut

8、ion1_Sum(intn)Temp:Reset();Temp *a =new Tempn;deletea;a = 0;returnTemp:GetSum();我們同樣也可以圍繞遞歸做文章。既然不能判斷是不是應(yīng)該終止遞歸，我們不妨定義兩個函數(shù)。一個函數(shù)充當(dāng)遞歸函數(shù)的角色，另一個函數(shù)處理終止遞歸的情況，我們需要做的就是在兩個函數(shù)里二選一。從二選一我們很自然的想到布爾變量，比如ture （ 1）的時候調(diào)用第一個函數(shù)， false （0）的時候調(diào)用第二個函數(shù)。那現(xiàn)在的問題是如和把數(shù)值變量n 轉(zhuǎn)換成布爾值。如果對 n 連續(xù)做兩次反運算，即 !n ，那么非零的 n 轉(zhuǎn)換為 true ，0轉(zhuǎn)換為 fals

9、e 。有了上述分析，我們再來看下面的代碼：classA;A* Array2;classApublic:virtualintSum ( intn) return0; ;classB:publicApublic:virtualintSum ( intn) returnArray!n->Sum(n-1)+n; ;intsolution2_Sum(intn)enum Value N = 1;A a;B b;Array0 = &a;Array1 = &b;intvalue = Array1->Sum(n);returnvalue;這種方法是用虛函數(shù)來實現(xiàn)函數(shù)的選擇。當(dāng)n 不為

10、零時，執(zhí)行函數(shù)B:Sum ；當(dāng)n 為0 時，執(zhí)行 A:Sum 。我們也可以直接用函數(shù)指針數(shù)組，這樣可能還更直接一些：typedefint(*fun)(int );intsolution3_f1(inti)return0;intsolution3_f2(inti)fun f2=solution3_f1, solution3_f2;returni+f!i(i-1);另外我們還可以讓編譯器幫我們來完成類似于遞歸的運算，比如如下代碼：template< intn>structsolution4_Sumenum Value N = solution4_Sum<n - 1>:N +

11、 n;template<>structsolution4_Sum<1>solution4_Sum<100>:N就是 1+2+.+100的結(jié)果。當(dāng)編譯器看到solution4_Sum<100>時，就是為模板類solution4_Sum以參數(shù) 100 生成該類型的代碼。但以 100 為參數(shù)的類型需要得到以 99 為參數(shù)的類型，因為solution4_Sum<100>:N=solution4_Sum<99>:N+100。這個過程會遞歸一直到參數(shù)為1 的類型， 由于該類型已經(jīng)顯式定義，編譯器無需生成，遞歸編譯到此結(jié)束。由于這個過程

12、是在編譯過程中完成的，因此要求輸入n 必須是在編譯期間就能確定，不能動態(tài)輸入。 這是該方法最大的缺點。 而且編譯器對遞歸編譯代碼的遞歸深度是有限制的，也就是要求 n 不能太大。大家還有更多、更巧妙的思路嗎？歡迎討論_(9) 查找鏈表中倒數(shù)第 k 個結(jié)點題目： 輸入一個單向鏈表，輸出該鏈表中倒數(shù)第k 個結(jié)點。 鏈表的倒數(shù)第尾指針。鏈表結(jié)點定義如下：0 個結(jié)點為鏈表的structListNodeintm_nKey;ListNode* m_pNext;分析：為了得到倒數(shù)第k 個結(jié)點，很自然的想法是先走到鏈表的尾端，再從尾端回溯k 步。可是輸入的是單向鏈表，只有從前往后的指針而沒有從后往前的指針。因此

13、我們需要打開我們的思路。既然不能從尾結(jié)點開始遍歷這個鏈表，我們還是把思路回到頭結(jié)點上來。假設(shè)整個鏈表有n個結(jié)點，那么倒數(shù)第 k 個結(jié)點是從頭結(jié)點開始的第n-k-1 個結(jié)點（從0 開始計數(shù)）。 如果我們能夠得到鏈表中結(jié)點的個數(shù)n，那我們只要從頭結(jié)點開始往后走n-k-1步就可以了。如何得到結(jié)點數(shù) n？這個不難， 只需要從頭開始遍歷鏈表，每經(jīng)過一個結(jié)點， 計數(shù)器加一就行了。這種思路的時間復(fù)雜度是O(n) ，但需要遍歷鏈表兩次。第一次得到鏈表中結(jié)點個數(shù)n，第二次得到從頭結(jié)點開始的第n-k-1 個結(jié)點即倒數(shù)第k 個結(jié)點。如果鏈表的結(jié)點數(shù)不多，這是一種很好的方法。但如果輸入的鏈表的結(jié)點個數(shù)很多，有可能不能

14、一次性把整個鏈表都從硬盤讀入物理內(nèi)存，那么遍歷兩遍意味著一個結(jié)點需要兩次從硬盤讀入到物理內(nèi)存。 我們知道把數(shù)據(jù)從硬盤讀入到內(nèi)存是非常耗時間的操作。我們能不能把鏈表遍歷的次數(shù)減少到1？如果可以，將能有效地提高代碼執(zhí)行的時間效率。如果我們在遍歷時維持兩個指針，第一個指針從鏈表的頭指針開始遍歷，在第k-1步之前，第二個指針保持不動；在第 k-1步開始， 第二個指針也開始從鏈表的頭指針開始遍歷。由于兩個指針的距離保持在k-1 ，當(dāng)?shù)谝粋€（走在前面的）指針到達鏈表的尾結(jié)點時，第二個指針（走在后面的）指針正好是倒數(shù)第k 個結(jié)點。這種思路只需要遍歷鏈表一次。對于很長的鏈表， 只需要把每個結(jié)點從硬盤導(dǎo)入到內(nèi)存

15、一次。因此這一方法的時間效率前面的方法要高。思路一的參考代碼：. n - 1) form a circle. Remove the mth fromFind the last number remaining. n - 1)list<int > integers;for (i = 0; i < n; + i)(i);list<whileint >:iterator curinteger = ();()>1)Note that std:list is not a circleNote that std:list is not a circle. n - 1)

16、form a circle. Remove the mth fromFind the last number remaining如果 x=y，那么 z=x=yn-1，并且 Z是 X和 Y的 LCS；m-1n-1k-1m-1k-1m-1n-12.如果 xm-1yn-1 ，那么當(dāng) zk-1 xm-1 時 Z 是 Xm-1 和 Y 的 LCS；3.如果 xm-1yn-1 ，那么當(dāng) zk-1 yn-1 時 Z 是 Yn-1 和 X 的 LCS；下面簡單證明一下這些性質(zhì)：1.如果 zk-1x ，那么我們可以把xm-1（ yn-1 ）加到 Z 中得到 Z，這樣就得到m-1X 和 Y 的一個長度為k+1 的

17、公共子串 Z。這就與長度為k 的 Z 是 X 和 Y 的 LCS相矛盾了。因此一定有 z=x=yn-1。k-1m-1既然 zk-1=x=yn-1，那如果我們刪除zk-1（ x、 yn-1）得到的 Z， X和 Y，顯然 Z是 Xm-1m-1k-1m-1n-1k-1m-1和 Yn-1 的一個公共子串，現(xiàn)在我們證明Zk-1是 Xm-1 和 Yn-1的 LCS。用反證法不難證明。假設(shè)有Xm-1 和 Yn-1 有一個長度超過k-1的公共子串W，那么我們把加到W中得到 W，那 W就是 X和 Y 的公共子串，并且長度超過k，這就和已知條件相矛盾了。2.還是用反證法證明。 假設(shè) Z 不是 Xm-1 和 Y 的

18、 LCS，則存在一個長度超過k 的W是 Xm-1 和 Y 的 LCS，那 W肯定也 X 和 Y 的公共子串，而已知條件中X 和 Y 的公共子串的最大長度為 k。矛盾。3.證明同 2。有 了 上 面 的 性 質(zhì) ， 我 們 可 以 得 出 如 下 的 思 路 ： 求 兩 字 符 串 Xm=x 0,x1, xm-1和Y =y ,y1, ,yn-1 的 LCS，如果 xm-1=yn-1，那么只需求得X和 Y的 LCS，并在其后添加xm-1n0m-1n-1（yn-1）即可；如果xy，我們分別求得X和 Y的 LCS和 Y和 X 的 LCS，并且這兩個m-1n-1m-1n-1LCS中較長的一個為X和 Y

19、的 LCS。如果我們記字符串Xi 和 Yj的 LCS的長度為 ci,j，我們可以遞歸地求ci,j：/0if i<0 or j<0ci,j=ci-1,j-1+1if i,j>=0 and xi =xjmax(ci,j-1,ci-1,jif i,j>=0 and xi xj上面的公式用遞歸函數(shù)不難求得。但從前面求 Fibonacci第 n 項( 本面試題系列第 16 題）的分析中我們知道直接遞歸會有很多重復(fù)計算，我們用從底向上循環(huán)求解的思路效率更高。為了能夠采用循環(huán)求解的思路， 我們用一個矩陣 （參考代碼中的 LCS_length ）保存下來當(dāng)前已經(jīng)計算好了的 ci,j ，

20、當(dāng)后面的計算需要這些數(shù)據(jù)時就可以直接從矩陣讀取。另外，求取 ci,j 可以從 ci-1,j-1、 ci,j-1或者 ci-1,j三個方向計算得到，相當(dāng)于在矩陣LCS_length中是從ci-1,j-1， ci,j-1或者 ci-1,j的某一個各自移動到ci,j，因此在矩陣中有三種不同的移動方向：向左、 向上和向左上方，其中只有向左上方移動時才表明找到 LCS 中的一個字符。于是 我們需要用另外一個矩陣（參考代碼中的LCS_direction）保存移動的方向。參考代碼如下：#include""It'sif (firstDigit > 1)numFirstDigi

21、t = PowerBase10(length - 1);It'selseif (firstDigit = 1)numFirstDigit = atoi(strN + 1) + 1;returnnumFirstDigit + numOtherDigits + numRecursive;從尾到頭輸出一個字符串；2.定義一個函數(shù)求字符串的長度，要求該函數(shù)體內(nèi)不能聲明任何變量。(32)- 不能被繼承的類題目：用 C+設(shè)計一個不能被繼承的類。分析：這是 Adobe 公司 2007年校園招聘的最新筆試題。這道題除了考察應(yīng)聘者的C+基本功底外，還能考察反應(yīng)能力，是一道很好的題目。在 Java 中定義

22、了關(guān)鍵字final，被 final修飾的類不能被繼承。但在 C+中沒有 final這個關(guān)鍵字，要實現(xiàn)這個要求還是需要花費一些精力。首先想到的是在 C+ 中，子類的構(gòu)造函數(shù)會自動調(diào)用父類的構(gòu)造函數(shù)。同樣，子類的析構(gòu)函數(shù)也會自動調(diào)用父類的析構(gòu)函數(shù)。要想一個類不能被繼承， 我們只要把它的構(gòu)造函數(shù)和析構(gòu)函數(shù)都定義為私有函數(shù)。那么當(dāng)一個類試圖從它那繼承的時候，必然會由于試圖調(diào)用構(gòu)造函數(shù)、析構(gòu)函數(shù)而導(dǎo)致編譯錯誤?？墒沁@個類的構(gòu)造函數(shù)和析構(gòu)函數(shù)都是私有函數(shù)了，我們怎樣才能得到該類的實例呢？這難不倒我們， 我們可以通過定義靜態(tài)來創(chuàng)建和釋放類的實例?；谶@個思路， 我們可以寫出如下的代碼：If there is

23、 no common和” aeiou ” ，則刪除之后的第一個字符串變成”Thy r stdnts.”。分析： 這是一道微軟面試題。在微軟的常見面試題中，與字符串相關(guān)的題目占了很大的一部分，因為寫程序操作字符串能很好的反映我們的編程基本功。要編程完成這道題要求的功能可能并不難。畢竟，這道題的基本思路就是在第一個字符串中拿到一個字符，在第二個字符串中查找一下，看它是不是在第二個字符串中。如果在的話，就從第一個字符串中刪除。但如何能夠把效率優(yōu)化到讓人滿意的程度，卻也不是一件容易的事情。 也就是說， 如何在第一個字符串中刪除一個字符，以及如何在第二字符串中查找一個字符，都是需要一些小技巧的。首先我們

24、考慮如何在字符串中刪除一個字符。由于字符串的內(nèi)存分配方式是連續(xù)分配的。我們從字符串當(dāng)中刪除一個字符，需要把后面所有的字符往前移動一個字節(jié)的位置。但如果每次刪除都需要移動字符串后面的字符的話，對于一個長度為n 的字符串而言，刪除一個字符的時間復(fù)雜度為 O(n)。而對于本題而言， 有可能要刪除的字符的個數(shù)是n ，因此該方法就刪除而言的時間復(fù)雜度為O(n2)。事實上，我們并不需要在每次刪除一個字符的時候都去移動后面所有的字符。我們可以設(shè)想，當(dāng)一個字符需要被刪除的時候，我們把它所占的位置讓它后面的字符來填補，也就相當(dāng)于這個字符被刪除了。在具體實現(xiàn)中，我們可以定義兩個指針(pFast 和 pSlow)

25、，初始的時候都指向第一字符的起始位置。當(dāng) pFast指向的字符是需要刪除的字符，則 pFast直接跳過，指向下一個字符。如果pFast指向的字符是不需要刪除的字符，那么把pFast 指向的字符賦值給 pSlow指向的字符，并且 pFast和 pStart同時向后移動指向下一個字符。這樣，前面被 pFast跳過的字符相當(dāng)于被刪除了。 用這種方法， 整個刪除在 O(n) 時間內(nèi)就可以完成。接下來我們考慮如何在一個字符串中查找一個字符。當(dāng)然，最簡單的辦法就是從頭到尾掃描整個字符串。顯然，這種方法需要一個循環(huán)，對于一個長度為n 的字符串，時間復(fù)雜度是O(n) 。由于字符的總數(shù)是有限的。對于八位的cha

26、r 型字符而言，總共只有28=256 個字符。我們可以新建一個大小為256 的數(shù)組，把所有元素都初始化為0 。然后對于字符串中每一個字符，把它的ASCII 碼映射成索引，把數(shù)組中該索引對應(yīng)的元素設(shè)為。這個時候，要查找一個字符就變得很快了：根據(jù)這個字符的ASCII 碼，在數(shù)組中對應(yīng)的下標(biāo)找到該元素，如果為 0 ，表示字符串中沒有該字符，否則字符串中包含該字符。此時，查找一個字符的時間復(fù)雜度是O(1) 。其實， 這個數(shù)組就是一個 hash表。這種思路的詳細說明，詳見本面試題系列的第13題 。基于上述分析，我們可以寫出如下代碼：constunsignedintnTableSize= 256;inth

27、ashTable nTableSize ;memset( hashTable , 0,sizeof( hashTable );constwhilechar * ( '0'pTemp= pStrDelete != * pTemp);hashTable * pTemp = 1;+pTemp;char *pSlow =pStrSource;char *pFast=pStrSource;while( '0'!= *pFast )Maind:n", +iCount);for ( int i=0; i < ROWS; i+)for( int j=0; j &

28、lt; COLS; j+)printf("%d%c", Gridij, (j+1) % COLS ? ' ' : 'n');iFound = 1;LenALenALenA456789”2005 年 5月 29 日 2005 年 11 月 15 日 123” -0123 ” 45” 123.45 ” 2005 年 11 月 23 日 56” 4g,n ，給定關(guān)于 n 元組中的分量的一個約束集D，要求 E 中滿足 D的全部約束的所有n 元組。其中 Si是分量 xi 的定義域且 |Si|有限， i=1,2,.n。我們稱E 中滿足 D 的全部約束條件

29、的任一n元組為問題P 的一個解。對于 n 元組 (x1,x2, ， xn)元組中分量的顯式限制，比如當(dāng)中分量的約束，一般分為兩類，一類是顯約束，它給出對于ni j時 xi xj ；另一類是隱約束，它給出對于n 元組中分量的隱式限制， 比如： f(x1,x2, ， xn) 0，其中 f 是隱函數(shù)。 不過隱式顯式并不絕對，兩者可以相互轉(zhuǎn)換。解問題 P 的最樸素的方法是窮舉法，即對 E 中的所有 n 元組，逐一地檢測其是否滿足D的全部約束。全部滿足，才是問題p 的解 ; 只要有一個不滿足，就不是問題P 的解。顯然，如果記 m(i)=|S(i+1)|,i=0,1,.n-1，那么，窮舉法需要對 m=m(

30、0)*m(1)*.*m(n-1)個 n 元組一個不漏地加以檢測。可想而知，其計算量是非常之大的。我們發(fā)現(xiàn)， 對于許多問題，所給定的約束集D 具有完備性，即i 元組 (x1,x2, ， xi) 滿足D 中僅涉及到 x1,x2, ， xi的所有約束意味著j(j<i)元組 (x1,x2, ， xj)一定也滿足D中僅涉及到 x1,x2, ， xj的所有約束， i=1,2,n 。 換句話說， 只要存在Oj n-1 ，使得 (x1,x2, ， xj) 違反 D 中僅涉及到 x1,x 2, ， xj的約束之一， 以(x1,x2, ， xj)為前綴的任何n 元組 (x1,x2,xj,xn)一定也違反D

31、中僅涉及到又 x1,x2, ， xi的一個約束，其中ni j 。這個發(fā)現(xiàn)告訴我們，對于約束集D 具有完備性的問題P，一旦檢測斷定某個j 元組(x1,x2,xj)違 反 D 中 僅 涉 及 x1,x2,xj 的 一 個 約 束 ， 就 可 以 肯 定 ， 以(x1,x2,xj)為前綴的任何n 元組 (x1,x2,xj,xn) 都不會是問題的解，因而就不必去搜索它們、 檢測它們。 回溯法正是針對這類問題，利用這類問題的上述性質(zhì)而提出來的比窮舉法效率高得多的算法?；厮莘ㄊ紫葘栴}P 的 n 元組的狀態(tài)空間E 表示成一棵高為n 的帶權(quán)有序樹 T，把在 E 中求問題 P 的所有解轉(zhuǎn)化為在 T 中搜索問題

32、 P 的所有解。 樹 T 類似于檢索樹。 它可這樣構(gòu)造： 設(shè)Si 中的元素可排成 x(i,1),x(i,2),x(i,m(i- 1),i=1,2,n 。 從根開始， 讓 T 的第i 層的每一個結(jié)點都有m(i) 個兒子。這m(i) 個兒子到它們的共同父親的邊，按從左到右的次序分別帶權(quán)x(i+1,1),x(i+1,2),x(i+1,m(i),i=0,1,2,n-1 。照這種構(gòu)造方式， E 中的一個 n 元組 (x1,x2, ， xn) 對應(yīng)于 T 中的一個葉結(jié)點，T 的根到這個葉結(jié)點的路上依次的 n 條邊分別以 x1,x2, ， xn 為其權(quán)，反之亦然。 另外，對于任意的0i n-1 ，E 中 n

33、 元組 (x1,x2, ， xn) 的一個前綴 i元組 (x1,x2, ， xi) 對應(yīng)于 T 中的一個非葉結(jié)點， T 的根到這個非葉結(jié)點的路上依次的i條邊分別以了x1,x2, ， xi 為其權(quán)，反之亦然。特別， E 中的任意一個 n 元組的空前綴() ，對應(yīng)于 T 的根。因而，在 E 中尋找問題 P 的一個解等價于在T 中搜索一個葉結(jié)點， 要求從 T 的根到該葉結(jié)點的路上依次的n 條邊相應(yīng)帶的n 個權(quán) x1,x2, ， xn 滿足約束集 D 的全部約束。在T 中搜索所要求的葉結(jié)點， 很自然的一種方式是從根出發(fā)逐步深入，讓路逐步延伸， 即依次搜索滿足約柬條件的前綴1 元組 (xl)，前綴 2

34、元組 (xl,x2)，前綴 i元組 (x1,x2, ， xi)， ，直到 i=n 為止。注意，在這里，我們把 (x1,x2, ， xi) 應(yīng)該滿足的 D中僅涉及 x1,x2, ，xi 的所有約束當(dāng)做判斷 (x1,x2, ， xi) 是問題 p 的解的必要條件，只有當(dāng)這個必要條件加上條件 i=n 才是充要條件。 為了區(qū)別， 我們稱使積累的判別條件成為充要條件的那個條件( 如條件 i=n) 為終結(jié)條件。在回溯法中，上面引入的樹 T 被稱為問題 P 的狀態(tài)空間樹 ; 樹 T 上的任意一個結(jié)點被稱為問題 p 的狀態(tài)結(jié)點 ; 樹 T 上的任意一個葉結(jié)點被稱為問題 P的一個解狀態(tài)結(jié)點 ; 樹 T 上滿足約

35、束集 D 的全部約柬的任意一個葉結(jié)點被稱為問題 P 的一個回答狀態(tài)結(jié)點， 簡稱為回答結(jié)點或回答狀態(tài)，它對應(yīng)于問題P 的一個解。例如 8 皇后問題，就是要確定一個8 元組（ x1,x2,.,x8)，xi 表示第 i 行的皇后所在的列，這樣的問題很容易應(yīng)用上面的搜索樹模型；然而，有些問題的解無法表示成一個n 元組， 因為事先無法確定這個n 是多少，比如這個喝酒問題，問題的解就是一系列的倒酒喝酒策略，但是事先無法確定究竟需要進行多少步；還有著名的 8 數(shù)碼問題 （文曲星上的那個 9x9 方格中移數(shù)字的游戲） ，那個問題也是預(yù)先不知道需要移動多少步才能達到目標(biāo)。不過這并不影響回溯法的使用，只要該問題有

36、解，一定可以將解用有限的變元來表示，我們可以假設(shè)n就是問題的一個解的變元的個數(shù)，這樣就可以繼續(xù)利用上面的搜索樹模型了。事實上， 這棵搜索樹并非預(yù)先生成的， 而是在搜索的過程中逐步生成的，所以不知道樹的深度n 并不影響在樹中搜索葉子節(jié)點。但是有一點很重要， 如果問題根本不存在有限的解，或者問題的狀態(tài)空間無窮大， 那么沿著某條道路從根出發(fā)搜索葉節(jié)點，可能永遠無法達到葉結(jié)點， 因為搜索樹會不斷地擴展， 然而葉結(jié)點也許是確實存在的，只要換一條道路就可以找到，只不過一開始就走錯了路， 而這條錯路是永遠無法終止的。為了避免這種情況我們一般都規(guī)定狀態(tài)空間是有限的， 這樣即使搜索整個狀態(tài)空間的每個狀態(tài)也可以在有限時間內(nèi)完成，否則的話回溯法很可能不適用。搜索樹的每一個節(jié)點表示一個狀態(tài)，節(jié)點i 要生成節(jié)點j 必