第 2 章 緒論

????????本章主要介紹數據結構相關的一些基本概念，是后續章節的基礎。我們也將 408 考試大綱中，關于數據結構部分的考查目標羅列在這里，供各位考生參考：

????????1.掌握數據結構的基本概念、基本原理和基本方法。

????????2.掌握數據的邏輯結構、存儲結構及基本操作的實現，能夠對算法進行基本的時間復雜度與空間復雜度分析。

????????3.能夠運用數據結構的基本原理和方法進行問題的分析與求解，具備采用 C 或 C++ 語言設計與實現算法的能力。

【考綱內容】

1.數據結構的基本概念；

2.算法的基本概念。

【考情統計】

年份	題數及分值			考點
	單選題	綜合題	總分值
2009	0	0	0	未直接考察本章內容
2010	0	1	2	時間復雜度、空間復雜度
2011	1	1	4	時間復雜度、空間復雜度
2012	2	1	5	時間復雜度
2013	1	1	4	時間復雜度、空間復雜度
2014	1	0	2	時間復雜度
2015	0	1	2	時間復雜度、空間復雜度
2016	0	1	2	時間復雜度、空間復雜度
2017	1	0	2	時間復雜度
2018	0	1	2	時間復雜度、空間復雜度
2019	1	1	4	時間復雜度
2020	0	1	2	時間復雜度、空間復雜度
2021	0	1	2	時間復雜度、空間復雜度
2022	1	1	4	時間復雜度、空間復雜度
2023	1	0	2	時間復雜度、空間復雜度
2024	0	0	0	未直接考察本章內容

【考點解讀】

????????在 408 考試中，本章內容幾乎每年都有相關考查，主要是考查時間復雜度和空間復雜度的計算。通常是考一個時間復雜度分析的選擇題（占 2 分）。有些年份在算法題的最后一問中，也會要求分析所寫算法的時間和空間復雜度（占 2 - 3 分）。本章常見的題目形式有：給定一段循環或遞歸代碼，分析時間復雜度；分析算法代碼的空間復雜度等。

【復習建議】

????????本章內容雖然考試所占分值較少，但時間和空間復雜度的分析是每個 408 考生都必須要掌握的基本內容。重點掌握時間復雜度和空間復雜度的分析方法。而對于數據結構的基本概念，了解即可。另外，第一次學習這些概念不理解也沒關系，學完本書再回過頭來看這些概念，會有更進一步的理解。

2.1 數據結構的定義

????????數據結構暫時沒有一個統一的官方定義。這里僅列舉一個容易理解的定義：數據結構是數據對象，以及存在于該對象的實例和組成實例的數據元素之間的各種聯系。這些聯系可以通過定義相關的函數來給出。

????????數據結構是一門討論 “描述現實世界實體的數學模型及其之上的運算在計算機中如何表示和實現” 的學科。數據結構包含以下三個方面的內容：

（1）數據的邏輯結構：指從具體問題中抽象出來的、描述數據之間邏輯關系的、與數據的存儲無關的數學模型。本書后面介紹的線性表、樹、圖均是指邏輯結構。

（2）數據的物理結構：指數據的邏輯結構在計算機中的存儲實現 2。常用的物理結構如下：

????????①順序存儲結構：利用數據元素在存儲器中的相對位置來表示元素之間的邏輯關系 3，通常用數組來實現。

????????②鏈式存儲結構：是一種數據元素的邏輯地址相鄰、物理地址不一定相鄰的存儲結構，通過鏈表中指針的鏈接次序來表示數據元素之間的邏輯順序。

????????提示：數據元素是數據的基本單位，用于完整地描述一個對象 2。數據元素通常也稱為結點、頂點、記錄、元素等。

????????③散列存儲結構：根據元素的關鍵字通過散列函數計算出一個值，并將這個值作為該元素的地址 2。散列存儲結構在本書 7.5 小節（第 333 頁）有詳細介紹。

