目 錄
序
前言
第1章 緒論1
本章概略1
1.1 針對考研數據結構的代碼書寫規(guī)范以及C與C 語言基礎1
1.1.1 考研綜合應用題中算法設計部分的代碼書寫規(guī)范1
1.1.2 考研中的C與C 語言基礎3
1.2 算法的時間復雜度與空間復雜度分析基礎12
1.2.1 考研中的算法時間復雜度分析12
1.2.2 例題選講12
1.2.3 考研中的算法空間復雜度分析14
1.3 數據結構和算法的基本概念14
1.3.1 數據結構的基本概念14
1.3.2 算法的基本概念15
習題16
習題答案17
第2章 線性表20
大綱要求20
考點與要點分析20
核心考點20
基礎要點20
知識點講解20
2.1 線性表的基本概念與實現20
2.2 線性表的結構體定義和基本操作24
2.2.1 線性表的結構體定義24
2.2.2 順序表的操作26
2.2.3 單鏈表的操作28
2.2.4 雙鏈表的操作33
2.2.5 循環(huán)鏈表的操作35
2.2.6 逆置問題（408科目重要考點）35
▲真題仿造36
真題仿造答案與解析37
習題 真題精選38
習題答案 真題精選答案42
第3章 棧和隊列60
大綱要求60
考點與要點分析60
核心考點60
基礎要點60
知識點講解60
3.1 棧和隊列的基本概念60
3.1.1 棧的基本概念60
3.1.2 隊列的基本概念61
3.2 棧和隊列的存儲結構、算法與應用61
3.2.1 本章所涉及的結構體定義61
3.2.2 順序棧62
3.2.3 鏈棧64
3.2.4 棧的應用65
3.2.5 順序隊69
3.2.6 鏈隊71
3.2.7 共享棧和雙端隊列72
3.2.8 隊列的配置問題74
3.3 抽象數據類型75
▲真題仿造77
真題仿造答案與解析77
習題 真題精選80
習題答案 真題精選答案85
第4章 串98
知識點講解98
4.1 串數據類型的定義98
4.1.1 串的定義98
4.1.2 串的存儲結構98
4.1.3 串的基本操作99
4.2 串的模式匹配算法102
4.2.1 簡單模式匹配算法102
4.2.2 KMP算法103
4.2.3 KMP算法的改進107
習題109
習題答案110
第5章 數組、矩陣與廣義表120
知識點講解120
5.1 數組120
5.2 矩陣的壓縮存儲121
5.2.1 矩陣121
5.2.2 特殊矩陣和稀疏矩陣122
5.3 廣義表128
習題129
習題答案130
第6章 樹與二叉樹139
大綱要求139
考點與要點分析139
核心考點139
基礎要點139
知識點講解139
6.1 樹的基本概念139
6.1.1 樹的定義139
6.1.2 樹的基本術語140
6.1.3 樹的存儲結構140
6.2 二叉樹141
6.2.1 二叉樹的定義141
6.2.2 二叉樹的主要性質142
6.2.3 二叉樹的存儲結構144
6.2.4 二叉樹的遍歷算法145
6.2.5 二叉樹遍歷算法的改進153
6.3 樹和森林與二叉樹的互相轉換162
6.3.1 樹轉換為二叉樹162
6.3.2 二叉樹轉換為樹163
6.3.3 森林轉換為二叉樹164
6.3.4 二叉樹轉換為森林164
6.3.5 樹和森林的遍歷164
6.4 樹與二叉樹的應用166
6.4.1 二叉排序樹與平衡二叉樹166
6.4.2 赫夫曼樹和赫夫曼編碼166
6.4.3 并查集及其應用（2022統(tǒng)考大綱新增內容）169
▲真題仿造169
真題仿造答案與解析169
習題 真題精選170
習題答案 真題精選答案176
第7章 圖191
大綱要求191
考點與要點分析191
核心考點191
基礎要點191
知識點講解191
7.1 圖的基本概念191
7.2 圖的存儲結構192
7.2.1 鄰接矩陣193
7.2.2 鄰接表194
7.2.3 鄰接多重表195
7.3 圖的遍歷算法操作196
7.3.1 深度優(yōu)先搜索遍歷196
7.3.2 廣度優(yōu)先搜索遍歷197
7.3.3 例題選講198
7.4 最�。ù鷥r）生成樹201
7.4.1 普里姆算法和克魯斯卡爾算法（含2022統(tǒng)考大綱新增內容并查集的講解）201
7.4.2 例題選講205
7.5 最短路徑206
7.5.1 迪杰斯特拉算法206
7.5.2 弗洛伊德算法212
7.6 拓撲排序215
7.6.1 AOV網215
7.6.2 拓撲排序核心算法215
7.6.3 例題選講217
7.7 關鍵路徑218
7.7.1 AOE網218
7.7.2 關鍵路徑核心算法218
▲真題仿造221
真題仿造答案與解析221
習題 真題精選223
習題答案 真題精選答案229
第8章 排序243
大綱要求243
考點與要點分析243
核心考點243
基礎要點243
知識點講解244
8.1 排序的基本概念244
8.1.1 排序244
8.1.2 穩(wěn)定性244
8.1.3 排序算法的分類244
8.2 插入類排序245
8.2.1 直接插入排序245
8.2.2 折半插入排序246
8.2.3 希爾排序247
8.3 交換類排序249
8.3.1 起泡排序249
8.3.2 快速排序250
8.4 選擇類排序252
8.4.1 簡單選擇排序252
8.4.2 堆排序253
8.5 二路歸并排序256
8.6 基數排序257
8.7 外部排序261
8.7.1 概念與流程261
8.7.2 置換-選擇排序262
8.7.3 最佳歸并樹263
8.7.4 敗者樹263
8.7.5 時間與空間復雜度相關問題266
8.8 排序知識點小結266
▲真題仿造267
真題仿造答案與解析268
習題 真題精選269
習題答案 真題精選答案274
第9章 查找285
大綱要求285
考點與要點分析285
核心考點285
基礎要點285
知識點講解285
9.1 查找的基本概念、順序查找法、折半查找法285
9.1.1 查找的基本概念285
9.1.2 順序查找法286
9.1.3 折半查找法287
9.1.4 分塊查找289
9.2 樹形查找 290
9.2.1 二叉排序樹290
9.2.2 平衡二叉樹293
9.2.3 紅黑樹296
9.3 B-樹的基本概念及基本操作、B 樹的基本概念304
9.3.1 B-樹（B樹）的基本概念304
9.3.2 B-樹的基本操作305
9.3.3 B 樹的基本概念309
9.4 散列表310
9.4.1 散列表的概念310
9.4.2 散列表的建立方法以及沖突解決方法310
9.4.3 散列表的性能分析314
▲真題仿造315
真題仿造答案與解析315
習題 真題精選316
習題答案 真題精選答案321
第10章 考研中某些算法的分治法解釋335
參考文獻338