第一篇：軟考教材分享：程序員考試考點分析與真題詳解(第4版 )

程序員

http://

程序員考試考點分析與真題詳解（第4版）

第 1 章 數據結構與算法

數據結構是指數據對象及其相互關系和構造方法，一個數據結構S可以用一個二元組表示為S=（D,R）。其中，D是數據結構中的數據的非空有限集合，R是定義在D上的關系的非空有限集合。在數據結構中，結點與結點間的相互關系稱為數據的邏輯結構，數據在計算機中的存儲形式稱為數據的存儲結構。

數據結構按邏輯結構不同分為線性結構和非線性結構兩大類，其中非線性結構又可分為樹形結構和圖結構，而樹形結構又可分為樹結構和二叉樹結構。

按照考試大綱的要求，在數據結構與算法方面，要求考生掌握以下知識點。

1.常用數據結構

數組（一維數組、二維數組、靜態數組、動態數組）、線性表、鏈表（單向鏈表、雙向鏈表、環形鏈表）、隊列、棧、樹（二叉樹、查找樹）和圖（鄰接矩陣、鄰接表）等的定義、存儲和操作。

2.常用算法

（1）排序算法、查找算法、數值計算算法、字符串處理算法、遞歸算法、最小生成樹、拓撲排序和單源點最短路徑求解算法、圖的相關算法。

（2）算法與數據結構的關系、算法效率、算法設計、算法描述（流程圖、偽代碼、決策表）、算法的復雜性。

1.1 算法設計概述

程序員

http://

算法是在有限步驟內求解某一問題所使用的一組定義明確的規則。通俗地說，就是計算機解題的過程。在這個過程中，無論是形成解題思路還是編寫程序，都是在實施某種算法。前者是推理實現的算法，后者是操作實現的算法。一個算法應該具有以下5個重要的特征。

（1）有窮性：一個算法（對任何合法的輸入值）必須總是在執行有窮步之后結束，且每一步都可在有窮時間內完成。

（2）確定性：算法中每一條指令必須有確切的含義，讀者理解時不會產生二義性。在任何條件下，算法只有唯一的一條執行路徑，即對于相同的輸入只能得出相同的輸出。

（3）輸入：一個算法有零個或多個輸入，以確定運算對象的初始情況。所謂零個輸入是指算法本身定出了初始條件。這些輸入取自于某個特定對象的集合。

（4）輸出：一個算法有一個或多個輸出，以反映對輸入數據加工后的結果。沒有輸出的算法是毫無意義的。

（5）可行性：一個算法是可行的，即算法中描述的操作都是可以通過已經實現的基本運算執行有限次來實現的。

算法設計要求正確性、可讀性、健壯性、高效率與低存儲量需求。

效率指的是算法執行的時間。對于解決同一問題的多個算法，執行時間短的算法效率高。存儲量需求指算法執行過程中所需要的最大存儲空間。兩者都與問題的規模有關。

算法的復雜性是算法效率的度量，是算法運行所需要的計算機資源的量，是評價算法優劣的重要依據。可以從一個算法的時間復雜度與空間復雜度來評價算法的優劣。當將一個算法轉換成程序并在計算機上執行時，其運行所需要的時間取決于下列因素。

（1）硬件的速度。例如，使用486還是使用586.（2）書寫程序的語言。實現語言的級別越高，其執行效率就越低。

程序員

http://

（3）編譯程序所生成目標代碼的質量。對于代碼優化較好的編譯程序其所生成的程序質量較高。

（4）問題的規模。例如，求100以內的素數與求1 000以內的素數其執行時間必然是不同的。

顯然，在各種因素都不能確定的情況下，很難比較出算法的執行時間。也就是說，使用執行算法的絕對時間來衡量算法的效率是不合適的。為此，可以將上述的各種與計算機相關的軟、硬件因素都確定下來，這樣一個特定算法的運行工作量大小就只依賴于問題的規模（通常用正整數n表示），或者說它是問題規模的函數。

1.時間復雜度

一個程序的時間復雜度是指程序運行從開始到結束所需要的時間。

一個算法是由控制結構和原操作構成的，其執行時間取決于兩者的綜合效果。為了便于比較同一問題的不同算法，通常的做法是：從算法中選取一種對于所研究的問題來說是基本運算的原操作，以該操作重復執行的次數作為算法的時間度量。在一般情況下，算法中原操作重復執行的次數是規模n的某個函數T（n）。

