1.1 數據結構與算法

考點1 算法

1.算法的基本概念

算法是指一系列解決問題的清晰指令。

真考鏈接

考核概率為45%。考生要熟記該考點的內容，尤其是算法的概念，以及時間復雜度和空間復雜度的概念。

（1）算法的基本特征。

●可行性：針對實際問題而設計的算法，執行后能夠得到滿意的結果，即必須有一個或多個輸出，即使在數學理論上是正確的，如果在實際的計算工具上不能執行，則該算法也是不具有可行性的。

●確定性：是指算法中每一步驟都必須是有明確定義的。

●有窮性：是指算法必須能在有限的時間內做完。

●擁有足夠的信息：一個算法是否有效，還取決于為算法所提供的信息是否足夠。

（2）算法的基本要素。

算法一般由兩種基本要素構成：

●對數據對象的運算和操作；

●算法的控制結構，即運算和操作時間的順序。

算法中對數據的運算和操作：算法就是按解題要求從指令系統中選擇合適的指令組成的指令序列。因此計算機算法就是計算機能執行的操作所組成的指令序列。不同的計算機系統，指令系統是有差異的，但一般的計算機系統中包括的運算和操作有4類：算術運算、邏輯運算、關系運算和數據傳輸。

算法的控制結構：算法中各操作之間的執行順序稱為算法的控制結構。算法的功能不僅取決于所選用的操作，還與各操作之間的執行順序有關。基本的控制結構包括順序結構、選擇結構和循環結構。

（3）算法設計的基本方法。

算法設計的基本方法有列舉法、歸納法、遞推法、遞歸法、減半遞推技術和回溯法。

2.算法復雜度

算法的復雜度主要包括時間復雜度和空間復雜度。

（1）算法的時間復雜度。

所謂算法的時間復雜度是指執行算法所需要的計算工作量。

一般情況下，算法的工作量用算法所執行的基本運算次數來度量，而算法所執行的基本運算次數是問題規模的函數，即：

算法的工作量=f（n）

其中n表示問題的規模。該表達式表示隨著問題規模n的增大，算法執行時間的增長率和f（n）的增長率相同。

在同一個問題規模下，如果算法執行所需的基本運算次數取決于某一特定輸入時，可以用兩種方法來分析算法的工作量：平均性態分析和最壞情況分析。

（2）算法的空間復雜度。

算法的空間復雜度一般是指執行這個算法所需要的內存空間。算法執行期間所需要的存儲空間包括以下3個部分：

●算法程序所占的空間；

●輸入的初始數據所占的存儲空間；

●算法執行過程中所需要的額外空間。

在實際操作中，為了減少算法所占的存儲空間，通常采用壓縮存儲的技術，用于減少不必要的額外空間。

考點2 數據結構的基本概念

1.數據結構的定義

數據結構是指相互有關聯的數據元素的集合，即數據的組織形式。

（1）數據的邏輯結構。

所謂數據的邏輯結構，是指反映數據元素之間邏輯關系（即前后件關系）的數據結構。它包括兩個要素，數據元素的集合和數據元素之間的關系。

（2）數據的存儲結構。

真考鏈接

考核概率為45%。考生要熟記該考點的內容，尤其是數據結構的定義、分類，能區分線性結構與非線性結構。

數據的邏輯結構在計算機存儲空間中的存放形式稱為數據的存儲結構（也稱為數據的物理結構）。數據結構的存儲方式包括順序存儲方法、鏈式存儲方法、索引存儲方法和散列存儲方法。而采用不同的存儲結構，其數據處理的效率是不同的。因此，在進行數據處理時，選擇合適的存儲結構是很重要的。

數據結構研究的內容主要包括3個方面：

●數據集合中各數據元素之間的邏輯關系，即數據的邏輯結構；

●在對數據進行處理時，各數據元素在計算機中的存儲關系，即數據的存儲結構；

●對各種數據結構進行的運算。

2.數據結構的圖形表示

