本書是計算機專業(yè)碩士研究生入學考試"數(shù)據(jù)結構課程的復習用書，內容包括緒論，線性表，棧、隊列和數(shù)組，串，樹與二叉樹，圖、查找，排序等。全書嚴格按照最新計算機考研大綱的數(shù)據(jù)結構部分的要求，對大綱所涉及的知識點進行集中梳理，力求內容精煉、重點突出、深入淺出。本書精選部分名校的歷年考研真題，并給出詳細的解題思路，力求實現(xiàn)講練結合、靈活掌握、舉一反三的功效。本書可作為考生參加計算機專業(yè)碩士研究生入學考試的復習用書，也可作為計算機專業(yè)學生學習數(shù)據(jù)結構課程的輔導用書。
王道考研系列的定位是考試類輔導書。本書主要分為考點講解部分和習題講解部分，前者的篇幅約占35%，后者的篇幅約占65%�？键c講解部分按照統(tǒng)考大綱梳理考點，主要參考了一些權威教材，如嚴蔚敏老師的《數(shù)據(jù)結構》、李春葆老師的《數(shù)據(jù)結構教程》等，并且融合了作者的總結與理解，在此對這些老師表示致敬和感謝！習題講解部分主要精選自多所名校的自命題考研真題、教材配套習題冊、同類輔導書，或者改編自統(tǒng)考真題。
由于篇幅限制，考點講解部分較為精煉，對學科基礎較為薄弱的讀者來說，可能難以理解。為此，我們提供了配套的考點精講視頻和習題講解視頻�？键c精講視頻有形象豐富的動畫演示、由淺入深的考點分析，相信能打通讀者復習過程中的任督二脈。往年有不少讀者反饋視頻和王道書不太匹配，這是因為王道書的出版時間遠早于課程制作時間，而咸魚老師錄制課程時會參考眾多的優(yōu)秀教材（不限于王道書）；后面，我們將逐步解決這個問題。此外，之前的習題講解視頻主要由高分學長錄制，質量參差不齊，今年將改由王道全職老師全盤更新，且只提供更新后的習題講解視頻，但更新速度可能趕不上讀者的復習速度，還請諒解。
考點精講視頻和習題講解視頻免費發(fā)布在B站賬號王道計算機教育上。
王道考研系列是計算機考研學子口碑相傳的輔導書，自2011版首次推出以來，就始終占據(jù)同類書銷量的榜首位置，這就是口碑的力量。有這么多學長的成功經(jīng)驗，相信讀者只要合理地利用本套書，并采用科學的復習方法，就一定能收獲屬于自己的那份回報。
針對考研學子的需求，我們還開發(fā)了除本書配套視頻外的一系列計算機考研課程，包括C語言督學課、408基礎課、408暑期強化課、408沖刺串講課、機試課、復習規(guī)劃、伴學督學、一對一指導、全程實時答疑和擇校服務等。王道的課程同樣是市面上領先的計算機考研課程，對學科基礎較為薄弱的讀者來說，相信這些課程和服務定能助你一臂之力。
不包就業(yè)、不包推薦，培養(yǎng)有態(tài)度的碼農。王道訓練營是王道團隊打造的線下魔鬼式編程訓練營。打下編程功底、增強項目經(jīng)驗，徹底轉行入行，不再迷茫，期待有夢想的你！
參與本書編寫的人員主要有趙霖、羅樂、徐秀瑛、趙淑芬、趙淑芳、羅慶學、趙曉宇、喻云珍、余勇、劉政學等。予人玫瑰，手有余香，王道論壇伴你一路同行！
對本書的任何建議，或發(fā)現(xiàn)有錯誤，歡迎掃碼與我們聯(lián)系，以便及時優(yōu)化或糾錯。
風華漫舞
第1章 緒論 1
1.1 數(shù)據(jù)結構的基本概念 1
1.1.1 基本概念和術語 1
1.1.2 數(shù)據(jù)結構三要素 2
1.1.3 本節(jié)試題精選 3
1.1.4 答案與解析 4
1.2 算法和算法評價 4
1.2.1 算法的基本概念 4
1.2.2 算法效率的度量 5
1.2.3 本節(jié)試題精選 6
1.2.4 答案與解析 8
歸納總結 11
思維拓展 11
第2章 線性表 12
2.1 線性表的定義和基本操作 12
2.1.1 線性表的定義 12
2.1.2 線性表的基本操作 13
2.1.3 本節(jié)試題精選 13
2.1.4 答案與解析 14
2.2 線性表的順序表示 14
2.2.1 順序表的定義 14
2.2.2 順序表上基本操作的實現(xiàn) 15
2.2.3 本節(jié)試題精選 17
2.2.4 答案與解析 20
2.3 線性表的鏈式表示 29
2.3.1 單鏈表的定義 29
2.3.2 單鏈表上基本操作的實現(xiàn) 30
2.3.3 雙鏈表 35
2.3.4 循環(huán)鏈表 36
2.3.5 靜態(tài)鏈表 37
2.3.6 順序表和鏈表的比較 37
2.3.7 本節(jié)試題精選 38
2.3.8 答案與解析 44
歸納總結 61
思維拓展 61
第3章 棧、隊列和數(shù)組 62
3.1 棧 62
3.1.1 棧的基本概念 62
3.1.2 棧的順序存儲結構 63
3.1.3 棧的鏈式存儲結構 65
3.1.4 本節(jié)試題精選 66
3.1.5 答案與解析 69
3.2 隊列 75
3.2.1 隊列的基本概念 75
3.2.2 隊列的順序存儲結構 76
3.2.3 隊列的鏈式存儲結構 78
3.2.4 雙端隊列 80
3.2.5 本節(jié)試題精選 81
3.2.6 答案與解析 84
3.3 棧和隊列的應用 89
3.3.1 棧在括號匹配中的應用 89
3.3.2 棧在表達式求值中的應用 90
3.3.3 棧在遞歸中的應用 92
3.3.4 隊列在層次遍歷中的應用 93
3.3.5 隊列在計算機系統(tǒng)中的應用 94
3.3.6 本節(jié)試題精選 94
3.3.7 答案與解析 96
3.4 數(shù)組和特殊矩陣 100
3.4.1 數(shù)組的定義 100
3.4.2 數(shù)組的存儲結構 100
3.4.3 特殊矩陣的壓縮存儲 101
3.4.4 稀疏矩陣 104
3.4.5 本節(jié)試題精選 104
3.4.6 答案與解析 106
歸納總結 108
思維拓展 108
第4章 串 109
*4.1 串的定義和實現(xiàn) 109
4.1.1 串的定義 109
4.1.2 串的基本操作 110
4.1.3 串的存儲結構 110
4.2 串的模式匹配 111
4.2.1 簡單的模式匹配算法 111
4.2.2 串的模式匹配算法KMP算法 112
4.2.3 KMP算法的進一步優(yōu)化 117
4.2.4 本節(jié)試題精選 118
4.2.5 答案與解析 119
歸納總結 123
思維拓展 123
第5章 樹與二叉樹 124
5.1 樹的基本概念 124
5.1.1 樹的定義 124
5.1.2 基本術語 125
5.1.3 樹的性質 126
5.1.4 本節(jié)試題精選 126
5.1.5 答案與解析 127
5.2 二叉樹的概念 130
5.2.1 二叉樹的定義及其主要特性 130
5.2.2 二叉樹的存儲結構 132
5.2.3 本節(jié)試題精選 133
5.2.4 答案與解析 136
5.3 二叉樹的遍歷和線索二叉樹 140
5.3.1 二叉樹的遍歷 140
5.3.2 線索二叉樹 145
5.3.3 本節(jié)試題精選 148
5.3.4 答案與解析 154
5.4 樹、森林 171
5.4.1 樹的存儲結構 171
5.4.2 樹、森林與二叉樹的轉換 172
5.4.3 樹和森林的遍歷 174
5.4.4 本節(jié)試題精選 175
5.4.5 答案與解析 177
5.5 樹與二叉樹的應用 183
5.5.1 哈夫曼樹和哈夫曼編碼 183
5.5.2 并查集 186
5.5.3 本節(jié)試題精選 188
5.5.4 答案與解析 190
歸納總結 196
思維拓展 196
第6章 圖 198
6.1 圖的基本概念 198
6.1.1 圖的定義 198
6.1.2 本節(jié)試題精選 201
6.1.3 答案與解析 203
6.2 圖的存儲及基本操作 206
6.2.1 鄰接矩陣法 206
6.2.2 鄰接表法 207
6.2.3 十字鏈表 209
6.2.4 鄰接多重表 209
6.2.5 圖的基本操作 210
6.2.6 本節(jié)試題精選 211
6.2.7 答案與解析 214
6.3 圖的遍歷 219
6.3.1 廣度優(yōu)先搜索 219
6.3.2 深度優(yōu)先搜索 222
6.3.3 圖的遍歷與圖的連通性 223
6.3.4 本節(jié)試題精選 223
6.3.5 答案與解析 226
6.4 圖的應用 231
6.4.1 最小生成樹 231
6.4.2 最短路徑 234
6.4.3 有向無環(huán)圖描述表達式 237
6.4.4 拓撲排序 238
6.4.5 關鍵路徑 240
6.4.6 本節(jié)試題精選 242
6.4.7 答案與解析 252
歸納總結 267
思維拓展 268
第7章 查找 269
7.1 查找的基本概念 269
7.2 順序查找和折半查找 270
7.2.1 順序查找 270
7.2.2 折半查找 272
7.2.3 分塊查找 273
7.2.4 本節(jié)試題精選 274
7.2.5 答案與解析 277
7.3 樹形查找 283
7.3.1 二叉排序樹（BST） 283
7.3.2 平衡二叉樹 287
7.3.3 紅黑樹 291
7.3.4 本節(jié)試題精選 296
7.3.5 答案與解析 300
7.4 B樹和B 樹 310
7.4.1 B樹及其基本操作 311
7.4.2 B 樹的基本概念 314
7.4.3 本節(jié)試題精選 315
7.4.4 答案與解析 317
7.5 散列（Hash）表 323
7.5.1 散列表的基本概念 323
7.5.2 散列函數(shù)的構造方法 324
7.5.3 處理沖突的方法 324
7.5.4 散列查找及性能分析的應用 326
7.5.5 本節(jié)試題精選 327
7.5.6 答案與解析 330
歸納總結 336
思維拓展 336
第8章 排序 337
8.1 排序的基本概念 338
8.1.1 排序的定義 338
8.1.2 本節(jié)試題精選 338
8.1.3 答案與解析 339
8.2 插入排序 339
8.2.1 直接插入排序 339
8.2.2 折半插入排序 340
8.2.3 希爾排序 341
8.2.4 本節(jié)試題精選 342
8.2.5 答案與解析 344
8.3 交換排序 346
8.3.1 冒泡排序 347
8.3.2 快速排序 348
8.3.3 本節(jié)試題精選 350
8.3.4 答案與解析 353
8.4 選擇排序 357
8.4.1 簡單選擇排序 358
8.4.2 堆排序 358
8.4.3 本節(jié)試題精選 361
8.4.4 答案與解析 364
8.5 歸并排序、基數(shù)排序和計數(shù)排序 370
8.5.1 歸并排序 370
8.5.2 基數(shù)排序 371
*8.5.3 計數(shù)排序 373
8.5.4 本節(jié)試題精選 375
8.5.5 答案與解析 377
8.6 各種內部排序算法的比較及應用 380
8.6.1 內部排序算法的比較 380
8.6.2 內部排序算法的應用 381
8.6.3 本節(jié)試題精選 382
8.6.4 答案與解析 384
8.7 外部排序 387
8.7.1 外部排序的基本概念 387
8.7.2 外部排序的方法 387
8.7.3 多路平衡歸并與敗者樹 388
8.7.4 置換-選擇排序（生成初始歸并段） 389
8.7.5 最佳歸并樹 390
8.7.6 本節(jié)試題精選 392
8.7.7 答案與解析 394
歸納總結 398
思維拓展 399
參考文獻 400
書單推薦
