●第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單鏈表的定義29
2．3．2單鏈表上基本操作的實現29
2．3．3雙鏈表33
2．3．4循環鏈表34
2．3．5靜態鏈表35
2．3．6順序表和鏈表的比較36
2．3．7本節試題精選37
2．3．8答案與解析42
歸納總結63
思維拓展63
第3章棧、隊列和數組64
3．1棧64
3．1．1棧的基本概念64
3．1．2棧的順序存儲結構65
3．1．3棧的鏈式存儲結構67
3．1．4本節試題精選67
3．1．5答案與解析70
3．2隊列77
3．2．1隊列的基本概念77
3．2．2隊列的順序存儲結構78
3．2．3隊列的鏈式存儲結構80
3．2．4雙端隊列81
3．2．5本節試題精選83
3．2．6答案與解析86
3．3棧和隊列的應用91
3．3．1棧在括號匹配中的應用91
3．3．2棧在表達式求值中的應用92
3．3．3棧在遞歸中的應用93
3．3．4隊列在層次遍歷中的應用94
3．3．5隊列在計算機繫統中的應用94
3．3．6本節試題精選95
3．3．7答案與解析96
3．4數組和特殊矩陣102
3．4．1數組的定義102
3．4．2數組的存儲結構103
3．4．3特殊矩陣的壓縮存儲103
3．4．4稀疏矩陣105
3．4．5本節試題精選106
3．4．6答案與解析107
歸納總結108
思維拓展109
第4章串110
*4．1串的定義和實現110
4．1．1串的定義110
4．1．2串的存儲結構111
4．1．3串的基本操作112
4．2串的模式匹配112
4．2．1簡單的模式匹配算法112
4．2．2串的模式匹配算法――KMP算法113
4．2．3KMP算法的進一步優化118
4．2．4本節試題精選118
4．2．5答案與解析119
歸納總結123
思維拓展124
第5章樹與二叉樹125
5．1樹的基本概念125
5．1．1樹的定義125
5．1．2基本術語126
5．1．3樹的性質127
5．1．4本節試題精選127
5．1．5答案與解析128
5．2二叉樹的概念129
5．2．1二叉樹的定義及其主要特性129
5．2．2二叉樹的存儲結構131
5．2．3本節試題精選132
5．2．4答案與解析134
5．3二叉樹的遍歷和線索二叉樹139
5．3．1二叉樹的遍歷139
5．3．2線索二叉樹143
5．3．3本節試題精選146
5．3．4答案與解析151
5．4樹、森林169
5．4．1樹的存儲結構169
5．4．2樹、森林與二叉樹的轉換171
5．4．3樹和森林的遍歷172
5．4．4本節試題精選173
5．4．5答案與解析175
5．5樹與二叉樹的應用181
5．5．1哈夫曼樹和哈夫曼編碼181
5．5．2並查集183
5．5．3本節試題精選184
5．5．4答案與解析186
歸納總結190
思維拓展191
第6章圖192
6．1圖的基本概念192
6．1．1圖的定義192
6．1．2本節試題精選195
6．1．3答案與解析197
6．2圖的存儲及基本操作199
6．2．1鄰接矩陣法199
6．2．2鄰接表法201
6．2．3十字鏈表202
6．2．4鄰接多重表203
6．2．5圖的基本操作203
6．2．6本節試題精選204
6．2．7答案與解析207
6．3圖的遍歷211
6．3．1廣度優先搜索211
6．3．2深度優先搜索213
6．3．3圖的遍歷與圖的連通性214
6．3．4本節試題精選214
6．3．5答案與解析217
6．4圖的應用222
6．4．1最小生成樹222
6．4．2最短路徑225
6．4．3有向無環圖描述表達式228
6．4．4拓撲排序228
6．4．5關鍵路徑230
6．4．6本節試題精選232
6．4．7答案與解析240
歸納總結254
思維拓展255
第7章查找256
7．1查找的基本概念256
7．2順序查找和折半查找257
7．2．1順序查找257
7．2．2折半查找259
7．2．3分塊查找260
7．2．4本節試題精選261
7．2．5答案與解析264
7．3樹型查找270
7．3．1二叉排序樹（BST）270
7．3．2平衡二叉樹273
7．3．3紅黑樹277
7．3．4本節試題精選282
7．3．5答案與解析286
7．4B樹和B+樹295
7．4．1B樹及其基本操作296
7．4．2B+樹的基本概念299
7．4．3本節試題精選300
7．4．4答案與解析302
7．5散列表307
7．5．1散列表的基本概念307
7．5．2散列函數的構造方法307
7．5．3處理衝突的方法308
7．5．4散列查找及性能分析309
7．5．5本節試題精選310
7．5．6答案與解析313
歸納總結318
思維拓展319
第8章排序320
8．1排序的基本概念321
8．1．1排序的定義321
8．1．2本節試題精選321
8．1．3答案與解析322
8．2插入排序322
8．2．1直接插入排序322
8．2．2折半插入排序324
8．2．3希爾排序324
8．2．4本節試題精選326
8．2．5答案與解析327
8．3交換排序330
8．3．1冒泡排序330
8．3．2快速排序331
8．3．3本節試題精選333
8．3．4答案與解析335
8．4選擇排序341
8．4．1簡單選擇排序341
8．4．2堆排序342
8．4．3本節試題精選344
8．4．4答案與解析346
8．5歸並排序和基數排序350
8．5．1歸並排序350
8．5．2基數排序352
8．5．3本節試題精選353
8．5．4答案與解析355
8．6各種內部排序算法的比較及應用357
8．6．1內部排序算法的比較357
8．6．2內部排序算法的應用358
8．6．3本節試題精選359
8．6．4答案與解析361
8．7外部排序365
8．7．1外部排序的基本概念365
8．7．2外部排序的方法365
8．7．3多路平衡歸並與敗者樹366
8．7．4置換-選擇排序（生成初始歸並段）367
8．7．5很好歸並樹368
8．7．6本節試題精選369
8．7．7答案與解析370
歸納總結373
思維拓展374
參考文獻375

本書是計算機專業研究生入學考試“數據結構”課程的復習用書，內容包括緒論，線性表，棧、隊列和數組，串，樹與二叉樹，圖、查找，排序等。全書嚴格按照近期新計算機考研大綱的數據結構部分，對大綱所涉及的知識點進行集中梳理，力求內容精煉、重點突出、深入淺出。本書精選各名校的歷年考研真題，並給出詳細的解題思路，力求實現講練結合、靈活掌握、舉一反三的功效。本書可作為考生參加計算機專業研究生入學考試的復習用書，也可作為計算機專業學生學習數據結構課程的輔導用書。