目 錄
序
前言
第1章 緒論1
本章概略1
1.1 針對(duì)考研數(shù)據(jù)結(jié)構(gòu)的代碼書寫規(guī)范以及C與C 語(yǔ)言基礎(chǔ)1
1.1.1 考研綜合應(yīng)用題中算法設(shè)計(jì)部分的代碼書寫規(guī)范1
1.1.2 考研中的C與C 語(yǔ)言基礎(chǔ)3
1.2 算法的時(shí)間復(fù)雜度與空間復(fù)雜度分析基礎(chǔ)12
1.2.1 考研中的算法時(shí)間復(fù)雜度分析12
1.2.2 例題選講12
1.2.3 考研中的算法空間復(fù)雜度分析14
1.3 數(shù)據(jù)結(jié)構(gòu)和算法的基本概念14
1.3.1 數(shù)據(jù)結(jié)構(gòu)的基本概念14
1.3.2 算法的基本概念15
習(xí)題16
習(xí)題答案17
第2章 線性表20
大綱要求20
考點(diǎn)與要點(diǎn)分析20
核心考點(diǎn)20
基礎(chǔ)要點(diǎn)20
知識(shí)點(diǎn)講解20
2.1 線性表的基本概念與實(shí)現(xiàn)20
2.2 線性表的結(jié)構(gòu)體定義和基本操作24
2.2.1 線性表的結(jié)構(gòu)體定義24
2.2.2 順序表的操作26
2.2.3 單鏈表的操作28
2.2.4 雙鏈表的操作33
2.2.5 循環(huán)鏈表的操作35
2.2.6 逆置問(wèn)題（408科目重要考點(diǎn)）35
▲真題仿造36
真題仿造答案與解析37
習(xí)題 真題精選38
習(xí)題答案 真題精選答案42
第3章 棧和隊(duì)列60
大綱要求60
考點(diǎn)與要點(diǎn)分析60
核心考點(diǎn)60
基礎(chǔ)要點(diǎn)60
知識(shí)點(diǎn)講解60
3.1 棧和隊(duì)列的基本概念60
3.1.1 棧的基本概念60
3.1.2 隊(duì)列的基本概念61
3.2 棧和隊(duì)列的存儲(chǔ)結(jié)構(gòu)、算法與應(yīng)用61
3.2.1 本章所涉及的結(jié)構(gòu)體定義61
3.2.2 順序棧62
3.2.3 鏈棧64
3.2.4 棧的應(yīng)用65
3.2.5 順序隊(duì)69
3.2.6 鏈隊(duì)71
3.2.7 共享?xiàng)：碗p端隊(duì)列72
3.2.8 隊(duì)列的配置問(wèn)題74
3.3 抽象數(shù)據(jù)類型75
▲真題仿造77
真題仿造答案與解析77
習(xí)題 真題精選80
習(xí)題答案 真題精選答案85
第4章 串98
知識(shí)點(diǎn)講解98
4.1 串?dāng)?shù)據(jù)類型的定義98
4.1.1 串的定義98
4.1.2 串的存儲(chǔ)結(jié)構(gòu)98
4.1.3 串的基本操作99
4.2 串的模式匹配算法102
4.2.1 簡(jiǎn)單模式匹配算法102
4.2.2 KMP算法103
4.2.3 KMP算法的改進(jìn)107
習(xí)題109
習(xí)題答案110
第5章 數(shù)組、矩陣與廣義表120
知識(shí)點(diǎn)講解120
5.1 數(shù)組120
5.2 矩陣的壓縮存儲(chǔ)121
5.2.1 矩陣121
5.2.2 特殊矩陣和稀疏矩陣122
5.3 廣義表128
習(xí)題129
習(xí)題答案130
第6章 樹與二叉樹139
大綱要求139
考點(diǎn)與要點(diǎn)分析139
核心考點(diǎn)139
基礎(chǔ)要點(diǎn)139
知識(shí)點(diǎn)講解139
6.1 樹的基本概念139
6.1.1 樹的定義139
6.1.2 樹的基本術(shù)語(yǔ)140
6.1.3 樹的存儲(chǔ)結(jié)構(gòu)140
6.2 二叉樹141
6.2.1 二叉樹的定義141
6.2.2 二叉樹的主要性質(zhì)142
6.2.3 二叉樹的存儲(chǔ)結(jié)構(gòu)144
6.2.4 二叉樹的遍歷算法145
6.2.5 二叉樹遍歷算法的改進(jìn)153
6.3 樹和森林與二叉樹的互相轉(zhuǎn)換162
6.3.1 樹轉(zhuǎn)換為二叉樹162
6.3.2 二叉樹轉(zhuǎn)換為樹163
6.3.3 森林轉(zhuǎn)換為二叉樹164
6.3.4 二叉樹轉(zhuǎn)換為森林164
6.3.5 樹和森林的遍歷164
6.4 樹與二叉樹的應(yīng)用166
6.4.1 二叉排序樹與平衡二叉樹166
6.4.2 赫夫曼樹和赫夫曼編碼166
6.4.3 并查集及其應(yīng)用（2022統(tǒng)考大綱新增內(nèi)容）169
▲真題仿造169
真題仿造答案與解析169
習(xí)題 真題精選170
習(xí)題答案 真題精選答案176
第7章 圖191
大綱要求191
考點(diǎn)與要點(diǎn)分析191
核心考點(diǎn)191
基礎(chǔ)要點(diǎn)191
知識(shí)點(diǎn)講解191
7.1 圖的基本概念191
7.2 圖的存儲(chǔ)結(jié)構(gòu)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 最小（代價(jià)）生成樹201
7.4.1 普里姆算法和克魯斯卡爾算法（含2022統(tǒng)考大綱新增內(nèi)容并查集的講解）201
7.4.2 例題選講205
7.5 最短路徑206
7.5.1 迪杰斯特拉算法206
7.5.2 弗洛伊德算法212
7.6 拓?fù)渑判?15
7.6.1 AOV網(wǎng)215
7.6.2 拓?fù)渑判蚝诵乃惴?15
7.6.3 例題選講217
7.7 關(guān)鍵路徑218
7.7.1 AOE網(wǎng)218
7.7.2 關(guān)鍵路徑核心算法218
▲真題仿造221
真題仿造答案與解析221
習(xí)題 真題精選223
習(xí)題答案 真題精選答案229
第8章 排序243
大綱要求243
考點(diǎn)與要點(diǎn)分析243
核心考點(diǎn)243
基礎(chǔ)要點(diǎn)243
知識(shí)點(diǎn)講解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 簡(jiǎn)單選擇排序252
8.4.2 堆排序253
8.5 二路歸并排序256
8.6 基數(shù)排序257
8.7 外部排序261
8.7.1 概念與流程261
8.7.2 置換-選擇排序262
8.7.3 最佳歸并樹263
8.7.4 敗者樹263
8.7.5 時(shí)間與空間復(fù)雜度相關(guān)問(wèn)題266
8.8 排序知識(shí)點(diǎn)小結(jié)266
▲真題仿造267
真題仿造答案與解析268
習(xí)題 真題精選269
習(xí)題答案 真題精選答案274
第9章 查找285
大綱要求285
考點(diǎn)與要點(diǎn)分析285
核心考點(diǎn)285
基礎(chǔ)要點(diǎn)285
知識(shí)點(diǎn)講解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
習(xí)題 真題精選316
習(xí)題答案 真題精選答案321
第10章 考研中某些算法的分治法解釋335
參考文獻(xiàn)338