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

程序員

http://

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

第 1 章 數(shù)據(jù)結構與算法

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

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

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

1.常用數(shù)據(jù)結構

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

2.常用算法

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

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

1.1 算法設計概述

程序員

http://

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

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

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

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

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

（5）可行性：一個算法是可行的，即算法中描述的操作都是可以通過已經(jīng)實現(xiàn)的基本運算執(zhí)行有限次來實現(xiàn)的。

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

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

算法的復雜性是算法效率的度量，是算法運行所需要的計算機資源的量，是評價算法優(yōu)劣的重要依據(jù)?？梢詮囊粋€算法的時間復雜度與空間復雜度來評價算法的優(yōu)劣。當將一個算法轉換成程序并在計算機上執(zhí)行時，其運行所需要的時間取決于下列因素。

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

程序員

http://

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

（4）問題的規(guī)模。例如，求100以內(nèi)的素數(shù)與求1 000以內(nèi)的素數(shù)其執(zhí)行時間必然是不同的。

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

1.時間復雜度

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

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

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

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

f（n）≤ cg（n）

則有：

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

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

程序員

http://

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

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

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

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

2.空間復雜度

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

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

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

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

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

1.2 線性表

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

程序員

http://

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

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

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

1.線性表的基本運算

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

1）查找運算

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

2）插入運算

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

3）刪除運算

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

4）其他運算

統(tǒng)計線性表中結點的個數(shù)；

程序員

http://

輸出線性表各結點的值；

復制線性表；

線性表分拆；

線性表合并；

線性表排序；

按某種規(guī)則整理線性表。

2.線性表的存儲

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

1）順序存儲

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

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

2）鏈接存儲

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

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

程序員

http://

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

3.線性表上的查找

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

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

1）順序存儲

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

檢查插入要求的有關參數(shù)的合理性；

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

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

修改線性表的結點個數(shù)。

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

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

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

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

程序員

http://

接在線性表的末尾；

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

5.刪除線性表的結點

1）順序存儲

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

檢查刪除要求的有關參數(shù)的合理性；

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

修改線性表表元個數(shù)。

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

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

如鏈表為空鏈表，則不執(zhí)行刪除操作；

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

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

程序員

http://

將找到的結點刪除。

1.2.1 棧

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

1.順序存儲

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

2.鏈接存儲

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

1.2.2 隊列

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

1.順序存儲

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

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

程序員

http://

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

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

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

1.2.3 數(shù)組

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

1.三元組數(shù)組

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

程序員

http://

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

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

2.十字鏈表

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

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

圖1-1 十字鏈表

如果對稀疏矩陣某行或某列整體進行某種處理，可能會使原來為零的元素變?yōu)榉橇悖瓉頌榉橇愕脑乜赡茏兂闪?。對于這種場合，稀疏矩陣宜用十字鏈表來表示。

1.2.4 字符串

程序員

http://

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

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