數據元素之間最基本的關系是前后件關系。前后件關系，即每一個二元組，都可以用圖形來表示。用中間標有元素值的方框表示數據元素，一般稱為數據節點，簡稱為節點。對于每一個二元組，用一條有向線段從前件指向后件。

圖形表示數據結構具有直觀易懂的特點，在不引起歧義的情況下，前件節點到后件節點連線上的箭頭可以省略。例如，樹型結構中，通常都是用無向線段來表示前后件關系的。

3.線性結構與非線性結構

根據數據結構中各數據元素之間前后件關系的復雜程度，一般將數據結構分為兩大類型，即線性結構和非線性結構。

如果一個非空的數據結構滿足有且只有一個根節點，并且每個節點最多有一個前件，也最多有一個后件，則稱該數據結構為線性結構，又稱線性表。如果不滿足上述條件的數據結構則稱為非線性結構。

小提示

需要注意的是，在一個線性結構中插入或刪除任何一個節點后還應該是線性結構。否則，不能稱為線性結構。

真題精選

下列敘述中正確的是______。

A）程序執行的效率與數據的存儲結構密切相關

B）程序執行的效率只取決于程序的控制結構

C）程序執行的效率只取決于所處理的數據量

D）以上3種說法都不對

【答案】 A

【解析】在計算機中，數據的存儲結構對數據的執行效率有較大影響，如在有序存儲的表中查找某個數值比在無序存儲的表中查找的效率高很多。

考點3 線性表及其順序存儲結構

1.線性表的基本概念

數據結構中，線性結構又稱為線性表，線性表是最簡單也是最常用的一種數據結構。

真考鏈接

考核概率為45%。考生要熟記該知識點屬于了解性內容，主要是線性表的基本概念。

線性表是由n（n≥0）個數據元素a1,a2,…,an組成的一個有限序列，表中的第一個元素外，有且只有一個前件，除了最后一個元素外，有且只有一個后件。

線性表或者是個空表，或者可以表示為：

（a1,a2,…,ai,…,an）

其中，ai（i=1,2,…,n）是線性表的數據元素，也稱為線性表的一個節點。

每個數據元素在不同情況下其具體含義各不相同，它可以是一個數或一個字符，也可以是一個具體的事物，甚至是更復雜的信息。但是需要注意的是同一線性表中的數據元素必定具有相同的特性，即屬于同一數據對象。

小提示

非空線性表具有以下一些結構特征：

● 只有一個根節點，即頭節點，它無前件；

● 有且只有一個終節點，即尾節點，它無后件；

● 除頭節點與尾節點外，其他所有節點有且只有一個前件，也有且只有一個后件。節點個數n稱為線性表的長度，當n=0時，稱為空表。

2.線性表的順序存儲結構

將線性表中的元素逐個存儲在一片相鄰的存儲區域中。這種順序表示的線性表也稱為順序表。

線性表的順序存儲結構具有以下兩個基本特點。

●元素所占的存儲空間必須是連續的。

●元素在存儲空間的位置是按邏輯順序存放的。

從上述特點也可以看出，線性表是用元素在計算機內物理位置上的相鄰關系來表示元素之間邏輯上的相鄰關系。只要確定了首地址，線性表內任意元素的地址都可以方便地計算出來。

3.線性表的插入運算

線性表的插入運算中，在第i個元素之前插入一個新元素，完成插入操作主要有以下3個步驟。

（1）把原來第n個節點至第i個節點依次往后移一個元素位置。

（2）把新節點放在第i個位置上。

（3）修正線性表的節點個數。

小提示

一般會為線性表開辟一個大于線性表長度的存儲空間，經過多次插入運算，可能出現存儲空間已滿的情況，如果此時仍繼續插入運算，將會產生錯誤，此類錯誤稱為“上溢”。

如果需要在線性表末尾進行插入運算，則只需在表的末尾增加一個元素即可，不需要移動線性表中的元素。

如果在第一個位置插入新的元素，則需要移動表中所有的元素。

4.線性表的刪除運算

在線性表的刪除運算中，刪除第i個位置的元素，則要從第i+1個元素開始，直到第n個元素之間共n-i個元素依次向前移一個位置，完成刪除運算主要有以下幾個步驟。

