返回列表 发布时间:2021-06-18

东莞理工学院2022年全国硕士研究生入学考试《数据结构》考试大纲

东莞理工学院2022年全国硕士研究生入学考试《数据结构》考试大纲

 

第一部分 考试说明

一、考试性质

数据结构是报考电子信息专业的考试科目之一。为帮助考生明确考试复习范围和有关要求,特制定出本考试大纲。

本考试大纲适用于报考东莞理工学院电子信息专业2022年全国硕士研究生入学考试的准考考生。

二、考试形式与试卷结构

()答题时间:180分钟

()答题方式:闭卷,笔试

()总分:150

()试卷结构:填空题20,选择题45解析60程序设计题25

三、参考书目

《数据结构(C语言版)》,严蔚敏等,清华大学出版社,2018年

第二部分 考查要点

一、考试要求

要求学生能够掌握数据的逻辑结构、存储结构以及其它结构定义的各种运算及应用。具体要求如下:

1)掌握算法的空间复杂度和时间复杂度分析的基本算法;

2)掌握堆栈、队列、表、树、图等的数据结构;

3)掌握分类和查找等算法的实现和分析;

4)掌握算法设计的常用技术和应用。

二、考试内容

1绪论

1数据结构基本概念:(1数据、数据元素、数据类型2数据的逻辑结构和存储结构(3)数据的操作

基本要求:掌握和理解数据结构相关的基本概念

2算法和算法的时间复杂度:(1算法的概念和性质2算法的时间效率分析

基本要求:掌握和理解算法的概念和性质,掌握和理解算法的时间效率分析,初步能够分析简单算法的时间效率

2线性表

1线性表的概念

基本要求:掌握和理解线性表的定义和特性

2顺序表:1顺序表的存储结构2顺序表操作的实现3顺序表的效率分析(4)顺序表的应用

基本要求:掌握和理解顺序表的存储结构,会实现顺序表的基本操作,对顺序表的基本操作能够进行时间效率分析,能够用顺序表进行简单的应用设计和实现

3链表:1单链表的存储结构2单链表的基本操作3单链表的应用4循环单链表(5)双向链表(6)静态链表

基本要求:掌握和理解单链表的存储结构,能够实现单链表的基本操作,能够使用单链表实现初步应用,能够分析单链表操作的时间复杂度,掌握和理解循环单链表,双向链表和静态链表的概念和特点,能够实现简单的循环单链表,双向链表和静态链表的基本操作

3堆栈和队列

1堆栈1堆栈的概念2堆栈的顺序和链式实现

基本要求:掌握堆栈的概念和特点,能实现顺序堆栈和链式堆栈的基本操作。

2队列1队列的基本概念2顺序循环队列3链式队列(4)优先级队列

基本要求:掌握队列的概念和特点,掌握顺序循环队列的概念和特点,能够实现队列的基本操作,掌握优先级队列的概念

3堆栈和队列的应用

基本要求:理解堆栈和队列的经典应用:括号匹配问题,算术表达式计算问题,迷宫问题,调度问题。

4

1串的概念和存储结构1串的概念2串的存储结构和基本算法的实现

基本要求:掌握串的概念,串的存储结构(静态存储结构和动态存储结构),能够实现串的基本操作。

2串的匹配算法1BF算法2KMP算法3链式队列(4)优先级队列

基本要求:掌握和理解串的匹配算法:BF算法和KMP算法

5 数组

1数组的概念1数组概念2数组的实现

基本要求:掌握数组的概念和数组的内存分配和实现。

2特殊矩阵和稀疏矩阵的压缩存储1特殊矩阵的压缩存储2稀疏矩阵的压缩存储。

基本要求:掌握和理解特殊矩阵(比如对称矩阵,三角矩阵等)的压缩方法,掌握和理解稀疏矩阵的压缩存储方法。

6 递归算法和广义表

1递归算法1递归算法概念2递归算法的设计

基本要求:掌握递归算法的概念,递归算法的执行过程,初步能够使用递归算法设计和解决问题。

2广义表1广义表的概念2广义表的存储结构和操作实现。

基本要求:掌握和理解广义表概念,掌握和理解广义表的存储结构和基本操作算法的实现。

7 树和二叉树

1树的概念1树的概念2树的存储结构

基本要求:掌握和理解有关树的概念,掌握和理解树的常用存储结构。

2二叉树1二叉树的概念和性质2二叉树的存储结构和基本算法实现。

基本要求:掌握和理解二叉树的概念和基本性质,掌握和理解二叉树的存储结构(特别是链式存储结构),能够实现二叉树的基本算法。

3二叉树的遍历算法1深度递归和广度递归算法2遍历算法的应用

基本要求:掌握理解二叉树深度遍历(前序,中序和后序)的递归和非递归算法,能够用二叉树遍历思想解决一些树的问题。

4线索二叉树

基本要求:掌握和理解线索二叉树的概念。

5哈夫曼树1哈夫曼树的概念2哈夫曼编码问题。

基本要求:掌握和理解哈夫曼树的概念,掌握和理解哈夫曼编码问题的实现。

6树与二叉树的转换1树的遍历2树和二叉树的转换

基本要求:掌握和理解树的遍历方法,能够进行树和二叉树的转换。

8

1图的概念和存储结构1树的相关概念2图的存储结构 3)图的基本算法实现

基本要求:掌握和理解有关图的相关概念,掌握和理解图的常用存储结构,掌握和理解图的基本操作算法的实现。

2图的遍历算法

基本要求:掌握和理解图的深度遍历和广度遍历的算法以及算法的实现。

3最小生成树1最小生成树概念2普利姆算法(3)克鲁斯卡尔算法

基本要求:掌握理解最小生成树概念和性质,掌握和理解最小生成树的两种经典算法:普利姆算法和克鲁斯卡尔算法。

4最短路径、拓扑排序和关键路径

基本要求:掌握和理解求最短路径算法,拓扑算法和关键路径算法。

9 排序

1排序的概念

基本要求:掌握和理解排序的概念,掌握和理解各类排序算法的特点和时空复杂度分析。

2插入排序(1)直接插入排序(2)希尔排序

基本要求:掌握和理解插入排序思想,能够实现插入排序算法,能够分析插入排序算法的时空复杂度。

3选择排序1直接选择排序2堆排序

基本要求:掌握和理解选择排序思想,能够实现选择排序算法,能够分析选择排序算法的时空复杂度。

4交换排序(1)冒泡排序(2)快速排序

基本要求:掌握和理解交换排序思想,能够实现交换排序算法,能够分析交换排序算法的时空复杂度。

5归并排序

基本要求:掌握和理解归并排序思想,能够实现归并排序算法,能够分析归并排序算法的时空复杂度。

6基数排序

基本要求:掌握和理解基数排序思想,能够实现基数排序算法,能够分析基数排序算法的时空复杂度。

10 查找

1查找的概念

基本要求:掌握和理解查找的相关概念,掌握和理解各类查找算法的特点和时空复杂度分析。

2静态查找(1)顺序查找(2)二分查找(3)索引查找

基本要求:掌握和理解静态查找思想,能够实现顺序查找和二分查找算法,能够分析静态查找算法的时空复杂度。

3动态查找1二叉排序树

基本要求:掌握和理解动态查找思想,能够实现二叉排序树的创建,插入,查找和删除算法,能够分析动态查找算法的时空复杂度。

4哈希查找(1)哈希查找的概念(2)哈希函数(3)哈希冲突的解决方法

基本要求:掌握和理解哈希查找思想,掌握常用的哈希函数和哈希冲突的解决方法。