●第1章緒論1
1.1數據結構的基本概念1
1.1.1基本概念和術語1
1.1.2數據結構三要素2
1.1.3本節試題精選3
1.1.4答案與解析4
1.2算法和算法評價5
1.2.1算法的基本概念5
1.2.2算法效率的度量5
1.2.3本節試題精選6
1.2.4答案與解析8
歸納總結10
思維拓展11
第2章線性表12
2.1線性表的定義和基本操作12
2.1.1線性表的定義12
2.1.2線性表的基本操作13
2.1.3本節試題精選13
2.1.4答案與解析13
2.2線性表的順序表示14
2.2.1順序表的定義14
2.2.2順序表上基本操作的實現15
2.2.3本節試題精選17
2.2.4答案與解析19
2.3線性表的鏈式表示28
2.3.1單鏈表的定義28
2.3.2單鏈表上基本操作的實現28
2.3.3雙鏈表32
2.3.4循環鏈表33
2.3.5靜態鏈表34
2.3.6順序表和鏈表的比較35
2.3.7本節試題精選36
2.3.8答案與解析41
歸納總結60
思維拓展60
第3章棧和隊列61
3.1棧61
3.1.1棧的基本概念61
3.1.2棧的順序存儲結構62
3.1.3棧的鏈式存儲結構64
3.1.4本節試題精選64
3.1.5答案與解析67
3.2隊列73
3.2.1隊列的基本概念73
3.2.2隊列的順序存儲結構74
3.2.3隊列的鏈式存儲結構76
3.2.4雙端隊列77
3.2.5本節試題精選79
3.2.6答案與解析81
3.3棧和隊列的應用86
3.3.1棧在括號匹配中的應用86
3.3.2棧在表達式求值中的應用87
3.3.3棧在遞歸中的應用88
3.3.4隊列在層次遍歷中的應用89
3.3.5隊列在計算機繫統中的應用89
3.3.6本節試題精選90
3.3.7答案與解析92
3.4特殊矩陣的壓縮存儲97
3.4.1數組的定義97
3.4.2數組的存儲結構97
3.4.3矩陣的壓縮存儲98
3.4.4稀疏矩陣100
3.4.5本節試題精選100
3.4.6答案與解析101
歸納總結103
思維拓展103
第4章串104
4.1串的定義和實現104
4.1.1串的定義104
4.1.2串的存儲結構105
4.1.3串的基本操作106
4.2串的模式匹配106
4.2.1簡單的模式匹配算法106
4.2.2改進的模式匹配算法――KMP算法107
4.2.3KMP算法的進一步優化112
4.2.4本節試題精選112
4.2.5答案與解析113
歸納總結117
思維拓展118
第5章樹與二叉樹119
5.1樹的基本概念119
5.1.1樹的定義119
5.1.2基本術語120
5.1.3樹的性質121
5.1.4本節試題精選121
5.1.5答案與解析122
5.2二叉樹的概念123
5.2.1二叉樹的定義及其主要特性123
5.2.2二叉樹的存儲結構125
5.2.3本節試題精選126
5.2.4答案與解析128
5.3二叉樹的遍歷和線索二叉樹132
5.3.1二叉樹的遍歷132
5.3.2線索二叉樹136
5.3.3本節試題精選139
5.3.4答案與解析144
5.4樹、森林161
5.4.1樹的存儲結構161
5.4.2樹、森林與二叉樹的轉換163
5.4.3樹和森林的遍歷164
*5.4.4樹的應用――並查集165
5.4.5本節試題精選166
5.4.6答案與解析168
5.5樹與二叉樹的應用174
5.5.1二叉排序樹（BST）174
5.5.2平衡二叉樹177
5.5.3哈夫曼樹和哈夫曼編碼180
5.5.4本節試題精選182
5.5.5答案與解析186
歸納總結197
思維拓展198
第6章圖199
6.1圖的基本概念199
6.1.1圖的定義199
6.1.2本節試題精選202
6.1.3答案與解析204
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本節試題精選211
6.2.7答案與解析213
6.3圖的遍歷216
6.3.1廣度優先搜索216
6.3.2深度優先搜索218
6.3.3圖的遍歷與圖的連通性219
6.3.4本節試題精選220
6.3.5答案與解析222
6.4圖的應用227
6.4.1最小生成樹227
6.4.2最短路徑229
6.4.3有向無環圖描述表達式232
6.4.4拓撲排序233
6.4.5關鍵路徑234
6.4.6本節試題精選236
6.4.7答案與解析244
歸納總結256
思維拓展257
第7章查找258
7.1查找的基本概念258
7.2順序查找和折半查找259
7.2.1順序查找259
7.2.2折半查找261
7.2.3分塊查找262
7.2.4本節試題精選263
7.2.5答案與解析266
7.3B樹和B+樹271
7.3.1B樹及其基本操作271
7.3.2B+樹的基本概念274
7.3.3本節試題精選275
7.3.4答案與解析277
7.4散列表282
7.4.1散列表的基本概念282
7.4.2散列函數的構造方法282
7.4.3處理衝突的方法283
7.4.4散列查找及性能分析284
7.4.5本節試題精選285
7.4.6答案與解析288
歸納總結293
思維拓展293
第8章排序294
8.1排序的基本概念295
8.1.1排序的定義295
8.1.2本節試題精選295
8.1.3答案與解析296
8.2插入排序296
8.2.1直接插入排序296
8.2.2折半插入排序298
8.2.3希爾排序298
8.2.4本節試題精選299
8.2.5答案與解析301
8.3交換排序303
8.3.1冒泡排序303
8.3.2快速排序304
8.3.3本節試題精選306
8.3.4答案與解析308
8.4選擇排序314
8.4.1簡單選擇排序314
8.4.2堆排序315
8.4.3本節試題精選317
8.4.4答案與解析319
8.5歸並排序和基數排序323
8.5.1歸並排序323
8.5.2基數排序324
8.5.3本節試題精選326
8.5.4答案與解析327
8.6各種內部排序算法的比較及應用329
8.6.1內部排序算法的比較329
8.6.2內部排序算法的應用330
8.6.3本節試題精選331
8.6.4答案與解析332
8.7外部排序336
8.7.1外部排序的基本概念336
8.7.2外部排序的方法336
8.7.3多路平衡歸並與敗者樹337
8.7.4置換-選擇排序（生成初始歸並段）338
8.7.5很好歸並樹339
8.7.6本節試題精選340
8.7.7答案與解析341
歸納總結344
思維拓展345
參考文獻346

本書是計算機專業研究生入學考試“數據結構"課程的復習用書，內容包括緒論、線性表、棧和隊列、串、樹與二叉樹、圖、查找、非序等。全書嚴格按照近期新計算機考研大綱的數據結構部分，對大綱所涉及的知識點進行集中梳理，力求內容精煉，重點突出。深入淺出。本書精選各名校的歷年考研真題，並給出詳細的解題思路。力求實現講練結合、靈活掌握、舉反三的功效。通過“書本+在線”的學習方式和網上答疑方式，讀者在使用本書時遇到的任何疑難點，都可以在王道論壇發帖與道友互動。
本書可作為考生參加計算機專業研究生入學考試的復習用書。也可作為計算機專業學生學習數據結構課程的輔導用書。