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

《2021年硕士研究生入学考试自命题科目考试大纲.pdf》由会员分享，可在线阅读，更多相关《2021年硕士研究生入学考试自命题科目考试大纲.pdf（4页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、2021年硕士研究生入学考试自命题科目考试大纲考试阶段：复试 科目满分值：100考试科目：数据结构 科目代码：/考试方式：闭卷笔试 考试时长：180分钟一、科目的总体要求数据结构是计算机科学与技术专业的核心必修课程，要求学生掌握各种基本的数据结构及相关的存储方式、基本操作的算法思想和和算法实现，掌握实际数据处理中常用的几种排序方法和几种常用的数据查找方法，以及不同的排序算法之间的性能比较，不同查找算法对查找速度的影响情况。并能应用高级语言编写算法(C/C+)o建立有关数据结构最基本的概念，包括数据的逻辑结构、存储结构和算法，算法分析的基本概念与基本方法。掌握线性表的基本概念以及两种存储结构(顺

2、序和链式)的构造原理，掌握在各种存储结构下对线性表进行的基本操作的算法设计。掌握维栈和队列的基本概念与特征，掌握在两种存储结构下如何对堆栈和队列进行插入和删除等操作，以及利用堆栈与队列解决实际问题的基本方法。充分了解串的基本概念、掌握串的存储结构和相关的操作算法。掌握数组、广义表和稀疏矩阵的基本概念，物理结构和基本操作的实现充分了解二叉树型结构的逻辑特征，掌握顺序和链式存储结构的构造原理，能够熟练地利用常用的三种遍历方法（递归和非递归实现），掌握利用二叉树的遍历操作解决实际问题的方法，掌握二叉树的其它相关的操作算法。掌握树的各种存储结构和相关的操作算法。充分了解图的逻辑结构的特点，掌握常用的两

3、种存储方法（邻接矩阵和邻接链表），掌握最小生成树（P r i m算法和K r u s k a l算法）、最短路径、拓扑排序、关键路径的具体求解过程。充分了解各种顺序文件的结构与相应的查找方法；了解各种查找算法之间时空效率的差异；掌握二叉排序树的建立以及相关算法，平衡二叉树的创建过程；从结构与操作上了解散列文件的建立、散列函数的选择（构造）原则、处理散列冲突的方法以及在散列文件中查找一个记录存在与否的过程。比较各种查找方法的性能。充分了解各种排序方法的排序特点、排序过程和算法实现，对于任意给出的数据元素序列，能够熟练地采用指定排序方法进行排序，并且能够对每一种排序方法排序过程中所进行的元素之间的

4、比较次数、相应排序算法的时间、空间、排序的稳定性等性能进行简单分析。二、考核内容与考核要求1、绪论1）数据结构的基本概念，数据的逻辑结构、存储结构。2）算法的定义、算法的基本特性以及算法分析的基本概念。2、线性表1）线性关系、线性表的定义，线性表的基本操作。2）线性表的顺序存储结构与链式存储结构（包括单链表、循环链表和双向链表）的构造原理。在以上两种存储结构上对线性表实施的最主要的操作（包括三种链表的建立、插入和删除、检索等）的算法设计。3、堆栈与队列1）堆栈与队列的基本概念、基本操作2）堆栈与队列的顺序存储结构与链式存储结构的构造原理3）在不同存储结构的基础上对堆栈与队列实施插入与删除等基本

5、操作对应的算法设计4）堆栈与队列的应用算法4、串1）串的基本概念、串的基本操作和存储结构。2）串的模式匹配算法5、数组和广义表1）数组的概念、多维数组的实现2）对称矩阵和稀疏矩阵的压缩存储3）广义表的基本概念6、树与二叉树1）树的定义和性质2）二叉树的概念、性质和实现3）遍历二叉树和线索二叉树4）赫夫曼树及其应用7、图1）图的定义，基本概念，图的分类，常用名词术语2）图的邻接矩阵存储方法、邻接表存储方法的构造原理3）图的遍历操作及连通性问题4）最小生成树，最短路径，A O V网与拓扑排序，关键路径8、查找1）顺序表的顺序查找方法、有序顺序表的折半查找方法。2）二叉排序树、平衡二叉树3）散列表的构造9、内排序1）排序的基本概念，排序方法的分类。2）插入排序法（含折半插入排序法和希尔排序）、选择排序法（含堆排序）、冒泡排序法、快速排序法、归并排序。各种排序方法排序的原理、规律和特点，各种排序算法的时空复杂度的简单分析。三、题型结构考试包含多种题型：填空题、选择题、综合题和算法编写题等。四、其它要求具体考试时间以 准考证为准。