湖北民族大学2020年硕士研究生入学考试自命题科目考试大纲-810数据结构

科目名称

数据结构

编号

810

考试专业

信息安全

一、考试性质

《数据结构》是我校信息安全专业的硕士研究生入学考试的一门专业基础课程，考试对象为参加本年度全国硕士研究生入学考试的本科应届毕业生，或具有同等学历的在职人员及其他人员。它的评价标准是计算机类专业优秀本科毕业生所能达到的及格或及格以上的水平，以保证被录取者具有较扎实的算法设计基础及有利于学校对考生的择优选拔。

二、考核目标

例：《数据结构》试卷旨在考查考生对算法基本知识、基本理论的掌握，注重考查考生灵活运用这些基础知识的能力和分析解决计算问题的能力。
具体要求如下：
1、了解数据结构及其分类、数据结构与算法的密切关系。
2、熟悉各种基本数据结构及其操作，学会根据实际问题要求来选择数据结构。
3、掌握设计算法的步骤和算法分析方法。
4、掌握数据结构在排序和查找等常用算法中的应用。
5、初步掌握文件组织方法和索引技术。

三、考试形式与试卷结构

包括：1．考试时间：考试时间为180分钟，3小时。
2．试卷满分：本试卷满分为150分。
3．考试形式：闭卷、笔试。
4．试卷题型结构：
（1）填空题约20%
（2）选择题约20%
（3）计算题约50%
（4）分析论述题约10%
5．试卷内容结构：
（1）数据结构基本概念及简单的算法分析约5%
（2）线性表约10%
（3）栈与队列约10%
（4）串约10%
（5）数组与广义表约15%
（6）树与二叉树约20%
（7）查找与排序约20%
（8）图约10%

四、考试内容

1．绪论
要求掌握数据结构的基本概念，理解数据、数据元素和数据项的概念及其相互间关系，清楚数据的逻辑结构、存储结构的联系与区别，理解抽象数据类型的概念，掌握算法的时间性能和空间性能分析。要点是分析算法的时间和空间性能。
2．线性表
要求掌握线性表的基本概念、线性表的顺序实现、线性表的链式实现、线性表顺序实现与链接实现的异同。要点是线性表的顺序结构与线性表的链式结构的插入、删除和按关键字查找的算法实现。
3．栈与队列
要求掌握栈与队列的概念与基本操作，栈的应用，链队列与循环队列的组织方法。要点是链队列与循环队列的组织方法与基本操作的实现。
4．串
要求掌握串的概念与串的表示和实现。要点是以堆形式实现的串的组织方法与基本操作的实现。
5．数组与广义表
要求掌握多维数组的结构特点及其存储地址计算方法，矩阵的压缩存储思想，广义表及其存储结构。要点是数组的存储地址计算、矩阵压缩存储地址映射关系及广义表的逻辑结构与存储结构。
6．树与二叉树
要求掌握树的基本概念、二叉树的定义与性质，二叉树的存储结构，二叉树的遍历算法，树和森林的基本概念，哈夫曼树等。要点是二叉树的顺序存储结构与链式存储结构，二叉树的遍历算法与哈夫曼编码。
7．图
要求掌握图的基本概念，图的两种存储结构(邻接矩阵和邻接表)的表示方法，图的遍历算法，图的最小生成树的概念及相关算法，拓扑排序与关健路径。要点是图的存储结构与图的遍历算法，图的拓扑排序算法。
8．查找
要求掌握查找的基本概念，静态查找表的实现，二叉排序树的概念及查找，哈希表的思想及相关算法。要点是折半查找、二叉排序树与哈希表。
9．排序
要求掌握排序的基本概念，插入排序，交换排序，选择排序，归并排序与基数排序。要点是快速排序、堆排序与归并排序算法实现与性能分析。

五、参考书目

数据结构（C语言版）、严蔚敏，吴伟民、清华大学出版社