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

本书面向参加计算机相关专业的硕士研究生招生考试（简称计算机考研）的考生，以全国硕士研究生招生考试计算机学科专业基础（简称全国统考）的考试大纲中数据结构部分的内容为依据，在研究、分析全国统考和院校自主命题考试的历年真题及其命题规律的基础上编写而成。 本书对全国统考的考试大纲进行了深入解读，提供了应试策略，并根据数据结构部分所涉及考点的知识体系分章讲解，每章以“知识点分类+经典例题精解”的形式，剖析了常考题型、命题特点及解题方法，帮助考生掌握解题思路与解题技巧。此外，章末提供了“过关练习”，供考生进行自测练习。本书还提供了面向数据结构的1套全真模拟题，供考生实战演练。 本书适合参加计算机考研（包括全国统考和院校自主命题考试）的考生备考学习，也适合作为计算机相关专业学生的学习用书和培训机构的辅导用书。

海贼宝藏是一个专注于IT 教育的在线学习平台，集课程、任务、在线评测、考试等不同学习模式为一体，旨在为学习者提供一套完整的学习系统。其提供的计算机考研线上课程，以及历年真题、模拟题、复试上机练习环境等，有利于考生在不同的备考阶段进行有针对性的学习及训练，是考生提升学习效能的“利器”。

目 录 考纲分析与应试策略 一、考试简介 001 二、考试方式 001 三、考试大纲解读 001 四、应试经验与答题技巧 003 五、复习策略 004 第 一章　绪论 第 一节　数据结构与算法的基本概念 005 考点1　数据结构的基本概念 005 考点2　算法的基本概念 006 第二节　算法的时间复杂度与空间复杂度 007 考点3　时间复杂度 007 考点4　空间复杂度 009 过关练习 009 单项选择题 009 答案与解析 011 第二章　线性表 第 一节　线性表的顺序表示 014 考点1　线性表的定义和性质 014 考点2　顺序表的性质和操作 015 第二节　线性表的链式表示 015 考点3　单链表的性质和操作 015 考点4　双向链表的性质和操作 017 考点5　循环链表与静态链表 018 考点6　顺序结构与链式结构的比较 019 过关练习 019 单项选择题 019 综合应用题 020 答案与解析 025 第三章　栈、队列和数组 第 一节　栈 047 考点1　栈的基本概念 047 考点2　栈的顺序存储 050 考点3　栈的链式存储 051 考点4　栈的应用 051 第二节　队列 053 考点5　队列的基本概念 053 考点6　队列的顺序存储 054 考点7　队列的链式存储 057 考点8　队列的应用 057 第三节　数组 058 考点9　多维数组的存储 058 考点10　特殊矩阵的压缩存储 059 过关练习 060 单项选择题 060 综合应用题 064 答案与解析 065 第四章　树形结构 第 一节　树 076 考点1　树的基本概念和性质 076 考点2　树的存储结构 078 第二节　二叉树 078 考点3　二叉树的定义和性质 078 考点4　特殊的二叉树 080 第三节　二叉树的存储与遍历 082 考点5　二叉树的链式存储 082 考点6　二叉树的顺序存储 082 考点7　二叉树的遍历 083 考点8　线索二叉树 085 第四节　森林 087 考点9　树、森林与二叉树的转换 087 考点10　树与森林的遍历 089 第五节　树形结构的应用 090 考点11　哈夫曼树与哈夫曼编码 090 考点12　并查集 092 过关练习 092 单项选择题 092 综合应用题 099 答案与解析 103 第五章　图 第 一节　图的基本概念与图的存储 125 考点1　图的基本概念 125 考点2　邻接矩阵 126 考点3　邻接表 127 考点4　其他存储方式 128 第二节　图的遍历 128 考点5　深度优先搜索 128 考点6　广度优先搜索 130 第三节　最小生成树 132 考点7 最小生成树的概念 132 考点8 Kruskal算法与Prim算法 134 第四节　最短路径 135 考点9　最短路径的概念 135 考点10　Dijkstra算法与Floyd算法 136 第五节　拓扑排序 137 考点11　AOV网与拓扑排序的概念 137 考点12　拓扑排序的求解 137 第六节　 关键路径 138 考点13　AOE网与关键路径的概念 138 考点14　关键路径的求解 139 过关练习 140 单项选择题 140 综合应用题 147 答案与解析 151 第六章　查找 第 一节　线性查找 166 考点1　顺序查找 166 考点2　折半查找 167 考点3　分块查找 168 第二节　树形查找 168 考点4　二叉排序树 168 考点5　平衡二叉树 169 考点6　B树与B+树 171 考点7　红黑树 173 第三节　散列查找 173 考点8　散列表的基本概念 173 考点9　散列函数设计与冲突处理 174 考点10　散列表的性能分析 176 第四节　串的匹配 177 考点11　暴力匹配算法 177 考点12　 KMP算法 178 过关练习 179 单项选择题 179 综合应用题 183 答案与解析 185 第七章　排序 第 一节　插入类排序 196 考点1 直接插入排序 196 考点2 折半插入排序 197 考点3 希尔排序 197 第二节　交换类排序 199 考点4 冒泡排序 199 考点5 快速排序 199 第三节　选择类排序 200 考点6　简单选择排序 200 考点7　堆排序 201 第四节　归并排序与基数排序 202 考点8　归并排序 202 考点9　基数排序 203 第五节　排序总结 203 考点10　内部排序的对比 203 考点11　排序的应用 205 第六节　外部排序 205 考点12　外部排序算法 205 考点13　最佳归并树 206 过关练习 206 单项选择题 206 综合应用题 211 答案与解析 213 全真模拟题及答案解析 全真模拟题 226 全真模拟题参考答案及解析 229