目　录

第 1章　概论　1
1.1　课程目的和内容　1
1.2　研究生入学统一考试考查目标和数据结构考查范围　1
1.3　内容和要点　2
1.3.1　学习要求　2
1.3.2　基本概念　2
1.3.3　数据抽象和抽象数据类型　3
1.3.4　数据结构和算法描述　3
1.3.5　算法和算法分析　3
1.4　典型题解　4
1.4.1　基本题　4
1.4.2　算法分析题　6
1.4.3　算法设计题　6
1.5　考研试题解析　8
1.5.1　基本题　8
1.5.2　算法分析题　9
1.6　配书习题选解　10
1.7　练习题　12

第 2章　数组和链表　14
2.1　内容和要点　14
2.1.1　学习要求　14
2.1.2　数组　14
2.1.3　指针和动态存储分配　15
2.1.4　单链表　16
2.1.5　其他链表　17
2.2　典型题解　17
2.2.1　基本题　17
2.2.2　算法设计题　19
2.3　考研试题解析　19
2.3.1　基本题　19
2.3.2　算法设计题　20
2.4　配书习题选解　21
2.5　练习题　23

第3章　堆栈和队列　26
3.1　内容和要点　26
3.1.1　学习要求　26
3.1.2　堆栈ADT　26
3.1.3　堆栈的实现　27
3.1.4　队列ADT　27
3.1.5　队列的实现　28
3.1.6　表达式计算　28
3.1.7　递归　29
3.2　典型题解　29
3.2.1　基本题　29
3.2.2　算法设计题　31
3.3　考研试题解析　32
3.3.1　基本题　32
3.3.2　算法设计题　34
3.4　配书习题选解　35
3.5　练习题　39

第4章　线性表　41
4.1　内容和要点　41
4.1.1　学习要求　41
4.1.2　线性表ADT　41
4.1.3　线性表的顺序表示　42
4.1.4　线性表的链接表示　43
4.1.5　两种存储表示的比较　43
4.1.6　多项式的算术运算　44
4.2　典型题解　44
4.2.1　基本题　44
4.2.2　算法设计题　45
4.3　考研试题解析　46
4.3.1　基本题　46
4.3.2　算法设计题　48
4.4　配书习题选解　49
4.5　练习题　51

第5章　数组ADT和字符串　53
5.1　内容和要点　53
5.1.1　学习要求　53
5.1.2　数组作为抽象数据类型　53
5.1.3　对称矩阵　54
5.1.4　稀疏矩阵　54
5.1.5　字符串　55
5.1.6　模式匹配　55
5.2　典型题解　56
5.2.1　基本题　56
5.2.2　算法设计题　57
5.3　考研试题解析　58
5.3.1　基本题　58
5.3.2　算法设计题　60
5.4　配书习题选解　61
5.5　练习题　64

第6章　树　66
6.1　内容和要点　66
6.1.1　学习要求　66
6.1.2　树的定义和基本术语　67
6.1.3　二叉树的定义和性质　67
6.1.4　二叉树ADT和二叉链表　68
6.1.5　二叉树遍历递归算法　68
6.1.6　线索二叉树　69
6.1.7　树和森林　69
6.1.8　堆和优先权队列　70
6.1.9　哈夫曼树和哈夫曼编码　70
6.1.10　并查集和等价关系　70
6.2　典型题解　71
6.2.1　基本题　71
6.2.2　算法设计题　72
6.3　考研试题解析　73
6.3.1　基本题　73
6.3.2　算法设计题　75
6.4　配书习题选解　76
6.5　练习题　81

第7章　集合与搜索　83
7.1　内容和要点　83
7.1.1　学习要求　83
7.1.2　基本概念　83
7.1.3　动态集ADT　84
7.1.4　集合的表示　84
7.1.5　集合的顺序表表示　84
7.1.6　顺序搜索　85
7.1.7　二分搜索和对半搜索　85
7.1.8　二叉判定树　85
7.2　典型题解　86
7.2.1　基本题　86
7.2.2　算法设计题　87
7.3　考研试题解析　89
7.3.1　基本题　89
7.3.2　算法设计题　90
7.4　配书习题选解　91
7.5　练习题　92

第8章　搜索树　95
8.1　内容和要点　95
8.1.1　学习要求　95
8.1.2　二叉搜索树　95
8.1.3　二叉搜索树的搜索　96
8.1.4　二叉平衡树　96
8.1.5　B树　97
8.2　典型题解　98
8.2.1　基本题　98
8.2.2　算法设计题　101
8.3　考研试题解析　102
8.3.1　基本题　102
8.3.2　算法设计题　105
8.4　配书习题选解　105
8.5　练习题　108

第9章　散列表　110
9.1　内容和要点　110
9.1.1　学习要求　110
9.1.2　字典　110
9.1.3　散列表　110
9.1.4　拉链法　111
9.1.5　开地址法　111
9.2　典型题解　112
9.2.1　基本题　112
9.2.2　算法设计题　114
9.3　考研试题解析　114
9.3.1　基本题　114
9.3.2　算法设计题　117
9.4　配书习题选解　118
9.5　练习题　119

第 10章　图　121
10.1　内容和要点　121
10.1.1 学习要求　121
10.1.2　图的基本概念　121
10.1.3　图ADT　122
10.1.4　图的存储结构　122
10.1.5　图的遍历　124
10.1.6　拓扑排序和关键路径　124
10.1.7　**小代价生成树　125
10.1.8　**短路径　125
10.2　典型题解　126
10.2.1　基本题　126
10.2.2　算法设计题　128
10.3　考研试题解析　129
10.3.1　基本题　129
10.3.2　算法设计题　132
10.4　配书习题选解　133
10.5　练习题　139

第 11章　内排序　142
11.1　内容和要点　142
11.1.1　学习要求　142
11.1.2　基本概念　142
11.1.3　可排序表类　143
11.1.4　排序算法　143
11.1.5　算法分析　144
11.2　典型题解　145
11.2.1　基本题　145
11.2.2　算法设计题　147
11.3　考研试题解析　148
11.3.1　基本题　148
11.3.2　算法设计题　150
11.4　配书习题选解　151
11.5　练习题　156

第 12章　文件和外排序　158
12.1　内容和要点　158
12.1.1　学习要求　158
12.1.2　文件　158
12.1.3　外排序　159
12.2　典型题解　160
12.3　考研试题解析　163
12.4　配书习题选解　165
12.5　练习题　166

第 13章　模拟试题解析　168
13.1　本科《数据结构》期末模拟试题　168
13.2　本科《数据结构》期末模拟试题解析　171
13.3　攻读硕士学位研究生入学考试《数据结构》模拟试题　174
13.4　攻读硕士学位研究生入学考试《数据结构》模拟试题解析　177

附录一　南京邮电大学近4年研究生入学《数据结构》试题　182
附录A　2005年攻读硕士学位研究生入学考试试题　182
附录B　2006年攻读硕士学位研究生入学考试试题　185
附录C　2007年攻读硕士学位研究生入学考试试题　187
附录D　2008年攻读硕士学位研究生入学考试试题　190
附录二　2009研究生计算机学科专业基础综合考试数据结构考试要求和试题示例　193

参考文献　196