數據結構高分筆記（2023版天勤第11版）

本書針對近幾年全國電腦學科專業綜合考試大綱的“資料結構”部分進行了深入解讀，以一種獨創的方式對考試大綱中的知識點進行了講解，即從考生的視角剖析知識難點；以通俗易懂的語言取代晦澀難懂的專業術語；以成功考生的親身經歷指引複習方向；以風趣幽默的筆觸緩解考研壓力。
 
讀者對書中的知識點講解有任何疑問都可與作者進行線上互動，為考生解決複習中的疑難點，提高考生的複習效率。根據電腦專業研究生入學考試形勢的變化（逐漸實行非統考），書中對大量非統考知識點進行了講解，使本書所包含的知識點除覆蓋統考大綱的所有內容外，還包括了各自主命題高校所要求的知識點。

第1章緒論1
本章概略1
1.1針對考研資料結構的代碼書寫規範以及C與C++語言基礎1
1.1.1考研綜合應用題中演算法設計部分的代碼書寫規範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章線性表19
大綱要求19
考點與要點分析19
核心考點19
基礎要點19
知識點講解19
2.1線性表的基本概念與實現19
2.2線性表的結構體定義和基本操作23
2.2.1線性表的結構體定義23
2.2.2順序表的操作25
2.2.3單鏈表的操作27
2.2.4雙鏈表的操作32
2.2.5迴圈鏈表的操作34
2.2.6逆置問題（408科目重要考點）34
▲真題仿造35
真題仿造答案與解析36
習題+真題精選37
習題答案+真題精選答案42
 
第3章棧和佇列58
大綱要求58
考點與要點分析58
核心考點58
基礎要點58
知識點講解58
3.1棧和佇列的基本概念58
3.1.1棧的基本概念58
3.1.2佇列的基本概念59
3.2棧和佇列的存儲結構、演算法與應用59
3.2.1本章所涉及的結構體定義59
3.2.2順序棧60
3.2.3鏈棧62
3.2.4棧的應用63
3.2.5順序隊67
3.2.6鏈隊69
3.2.7共用棧和雙端佇列71
3.2.8佇列的配置問題72
3.3抽象資料類型73
▲真題仿造75
真題仿造答案與解析75
習題+真題精選78
習題答案+真題精選答案83


第4章串95知識點講解95
4.1串資料類型的定義95
4.1.串的定義95
4.1.2串的存儲結構95
4.1.3串的基本操作96
4.2串的模式匹配演算法99
4.2.1簡單模式匹配演算法99
4.2.2KMP演算法100
4.2.3KMP演算法的改進104
習題106
習題答案107

第5章陣列、矩陣與廣義表117
知識點講解117
5.1陣列117
5.2矩陣的壓縮存儲118
5.2.1矩陣118
5.2.2特殊矩陣和疏鬆陣列119
5.3廣義表125
習題126
習題答案127
 
第6章樹與二叉樹136
大綱要求136
考點與要點分析136
核心考點136
基礎要點136
知識點講解136
6.1樹的基本概念136
6.1.1樹的定義136
6.1.2樹的基本術語136
6.1.3樹的存儲結構137
6.2二叉樹138
6.2.1二叉樹的定義138
6.2.2二叉樹的主要性質139
6.2.3二叉樹的存儲結構141
6.2.4二叉樹的遍歷演算法141
6.2.5二叉樹遍歷演算法的改進150
6.3樹和森林與二叉樹的互相轉換159
6.3.1樹轉換為二叉樹159
6.3.2二叉樹轉換為樹160
6.3.3森林轉換為二叉樹160
6.3.4二叉樹轉換為森林161
6.3.5樹和森林的遍歷161
6.4樹與二叉樹的應用162
6.4.1二叉排序樹與平衡二叉樹162
6.4.2赫夫曼樹和赫夫曼編碼163

6.4.3並查集及其應用（2022統考大綱新增內容）166
▲真題仿造166
真題仿造答案與解析166
習題+真題精選167
習題答案+真題精選答案172
 
第7章圖187
大綱要求187
考點與要點分析187
核心考點187
基礎要點187
知識點講解187
7.1圖的基本概念187
7.2圖的存儲結構188
7.2.1鄰接矩陣189
7.2.2鄰接表190
7.2.3鄰接多重表191
7.3圖的遍歷演算法操作192
7.3.1深度優先搜索遍歷192
7.3.2廣度優先搜索遍歷193
7.3.3例題選講194
7.4小（代價）生成樹197
7.4.1普裡姆演算法和克魯斯卡爾演算法（含2022統考大綱新增內容並查集的講解）197
7.4.2例題選講201
7.5短路徑202
7.5.1迪傑斯特拉演算法202
7.5.2佛洛德演算法208
7.6拓撲排序211
7.6.1AOV網211
7.6.2拓撲排序核心演算法211
7.6.3例題選講213
7.7關鍵路徑214
7.7.1AOE網214
7.7.2關鍵路徑核心演算法214
▲真題仿造217
真題仿造答案與解析217
習題+真題精選219
習題答案+真題精選答案225
 
第8章排序238大綱要求238考點與要點分析238
核心考點238基礎要點238知識點講解239
8.1排序的基本概念239
8.1.1排序239
8.1.2穩定性239
8.1.3排序演算法的分類239
8.2插入類排序240
8.2.1直接插入排序240
8.2.2折半插入排序241
8.2.3希爾排序242
8.3交換類排序244
8.3.1起泡排序244
8.3.2快速排序245
8.4選擇類排序247
8.4.1簡單選擇排序247
8.4.2堆排序248
8.5二路歸併排序251
8.6基數排序252
8.7外部排序256
8.7.1概念與流程256
8.7.2置換-選擇排序257
8.7.3歸併樹258
8.7.4敗者樹259
8.7.5時間與空間複雜度相關問題261
8.8排序知識點小結262
▲真題仿造263
真題仿造答案與解析263
習題+真題精選264
習題答案+真題精選答案269
 
第9章查找279
大綱要求279
考點與要點分析279
核心考點279基礎要點279
知識點講解279
9.1查找的基本概念、順序查找法、折半查找法279
9.1.1查找的基本概念279
9.1.2順序查找法280
9.1.3折半查找法281
9.1.4分塊查找283
9.2樹型查找284
9.2.1二叉排序樹284
9.2.2平衡二叉樹287
9.2.3紅黑樹290
9.3B-樹的基本概念及其基本操作、B+樹的基本概念298
9.3.1B-樹（B樹）的基本概念298
9.3.2B-樹的基本操作299
9.3.3B+樹的基本概念304
9.4散列表305
9.4.1散列表的概念305
9.4.2散列表的建立方法以及衝突解決方法305
9.4.3散清單的性能分析309
▲真題仿造310
真題仿造答案與解析310
習題+真題精選311
習題答案+真題精選答案316

第10章考研中某些演算法的分治法解釋329
參考文獻332