許多時候要精確地計算T（n）是困難的，我們引入漸近時間復雜度在數量上估計一個算法的執行時間，也能夠達到分析算法的目的。

定義（大Ο記號）：如果存在兩個正常數c和n0,對于所有的n,當n≥n0時有：

f（n）≤ cg（n）

則有：

f（n）= Ο（g（n））

也就是說，隨著n的增大，f（n）漸近的不大于g（n）。例如，一個程序的實際執行

程序員

http://

時間為T（n）=2n3+n2+5,則T（n）=Ο（n3）。T（n）和n3的值隨n的增大漸近地靠攏。

使用大Ο記號表示的算法的時間復雜度，稱為算法的漸近時間復雜度。

通常用Ο（1）表示常數計算時間。常見的漸近時間復雜度有：

Ο（1）<Ο（log2n）<Ο（n）<Ο（nlog2n）<Ο（n2）<Ο（n3）<Ο（2n）

2.空間復雜度

一個程序的空間復雜度是指程序運行從開始到結束所需的存儲量。

程序運行所需的存儲空間包括以下兩部分。

（1）固定部分：這部分空間與所處理數據的大小和個數無關。主要包括程序代碼、常量、簡單變量和定長成分的結構變量所占的空間。

（2）可變部分：這部分空間大小與算法在某次執行中處理特定數據的大小和規模有關。例如，100個數據元素的排序算法與1 000個數據元素的排序算法所需的存儲空間顯然是不同的。

算法由數據結構來體現，所以看一個程序首先要搞懂程序實現中所使用的數據結構，如解決裝箱問題就使用鏈表這種數據結構。數據結構是算法的基礎，數據結構支持算法，如果數據結構是遞歸的，算法也可以用遞歸來實現，如二叉樹的遍歷。經常采用的算法有迭代法、遞推法、遞歸法、窮舉法、貪婪法、分治法和回溯法等，根據考試大綱的要求，對程序員級別的考試，需要考生掌握遞歸法。

1.2 線性表

線性表是最簡單和最常用的一種數據結構，線性表是由相同類型的結點組成的有限序

程序員

http://

列。一個由n個結點a0,a1,…，an-1組成的線性表可記為（a0,a1,…，an-1）。線性表的結點個數為線性表的長度，長度為0的線性表稱為空表。對于非空線性表，a0是線性表的第一個結點，an-1是線性表的最后一個結點。線性表的結點構成一個序列，對序列中兩相鄰結點ai和ai+1,稱ai是ai+1的前驅結點，ai+1是ai的后繼結點。其中a0沒有前驅結點，an-1沒有后繼結點。

線性表中結點之間的關系可由結點在線性表中的位置所確定，通常用（ai,ai+1）（0≤i≤n–2）表示兩個結點之間的先后關系。例如，如果兩個線性表有相同的數據結點，但它們的結點在線性表中出現的順序不同，則它們是兩個不同的線性表。

線性表的結點可由若干個成分組成，其中能唯一標識該結點的成分稱為關鍵字，或簡稱鍵。為了討論方便，往往只考慮結點的關鍵字，而忽略其他成分。

1.線性表的基本運算

線性表包含的結點個數可以動態地增加或減少，可以在任何位置上插入或刪除結點。線性表常用的運算可分成幾類，每類有若干種運算，如下所示。

1）查找運算

在線性表中查找具有給定鍵值的結點。

2）插入運算

在線性表的第i（0≤i≤n–1）個結點的前面或后面插入一個新結點。

3）刪除運算

刪除線性表的第i（0≤i≤n–1）個結點。

4）其他運算

統計線性表中結點的個數；

程序員

http://

輸出線性表各結點的值；

復制線性表；

線性表分拆；

線性表合并；

線性表排序；

按某種規則整理線性表。

2.線性表的存儲

線性表常用的存儲方式有順序存儲和鏈接存儲。

1）順序存儲

順序存儲是最簡單的存儲方式，通常用一個數組，從數組的第一個元素開始，將線性表的結點依次存儲在數組中，即線性表的第i個結點存儲在數組的第i（0≤i≤n–1）個元素中，用數組元素的順序存儲來體現線性表中結點的先后次序關系。

順序存儲線性表的最大優點就是能隨機存取線性表中的任何一個結點。缺點主要有兩個：一是數組的大小通常是固定的，不利于任意增加或減少線性表的結點個數；二是插入和刪除線性表的結點時，要移動數組中的其他元素，操作復雜。

