研究生考试大纲（数据结构）

一、考试科目：数据结构

二、适用专业：职业技术教育

三、参考书目

(1) 数据结构（C语言版），严蔚敏主编，2011，清华大学出版社。

四、考查目标

(1) 理解数据结构的基本概念；掌握数据的基本逻辑结构、存储结构及其差异以及各种基本操作的实现；能够选择合适的数据结构和方法进行问题求解。

(2) 能够对算法进行设计与分析。

(3) 了解常用面向对象的编程语言特点和编程规范

(4) 熟练应用C程序语言编写和实现简单应用程序（如数据结构算法等）

(5) 了解数据结构算法与计算机程序设计的关系，具有运用所学知识分析和解决问题的能力。

五、考查范围

（一）数据结构考查范围

1、数据结构基本概念及简单的算法分析

　　(1) 什么是数据结构。

　　(2) 抽象数据类型及面向对象概念：数据类型；数据抽象与抽象数据类型；面向对象的概念；用于描述数据结构的语言。

　　(3) 数据结构的抽象层次。

　　(4) 算法定义。

　　(5) 性能分析与度量：算法的性能标准；算法的后期测试；算法的事前估计；空间复杂度度量；时间复杂度度量。

2、线性表

(1)线性表的定义和基本操作。

(2)线性表的实现：线性表的顺序存储结构；线性表的链式存储结构。

(3)线性表的应用。

3、栈和队列

　 (1) 栈：栈的抽象数据类型；栈的顺序存储表示；栈的链接存储表示。

(2) 队列 ：队列的抽象数据类型；队列的顺序存储表示；队列的链接存储表示。

　　(3) 优先级队列：优先级队列的定义；优先级队列的存储表示。

4、串

(1) 字符串的抽象数据类型；串的存储表示；字符串操作的实现。

　 (2) 串的应用。

5、数组和广义表

(1)数组的定义和初始化；数组的顺序存储方式。

(2)顺序表：顺序表的定义和特点；顺序表的类定义；顺序表的查找、插入和删除；使用顺序表的事例。

(3)矩阵的压缩存储。

6、树和二叉树

(1)树的概念。

(2)二叉树：二叉树的定义及其主要特征；二叉树的顺序存储结构和链式存储结构；二叉树的遍历。

(3) 线索二叉树的基本概念和构造。

(4) 堆；二叉排序树；平衡二叉树。

(5) 树：树的存储结构；树的遍历。

(6) 树的应用：最优二叉树；哈夫曼（Huffman）树和哈夫曼编码。

7、图

(1) 图的定义及基本术语。

(2) 图的存储及基本操作：数组表示法；邻接矩阵；邻接表；十字链表；

(3) 图的遍历：深度优先搜索；广度优先搜索

(4) 图的连通性问题：无向图的连通分量和生成树；最小生成树。

8、查找

(1) 查找的基本概念。

(2) 静态查找表：顺序表的查找；有序表的查找；静态树表的查找；索引顺序表的查找。

(3) 动态查找表：折半查找；分块查找；二叉排序树查找；

(4) B_树：B_树的定义；B_树的插入；B_树的删除

(5) 哈希表：哈希表与哈希方法。

9、排序

(1) 排序的基本概念及各种排序算法比较。

(2) 插入排序：直接插入排序；对分插入排序；链表插入排序；希尔排序。

(3) 交换排序：起泡排序；快速排序。

(4) 选择排序：直接选择排序；锦标赛排序；堆排序。

(5) 归并排序：归并；迭代的归并排序算法；递归的表归并排序。