????????④索引存儲結構：索引通常基于一個或多個字段的值創建，這些字段被稱為索引鍵。索引通過將索引鍵與對應的數據記錄或數據塊建立關聯，形成索引項。索引項可以按照特定的排序順序組織，以支持快速的查找和范圍查詢操作。

（3）數據的運算：指對數據實施的操作。常見的運算有：對數據的增刪改查、排序等。

????????數據的邏輯結構和物理結構的區別：物理結構是數據在計算機內存中的存儲方式，比如順序存儲、鏈式存儲、散列存儲等，邏輯結構是描述數據與數據之間的關系，比如隊列、棧、堆等。

2.2 算法的基本概念

????????算法（Algorithm）還沒有一個公認的定義，這里列舉一個易于理解的定義：算法是為了解決某類問題而規定的一個有限長的操作序列。

一個算法必須具備以下 5 個要素：

1.有窮性：在執行有限次基本操作之后結束。

2.確定性：在算法中明確規定了每種情況應該執行的操作。相同的輸入得到相同的輸出，不存在二義性。

3.可行性：算法由若干語義明確的基本操作組成。算法中所有的操作均可通過調用有限次基本操作來實現。

4.輸入：可理解為對所求的特定問題的描述。一個算法可以有零個或多個輸入。

5.輸出：可理解為輸入的問題經過算法的處理之后，得到的求解結果。算法至少有一個輸出。

????????提示：算法和程序的區別在于，算法主要描述解決問題的方法，而程序則是通過某種計算機語言具體實現一個算法。

一個算法的好壞可以從以下幾個方面來評價：

1.正確性：指算法執行后能得到預期的結果。這是算法最基礎的功能。

2.易讀性：算法應方便使用，便于理解、修改、調試。

3.健壯性：具備對異常情況的處理。

4.高效性：執行效率高，合理占用存儲空間。

2.3 算法效率分析

????????衡量算法效率的指標主要有兩個：時間復雜度和空間復雜度。

2.3.1 時間復雜度

1.時間復雜度的定義

①問題規模 n 指算法的輸入量。可以理解為數據量的大小。例如：在排序算法中，問題規模 n 指參與排序的數據個數；在樹相關運算中，問題規模 n 指樹中結點的個數。

②語句頻度指一條語句的重復執行次數 3。

③基本語句指對算法運行時間影響最大的語句。

④用函數 f (n) 表示一個算法中基本語句的頻度之和。

時間復雜度（Time complexity），常用函數 T (n) 表示，指基本語句執行次數的數量級。通常用符號 O（Order 的簡寫）表示取數量級的操作，則有：

????????????????????????????????????????????????????????T (n)=O (f (n))

提示：一個算法中所有語句頻度之和與基本語句頻度之和是同一個數量級的。

2.時間復雜度計算

時間復雜度的計算步驟為：

(1) 找到所有語句中執行次數最多的那條語句作為基本語句。

(2) 計算基本語句執行次數的數量級。

(3) 取其數量級用大 O 來表示即可。
例如，有以下 A、B、C 三段代碼：

A：
A[0][0]++;B：for (int i = 0; i < n; i++)①A[i][i] += 2;②C：for (int k = 0; k < n; k++)①if (A[k][k] > 9)②for (int i = 0; i < n; i++)③for (int j = 0; j < n; j++)④++A[i][j];⑤

(1) 在代碼 A 中：基本語句 “A [0][0]++” 的執行次數為 1 次，算法的時間復雜度 T (n)=O (1)。

(2) 在代碼 B 中：基本語句 “A [i][i]+=2;” 的執行次數為 n 次，算法的時間復雜度 T (n)=O (n)。

(3) 在代碼 C 中：基本語句 “++A [i][j]” 的執行與判斷語句 “if (A [k][k]>9)” 有關，若該判斷語句一直不成立，則基本語句 “++A [i][j]” 的執行次數為 0。反之若一直成立的話，則執行次數為 n3，算法的時間復雜度 T (n)=O (n3)。

3.時間復雜度的分類