2）鏈接存儲

鏈接存儲是用鏈表存儲線性表（鏈表），最簡單的是用單向鏈表，即從鏈表的第一個結點開始，將線性表的結點依次存儲在鏈表的各結點中。鏈表的每個結點不但要存儲線性表結點的信息，還要用一個域存儲其后繼結點的指針。單向鏈表通過鏈接指針來體現線性表中結點的先后次序關系。

鏈表存儲線性表的優點是線性表的每個結點的實際存儲位置是任意的，這給線性表的插

程序員

http://

入和刪除操作帶來方便，只要改變鏈表有關結點的后繼指針就能完成插入或刪除的操作，不需移動任何表元。鏈表存儲方式的缺點主要有兩個：一是每個結點增加了一個后繼指針成分，要花費更多的存儲空間；二是不方便隨機訪問線性表的任一結點。

3.線性表上的查找

線性表上的查找運算是指在線性表中找某個鍵值的結點。根據線性表中的存儲形式和線性表本身的性質差異，有多種查找算法，例如順序查找、二分法查找、分塊查找、散列查找等。其中二分法查找需要線性表是一個有序序列。

4.在線性表中插入新結點

1）順序存儲

設線性表結點的類型為整型，插入之前有n個結點，把值為x的新結點插在線性表的第i（0≤i≤n）個位置上。完成插入主要有以下步驟。

檢查插入要求的有關參數的合理性；

把原來的第n–1個結點至第i個結點依次往后移一個數組元素的位置；

把新結點放在第i個位置上；

修改線性表的結點個數。

在具有n個結點的線性表上插入新結點，其時間主要花費在移動結點的循環上。若插入任一位置的概率相等，則在順序存儲線性表中插入一個新結點，平均移動次數為n/2.2）鏈接存儲

在鏈接存儲線性表中插入一個鍵值為x的新結點，分以下4種情況。

在某指針p所指結點之后插入；

插在首結點之前，使待插入結點成為新的首結點；

程序員

http://

接在線性表的末尾；

在有序鏈表中插入，使新的線性表仍然有序。

5.刪除線性表的結點

1）順序存儲

在有n個結點的線性表中，刪除第i（0≤i≤n–1）個結點。刪除時應將第i+1個表元至第n–1個結點依次向前移一個數組元素的位置，共移動n–i–1 個結點。完成刪除主要有以下幾個步驟。

檢查刪除要求的有關參數的合理性；

把原來第i+1個表元至第n–1個結點依次向前移一個數組元素的位置；

修改線性表表元個數。

在具有n個結點的線性表上刪除結點，其時間主要花費在移動表元的循環上。若刪除任一表元的概率相等，則在順序存儲線性表中刪除一個結點，平均移動次數為n/2.2）鏈接存儲

對于鏈表上刪除指定值結點的刪除運算，需考慮幾種情況：一是鏈表為空鏈表，不執行刪除操作；二是要刪除的結點恰為鏈表的首結點，應將鏈表頭指針改為指向原首結點的后繼結點；其他情況，先要在鏈表中尋找要刪除的結點，從鏈表首結點開始順序尋找。若找到，執行刪除操作，若直至鏈表末尾沒有指定值的結點，則不執行刪除操作。完成刪除由以下幾個步驟組成。

如鏈表為空鏈表，則不執行刪除操作；

若鏈表的首結點的值為指定值，更改鏈表的頭指針為原首結點的后繼結點；

在鏈表中找指定值的結點；

程序員

http://

將找到的結點刪除。

1.2.1 棧

棧是一種特殊的線性表，棧只允許在同一端進行插入和刪除運算。允許插入和刪除的一端稱為棧頂，另一端稱為棧底。稱棧的結點插入為進棧，結點刪除為出棧。因為最后進棧的結點必定最先出棧，所以棧具有后進先出的特征。

1.順序存儲

可以用順序存儲線性表來表示棧，為了指明當前執行插入和刪除運算的棧頂位置，需要一個地址變量top指出棧頂結點在數組中的下標。

2.鏈接存儲

棧也可以用鏈表實現，用鏈表實現的棧稱為鏈接棧。鏈表的第一個結點為頂結點，鏈表的首結點就是棧頂指針top,top為NULL的鏈表是空棧。

1.2.2 隊列

