《数据结构》考试大纲

一、考试性质

《数据结构》考试是为渤海大学信息科学与技术学院招收硕士研究生而设置的具有选拔性质的专业考试科目，其目的是科学、公平、有效地测试学生掌握大学本科阶段数据结构的基本概念以及运用它们设计程序的能力，评价的标准是高等院校本科毕业生能够达到的及格或者及格以上水平，以保证被录取者对数据结构的相关知识有较好的掌握，为被录取者在研究生阶段的研究工作能够顺利进行做好铺垫。

二、考查目标

数据结构考试要求考生：
1、熟悉数据结构中的基本概念，能够准确、恰当的使用本学科的专业术语；
2、掌握计算机能处理的数据结构的特性；
3、能够为所处理的数据选择适当的逻辑结构、存储结构；
4、能够基于数据结构编写结构清楚和正确易读的算法；
5、初步掌握算法的时间分析和空间分析的技术。

三、考查内容

1、数据结构有关的概念和术语
（1）数据类型和抽象数据类型的概念；
（2）数据结构的基本概念和相关术语；
（3）算法，算法设计的要求，算法效率的度量。
2、线性表
（1）线性表的定义和基本操作、静态链表的概念；
（2）顺序表、单链表、循环链表和双向链表的概念，顺序表的应用；
（3）线性表的顺序存储结构及链式存储结构的定义，查找、插入和删除等基本操作的实现。
3、栈和队列
（1）栈和队列的概念、结构特性、典型应用；
（2）栈和队列的顺序存储结构和链式存储结构实现；
（3）递归的概念及执行过程。
4、数组和广义表
（1）数组的概念和数组的存储结构，广义表的存储结构；
（2）特殊矩阵和稀疏矩阵的压缩存储方法。
5、树和二叉树
（1）树的定义、表示方法和基本操作；
（2）二叉树的概念、性质、存储结构和基本操作；
（3）二叉树遍历的递归算法及非递归算法；
（4）树和森林的遍历，树与二叉树的转换方法；
（5）哈夫曼树和哈夫曼编码的概念，哈夫曼树的构造方法。
6、图算法及其应用
（1）图的基本概念、邻接矩阵和邻接表存储结构
（2）图的遍历算法；
（3）最小生成树算法和最短路径算法；
（4）有向图的拓扑排序算法。
7、查找算法及其应用
（1）静态查找表：顺序表的查找、有序表的查找、索引顺序表的查找；
（2）动态查找表：二叉排序树和平衡二叉树；
（3）哈希表：哈希函数的构造方法、冲突处理的方法、哈希表的查找及其分析。
8、排序算法及其应用
插入排序、快速排序、选择排序、堆排序、归并排序、基数排序的算法思想、复杂度分析以及它们之间的比较。