集美大学2023年硕士研究生入学考试初试自命题考试大纲

考试科目代码:[822]

考试科目名称:数据结构

一、考试目标

(一)考查考生对基本数据结构相关知识的理解，包括逻辑结构、存储结构和运算三者的关系;考查考生对不同算法开销的分析能力。

(二)考查考生掌握线性结构、树、图和查找、排序算法的掌握程度，要求考生在指定的数据结构和算法中完成特定问题的求解。

(三)考查考生分析问题及设计简单解决方案的能力，要求考生能针对实际问题，选择合适的数据结构和算法，设计问题求解方案。

二、试卷结构

(一)考试时间：180分钟，满分：150分。

(二)题型结构

1、选择题：30分 ;

2、程序填空题：20分;

3、综合应用题：40分

4、算法设计题：共60分。

三、 答题方式

闭卷笔试

四、考试内容

1. 绪论

考试内容：数据结构、算法等的基本概念;抽象数据类型;算法的描述和算法分析等。

考试要求：

[1] 掌握数据逻辑结构的4种基本结构，掌握数据结构中的物理存储结构与逻辑结构。

[2] 熟练掌握时间复杂度与空间复杂度、语句频度等概念及计算，了解语句频度与时间复杂度的不同，掌握大O表示法来表示时间复杂度。

2. 线性表

考试内容：线性表的逻辑结构;线性表的顺序存储结构;线性表的链式存储结构，包括单链表、循环链表和双向链表等。

考试要求：

[1] 掌握线性表的顺序存储结构和链式存储结构的表示和基本运算的实现。

[2] 熟练掌握线性表的基本操作：查找、插入、删除，尤其是链式存储结构上的编程实现，如指针在链表中的操作。理解随机访问的含义。

3. 栈和队列

考试内容：栈的抽象数据类型;栈的表示与实现;栈的应用;队列的抽象数据类型;链式队列;循环队列等。

考试要求：

[1]掌握栈的操作特性及其应用，掌握顺序栈和链栈的四要素，掌握栈的常见应用示例。

[2]掌握队列的操作特性及其应用，掌握顺序队列、循环队列和链队列的表示，掌握队列的常见应用示例。

4. 串

考试内容：串类型的定义;串的表示和实现;串的模式匹配;串操作应用等。

考试要求：

[1]掌握顺序串和链串的主要特点及其应用场合。

[2]掌握KMP算法的原理和代码实现。

5. 递归

考试内容：递归的相关概念、递归调用的实现、递归算法的设计方法。

考试要求：

[1]掌握递归算法设计的步骤。

6. 数组和广义表

考试内容：数组的定义和运算;数组的顺序存储结构;矩阵的压缩存储;广义表的表示等。

考试要求:

[1]掌握稀疏矩阵的三元组表示及基本运算的实现。

[2]掌握广义表的定义和特点。

7. 树和二叉树

考试内容：树和二叉树的定义和基本操作;二叉树的性质;二叉树的存储结构;二叉树遍历算法和应用;线索二叉树;树和森林;哈夫曼树及其应用等。

考试要求：

[1]掌握树二叉树定义和性质。

[2]掌握二叉树的各种存储结构，重点掌握二叉链表的表示。

[3]重点掌握二叉树的遍历和应用。

[4]掌握哈夫曼树的构造算法。

8. 图

考试内容：图的定义和术语;图的存储结构;图的遍历;图的连通性;有向无环图及其应用;最短路径等。

考试要求:

[1] 掌握图的相关概念和性质。

[2] 掌握图的存储结构和图的两种遍历算法。

[3] 熟练掌握两种求解最小生成树的算法(Prim算法和Kruskal 算法)

[4] 熟练掌握最短路径算法——Dijkstra算法。

9. 查找

考试内容：静态查找表;动态查找表;哈希表等。

考试要求:

[1]掌握查找的相关概念、掌握顺序查找、二分查找、分块查找的算法及性能分析。

[2]掌握折半查找的算法描述。

[3]掌握二叉排序树的构造、插入算法，掌握二叉排序树的查找长度计算。

[4]掌握哈希表的构造，掌握常见的冲突处理方法，掌握查找成功与不成功时的平均查找长度的计算。

10. 内排序

考试内容：排序的定义，排序方法的稳定性，内部排序与外部排序，排序方法的分类;插入排序;交换排序;选择排序;归并排序;基数排序;各种内部排序方法的比较分析等。

[1]掌握排序的相关概念，理解排序的稳定性。

[2]掌握快速排序，正确描述算法并分析算法的开销。

[3]掌握堆排序，深入理解排序算法，并能用代码描述。

[4]掌握各种排序算法的性能比较。

五、主要参考书目

(一)《数据结构教程》(第5版)，李春葆，清华大学出版社，2017年

(二)《数据结构》(C语言版)，严蔚敏、吴伟民编著，清华大学出版社，2007年