（1）把第i個元素之后（不包括第i個元素）的n-i個元素依次前移一個位置。

（2）修正線性表的節點個數。

綜上所述，如果刪除運算在線性表的末尾進行，即刪除第n個元素，則不需要移動線性表中的元素。如果要刪除第1個元素，則需要移動表中所有的數據。

小提示

由線性表的上述性質可以看出，線性表的順序存儲結構適用于小線性表，或者建立之后其中元素不常變動的線性表，而不適用于需要經常進行插入和刪除運算的線性表盒長度較大的線性表。

真題精選

【例1】下列有關順序存儲結構的敘述，不正確的是______。

A）存儲密度大

B）邏輯上相鄰的節點物理上不必鄰接

C）可以通過計算機直接確定第i個節點的存儲地址

D）插入、刪除操作不方便

【答案】B

【解析】順序存儲結構要求邏輯上相鄰的元素物理地址上也相鄰，所以只有選項B敘述錯誤。

【例2】在一個長度為 n 的順序表中，向第 i個元素（1≤i≤n +1）的位置插入一個新元素，需要從后向前依次移動______個元素。

A）n-i

B）i

C）n-i-1

D）n-i+1

【答案】D

【解析】根據順序表的插入運算的定義知道，在第i個位置上插入x，從ai到an都要向后移動一個位置，所以共需要移動n-i+1個元素。

考點4 棧和隊列

1.棧及其基本運算

（1）棧的基本概念。

棧實際上也是線性表，只不過是一種特殊的線性表。在這種特殊的線性表中，其插入運算與刪除運算都只在線性表的一端進行。

在棧中，允許插入與刪除的一端稱為棧頂（top），另一端稱為棧底（bottom）。若棧中沒有元素稱為空棧，棧也被稱為“先進后出”表，或“后進先出”表。

真考鏈接

考核概率為90%，此部分屬于必考知識點。該考點較為基礎，考生要理解棧和隊列的概念和特點，掌握棧和隊列的運算。

（2）棧的特點。

根據棧的上述定義，棧具有以下特點。

●棧頂元素總是最后被插入的元素，也是最早被刪除的元素。

●棧底元素總是最早被插入的元素，也是最后才能被刪除的元素。

●棧具有記憶作用。

●在順序存儲結構下，棧的插入和刪除運算都不需要移動表中其他數據元素。

●棧頂指針top動態反映了棧中元素的變化情況。

（3）棧的順序存儲及其運算。

棧的狀態如圖1.1所示。

根據棧的狀態，可以得知棧的基本運算有以下3種。

●入棧運算：在棧頂位置插入一個新元素。

●退棧運算：取出棧頂元素并賦給一個指定的變量。

●讀棧頂元素：將棧頂元素賦給一個指定的變量。

2.隊列及其基本運算

（1）隊列的基本概念。

隊列是指允許在一端進行插入，而在另一端進行刪除的線性表。允許插入的一端稱為隊尾，通常用一個稱為尾指針（rear）的指針指向隊尾元素；允許刪除的一端稱為排頭，通常用一個頭指針（front）指向頭元素的前一個位置。

因此，隊列又稱為“先進先出”（FIFO-FirstIn FirstOut）的線性表。插入元素稱為入隊運算，刪除元素稱為退隊運算。

隊列的基本結構如圖1.2所示。

（2）循環隊列及其運算。

所謂循環隊列，就是將隊列存儲空間的最后一個位置繞到第一個位置，形成邏輯上的環狀空間，供隊列循環使用。

在循環隊列中，用尾指針（rear）指向隊列的尾元素，用頭指針（front）指向頭元素的前一個位置。因此，從頭指針（front）指向的后一個位置，直到尾指針（rear）指向的位置之間所有的元素均為隊列中的元素。循環隊列的初始狀態為空，即rear=front。

循環隊列的基本運算主要有兩種：入隊運算與退隊運算。

●入隊運算是指在循環隊列的隊尾加入一個新的元素。

●退隊運算是指在循環隊列的排頭位置退出一個元素，并賦給指定的變量。

