数据结构抢分攻略 真题分类分级详解

考纲分析与应试策略

一、考试简介 001
二、考试方式 001
三、考试大纲解读 002
四、应试经验与答题技巧 003
五、复习策略 004


第 一章　绪论

第 一节　数据结构与算法的基本概念 006
考点1　数据结构的基本概念 006
考点2　算法的基本概念 007
第二节　算法的时间复杂度与空间复杂度 008
考点3　时间复杂度 008
考点4　空间复杂度 010
过关练习 010
单项选择题 010
答案与解析 012


第二章　线性表

第 一节　线性表的顺序表示 015
考点1　线性表的定义和性质 015
考点2　顺序表的性质和操作 016
第二节　线性表的链式表示 016
考点3　单链表的性质和操作 016
考点4　双向链表的性质和操作 018
考点5　循环链表与静态链表 019
考点6　顺序结构与链式结构的比较 020
过关练习 020
单项选择题 020
综合应用题 022
答案与解析 027

第三章　栈、队列和数组

第 一节　栈 048
考点1　栈的基本概念 048
考点2　栈的顺序存储 051
考点3　栈的链式存储 052
考点4　栈的应用 052
第二节　队列 054
考点5　队列的基本概念 054
考点6　队列的顺序存储 055
考点7　队列的链式存储 058
考点8　队列的应用 058
第三节　数组 059
考点9　多维数组的存储 059
考点10　特殊矩阵的压缩存储 060
过关练习 061
单项选择题 061
综合应用题 065
答案与解析 066


第四章　树形结构

第 一节　树 077
考点1　树的基本概念和性质 077
考点2　树的存储结构 079
第二节　二叉树 079
考点3　二叉树的定义和性质 079
考点4　特殊的二叉树 081
第三节　二叉树的存储与遍历 083
考点5　二叉树的链式存储 083
考点6　二叉树的顺序存储 083
考点7　二叉树的遍历 084
考点8　线索二叉树 086
第四节　森林 088
考点9　树、森林与二叉树的转换 088
考点10　树与森林的遍历 090
第五节　树形结构的应用 091
考点11　哈夫曼树与哈夫曼编码 091
考点12　并查集 093
过关练习 093
单项选择题 093
综合应用题 100
答案与解析 104


第五章　图

第 一节　图的基本概念与图的存储 126
考点1　图的基本概念 126
考点2　邻接矩阵 127
考点3　邻接表 128
考点4　其他存储方式 129
第二节　图的遍历 129
考点5　深度优先搜索 129
考点6　广度优先搜索 131
第三节　最小生成树 133
考点7　最小生成树的概念 133
考点8　Kruskal算法与Prim算法 135
第四节　最短路径 136
考点9　最短路径的概念 136
考点10　Dijkstra算法与Floyd算法 137
第五节　拓扑排序 138
考点11　AOV网与拓扑排序的概念 138
考点12　拓扑排序的求解 138
第六节　 关键路径 139
考点13　AOE网与关键路径的概念 139
考点14　关键路径的求解 140
过关练习 141
单项选择题 141
综合应用题 148
答案与解析 152


第六章　查找

第 一节　线性查找 167
考点1　顺序查找 167
考点2　折半查找 168
考点3　分块查找 169
第二节　树形查找 170
考点4　二叉排序树 170
考点5　平衡二叉树 170
考点6　B树与B+树 172
考点7　红黑树 174
第三节　散列查找 175
考点8　散列表的基本概念 175
考点9　散列函数设计与冲突处理 176
考点10　散列表的性能分析 178
第四节　串的匹配 178
考点11　暴力匹配算法 178
考点12　KMP算法 179
过关练习 180
单项选择题 180
综合应用题 184
答案与解析 186


第七章　排序

第 一节　插入类排序 197
考点1　直接插入排序 197
考点2　折半插入排序 198
考点3　希尔排序 198
第二节　交换类排序 200
考点4　冒泡排序 200
考点5　快速排序 200
第三节　选择类排序 201
考点6　简单选择排序 201
考点7　堆排序 202
第四节　归并排序与基数排序 203
考点8　归并排序 203
考点9　基数排序 204
第五节　排序总结 204
考点10　内部排序的对比 204
考点11　排序的应用 206
第六节　外部排序 206
考点12　外部排序算法 206
考点13　最佳归并树 207
过关练习 207
单项选择题 207
综合应用题 213
答案与解析 214


全真模拟题及答案解析

全真模拟题 226
全真模拟题参考答案及解析 228