科目名称 数据结构 编号 810

考试专业 085404计算机技术、085412网络与信息安全

一、考试性质

本考试大纲适用于报考湖北民族大学电子信息计算机技术、网络与信息安全方法的硕士研究生入学考试。《数据结构》不仅是大学本科计算机类专业的专业基础课，也是其他从事计算机信息处理专业的一门重要的基础课程。它主要考查考生对数据的组织、存储、处理等能力，算法设计以及对算法的分析和评价的掌握程度。要求考生理解数据结构的逻辑结构和物理结构的基本概念，熟练掌握各种数据结构以及有关算法，并具有综合运用所学知识分析和解决实际问题的能力。

二、考核目标

《数据结构》试卷旨在考查考生对算法基本知识、基本理论的掌握，注重考查考生灵活运用这些基础知识的能力和分析解决计算问题的能力。

具体要求如下：

1. 了解数据结构及其分类、数据结构与算法的密切关系。

2. 掌握堆栈、队列、表、树、图等的数据结构，学会根据实际问题要求来选择数据结构。

3. 掌握设计算法的步骤和算法分析方法。

4. 掌握数据结构在排序和查找等常用算法中的应用。

5. 掌握算法的空间复杂度和时间复杂度分析的基本算法。

三、考试形式与试卷结构

1. 考试时间：考试时间为180分钟，3小时。

2. 试卷满分：本试卷满分为150分。

3. 考试形式：闭卷、笔试。

4.试卷内容结构：填空题20分，选择题45分，计算解析题60分，程序设计题25分。

四、考试内容

1. 绪论

要求掌握数据结构的基本概念，理解数据、数据元素和数据项的概念及其相互间关系，清楚数据的逻辑结构、存储结构的联系与区别，理解抽象数据类型的概念，掌握算法的时间性能和空间性能分析。要点是分析算法的时间和空间性能。

2. 线性表

要求掌握线性表的基本概念、线性表的顺序实现、线性表的链式实现、线性表顺序实现与链接实现的异同。要点是线性表的顺序结构与线性表的链式结构的插入、删除和按关键字查找的算法实现。

3.栈与队列

要求掌握栈与队列的概念与基本操作，栈的应用，链队列与循环队列的组织方法。要点是链队列与循环队列的组织方法与基本操作的实现。

4.串

要求掌握串的概念与串的表示和实现。要点是以堆形式实现的串的组织方法与基本操作的实现。

5.数组与广义表

要求掌握多维数组的结构特点及其存储地址计算方法，矩阵的压缩存储思想，广义表及其存储结构。要点是数组的存储地址计算、矩阵压缩存储地址映射关系及广义表的逻辑结构与存储结构。

6.树与二叉树

要求掌握树的基本概念、二叉树的定义与性质，二叉树的存储结构，二叉树的遍历算法，树和森林的基本概念，哈夫曼树等。要点是二叉树的顺序存储结构与链式存储结构，二叉树的遍历算法与哈夫曼编码。

7.图

要求掌握图的基本概念，图的两种存储结构(邻接矩阵和邻接表)的表示方法，图的遍历算法，图的最小生成树的概念及相关算法，拓扑排序与关健路径。要点是图的存储结构与图的遍历算法，图的拓扑排序算法。

8查找

要求掌握查找的基本概念，静态查找表的实现，二叉排序树的概念及查找，哈希表的思想及相关算法。要点是折半查找、二叉排序树与哈希表。

9.排序

要求掌握排序的基本概念，插入排序，交换排序，选择排序，归并排序与基数排序。要点是快速排序、堆排序与归并排序算法实现与性能分析。

五、参考书目

《数据结构(C语言版)》，严蔚敏等，清华大学出版社，2018年