小提示

棧是按照“先進后出”或“后進先出”的原則組織數據，而隊列是按照“先進先出”或“后進后出”的原則組織數據。這就是棧和隊列的不同。

真題精選

【例1】下列對隊列的敘述正確的是______。

A）隊列屬于非線性表

B）隊列按“先進后出”原則組織數據

C）隊列在隊尾刪除數據

D）隊列按“先進先出”原則組織數據

【答案】D

【解析】隊列是一種特殊的線性表，它只能在一端進行插入，在另一端進行刪除。允許插入的一端稱為隊尾，允許刪除的另一端稱為隊頭。隊列又稱為“先進先出”或“后進后出”的線性表，體現了“先到先服務”的原則。

【例2】下列關于棧的描述正確的是______。

A）在棧中只能插入元素而不能刪除元素

B）在棧中只能刪除元素而不能插入元素

C）棧是特殊的線性表，只能在一端插入或刪除元素

D）棧是特殊的線性表，只能在一端插入元素，而在另一端刪除元素

【答案】C

【解析】棧是一種特殊的線性表。在這種特殊的線性表中，其插入和刪除操作只能在線性表的一端進行。

考點5 線性鏈表

1.線性鏈表的基本概念

線性表的鏈式存儲結構稱為線性鏈表。

真考鏈接

考核概率為35%。考生要熟記該考點內容，尤其是線性鏈表的概念和特點、順序表和鏈表的優、缺點等。

為了存儲線性表中的每一個元素，一方面要存儲數據元素的值；另一方面要存儲各數據元素之間的前后件關系。為此，在鏈式存儲方式中，每個節點由兩部分組成：一部分稱為數據域，用于存放數據元素值；另一部分稱為指針域，用于存放下一個數據元素的存儲序號，即指向后件節點。鏈式存儲結構既可以表示線性結構，也可以表示非線性結構。

線性表鏈式存儲結構的特點是用一組不連續的存儲單元存儲線性表中的各個元素。因為存儲單元不連續，所以數據元素之間的邏輯關系就不能依靠數據元素的存儲單元之間的物理關系來表示。

2.線性鏈表的基本運算

線性鏈表主要包括以下8種運算：

●在線性鏈表中包含指定元素的節點之前插入一個新元素；

●在線性鏈表中刪除包含指定元素的節點；

●將兩個線性鏈表按要求合并成一個線性鏈表；

●將一個線性鏈表按要求進行分解；

●逆轉線性鏈表；

●復制線性鏈表；

●線性鏈表的排序；

●線性鏈表的查找。

3.循環鏈表及其基本運算

（1）循環鏈表的定義。

在單鏈表的第一個節點前增加一個表頭節點，隊頭指針指向表頭節點，在最后一個節點的指針域的值由NULL改為指向表頭節點，這樣的鏈表稱為循環鏈表。循環鏈表中，所有節點的指針構成了一個環狀鏈。

（2）循環鏈表與單鏈表的比較。

對單鏈表的訪問是一種順序訪問，從其中某一個節點出發，只能找到它的直接后繼，但無法找到它的直接前驅。而且對于空表和第一個節點的處理必須單獨考慮，空表與非空表的操作不統一。

在循環鏈表中，只要指出表中任何一個節點的位置，就可以從它出發訪問到表中其他所有的節點。由于表頭節點是循環鏈表所固有的節點，因此，即使在表中沒有數據元素的情況下，表中也至少有一個節點存在，從而使空表和非空表的運算統一。

真題精選

下列敘述中正確的是______。

A）線性鏈表是線性表的鏈式存儲結構

B）棧與隊列是非線性結構

C）雙向鏈表是非線性結構

D）只有根節點的二叉樹是線性結構

【答案】A

【解析】根據數據結構中各數據元素之間前后關系的復雜程序，可將數據結構分為兩大類型：線性結構與非線性結構。如果一個非空的數據結構滿足下列兩個條件：①有且只有一個根節點；②每個節點最多有一個前驅，也最多有一個后繼，則稱該數據結構為線性結構，也叫做線性表。若不滿足上述條件，則稱之為非線性結構。線性表、棧與隊列、線性鏈表都是線性結構，而二叉樹是非線性結構。