算法的時間復雜度不僅與問題規模 n 有關，還和其他因素有關，比如：初始狀態等。

(1) 在算法計算量最小的情況的復雜度稱為最好時間復雜度。例如：在上述的程序 C 中，若語句②一直不成立，則該情況下的時間復雜度稱為該算法的最好時間復雜度。

(2) 在算法計算量最大的情況的復雜度稱為最壞時間復雜度。例如：在上述的程序 C 中，若語句②一直成立，則該情況下的時間復雜度稱為該算法的最壞時間復雜度。

(3) 在所有可能情況下，各種輸入情況等概率出現，算法的計算量取加權平均值，在該情況下的復雜度稱為平均時間復雜度。例如：在上述的程序 C 中，若語句②成立的概率為 1/n，則該情況下的時間復雜度稱為該算法的平均時間復雜度。

通常，時間復雜度默認指最壞時間復雜度。

4.常用時間復雜度大小的比較

O (1)<O (log?n)<O (n)<O (nlog?n)<O (n2)<O (n3)<O (2?)<O (n!)<O (n?)

常數階，對數階，線性階，線性對數階，平方階，立方階，指數階，階乘階，n次方階

提示：任意底數的對數復雜度都是同階的，例如：O (log?n)=O (log?n)。

5.時間復雜度的相關總結

(1) 遞歸算法的時間復雜度計算方法比較固定，這里舉例說明：
假設有如下遞歸公式，計算 T (n) 的時間復雜度。

觀察 T (n) 的遞歸函數，可以將 T (n) 遞歸成
T (n)=T (n - 1)+1=T (n - 2)+2=T (n - 3)+3=…=T (1)+n - 1
可以看出，該遞歸的時間復雜度為 O (n)。
????????提示：還可以用算法分析中的主定理（master theorem）來快速求解遞歸式算法的時間復雜度，感興趣的考生可以自行了解相關知識。

(2) 基本操作：只有常數項，時間復雜度為 O (1)。

(3) 順序結構：時間復雜度按加法規則進行相加。

(4) 分支結構：時間復雜度按最壞情況下的時間復雜度進行計算。

(5) 循環結構：時間復雜度按乘法規則進行計算。

(6) 分析具體算法的時間復雜度時，一般分析最壞情況下的時間復雜度。

(7) 利用時間復雜度判斷算法的效率高低時，只需關注基本操作的最高次項即可。

例如：O (n2 + 2?)，則認為該算法的時間復雜度為指數階。

(8) 加法規則：T (n)=T?(n)+T?(n)=O (h (n))+O (f (n))=O (max (h (n),f (n)))。

(9) 乘法規則：T (n)=T?(n)×T?(n)=O (h (n))×O (f (n))=O (h (n)×f (n))。

2.3.2 空間復雜度

一個具體的算法在占用的存儲空間主要包括三部分：

（1）存儲程序本身的空間：比如具體的程序代碼。

（2）存儲算法輸入和輸出數據的空間：與問題規模 n 有關。

（3）對數據進行輔助操作的臨時變量所占存儲空間：分析算法的空間復雜度，就是分析這部分的空間。

????????空間復雜度（Space complexity）是對一個算法在運行過程中臨時占用存儲空間的大小的量度 2。若問題的規模為 n，f (n) 是算法運行過程中需要的輔助存儲空間的函數，符號 O（Order 的簡寫）表示取數量級的操作。用 S (n) 表示空間復雜度，則：

????????????????????????????????????????????????????????????????S (n)=O (f (n))

????????若算法在運行過程中占用的臨時空間為常數級別（即：O (1)），則稱算法是原地工作的。

????????遞歸算法的空間復雜度 = 每次遞歸的空間復雜度 × 遞歸深度。要求遞歸的深度是因為每次遞歸所需空間都被壓到調用棧，所以該棧最大的長度就是遞歸的深度。一般每次遞歸中需要的空間是一個常量，每次遞歸的空間復雜度皆為 O (1)。

2.4 章末總結

