2021年硕士研究生入学考试自命题科目

考试大纲

考试阶段：复试 科目满分值：100

考试科目：数据结构 科目代码：/

考试方式：闭卷笔试 考试时长：180分钟

一、科目的总体要求

数据结构是计算机科学与技术专业的核心必修课程,要求学生掌握各种基本的数据结构及相关的存储方式、基本操作的算法思想和和算法实现, 掌握实际数据处理中常用的几种排序方法和几种常用的数据查找方法，以及不同的排序算法之间的性能比较，不同查找算法对查找速度的影响情况。并能应用高级语言编写算法（C/C++）。

建立有关数据结构最基本的概念，包括数据的逻辑结构、存储结构和算法，算法分析的基本概念与基本方法。

掌握线性表的基本概念以及两种存储结构（顺序和链式）的构造原理，掌握在各种存储结构下对线性表进行的基本操作的算法设计。

掌握堆栈和队列的基本概念与特征，掌握在两种存储结构下如何对堆栈和队列进行插入和删除等操作，以及利用堆栈与队列解决实际问题的基本方法。

充分了解串的基本概念、掌握串的存储结构和相关的操作算法。

掌握数组、广义表和稀疏矩阵的基本概念，物理结构和基本操作的实现

充分了解二叉树型结构的逻辑特征，掌握顺序和链式存储结构的构造原理，能够熟练地利用常用的三种遍历方法（递归和非递归实现），掌握利用二叉树的遍历操作解决实际问题的方法，掌握二叉树的其它相关的操作算法。掌握树的各种存储结构和相关的操作算法。

充分了解图的逻辑结构的特点，掌握常用的两种存储方法（邻接矩阵和邻接链表），掌握最小生成树(Prim算法和Kruskal算法)、最短路径、拓扑排序、关键路径的具体求解过程。

充分了解各种顺序文件的结构与相应的查找方法；了解各种查找算法之间时空效率的差异；掌握二叉排序树的建立以及相关算法，平衡二叉树的创建过程；从结构与操作上了解散列文件的建立、散列函数的选择(构造)原则、处理散列冲突的方法以及在散列文件中查找一个记录存在与否的过程。比较各种查找方法的性能。

充分了解各种排序方法的排序特点、排序过程和算法实现，对于任意给出的数据元素序列，能够熟练地采用指定排序方法进行排序，并且能够对每一种排序方法排序过程中所进行的元素之间的比较次数、相应排序算法的时间、空间、排序的稳定性等性能进行简单分析。

二、考核内容与考核要求

1、绪论

1）数据结构的基本概念，数据的逻辑结构、存储结构。

2）算法的定义、算法的基本特性以及算法分析的基本概念。

2、线性表

1）线性关系、线性表的定义，线性表的基本操作。

2）线性表的顺序存储结构与链式存储结构(包括单链表、循环链表和双向链表)的构造原理。在以上两种存储结构上对线性表实施的最主要的操作(包括三种链表的建立、插入和删除、检索等)的算法设计。

3、堆栈与队列

1）堆栈与队列的基本概念、基本操作

2）堆栈与队列的顺序存储结构与链式存储结构的构造原理

3）在不同存储结构的基础上对堆栈与队列实施插入与删除等基本操作对应的算法设计

4）堆栈与队列的应用算法

4、串

1）串的基本概念、串的基本操作和存储结构。

2）串的模式匹配算法

5、数组和广义表

1）数组的概念、多维数组的实现

2）对称矩阵和稀疏矩阵的压缩存储

3）广义表的基本概念

6、树与二叉树

1）树的定义和性质

2）二叉树的概念、性质和实现

3）遍历二叉树和线索二叉树

4）赫夫曼树及其应用

7、图

1）图的定义，基本概念，图的分类，常用名词术语

2）图的邻接矩阵存储方法、邻接表存储方法的构造原理

3）图的遍历操作及连通性问题

4）最小生成树，最短路径，AOV网与拓扑排序，关键路径

8、查找

1）顺序表的顺序查找方法、有序顺序表的折半查找方法。

2）二叉排序树、平衡二叉树

3）散列表的构造

9、内排序

1）排序的基本概念，排序方法的分类。

2）插入排序法(含折半插入排序法和希尔排序)、选择排序法（含堆排序）、冒泡排序法、快速排序法、归并排序。各种排序方法排序的原理、规律和特点，各种排序算法的时空复杂度的简单分析。

三、题型结构

考试包含多种题型：填空题、选择题、综合题和算法编写题等。

四、其它要求

具体考试时间以《准考证》为准。

 

添加成都信息工程大学学姐微信，或微信搜索公众号“考研派小站”，关注[考研派小站]微信公众号，在考研派小站微信号输入[成都信息工程大学考研分数线、成都信息工程大学报录比、成都信息工程大学考研群、成都信息工程大学学姐微信、成都信息工程大学考研真题、成都信息工程大学专业目录、成都信息工程大学排名、成都信息工程大学保研、成都信息工程大学公众号、成都信息工程大学研究生招生）]即可在手机上查看相对应成都信息工程大学考研信息或资源。