考點6 樹和二叉樹

1.樹的基本概念

樹是一種簡單的非線性結構，直觀地來看樹是以分支關系定義的層次結構。樹是由n（n≥0）個節點構成的有限集合，當n=0時，樹稱為空樹。當n≠0時，樹中的節點應該滿足以下兩個條件：

真考鏈接

考核概率為100%，本節內容屬于必考知識點，特別是關于二叉樹的遍歷。考生要熟記該考點內容，尤其是二叉樹的概念及其相關術語，并掌握二叉樹的性質以及二叉樹的3種遍歷方法。本知識點是數據結構的重要部分。

●有且僅有一個沒有前驅的節點稱之為根；

●其余節點分成m（m＞0）個互不相交的有限集合T1,T2,…,Tm，其中每一個集合又都是一棵樹，稱T1,T2,…,Tm為根節點的子樹。

在樹的結構中主要涉及下面幾個概念。

●每一個節點只有一個前件，稱為父節點，沒有前件的節點只有一個，稱為樹的根節點，簡稱樹的根。

●每一個節點可以有多個后件，稱為該節點的子節點。沒有后件的節點稱為葉子節點。

●一個節點所擁有的后繼個數稱為該節點的度。

●所有節點最大的度稱為樹的度。

●樹的最大層次稱為樹的深度。

2.二叉樹及其基本性質

（1）二叉樹的定義。

二叉樹是一種非線性結構，是一個有限的節點集合，該集合或者為空，或者由一個根節點及其兩棵互不相交的左右二叉子樹所組成。當集合為空時，稱該二叉樹為空二叉樹。

二叉樹具有以下特點。

●二叉樹可以為空，空的二叉樹沒有節點，非空二叉樹有且只有一個根節點。

●每一個節點最多有兩棵子樹，且分別稱為該節點的左子樹與右子樹。

（2）滿二叉樹和完全二叉樹。

滿二叉樹：除最后一層外，每一層上的所有節點都有兩個子節點，即在滿二叉樹的第k層上有2k-1個節點，且深度為m的滿二叉樹中有2m-1個節點。

完全二叉樹：除最后一層外，每一層上的節點數都達到最大值；在最后一層上只缺少右邊的若干節點。

滿二叉樹與完全二叉樹的關系：滿二叉樹一定是完全二叉樹，但完全二叉樹不一定是滿二叉樹。

（3）二叉樹的主要性質。

●一棵非空二叉樹的第k層上最多有2k-1個節點（k≥1）。

●深度為m的滿二叉樹中有2m-1個節點。

●對任何一棵二叉樹，度為0的節點（即葉子節點）總是比度為2的節點多一個。

●具有n個節點的完全二叉樹的深度k為［log2n] +1。

3.二叉樹的存儲結構

在計算機中，二叉樹通常采用鏈式存儲結構，用于存儲二叉樹中各元素的存儲節點由數據域和指針域組成。由于每一個元素可以有兩個后件（即兩個子節點），所以用于存儲二叉樹的存儲節點的指針域有兩個：一個指向該節點的左子節點的存儲地址，稱為左指針域；另一個指向該節點的右子節點的存儲地址，稱為右指針域。因此，二叉樹的鏈式存儲結構也稱為二叉鏈表。

對于滿二叉樹與完全二叉樹可以按層次進行順序存儲。

4.二叉樹的遍歷

二叉樹的遍歷是指不重復地訪問二叉樹中的所有節點。二叉樹的遍歷主要是針對非空二叉樹的，對于空二叉樹，則結束返回。

二叉樹的遍歷有前序遍歷、中序遍歷和后序遍歷。

（1）前序遍序（DLR）。

首先訪問根節點，然后遍歷左子樹，最后遍歷右子樹。

（2）中序遍歷（LDR）。

首先遍歷左子樹，然后訪問根節點，最后遍歷右子樹。

（3）后序遍歷（LRD）。

