广东药科大学硕士研究生入学统一考试

《数据结构》考试大纲

《数据结构》是计算机程序设计的重要理论和实践基础课。本课程讨论软件设计中经常遇到的线性表、堆栈、队列、串、数组、二叉树、图等典型数据结构的设计方法以及各种典型排序和查找算法的性能和设计方法，并介绍各种典型数据结构的应用。要求考生了解数据的逻辑结构和物理结构之间的关系，数据结构和数据类型的关系，熟悉各种基本数据结构的概念特点存储结构，掌握排序和查找算法的分析方法，根据实际问题提出的要求学会如何选择合理的排序和查找算法，能综合利用数据结构进行算法设计和C语言进行编程实现。

第一章 绪 论

1.数据、数据元素、数据逻辑结构、数据存储结构、数据类型、抽象数据类型等;

2. 算法、算法设计的要求、算法效率的度量、算法存储空间的需求等

3. 抽象数据类型的表示和实现。

第二章 线性表

1. 线性表的定义和基本概念

2. 线性表的实现，包括顺序和链式存储结构

3. 线性表的应用

第三章 栈和队列

1. 栈和队列的定义和基本概念

2. 栈和队列的实现，包括顺序和链式存储结构

3. 栈和队列的应用

第四章 数组和广义表

1. 数组的顺序表示和实现

2. 动态数组的使用

3. 特殊矩阵的存储方式

4. 广义表的定义和存储结构

第五章 树和二叉树

1. 二叉树的定义及其主要特征

2. 二叉树顺序和链式存储结构的实现，二叉树的遍历算法

3. 线索二叉树的基本概念和构造

4. 树的定义和基本概念，树的存储结构

5. 树和森林与二叉树的转换，树和森林的遍历

6. 二叉排序树和平衡二叉树

7. 哈夫曼(Huffman)树和哈夫曼编码

第六章 图

1. 图的定义和基本概念

2. 图的存储结构，包括数组(邻接矩阵)和邻接表表示法

3. 图的遍历

4. 图的典型应用，包括最小(代价)生成树、拓扑排序和最短路径

第七章 内部排序

1. 排序的基本概念

2. 插入排序，包括直接插入排序、折半插入排序和希尔排序

3. 交换排序，包括冒泡排序和快速排序

4. 选择排序，包括简单选择排序和堆排序

5. 归并排序

6. 基数排序

7. 各种内部排序算法的比较和应用

第八章 查 找

1. 查找的基本概念

2. 静态查找表，包括顺序表的查找和有序表的查找

3. 动态查找表，包括二叉排序树和B-树及其基本操作

4. 哈希表