|
友情提示：本站提供全国400多所高等院校招收硕士、博士研究生入学考试历年考研真题、考博真题、答案，部分学校更新至2012年，2013年；均提供收费下载。 下载流程： 考研真题 点击“考研试卷””下载; 考博真题 点击“考博试卷库” 下载
西南石油大学数据结构2020年硕士研究生招生专业课考试大纲
考试科目名称：数据结构
一、考试性质
数据结构是硕士研究生入学考试科目之一，是硕士研究生招生院校自行命题的选拔性考试。本考试大纲的制定力求反映招生类型的特点，科学、公平、准确、规范地测评考生的相关基础知识掌握水平，考生分析问题和解决问题及综合知识运用能力。应考人员应根据本大纲的内容和要求自行组织学习内容和掌握有关知识。
本大纲主要包括三大常用数据结构的逻辑、物理表示与基本操作算法实现部分的知识，各种结构的经典应用和具体问题求解。考生应掌握各种数据结构及其操作，具备一定的算法设计与分析能力，能够根据实际问题选择合适的数据结构并设计算法实现。
二、考试主要内容
（一）绪论
1、基本概念和术语
1）基本要求
了解课程的研究内容，理解数据结构的相关概念。
2）考试范围
掌握数据结构的研究内容、基本概念和相关术语；理解抽象数据类型的表示与实现。
2、算法和算法分析
1）基本要求
理解算法的含义，熟悉算法描述语言，掌握算法的性能评价指标及评价方法,并能分析常用算法的时间复杂度。
2）考试范围
算法的概念与特征；算法效率的度量指标；时间复杂度与空间复杂度的计算方法；常见时间复杂度类型与性能优劣比较。
（二）线性表
1、线性表的类型定义
1）基本要求
掌握线性表的逻辑结构及相关概念；理解线性表的抽象数据类型。
2）考试范围
线性表的概念及文件、数据项及记录的相关概念；线性表的抽象数据类型；用线性表表示集合合并的算法；合并有序线性表的算法。
2、线性表的表示和实现
1）基本要求
掌握线性表的顺序与链式两种存储结构及其各种基本运算的的实现过程；掌握两种存储方式之间的差异及各自优缺点；能够灵活运用顺序表和链表解决实际问题。
2）考试范围
顺序存储结构的概念及计算第i个元素存储地址的公式；用类C描述线性表的顺序存储结构；顺序表的初始化、插入、删除、定位和有序表合并算法；线性链表及相关概念；用C语言描述线性表的链式存储结构；链表的访问、插入、删除和有序合并算法；线性表的静态链表表示基本定义；循环链表的定义以及与单链表的区别；双向链表的定义和存储表示；双向链表的插入与删除算法；一元多项式的表示及相加算法实现。
（三）栈和队列
1、栈
1）基本要求
理解栈的定义、特性和运算；掌握栈的顺序存储实现及其性能分析；理解和掌握用栈实现表达式求解的过程；了解栈的链式存储结构的实现。
2）考试范围
栈的抽象数据类型定义；栈的先进后出特性；栈的存储表示与基本操作实现；栈的应用。
2、队列
1）基本要求
理解队列的定义、特性和运算；理解队列的顺序存储实现及其性能分析；理解循环队列的背景和实现方法；理解队列的链式存储结构的实现及其性能分析。
2）考试范围
队列的抽象数据类型定义；队列的先进先出特性；队列的存储表示与基本操作实现。
（四）串
1）基本要求
掌握串的相关概念、串的存储结构（顺序串和链式串）及基本运算的实现；掌握KMP算法的基本思想及模式匹配过程；能灵活运用串的特点解决复杂的应用问题。
2）考试范围：
串类型的定义；串的定长顺序存储、堆分配存储、块链存储表示和实现；串的模式匹配算法；串的应用。
（五）数组和广义表
1）基本要求
理解数组结构及其存储，理解矩阵的压缩存储方式及其映射关系；理解广义表以及子表、原子和长度等概念；理解广义表的基本运算及其存储。
2）考试范围：
数组的定义；二维数组的两种存储方式（以行序为主、以列序为主）及其数组元素存储位置计算公式；特殊矩阵与稀疏矩阵的压缩存储方式；广义表的定义和存储结构。
（六）树和二叉树
1）基本要求
理解树和二叉树的定义及相关术语；理解二叉树的五个性质及相关概念；理解二叉树的两种存储结构的形式、描述及特点，理解二叉树的遍历运算，并能综合应用；理解线索二叉树及其存储结构，线索化方法和算法，以及在指定线索二叉树中求解指定次序的前趋和后继的算法；理解树和森林的存储结构及其描述，树（森林）与二叉树的相互转换，树（森林）的遍历算法；理解树模型在软件设计中的作用；理解赫夫曼树的有关概念、应用及构造。
2）考试范围：
树的定义和基本术语；二叉树的定义；二叉树的性质；二叉树的存储结构；遍历二叉树；线索二叉树；树的存储结构；森林与二叉树的转换；树和森林的遍历；最优二叉树（赫夫曼树）；赫夫曼编码。
（七）图
1）基本要求
理解图的相关概念、图的存储结构；熟练掌握图的两种遍历算法（深度优先搜索遍历和广度优先搜索遍历），并能灵活应用；熟练掌握求解最小生成树的算法；熟练掌握拓扑排序算法和关键路径算法，并能灵活应用；熟练掌握最短路径算法并能灵活应用。
2）考试范围：
图的定义和术语；图的数组表示法与邻接表存储结构；图的深度优先搜索与广度优先搜索；最小生成树；拓扑排序；关键路径；最短路径。
（八）查找
1）基本要求
理解查找的相关概念，理解简单顺序查找、折半查找算法及性能分析；理解二叉排序树的定义、特性和查找算法，二叉排序树的构造、插入结点的算法和删除结点的实现方法；理解平衡二叉树的定义及构造平衡二叉树的方法；理解Ｂ-树的定义、特性和查找方法，理解在Ｂ-树中插入和删除关键字的运算实现；理解散列表结构的相关概念和构造散列函数的基本方法；理解冲突及其处理的基本方法；理解哈希查找过程；掌握上述各种查找算法的时间性能分析。
2）考试范围：
顺序表的查找；有序表的查找；索引顺序表的查找；二叉排序树和平衡二叉树；B-树和B+树；什么是哈希表；哈希函数的构造方法；处理冲突的方法；哈希表的查找及分析。
（九）内部排序
1）基本要求
理解排序的相关概念；理解直接插入排序、Shell排序、冒泡排序、快速排序、简单选择排序、堆排序和归并排序等算法的基本思想、算法实现、时间复杂度和空间占用情况，并能根据具体问题选择合适的算法。
2）考试范围：
排序概述；插入排序；交换排序；选择排序；归并排序；各种内部排序方法的分析比较。
三、考试形式和试卷结构
1、考试时间和分值
如：考试时间为180分钟，试卷满分为150分。
2、考试题型结构
（1）单项选择题：每个问题都只有一个选择，根据题目内容选择正确答案。
（2）填空题：根据题目要求，填充对应位置的内容。
（3）判断题：根据题目内容判断其描述问题的正确性。
（4）应用题：根据题目内容完成相应问题的求解，要求给出具体求解过程。
（5）算法设计题：根据题目要求，采用类C语言或C语言完成算法的编写，解决实际问题。
四、参考书目
《数据结构》（C语言版），严蔚敏，吴伟民主编，清华大学出版社，2018
免责声明：本文系转载自网络，如有侵犯，请联系我们立即删除，另：本文仅代表作者个人观点，与本网站无关。其原创性以及文中陈述文字和内容未经本站证实，对本文以及其中全部或者部分内容、文字的真实性、完整性、及时性本站不作任何保证或承诺，请读者仅作参考，并请自行核实相关内容。
|
文章搜索
您现在的位置： 
