考研网

甘肃农业大学 2021 年全国硕士研究生招生考试

初试自命题科目考试大纲

科目代码： 849 科目名称：《数据结构和计算机网络》“数据结构”部分

考查目标

“数据结构”部分涵盖了数据逻辑结构、数据存储结构和算法设计与分析三方面的内容。

要求考生熟练掌握基本的线性和非线性数据的逻辑结构特点、常见物理存储实现方法以及各

自的优缺点；基本掌握针对具体问题，分析其数据结构特点，设计算法解决该问题的方法和

流程；初步掌握对算法进行时间复杂度与空间复杂度分析的方法。

试题类型 主要包括选择题、填空题、简答题、综合题。

参考书目

[1]《数据结构(C 语言版)》，严蔚敏主编，北京：清华大学出版社，2020 年

[2]《数据结构教程》（第 5 版）， 李春葆主编，北京：清华大学出版社，2017 年

[3]《数据结构精讲与习题详解（C 语言版）》（第2版），殷人昆主编.北京：清华大学出版社.2018

考查内容范围

考试内容将涉及如下内容：

（1）数据结构及算法基本概念；

（2）线性表；

（3）栈和队列；

（4）串；

（5）递归；

（6）数组和稀疏矩阵；

（7）树和二叉树；

（8）图；

（9）查找；

（10）内排序。

考查学生运用上述知识的综合分析能力，各部分的基本内容如下：

（一）基本概念

1.数据结构的基本概念；

2.算法的基本概念；

3.算法描述和基本特性；

4.算法时间复杂度和空间复杂度分析。

（二）线性表

1.线性表的逻辑结构特点和线性表抽象数据类型的描述方法；

2.线性表的两种存储结构（顺序存储结构及链式存储结构）以及各自的优缺点；

3.顺序表增加、删除、插入节点的算法；

4.单链表、双链表和循环链表中增加、删除、插入节点的算法。

（三）栈和队列

1.栈的逻辑结构特性和栈抽象数据类型的描述方法；

2.栈的先进后出特点；

3.栈的基本运算在顺序存储结构和链式存储结构下的实现算法；

4.栈在实际求解问题中的应用方法（求解简单表达式值）；

共 3 页 第 2 页

5.队列的逻辑结构特性和队列抽象数据类型的描述方法；

6.队列的先进先出特点；

7.队列的基本运算在顺序存储结构和链式存储结构下的实现算法；

8.循环队列的队空、队满的条件及求解队列元素个数。

（四）串

1.串的逻辑结构特性和串抽象数据类型的描述方法；

2.串的两类存储结构设计方法以及各自的优缺点；

3.串模式匹配的概念、BF 算法及 KMP 算法。

（五）递归

1.递归和递归模型的概念；

2.递归算法的执行过程；

3.递归算法设计的一般步骤。

（六）数组和稀疏矩阵

1.数组的逻辑结构特性和数组抽象数据类型的描述方法；

2.数组的顺序存储结构及某节点存储地址的求解；

3.对称矩阵、上三角矩阵、下三角矩阵和三对角矩阵的压缩存储；

4.稀疏矩阵的两种压缩存储方法（三元组表和十字链表）；

5.广义表的概念及求广义表的表头、表尾及深度。

（七）树和二叉树

1.树的定义及其逻辑结构特性；

2.树的遍历方法和树的存储结构；

3.二叉树的定义及其主要的五种性质；

4.二叉树与树、森林之间的转换；

5.二叉树的两种存储结构（顺序存储结构和链式存储结构）和二叉树的基本运算算

法设计（求某结点的双亲、孩子节点及二叉树深度）；

6.二叉树的遍历过程、（前序、中序、后序遍历）算法设计及其应用；

7.线索的概念，线索二叉树的特点及其构造过程；

8.哈夫曼树和哈夫曼编码的构造过程，WPL 的求值。

（八）图

1.图的定义及其逻辑结构特性，图抽象数据类型的描述方法；

2.图的基本术语及其含义；

3.图的两种主要的存储结构（邻接矩阵和邻接表）及其特点；

4.图的深度优先和广度优先遍历算法；

5.生成树的概念和最小生成树的定义和求最小生成树的 Prim 和 Kruskal 算法；

6.最短路径的概念和求最短路径的 Dijkstra 和 Flody 算法；

7.拓扑排序过程；

8.关键路径的定义及其构造过程。

（九）查找

1.掌握查找的概念；

2.线性表的顺序查找和折半查找算法，索引存储结构和分块查找方法；

3.二叉排序树的定义、查找和插入算法、删除过程；

4.平衡二叉树的特点及其调整方法；

5.B-树的定义和插入删除结点的操作过程，B+树的定义；

6.哈希表的定义、特点；

7.哈希函数构造方法和解决冲突的方法；

共 3 页 第 3 页

8.如何构造哈希表；

9.各种不同查找方法的性能（时空复杂度）比较和分析。

（十）内排序

1.排序的定义和相关概念；

2.插入排序算法，包括直接插入排序、折半插入排序和希尔排序；

3.交换排序算法，包括冒泡排序和快速排序；

4.选择排序算法，包括简单选择排序和堆排序；

5.归并排序算法，包括二路归并排序；

6.基数排序算法，包括最低位优先和最高位优先排序；

7.各种内排序方法的性能（时空复杂度）分析和比较。

原文标题：甘肃农业大学2021年全国硕士研究生招生考试初试自命题科目考试大纲

原文链接：https://yjsy.gsau.edu.cn/info/1010/88143.htm