广东药科大学研究生

入学考试《8--数据结构》考试大纲

（电子信息硕士专业学位使用）

考试目标

  《数据结构》是报考电子信息专业硕士的考试科目之一。为帮助考生明确考试复习范围和有关要求，特制定出本考试大纲。本考试大纲适用于报考广东药科大学电子信息专业全国硕士研究生入学考试的准考考生。

考试形式和试卷结构

1. 答题方式

闭卷、笔试

2. 题量、题分及考试时间

总分为150分，考试时间为180分钟。

（一） 绪论

1．考核知识点

数据结构；抽象数据类型；算法；算法的时间复杂度；算法的空间复杂度。

2．考核内容

(1)数据结构的基本概念和术语；

(2)抽象数据类型的表示与实现；

(3)算法的基本概念和算法的性能分析方法。

（二） 线性表

1．考核知识点

线性表；顺序表；链表；顺序存储结构；链式存储结构。

2．考核内容

(1)线性表的定义和逻辑结构特性；

(2)线性表的顺序存储方法和基本操作算法实现；

(3)线性表的链式存储方法和基本操作算法实现；

（三）栈和队列

1．考核知识点

栈；递归；链队列；循环队列。

2．考核内容

(1)掌握栈的类型定义、表示和基本操作的实现；

(2)运用栈的特性设计算法；

(3)递归算法的设计思路和设计方法；

(4)队列的类型定义、表示和基本操作的实现

（四）串

1．考核知识点

串的定义、基本运算算法，串的模式匹配定义和算法。

2．考核内容

(1)串类型的定义及其表示方法；

(2)串基本算法的实现方法；

(3)串的应用算法。

（五）数组和广义表

1．考核知识点

数组；稀疏矩阵；广义表的定义和基本运算

2．考核内容

(1) 数组的定义和数组的顺序表示方法；

(2) 数组元素顺序存储的地址计算；

(3) 特殊矩阵和稀疏矩阵的压缩存储方法；

(4) 广义表的定义和基本运算；

（六）树和二叉树

1．考核知识点

二叉树的存储结构及其遍历的方法；二叉树的线索化；哈夫曼树的构造方法及其编码的生成。

2．考核内容

(1) 树和二叉树的定义、术语和基本逻辑结构特性；

(2) 二叉树的基本性质；

(3) 二叉树存储结构；

(4) 二叉树的遍历算法思想，掌握递归和非递归遍历算法实现；

(5) 线索二叉树的基本概念和相应算法；

(6) 树和森林的存储方法及与二叉树的之间的转换方法；

（七）图

1．考核知识点

图的逻辑结构；邻接表；深度优先遍历；广度优先遍历；最小生成树、拓扑排序、关键路径、  最短路径。

2．考核内容

(1) 图的基本概念、术语和基本逻辑结构特征；

(2) 图的存储结构；

(3) 图的深度优先和广度优先遍历算法；

(4) 最小生成树、拓扑排序、关键路径、最短路径的应用。

（八）查找

1．考核知识点

顺序查找；折半查找；分块查找；二叉排序树；平衡二叉树；哈希表。

2．考核内容

(1) 静态查找表、动态查找表和哈希查找的基本概念；

(2) 静态查找表的各种查找方法如：顺序查找、折半查找、分块查找；

(3) 动态查找表的各种查找方法如二叉排序树与平衡二叉树，B树等；

(4) 哈希表的概念和查找方法和哈希函数的构造方法、解决冲突的基本方法；

（九）排序

1．考核知识点

直接插入排序；希尔排序；冒泡排序；快速排序；堆排序；归并排序；基数排序。

2．考核内容

(1) 排序的基本概念；

(2) 基于插入思想的排序算法如：直接插入排序、希尔排序；

(3) 基于交换思想的排序算法如：冒泡排序、快速排序；

(4) 基于选择思想的排序算法如：简单选择排序、堆排序；

(5) 其它排序算法如：归并排序、基数排序；

 参考书目：

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

 完整版大纲请下载附件查看：

2023《902数据结构》考试大纲.doc