隊列也是一種特殊的線性表，只允許在一端進行插入，另一端進行刪除運算。允許刪除運算的那一端稱為隊首，允許插入運算的一端稱為隊尾。稱隊列的結點插入為進隊，結點刪除為出隊。因最先進入隊列的結點將最先出隊，所以隊列具有先進先出的特征。

1.順序存儲

可以用順序存儲線性表來表示隊列，為了指明當前執行出隊運算的隊首位置，需要一個指針變量head（稱為頭指針），為了指明當前執行進隊運算的隊尾位置，也需要一個指針變量tail（稱為尾指針）。

若用有N個元素的數組表示隊列，隨著一系列進隊和出隊運算，隊列的結點移向存放隊列數組的尾端，會出現數組的前端空著，而隊列空間已用完的情況。一種可行的解決辦法

程序員

http://

是當發生這樣的情況時，把隊列中的結點移到數組的前端，修改頭指針和尾指針。另一種更好的解決辦法是采用循環隊列。

循環隊列就是將實現隊列的數組a[N]的第一個元素a[0]與最后一個元素a[N–1]連接起來。一般地，用tail指向隊尾元素的下一個位置（注意，并不是指向最后一個元素本身），用head指向隊頭元素。隊空的初態為 head=tail=0.在循環隊列中，當tail 趕上head時，隊列滿。反之，當head趕上tail時，隊列變為空。這樣隊空和隊滿的條件都同為head=tail,這會給程序判別隊空或隊滿帶來不便。因此，可采用當隊列只剩下一個空閑結點的空間時，就認為隊列已滿，用這種簡單辦法來區別隊空和隊滿。即對空的判別條件是head=tail,隊滿的判別條件是head=（tail+1）%N.2.鏈接存儲

隊列也可以用鏈接存儲線性表實現，用鏈表實現的隊列稱為鏈接隊列。鏈表的第一個結點是隊列首結點，鏈表的末尾結點是隊列的隊尾結點，隊尾結點的鏈接指針值為NULL.隊列的頭指針head 指向鏈表的首結點，隊列的尾指針tail指向鏈表的尾結點。當隊列的頭指針head值為NULL時，隊列為空。

1.2.3 數組

在計算機中存儲一個矩陣時，可使用二維數組。例如，M×N階矩陣可用一個數組a[M][N]來存儲（可按照行優先或列優先的順序）。如果一個矩陣的元素絕大部分為零，則稱為稀疏矩陣。若直接用一個二維數組表示稀疏矩陣，則會因存儲太多的零元素而浪費大量的內存空間。因此，通常采用三元組數組或十字鏈表兩種方法來存儲稀疏矩陣。

1.三元組數組

稀疏矩陣的每個非零元素用一個三元組來表示，即非零元素的行號、列號和它的值。然

程序員

http://

后按某種順序將全部非零元素的三元組存于一個數組中。

如果只對稀疏矩陣的某些單個元素進行處理，則宜用三元組表示。

2.十字鏈表

在十字鏈表中，矩陣的非零元素是一個結點，同一行的結點和同一列的結點分別順序循環鏈接，每個結點既在它所在行的循環鏈表中，又在它所在列的循環鏈表中。每個結點含5個域，分別為結點對應的矩陣元素的行號、列號、值，以及該結點所在行鏈表后繼結點指針、所在列鏈表后繼結點指針。

為了處理方便，通常對每個行鏈表和列鏈表分別設置一個表頭結點，并使它們構成帶表頭結點的循環鏈表。為了方便引用某行某列，全部行鏈表的表頭結點和全部列鏈表的表頭結點分別組成數組，這兩個數組的首結點指針存于一個十字鏈表的頭結點中，最后由一個指針指向該頭結點，如圖1-1所示。

圖1-1 十字鏈表

如果對稀疏矩陣某行或某列整體進行某種處理，可能會使原來為零的元素變為非零，而原來為非零的元素可能變成零。對于這種場合，稀疏矩陣宜用十字鏈表來表示。

1.2.4 字符串

程序員

http://

字符串是由某字符集上的字符所組成的任何有限字符序列。當一個字符串不包含任何字符時，稱它為空字符串。一個字符串所包含有效字符的個數稱為這個字符串的長度。一個字符串中任一連續的子序列稱為該字符串的子串。

字符串通常存于足夠大的字符數組中，每個字符串的最后一個有效字符之后有一個字符串結束標志，記為'