描述
开 本: 16开纸 张: 胶版纸包 装: 平装-胶订是否套装: 否国际标准书号ISBN: 9787302527084丛书名: 启航计算机考研专业课系列
产品特色
编辑推荐
知识点全面，代码简洁清晰，注释明了易懂，试题覆盖范围广泛，讲解清晰，易于掌握
内容简介
《计算机考研专业课——数据结构一本通（考点详解 习题全解)》严格遵守《全国硕士研究生入学考试计算机相关专业综合》大纲，分为考点详解与试题全解2部分。考点详解部分以伪代码进行讲解，关键步骤给出详细的代码注释，并用图形给出算法的流程分析，方便读者从原理上进行理解。试题全解部分以408试题以及部分高校历年真题为例进行详细解析，进一步增强读者的实际解题能力。
目 录
第 0 章 导学 · 1.
0.1 学习目标 1.
0.2 大纲 1.
0.3 本书知识结构 1.
第 1 章 绪论 · 3.
1.1 本章导学 3.
1.1.1 知识结构 · 3.
1.1.2 命题特点 · 4.
1.2 基本概念 4.
1.3 数据结构 5.
1.3.1 定义 · 5.
1.3.2 逻辑结构 · 6.
1.3.3 存储结构 · 8.
1.4 算法 10.
1.4.1 定义 · 10.
1.4.2 特征 · 10.
1.4.3 算法和程序 11.
1.4.4 评价 · 11.
1.5 本章小结 13.
第 2 章 线性表 · 14.
2.1 本章导学 14.
2.1.1 知识结构 · 14.
2.1.2 命题特点 · 15.
2.2 线性表概述 15.
2.2.1 定义 · 15.
2.2.2 基本操作 · 16.
2.3 线性表存储结构及操作
实现 · 17.
2.3.1 顺序表 · 17.
2.3.2 链表 · 23.
2.4 栈 56.
2.4.1 定义 · 56.
2.4.2 存储结构 · 57.
2.4.3 应用 · 60.
2.5 队列 62.
2.5.1 定义 · 62.
2.5.2 存储结构 · 63.
2.5.3 应用 · 66.
2.6 特殊矩阵 67.
2.6.1 对称矩阵 · 68.
2.6.2 三角矩阵 · 69.
2.6.3 对角矩阵 · 71.
2.6.4 稀疏矩阵 · 72.
2.7 串 76.
2.7.1 基本概念 · 76.
2.7.2 存储结构 · 76.
2.7.3 基本操作 · 76.
2.7.4 模式匹配 · 79.
2.8 综合应用 85.
2.8.1 两栈共享空间 · 85.
2.8.2 多项式求和 · 87.
2.9 本章小结 89.
第 3 章 树和二叉树 90.
3.1 本章导学 90.
3.1.1 知识结构 · 90.
3.1.2 命题特点 · 90.
3.2 树 91.
3.2.1 定义 · 91.
3.2.2 树的表示形式 · 92.
3.2.3 树的相关概念 · 93.
3.2.4 树的抽象数据类型 · 93.
3.2.5 存储结构 · 94.
3.2.6 树的遍历 · 96.
3.3 二叉树 97.
3.3.1 定义 · 98.
3.3.2 性质 · 99.
3.3.3 存储结构 · 100.
3.3.4 二叉树的遍历 · 103.
3.3.5 线索二叉树 · 112.
计算机考研专业课——数据结构一本通（考点详解＋习题全解）
IV
3.3.6 二叉排序树 114.
3.3.7 平衡二叉树 119.
3.3.8 哈夫曼树 · 122.
3.4 树和森林 125.
3.4.1 树与二叉树的转化 125.
3.4.2 森林与二叉树的
转化 · 126.
3.4.3 树的遍历 · 126.
3.4.4 森林的遍历 127.
3.5 本章小结 128.
第 4 章 图 129.
4.1 本章导学 129.
4.1.1 知识结构 · 129.
4.1.2 命题特点 · 130.
4.2 基本概念 130.
4.3 存储结构 132.
4.3.1 邻接矩阵 · 132.
4.3.2 邻接表 · 136.
4.3.3 十字链表 · 139.
4.4 遍历 142.
4.4.1 深度优先搜索 142.
4.4.2 广度优先搜索 145.
4.5 最小生成树 150.
4.5.1 普里姆算法 150.
4.5.2 克鲁斯卡尔算法 152.
4.6 最短路径 155.
4.6.1 单源最短路径 155.
4.6.2 任意两个顶点之间的
最短路径 · 158.
4.7 关键路径 160.
4.7.1 关键路径概述 161.
4.7.2 关键路径求解 161.
4.8 拓扑排序 163.
4.9 公共子表达式 164.
4.10 本章小结 164.
第 5 章 查找 · 165.
5.1 本章导学 165.
5.1.1 知识结构 · 165.
5.1.2 命题特点 · 165.
5.2 基本概念 166.
5.3 顺序表的静态查找 · 166.
5.3.1 顺序查找 · 166.
5.3.2 折半查找 · 167.
5.3.3 分块查找 · 169.
5.4 二叉排序树 · 170.
5.5 二叉平衡树 · 171.
5.6 B 树类 · 171.
5.6.1 B 树 · 171.
5.6.2 B 树 176.
5.7 散列表 177.
5.7.1 基本概念 · 177.
5.7.2 散列函数构造 · 178.
5.7.3 处理冲突方法 · 179.
5.7.4 填充因子 · 181.
5.8 本章小结 181.
第 6 章 排序 · 182.
6.1 本章导读 182.
6.1.1 知识结构 · 182.
6.1.2 命题规律 · 183.
6.2 基本概念 183.
6.3 插入排序 184.
6.3.1 直接插入排序 · 184.
6.3.2 折半插入排序 · 185.
6.3.3 希尔排序 · 186.
6.4 交换排序 188.
6.4.1 冒泡排序 · 188.
6.4.2 快速排序 · 189.
6.5 选择排序 191.
6.5.1 直接选择排序 · 191.
6.5.2 堆选择排序 · 192.
6.6 归并排序 194.
6.7 基数排序 196.
6.8 内部排序方法比较 · 199.
6.9 外部排序 200.
6.10 本章小结 201.
主要算法总结 · 202.
参考书目 203
0.1 学习目标 1.
0.2 大纲 1.
0.3 本书知识结构 1.
第 1 章 绪论 · 3.
1.1 本章导学 3.
1.1.1 知识结构 · 3.
1.1.2 命题特点 · 4.
1.2 基本概念 4.
1.3 数据结构 5.
1.3.1 定义 · 5.
1.3.2 逻辑结构 · 6.
1.3.3 存储结构 · 8.
1.4 算法 10.
1.4.1 定义 · 10.
1.4.2 特征 · 10.
1.4.3 算法和程序 11.
1.4.4 评价 · 11.
1.5 本章小结 13.
第 2 章 线性表 · 14.
2.1 本章导学 14.
2.1.1 知识结构 · 14.
2.1.2 命题特点 · 15.
2.2 线性表概述 15.
2.2.1 定义 · 15.
2.2.2 基本操作 · 16.
2.3 线性表存储结构及操作
实现 · 17.
2.3.1 顺序表 · 17.
2.3.2 链表 · 23.
2.4 栈 56.
2.4.1 定义 · 56.
2.4.2 存储结构 · 57.
2.4.3 应用 · 60.
2.5 队列 62.
2.5.1 定义 · 62.
2.5.2 存储结构 · 63.
2.5.3 应用 · 66.
2.6 特殊矩阵 67.
2.6.1 对称矩阵 · 68.
2.6.2 三角矩阵 · 69.
2.6.3 对角矩阵 · 71.
2.6.4 稀疏矩阵 · 72.
2.7 串 76.
2.7.1 基本概念 · 76.
2.7.2 存储结构 · 76.
2.7.3 基本操作 · 76.
2.7.4 模式匹配 · 79.
2.8 综合应用 85.
2.8.1 两栈共享空间 · 85.
2.8.2 多项式求和 · 87.
2.9 本章小结 89.
第 3 章 树和二叉树 90.
3.1 本章导学 90.
3.1.1 知识结构 · 90.
3.1.2 命题特点 · 90.
3.2 树 91.
3.2.1 定义 · 91.
3.2.2 树的表示形式 · 92.
3.2.3 树的相关概念 · 93.
3.2.4 树的抽象数据类型 · 93.
3.2.5 存储结构 · 94.
3.2.6 树的遍历 · 96.
3.3 二叉树 97.
3.3.1 定义 · 98.
3.3.2 性质 · 99.
3.3.3 存储结构 · 100.
3.3.4 二叉树的遍历 · 103.
3.3.5 线索二叉树 · 112.
计算机考研专业课——数据结构一本通（考点详解＋习题全解）
IV
3.3.6 二叉排序树 114.
3.3.7 平衡二叉树 119.
3.3.8 哈夫曼树 · 122.
3.4 树和森林 125.
3.4.1 树与二叉树的转化 125.
3.4.2 森林与二叉树的
转化 · 126.
3.4.3 树的遍历 · 126.
3.4.4 森林的遍历 127.
3.5 本章小结 128.
第 4 章 图 129.
4.1 本章导学 129.
4.1.1 知识结构 · 129.
4.1.2 命题特点 · 130.
4.2 基本概念 130.
4.3 存储结构 132.
4.3.1 邻接矩阵 · 132.
4.3.2 邻接表 · 136.
4.3.3 十字链表 · 139.
4.4 遍历 142.
4.4.1 深度优先搜索 142.
4.4.2 广度优先搜索 145.
4.5 最小生成树 150.
4.5.1 普里姆算法 150.
4.5.2 克鲁斯卡尔算法 152.
4.6 最短路径 155.
4.6.1 单源最短路径 155.
4.6.2 任意两个顶点之间的
最短路径 · 158.
4.7 关键路径 160.
4.7.1 关键路径概述 161.
4.7.2 关键路径求解 161.
4.8 拓扑排序 163.
4.9 公共子表达式 164.
4.10 本章小结 164.
第 5 章 查找 · 165.
5.1 本章导学 165.
5.1.1 知识结构 · 165.
5.1.2 命题特点 · 165.
5.2 基本概念 166.
5.3 顺序表的静态查找 · 166.
5.3.1 顺序查找 · 166.
5.3.2 折半查找 · 167.
5.3.3 分块查找 · 169.
5.4 二叉排序树 · 170.
5.5 二叉平衡树 · 171.
5.6 B 树类 · 171.
5.6.1 B 树 · 171.
5.6.2 B 树 176.
5.7 散列表 177.
5.7.1 基本概念 · 177.
5.7.2 散列函数构造 · 178.
5.7.3 处理冲突方法 · 179.
5.7.4 填充因子 · 181.
5.8 本章小结 181.
第 6 章 排序 · 182.
6.1 本章导读 182.
6.1.1 知识结构 · 182.
6.1.2 命题规律 · 183.
6.2 基本概念 183.
6.3 插入排序 184.
6.3.1 直接插入排序 · 184.
6.3.2 折半插入排序 · 185.
6.3.3 希尔排序 · 186.
6.4 交换排序 188.
6.4.1 冒泡排序 · 188.
6.4.2 快速排序 · 189.
6.5 选择排序 191.
6.5.1 直接选择排序 · 191.
6.5.2 堆选择排序 · 192.
6.6 归并排序 194.
6.7 基数排序 196.
6.8 内部排序方法比较 · 199.
6.9 外部排序 200.
6.10 本章小结 201.
主要算法总结 · 202.
参考书目 203
前 言
“数据结构”是全国硕士研究生入学考试科目——计算机学科专业综合的考查科目之
一，是研究“非数值计算的程序设计问题中计算机的操作对象及其关系和操作等的学科”，
是介于数学、计算机硬件和计算机软件三者之间的一门核心课程，同时也是计算机科学
与技术专业的专业基础课。课程内容不仅是一般程序设计（特别是非数值计算的程序设
计）的基础，同时也是设计和实现编译程序、操作系统、数据库系统及其他系统程序和
应用程序的重要基础。
“数据结构”主要研究数据及数据之间的关系、数据的存储以及具有关系的数据集上
的操作。主要涉及三种关系：一对一关系（线性表）、一对多关系（树和二叉树）、多对
多关系（图）。常见操作有创建、查找、删除、排序等。考生在复习时首先应熟练掌握理
论内容，单纯的刷题无法解决基础内容的欠缺问题，也无法应对考场上不曾谋面的试题。
然后再通过练习题及真题检验对课程知识的掌握程度。
本书分为两部分，第一部分是考点详解，第二部分为习题精讲。考点详解部分首先
是导学部分，主要介绍本科目考试大纲和本书各章节知识点分布。第 1 章为绪论，主要
介绍数据结构和算法的基本概念。第 2 章为线性表，主要介绍线性结构的基本概念、算
法及实现，以及特殊线性表（栈和队列）、特殊矩阵等。第 3 章介绍树及二叉树的相关概
念及算法。第 4 章介绍图的定义、算法。第 5 章介绍各种查找算法及其分析。第 6 章介
绍排序算法及其特点。习题精讲部分主要收集全国硕士研究生入学考试计算机学科专业
基础综合（专业课代码 408，本书文中统称 408）及各高校科研院所的历年真题，通过真
题使考生零距离感受考题形式和答题思路，通过做题，熟练、灵活地掌握理论内容，进
一步加强分析题目、求解问题的思维训练。
本书的知识详解部分尽可能多地给出基本操作的伪码实现、注释、算法的流程分析
等，帮助考生深入理解算法本质，为解题打下坚实基础。此外，我们还为本书配备了丰
富的视频讲解，扫描每章和图书封底的二维码即可观看。
备考过程中，考生需注意复习方法。首先应全局把握本书内容，熟悉本书特点、重
点章节等。然后进行系统学习和总结，熟练掌握各知识点。最后通过历年真题分析巩固
各知识点并了解各知识点的出题方式和考查频率。
备考过程漫长辛苦，考生应注意学习方法，提高复习效率，不搞消耗战，不做过多
重复题，以不变应万变。毫无头绪时不妨归本还原，静下心来认真研究基本概念和算法，
或许能打开解题思路。
编者
2019 年 1 月
一，是研究“非数值计算的程序设计问题中计算机的操作对象及其关系和操作等的学科”，
是介于数学、计算机硬件和计算机软件三者之间的一门核心课程，同时也是计算机科学
与技术专业的专业基础课。课程内容不仅是一般程序设计（特别是非数值计算的程序设
计）的基础，同时也是设计和实现编译程序、操作系统、数据库系统及其他系统程序和
应用程序的重要基础。
“数据结构”主要研究数据及数据之间的关系、数据的存储以及具有关系的数据集上
的操作。主要涉及三种关系：一对一关系（线性表）、一对多关系（树和二叉树）、多对
多关系（图）。常见操作有创建、查找、删除、排序等。考生在复习时首先应熟练掌握理
论内容，单纯的刷题无法解决基础内容的欠缺问题，也无法应对考场上不曾谋面的试题。
然后再通过练习题及真题检验对课程知识的掌握程度。
本书分为两部分，第一部分是考点详解，第二部分为习题精讲。考点详解部分首先
是导学部分，主要介绍本科目考试大纲和本书各章节知识点分布。第 1 章为绪论，主要
介绍数据结构和算法的基本概念。第 2 章为线性表，主要介绍线性结构的基本概念、算
法及实现，以及特殊线性表（栈和队列）、特殊矩阵等。第 3 章介绍树及二叉树的相关概
念及算法。第 4 章介绍图的定义、算法。第 5 章介绍各种查找算法及其分析。第 6 章介
绍排序算法及其特点。习题精讲部分主要收集全国硕士研究生入学考试计算机学科专业
基础综合（专业课代码 408，本书文中统称 408）及各高校科研院所的历年真题，通过真
题使考生零距离感受考题形式和答题思路，通过做题，熟练、灵活地掌握理论内容，进
一步加强分析题目、求解问题的思维训练。
本书的知识详解部分尽可能多地给出基本操作的伪码实现、注释、算法的流程分析
等，帮助考生深入理解算法本质，为解题打下坚实基础。此外，我们还为本书配备了丰
富的视频讲解，扫描每章和图书封底的二维码即可观看。
备考过程中，考生需注意复习方法。首先应全局把握本书内容，熟悉本书特点、重
点章节等。然后进行系统学习和总结，熟练掌握各知识点。最后通过历年真题分析巩固
各知识点并了解各知识点的出题方式和考查频率。
备考过程漫长辛苦，考生应注意学习方法，提高复习效率，不搞消耗战，不做过多
重复题，以不变应万变。毫无头绪时不妨归本还原，静下心来认真研究基本概念和算法，
或许能打开解题思路。
编者
2019 年 1 月
免费在线读
第 1 章 绪论
.. 了解数据、数据元素、数据项等基本概念。
.. 深入理解数据结构的含义、逻辑结构和存储结构的概念。
.. 理解不同逻辑结构的本质区别。
.. 掌握不同存储结构的实质。
.. 理解算法的概念。
.. 掌握算法的特征。
.. 能够分析各种算法的时间复杂度和空间复杂度。
1.1 本 章 导 学
1.1.1 知识结构
本章知识结构如图 1.1 所示，加粗框中的内容需要重点理解并掌握。
图 1.1 本章知识结构
绪论
计算机考研专业课——数据结构一本通（考点详解＋习题全解）
4
1.1.2 命题特点
1. 命题规律
（1）本章是历年各高校硕士研究生招生考试的基本考查内容，命题形式既有客观题
也有主观题。
（2）本章既可单独命题，也可与后续章节联合命题。
（3）顺序存储结构、链式存储结构的操作细节易出客观题。
（4）链表操作的综合应用易出主观题。
2．考查趋势
本章在全国硕士研究生入学考试中的重要性近年不会改变，主观题型、客观题型
出现的概率极大。特别注意顺序存储结构与查找、排序两章联合命题，以及链式存储结
构的综合应用。
1.2 基 本 概 念
（1）数据：客观事物的符号表示，指所有能输入到计算机中并被计算机程序处理的
符号。
（2）数据元素：又称结点，是数据的基本单位，在计算机中通常作为一个整体进行
处理。该概念根据具体问题进行具体界定，外延可大可小。
（3）数据项：又称属性，指数据中具有独立意义的、不可分割的最小单位。
注意，数据由多个数据元素组成，一个数据元素又包含若干数据项。
（4）数据对象：性质相同的数据元素的集合。
（5）数据类型：一组性质相同的值集合以及定义在该集合上的一组操作的总称。
（6）抽象数据类型：Abstract Data Type，简称 ADT，指一个数学模型及定义在该模
型上的一组操作。
（7）逻辑结构：数据元素之间固有的逻辑关系。该关系与计算机无关，是人的思维
层面对现实世界数据之间关系的理解。
（8）存储结构：逻辑结构在计算机中的表示，也称物理结构，不同存储结构对数据
处理效率具有较大影响。
（9）数据结构：相互之间具有特定关系的数据元素的集合，包含数据集、结构（逻
辑结构、物理结构）及施加其上的操作集。
（10）算法：解决特定问题的有限指令序列。
.. 了解数据、数据元素、数据项等基本概念。
.. 深入理解数据结构的含义、逻辑结构和存储结构的概念。
.. 理解不同逻辑结构的本质区别。
.. 掌握不同存储结构的实质。
.. 理解算法的概念。
.. 掌握算法的特征。
.. 能够分析各种算法的时间复杂度和空间复杂度。
1.1 本 章 导 学
1.1.1 知识结构
本章知识结构如图 1.1 所示，加粗框中的内容需要重点理解并掌握。
图 1.1 本章知识结构
绪论
计算机考研专业课——数据结构一本通（考点详解＋习题全解）
4
1.1.2 命题特点
1. 命题规律
（1）本章是历年各高校硕士研究生招生考试的基本考查内容，命题形式既有客观题
也有主观题。
（2）本章既可单独命题，也可与后续章节联合命题。
（3）顺序存储结构、链式存储结构的操作细节易出客观题。
（4）链表操作的综合应用易出主观题。
2．考查趋势
本章在全国硕士研究生入学考试中的重要性近年不会改变，主观题型、客观题型
出现的概率极大。特别注意顺序存储结构与查找、排序两章联合命题，以及链式存储结
构的综合应用。
1.2 基 本 概 念
（1）数据：客观事物的符号表示，指所有能输入到计算机中并被计算机程序处理的
符号。
（2）数据元素：又称结点，是数据的基本单位，在计算机中通常作为一个整体进行
处理。该概念根据具体问题进行具体界定，外延可大可小。
（3）数据项：又称属性，指数据中具有独立意义的、不可分割的最小单位。
注意，数据由多个数据元素组成，一个数据元素又包含若干数据项。
（4）数据对象：性质相同的数据元素的集合。
（5）数据类型：一组性质相同的值集合以及定义在该集合上的一组操作的总称。
（6）抽象数据类型：Abstract Data Type，简称 ADT，指一个数学模型及定义在该模
型上的一组操作。
（7）逻辑结构：数据元素之间固有的逻辑关系。该关系与计算机无关，是人的思维
层面对现实世界数据之间关系的理解。
（8）存储结构：逻辑结构在计算机中的表示，也称物理结构，不同存储结构对数据
处理效率具有较大影响。
（9）数据结构：相互之间具有特定关系的数据元素的集合，包含数据集、结构（逻
辑结构、物理结构）及施加其上的操作集。
（10）算法：解决特定问题的有限指令序列。
评论
还没有评论。