首先遍歷左子樹，然后遍歷右子樹，最后訪問根節點。

小提示

已知一棵二叉樹的前序遍歷序列和中序遍歷序列，可以唯一確定這棵二叉樹。已知一棵二叉樹的后序遍歷序列和中序遍歷序列，也可以唯一確定這棵二叉樹。已知一棵二叉樹的前序遍歷序列和后序遍歷序列，不能唯一確定這棵二叉樹。

真題精選

對如右圖中二叉樹進行后序遍歷的結果為______。

A）ABCDEF

B）DBEAFC

C）ABDECF

D）DEBFCA

【答案】D

【解析】執行后序遍歷，依次執行如下操作：

①按照后序遍歷的順序遍歷根節點的左子樹；

②按照后序遍歷的順序遍歷根節點的右子樹；

③訪問根節點。

考點7 查找技術

1.順序查找

順序查找一般是指在線性表中查找指定的元素。其基本思路是：從表中的第一個元素開始，依次將線性表中的元素與被查找元素進行比較，直到兩者相符，查到所要找的元素為止。否則，表中沒有要找的元素，查找不成功。

真考鏈接

考核概率為35%，考生需要理解該考點內容，主要是順序查找與二分查找的概念，以及一些查找的方法。

在最好的情況下，第一個元素就是要查找的元素，則比較次數為1次。

在最壞的情況下，順序查找需要比較n次。

在平均情況下，需要比較n／2次。因此查找算法的時間復雜度為O（n）。

在下列兩種情況下只能夠采取順序查找：

●如果線性表中元素的排列是無序的，則無論是順序存儲結構還是鏈式存儲結構，都只能用順序查找；

●即便是有序線性表，若采用鏈式存儲結構，只能進行順序查找。

2.二分查找

使用二分法查找的線性表必須滿足以下兩個條件：

●順序存儲結構；

●線性表是有序表。

所謂有序表，是指線性表中的元素按值非遞減排列（即從小到大，但允許相鄰元素值相等）。

對于長度為n的有序線性表，利用二分法查找元素x的過程如下。

（1）將x與線性表的中間項進行比較。

（2）若中間項的值等于x，則查找成功，結束查找。

（3）若x小于中間項的值，則在線性表的前半部分以二分法繼續查找。

（4）若x大于中間項的值，則在線性表的后半部分以二分法繼續查找。

這樣反復進行查找，直到查找成功或子表長度為0（說明線性表中沒有這個元素）為止。

當有序線性表為順序存儲時采用二分查找的效率要比順序查找高得多。對于長度為n的有序線性表，在最壞的情況下，二分查找只需比較log2n次，而順序查找則需要比較n次。

真題精選

下列數據結構中，能用二分法進行查找的是______。

A）順序存儲的有序線性表

B）線性鏈表

C）二叉鏈表

D）有序線性鏈表

【答案】A

【解析】二分法查找只適用于順序存儲的有序表。所謂有序表是指線性表中的元素按值非遞減排列（即從小到大，但允許相鄰元素值相等）。

考點8 排序技術

1.交換類排序法

交換類排序法是指借助數據元素的“交換”進行排序的一種方法。本節介紹的冒泡排序法和快速排序法就是屬于交換類排序法。

真考鏈接

考核概率為25%，考生需要掌握該考點內容，主要是各種排序方法的概念、基本思想以及它們的復雜度。

（1）冒泡排序法。

冒泡排序的基本思想。

在線性表中依次查找相鄰的數據元素，將表中最大的元素不斷往后移動，反復操作直到消除所有逆序。此時，該表已經排序結束。

冒泡排序法的基本過程。

①從表頭開始往后查找線性表，在查找過程中逐次比較相鄰兩個元素的大小。若在相鄰兩個元素中，前面的元素大于后面的元素，則將它們交換。

②從后向前查找剩下的線性表（除去最后一個元素），同樣，在查找過程中逐次比較相鄰兩個元素的大小。若在相鄰兩個元素中，后面的元素小于前面的元素，則將它們交換。