（1）理解 “邏輯結構” 和 “物理結構” 的概念，理解它們兩者之間定義的區別。

（2）重點掌握根據具體代碼分析算法的時間和空間復雜度的方法，牢記時間復雜度的 8 條計算規則。

2.5 習題精編

1.某算法的時間復雜度為 O (n2)，表明該算法的（ ）。
A. 問題規模是 n2
B. 執行時間等于 n2
C. 執行時間與 n2 成正比
D. 問題規模與 n2 成正比

1.【參考答案】?C
【解析】?假設問題規模為 n，且時間復雜度T(n)=kn^2（k 為常數系數），則可以得到時間復雜度T(n)=O(n^2)。可以看出 A、B 和 D 不正確，因為此時規模為 n，執行時間為kn^2。

2.下面所示的各個數據結構中，屬于非線性數據結構的是（ ）。
A. 樹結構
B. 隊列結構
C. 棧結構
D. A、B、C 均是

2.【參考答案】?A
【解析】?樹是一種分支結構，屬于非線性數據結構。棧和隊列屬于線性數據結構。

3.下面所示的各個選項中，（ ）屬于邏輯結構。
A. 順序表
B. 散列表
C. 有序表
D. 單鏈表

3.【參考答案】?C
【解析】?有序表是一種邏輯結構，“有序” 指明表中的數據是按一定的邏輯順序進行排列的，屬于邏輯結構。順序表、散列表和單鏈表都是物理結構。

4.以下算法的時間復雜度為（ ）。

void test(int n) {int i = -520;for (i = 0; i*i*i <= n; )++i;
}

A. O(n)
B. O(nlogn)
C. O(n1/3)
D. O(n1/2)

4.【參考答案】?C
【解析】?觀察程序發現，語句 “++i;” 執行頻率較高，且該語句影響 for 循環判斷語句。
(1) 假設該語句執行了 t 次，當執行到 t + 1 次時，for 的判斷語句為i?i?i>n。
(2) 由于 i 在循環里的初始值等于 0，當語句 “++i” 執行到第 t 次結束時，i=t。結合 (1) 的結論，有O(t^3>n)，解得t>n^(1/3)，即有T(n)=O(n^(1/3))。選擇 C。

5.以下代碼在最壞情況下的時間復雜度為（ ）。

for (k = n - 1; k >= 1; --k)for (t = 1; t < k; ++t)if (A[t] > A[t + 1])swap(A[t],A[t + 1]); // 將A[t]和A[t + 1]對換

A. O(n)
B. O(nlogn)
C. O(n3)
D. O(n2)

5.【參考答案】?D
【解析】?觀察程序發現，語句 “A[j]與A[j+1]對換；” 執行頻率較高，且該語句并不影響雙重 for 循環判斷語句，但會影響 if 的判斷語句。當 A 數組的所有元素都逆序時，語句 “A[j]與A[j+1]對換；” 會一直執行，此時為最壞情況。該語句在最壞情況下的頻度是O(n^2)，選 D。

6.下面算法中，語句 “x *= 2;” 的執行次數是（ ）。

int x = 1;
for (int i = 0; i < n; ++i)for (int j = i; j < n; ++j)x *= 2;

A. n(n + 1)/2
B. nlog?n
C. n2
D. n(n - 1)/2

6.【參考答案】?A
【解析】?經過觀察發現，語句 “x?=2;” 不影響雙重 for 循環的判斷條件，且內部 for 循環受外部 for 循環約束，每輪內循環執行的次數為(n?i)次，外循環共執行 n 次。因此 “x?=2;” 共執行t=n+(n?1)+(n?2)+?+(n?(n?1))=(n+1)n/2，選擇 A。

7.若下列代碼中 combine 函數的時間復雜度為 O (n)。則 combineSort 函數的時間復雜度是（ ）。

