目录


第0章试题分析与复习方法1
0.1数据结构的试题分析1
0.1.1数据结构的课程特点1
0.1.2数据结构的试题分析3
0.1.3算法设计题的答题技巧4
0.2数据结构的复习方法5
0.2.1教材的选择5
0.2.2描述算法的程序设计语言5
0.2.3只抓重点的复习方法6
0.2.4循序渐进的复习方法7

第1章绪论9
1.1考纲要求及分析9
1.2数据结构的基本概念10
1.2.1考核知识点10
1.2.2重点难点释疑10
1.2.3典型题解析11
1.3算法和算法分析13
1.3.1考核知识点13
1.3.2重点难点释疑13
1.3.3典型题解析14

第2章线性表19
2.1考纲要求及分析19
2.2线性表的逻辑结构20
2.2.1考核知识点20
2.2.2典型题解析20
2.3顺序表21
2.3.1考核知识点21
2.3.2重点难点释疑21
2.3.3典型题解析23
2.4单链表27
2.4.1考核知识点27
2.4.2重点难点释疑28
2.4.3典型题解析32
2.5双链表40
2.5.1考核知识点40
2.5.2重点难点释疑40
2.5.3典型题解析41
2.6循环链表44
2.6.1考核知识点44
2.6.2重点难点释疑44
2.6.3典型题解析46
2.7线性表存储结构的比较54
2.7.1考核知识点54
2.7.2重点难点释疑54
2.7.3典型题解析54
全国硕士研究生招生考试计算机科学与技术学科联考数据结构复习指导与真题解析 目录 
第3章栈、队列和数组57
3.1考纲要求及分析57
3.2栈58
3.2.1考核知识点58
3.2.2重点难点释疑58
3.2.3典型题解析61
3.3队列66
3.3.1考核知识点66
3.3.2重点难点释疑66
3.3.3典型题解析67
3.4多维数组的存储72
3.4.1考核知识点72
3.4.2典型题解析73
3.5矩阵的压缩存储74
3.5.1考核知识点74
3.5.2重点难点释疑74
3.5.3典型题解析75
3.6栈、队列和数组的应用79
3.6.1考核知识点79
3.6.2典型题解析79

第4章树和二叉树82
4.1考纲要求及分析82
4.2树的基本概念83
4.2.1考核知识点83
4.2.2典型题解析84
4.3二叉树的逻辑结构84
4.3.1考核知识点84
4.3.2重点难点释疑85
4.3.3典型题解析86
4.4二叉树的存储结构90
4.4.1考核知识点90
4.4.2典型题解析91
4.5树和二叉树的遍历95
4.5.1考核知识点95
4.5.2重点难点释疑95
4.5.3典型题解析98
4.6线索二叉树105
4.6.1考核知识点105
4.6.2典型题解析106
4.7树的存储结构108
4.7.1考核知识点108
4.7.2典型题解析108
4.8树、森林与二叉树的转换110
4.8.1考核知识点110
4.8.2典型题解析110
4.9哈夫曼树和哈夫曼编码113
4.9.1考核知识点113
4.9.2重点难点释疑113
4.9.3典型题解析114
4.10并查集及其应用118
4.10.1考核知识点118
4.10.2典型题解析118

第5章图122
5.1考纲要求及分析122
5.2图的基本概念123
5.2.1考核知识点123
5.2.2典型题解析124
5.3图的存储结构127
5.3.1考核知识点127
5.3.2典型题解析127
5.4图的遍历131
5.4.1考核知识点131
5.4.2典型题解析131
5.5最小生成树136
5.5.1考核知识点136
5.5.2典型题解析136
5.6最短路径140
5.6.1考核知识点140
5.6.2典型题解析140
5.7拓扑排序143
5.7.1考核知识点143
5.7.2重点难点释疑143
5.7.3典型题解析144
5.8关键路径147
5.8.1考核知识点147
5.8.2典型题解析147

第6章查找149
6.1考纲要求及分析149
6.2查找的基本概念150
6.2.1考核知识点150
6.2.2典型题解析151
6.3线性表的查找技术152
6.3.1考核知识点152
6.3.2重点难点释疑152
6.3.3典型题解析154
6.4二叉排序树156
6.4.1考核知识点156
6.4.2典型题解析157
6.5平衡二叉树161
6.5.1考核知识点161
6.5.2重点难点释疑162
6.5.3典型题解析163
6.6红黑树166
6.6.1考核知识点166
6.6.2典型题解析166
6.7B树和B+树170
6.7.1考核知识点170
6.7.2典型题解析170
6.8散列查找174
6.8.1考核知识点174
6.8.2典型题解析174
6.9字符串模式匹配180
6.9.1考核知识点180
6.9.2重点难点释疑180
6.9.3典型题解析181

第7章排序182
7.1考纲要求及分析182
7.2排序的基本概念183
7.2.1考核知识点183
7.2.2重点难点释疑184
7.2.3典型题解析184
7.3插入排序186
7.3.1考核知识点186
7.3.2重点难点释疑186
7.3.3典型题解析187
7.4交换排序189
7.4.1考核知识点189
7.4.2重点难点释疑189
7.4.3典型题解析190
7.5选择排序194
7.5.1考核知识点194
7.5.2重点难点释疑195
7.5.3典型题解析196
7.6归并排序202
7.6.1考核知识点202
7.6.2典型题解析202
7.7基数排序203
7.7.1考核知识点203
7.7.2典型题解析203
7.8外部排序206
7.8.1考核知识点206
7.8.2典型题解析206
7.9排序算法的分析与应用209
7.9.1考核知识点209
7.9.2典型题解析209

附录A计算机学科专业基础考试大纲
（数据结构部分）211

附录B计算机学科专业基础试题考核
知识点一览表（数据结构部分）214

附录C2009年计算机学科专业基础试题及解析222

附录D2010年计算机学科专业基础试题及解析228

附录E2011年计算机学科专业基础试题及解析234

附录F2012年计算机学科专业基础试题及解析240

附录G2013年计算机学科专业基础试题及解析248

附录H2014年计算机学科专业基础试题及解析254

附录I2015年计算机学科专业基础试题及解析262

附录J2016年计算机学科专业基础试题及解析269

附录K2017年计算机学科专业基础试题及解析276

附录L2018年计算机学科专业基础试题及解析282

附录M2019年计算机学科专业基础试题及解析289

附录N2020年计算机学科专业基础试题及解析296

附录O2021年计算机学科专业基础试题及解析302