③對剩下的線性表重復上述過程，直到剩下的線性表變空為止，線性表排序完成。

假設線性表的長度為n，則在最壞的情況下，冒泡排序需要經過n／2遍從前往后的掃描和n／2遍從后往前掃描，需要比較n（n-1）／2次，其數量級為n2。

（2）快速排序法。

快速排序法的基本思想。

在線性表中逐個選取元素，將線性表進行分割，直到所有元素全部選取完畢，此時線性表已經排序結束。

快速排序法的基本過程。

①從線性表中選取一個元素，設為T，將線性表后面小于T的元素移動到前面，而將大于T的元素移到后面，這樣就將線性表分成了兩部分（稱為兩個子表）。T就是處于分界線的位置，將線性表分成了前后兩個子表，且前面子表中的所有元素均不大于T，而后子表中的所有元素均不小于T，此過程稱為線性表的分割。

②對分割后的子表再按上述原則進行反復分割，直到所有子表為空為止，則此時的線性表就變成有序。

2.插入類排序法

插入排序是指將無序序列中的各元素依次插入已經有序的線性表中。本節將主要介紹簡單插入排序法和希爾排序法。

（1）簡單插入排序法。

簡單插入排序是把n個待排序的元素看成一個有序表和一個無序表，開始時，有序表只包含一個元素，而無序表包含n-1個元素，每次取無序表中的第一個元素插入到有序表中的正確位置，使之成為增加一個元素的新的有序表。插入元素時，插入位置及其后的記錄依次向后移動。最后有序表的長度為n，而無序表為空，此時排序完成。

在簡單插入排序中，每一次比較后最多移除一個逆序，因此，該排序方法的效率與冒泡排序法相同。一般簡單插入排序需要n（n-1）／2次比較。

（2）希爾排序法。

希爾排序法是將整個無序序列分割成若干個小的子序列并分別進行插入排序。

分割方法如下：

①將相隔某個增量h的元素構成一個子序列；

②在排序過程中，逐次減少這個增量，直到h減到1時，進行一次插入排序，排序即可完成。

希爾排序的效率與所選取的增量序列有關。

3.選擇類排序法

選擇排序是通過每次從待排序序列中選出的最小值是元素，順序放在已排好序的有序子表的后面，直到全部序列滿足排序要求為止。下面就介紹選擇類排序法中的簡單選擇排序法和堆排序法。

（1）簡單選擇排序法。

進行簡單選擇排序，首先從所有n個待排序的數據元素中選擇最小的元素，將該元素與第一個元素交換，再從剩下的n-1個元素中選出最小的元素與第二個元素交換。重復這樣的操作直到所有的元素有序為止。

簡單選擇排序需要比較n（n-1）／2次。

（2）堆排序法。

堆排序的方法如下：

①將一個無序序列建成堆；

②將堆頂元素與堆中最后一個元素交換。忽略已經交換到最后的那個元素，考慮前n-1個元素構成的子序列，只有左、右子樹是堆，可以將該子樹調整為堆。這樣反復下去做第二步，直到剩下的子序列空為止。

堆排序需要比較的次數為O（nlog2n）。

真題精選

對于長度為n的線性表，下列各排序法所對應的比較次數中正確的是______。

A）冒泡排序為n／2

B）冒泡排序為n

C）快速排序為n

D）快速排序為n（n-1）／2

【答案】D

【解析】假設線性表的長度為n，則冒泡排序需要經過n／2遍的從前往后掃描和n／2遍的從后往前掃描，需要比較次數為n（n-1）／2。快速排序法在最壞的情況下，比較次數也是n（n-1）／2。

常見問題

為什么只有二叉樹的前序遍歷和后序遍歷不能唯一確定一棵二叉樹？

在二叉樹遍歷中前序和后序中都可以肯定根節點，在中序是由左至根及右的順序，所以知道前序（或后序）和中序肯定能唯一確定二叉樹；在前序和后序中只能確定根節點而對于左右子樹的節點元素沒辦法正確選取，所以很難確定一個二叉樹。由此可見需要確定一棵二叉樹的基礎是必須得知道中序遍歷。