void combineSort(int i, int j) {if (i != j) {int k = (i + j) / 2;combineSort(i, k);combineSort(k + 1, j);combine(i, j, k); // 本函數的時間復雜度為O(n)}
}

A. O(n2)
B. O(n3)
C. O(n3/2)
D. O(nlog?n)

7.【參考答案】?D
【解析】?該程序代碼是歸并排序的核心代碼段。（具體歸并排序的操作可翻看本參考書相關章節的講解）假設 n 個元素進行 2 路歸并，設 s 為歸并趟數，則2^s≥n，可推導出歸并趟數s=?log2?n?。由于 n 個元素進行 2 路歸并需要進行?log2?n?趟歸并操作，每一趟都需對 n 個數據元素進行處理，因此 2 路歸并排序的時間復雜度為O(nlog2?n)。

8.下列各個選項的說法中，表述有錯誤的是（ ）。
I. 算法原地工作的含義是指不需要任何額外的輔助空間
II. 在相同規模 n 下，當 n 足夠大時，復雜度為 O (n) 的算法時間上總優于 O (2?) 的算法
III. 所謂時間復雜度是指最壞情況下估算算法執行時間的一個上界
IV. 同一個算法，實現語言的級別越高，執行效率越低
A. I
B. I,II
C. I,IV
D. III

8.【參考答案】?A
【解析】I 錯誤，算法原地工作的含義是指需要常量級別的輔助空間，而不是不需要任何額外輔助空間，這兩者有本質區別。

II 正確，時間復雜度指的是漸進時間復雜度。在 n 足夠大的情況下，根據記號 O 的定義可以得出，時間復雜度為 O (n) 的算法一定更優于 O (2?) 的算法。

III 正確，分析時間復雜度是總是考慮該算法在最壞情況下的時間復雜度，這是為了保證算法的運行時間不會比這更長，即最多需要運行多少時間。

IV 正確，該句是嚴蔚敏老師教材中的原話。一般情況下對同一個算法而言，實現語言的級別越高，其執行效率會越低。可以理解成，高級別的語言一般是由許多低級別語言 “組成實現” 的，雖然這樣使得高級別語言的 “包裝” 更為完整、使用更加簡單便捷，但一般需要付出比低級別語言更多的執行和維護花銷。

9.計算機算法指的是（1），它必須具備（2）這三個特性。
(1) A. 計算方法
B. 排序方法
C. 解決問題的步驟序列
D. 調度方法
(2) A. 可執行性、可移植性、可擴充性
B. 可執行性、確定性、有窮性
C. 確定性、有窮性、穩定性
D. 易讀性、穩定性、安全性

9.【參考答案】?(1) C (2) B
【解析】?算法：是解決具體問題的步驟方法，是一系列操作指令的有窮序列。通常每條指令中可以包含有一或多個小的操作。一般具有五大特性：有窮性、確定性、可行性、輸入和輸出。

10.下列關于數據結構的說法中錯誤的是（ ）。
A. 數據結構相同，對應的存儲結構也相同
B. 數據結構涉及數據的邏輯結構、存儲結構和施加在其上的操作
C. 數據結構操作的實現與存儲結構有關
D. 定義邏輯結構時可以不考慮存儲結構

10.【參考答案】?A
【解析】?A 錯誤，相同的數據結構也可以使用不同的存儲結構存儲。例如：線性表既可以使用順序存儲，也可以使用鏈式存儲。其它選項說法正確。對于 C 選項，一般而言，若存儲結構不同，相應的基本操作也會有區別。

11.下列說法中，不正確的是（ ）。
A. 數據元素是數據的基本單位
B. 數據項是數據元素中不可分割的最小可標識單位
C. 數據可由若干數據元素構成
D. 數據項可由若干個數據元素構成

11.【參考答案】?D
【解析】?數據元素：是數據的基本單位。在計算機中一般將數據元素作為一個整體來考慮和計算。一封信可作為一個數據元素，而信中包含的 “郵編”、“送信人” 等信息為該數據元素的數據項。即若干個數據項可組成一個數據元素。D 選項說法反了。

12.數據的四種基本存儲結構是指（ ）。
A. 順序存儲結構、索引存儲結構、直接存儲結構、倒排存儲結構
B. 順序存儲結構、索引存儲結構、鏈式存儲結構、散列存儲結構
C. 順序存儲結構、非順序存儲結構、指針存儲結構、樹型存儲結構
D. 順序存儲結構、鏈式存儲結構、樹型存儲結構、圖型存儲結構

12.【參考答案】?B
【解析】?數據的基本存儲結構有 4 種：順序存儲結構、索引存儲結構、鏈式存儲結構、散列存儲結構。具體概念可參照輔導書相關章節。考生同時需注意存儲結構和邏輯結構的區別。

13.下面關于 “算法” 的描述，錯誤的是（ ）。
A. 算法必須是正確的
B. 算法必須要能夠結束
C. 一個問題可以有多種算法解決
D. 算法的某些步驟可以有二義性

13.【參考答案】?D
【解析】?根據算法的五大特性之一的 “確定性” 可知，算法 (1) 每一條指令的操作都是確定的，理解上是沒有二義性的。(2) 對于同一套輸入和相同的執行環境，必須產生同一套的執行輸出結果。D 選項錯誤。

14.某算法的空間復雜度為 O (1)，則（ ）。
A. 該算法執行不需要任何輔助空間
B. 該算法執行所需輔助空間大小與問題規模 n 無關
C. 該算法執行不需要任何空間
D. 該算法執行所需空間大小與問題規模 n 無關

14.【參考答案】?B
【解析】?算法的空間復雜度為 O (1) 表示的是執行該算法所需的輔助空間大小相較于數據量來說是個常量，而不代表不需要任何空間或輔助空間，所以 A，C 錯誤。執行算法所需空間大小與問題規模有關（例如一般而言數據量的大小，會影響算法執行時存儲這些數據的所需空間大小），該算法的輔助空間大小與問題規模無關，D 錯誤。算法的輔助空間不隨著問題規模的變化而變化。選擇 B。

15.一個算法所需要時間由下述遞歸方程表示，試求出該算法的時間復雜度。

其中：n 是問題規模，為簡單起見，設 n 是 2 的整數冪。

16.將下列函數，按它們在 n 到無窮時的無窮大階數，從小到大排列。

17.斐波那契數列Fn?定義如下：
F0?=0,?F1?=1,?Fn?=Fn?1?+Fn?2?,?n=2,3,?
請就此斐波那契數列回答下列問題。
(1) 在遞歸計算Fn?的時候，需要對較小的Fn?1?,?Fn?2?,??,?F1?,?F0?精確計算多少次？
(2) 如果用大 O 表示法，試給出遞歸計算Fn?時遞歸函數的時間復雜度是多少。

2.6 真題演練

18.【2011】設 n 是描述問題規模的非負整數，下面程序片段的時間復雜度是（ ）。

x = 2;while (x < n/2)x = 2 * x;

A. O(log?n)
B. O(n)
C. O(nlog?n)
D. O(n2)

19.【2012】求整數 n（n≥0）階乘的算法如下，其時間復雜度是（ ）。

int fact(int n) {if (n <= 1) return 1;return n * fact(n - 1);
}

A. O(log?n)
B. O(n)
C. O(nlog?n)
D. O(n2)

20.【2014】下列程序段的時間復雜度是（ ）。

count = 0;
for (k = 1; k <= n; k *= 2)for (j = 1; j <= n; j++)count++;

A. O(log?n)
B. O(n)
C. O(nlog?n)
D. O(n2)

21.【2017】下列函數的時間復雜度是（ ）。

int func(int n) {int i = 0, sum = 0;while (sum < n) sum += ++i;return i;
}

A. O(log?n)
B. O(n1/2)
C. O(n)
D. O(nlog?n)

22.【2019】設 n 是描述問題規模的非負整數，下列程序段的時間復雜度是（ ）。

x = 0;
while (n >= (x + 1) * (x + 1))x = x + 1;

A. O(log?n)
B. O(n1/2)
C. O(n)
D. O(n2)