西南石油大学
2020年硕士研究生招生专业课考试大纲
考试科目名称：数据结构 一、考试性质
数据结构是硕士研究生入学考试科目之一，是硕士研究生招生院校自行命题的选拔性考试。本考试大纲的制定力求反映招生类型的特点，科学、公平、准确、规范地测评考生的相关基础知识掌握水平，考生分析问题和解决问题及综合知识运用能力。应考人员应根据本大纲的内容和要求自行组织学习内容和掌握有关知识。
本大纲主要包括三大常用数据结构的逻辑、物理表示与基本操作算法实现部分的知识，各种结构的经典应用和具体问题求解。考生应掌握各种数据结构及其操作，具备一定的算法设计与分析能力，能够根据实际问题选择合适的数据结构并设计算法实现。 二、考试主要内容 （一）绪论 1、基本概念和术语 1）基本要求
了解课程的研究内容，理解数据结构的相关概念。 2）考试范围
掌握数据结构的研究内容、基本概念和相关术语；理解抽象数据类型的表示与实现。
2、算法和算法分析
1）基本要求
理解算法的含义，熟悉算法描述语言，掌握算法的性能评价指标及评价方法,并能分析常用算法的时间复杂度。 2）考试范围
算法的概念与特征；算法效率的度量指标；时间复杂度与空间复杂度的计算方法；常见时间复杂度类型与性能优劣比较。 （二）线性表 1、线性表的类型定义 1）基本要求
掌握线性表的逻辑结构及相关概念；理解线性表的抽象数据类型。 2）考试范围
线性表的概念及文件、数据项及记录的相关概念；线性表的抽象数据类型；用线性表表示集合合并的算法；合并有序线性表的算法。 2、线性表的表示和实现 1）基本要求
掌握线性表的顺序与链式两种存储结构及其各种基本运算的的实现过程；掌握两种存储方式之间的差异及各自优缺点；能够灵活运用顺序表和链表解决实际问题。 2）考试范围
顺序存储结构的概念及计算第i个元素存储地址的公式；用类C描述线性表的顺序存储结构；顺序表的初始化、插入、删除、定位和有序表合并算法；线性链表及相关概念；用C语言描述线性表的链式存储结构；链表的访问、插入、删除和有序合并算法；线性表的静态链表表示基本定义；循环链表的定义以及与单链
表的区别；双向链表的定义和存储表示；双向链表的插入与删除算法；一元多项式的表示及相加算法实现。 （三）栈和队列 1、栈 1）基本要求
理解栈的定义、特性和运算；掌握栈的顺序存储实现及其性能分析；理解和掌握用栈实现表达式求解的过程；了解栈的链式存储结构的实现。 2）考试范围
栈的抽象数据类型定义；栈的先进后出特性；栈的存储表示与基本操作实现；栈的应用。 2、队列 1）基本要求
理解队列的定义、特性和运算；理解队列的顺序存储实现及其性能分析；理解循环队列的背景和实现方法；理解队列的链式存储结构的实现及其性能分析。 2）考试范围
队列的抽象数据类型定义；队列的先进先出特性；队列的存储表示与基本操作实现。 （四）串 1）基本要求
掌握串的相关概念、串的存储结构（顺序串和链式串）及基本运算的实现；掌握KMP算法的基本思想及模式匹配过程；能灵活运用串的特点解决复杂的应用问题。
2020年西南石油大学925数据结构考研大纲硕士研究生入学考试大纲
