东莞理工学院2023年全国硕士研究生入学考试《数据结构》考试大纲
第一部分 考试说明 一、考试性质 《数据结构》课程是报考计算机科学与技术专业的考试科目之一。为帮助考生明确考试复习范围和有关要求,特制定出本考试大纲。 本考试大纲适用于报考东莞理工学院计算机科学与技术2023年全国硕士研究生入学考试的准考考生。 二、考试形式与试卷结构 (一)答题时间:180分钟; (二)答题方式:闭卷,笔试; (三)总分:150分; (四)试卷结构:填空题10%,选择题20%,判断题10%,解析题40%,程序设计题20%。 三、参考书目 严蔚敏、吴伟民主编:《数据结构(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.串的匹配算法(1)BF算法(2)KMP算法(3)链式队列(4)优先级队列 基本要求:掌握和理解串的匹配算法:BF算法和KMP算法。 第5篇 数组 1.数组的概念(1)数组概念(2)数组的实现 基本要求:掌握数组的概念和数组的内存分配和实现。 2.特殊矩阵和稀疏矩阵的压缩存储(1)特殊矩阵的压缩存储(2)稀疏矩阵的压缩存储。 基本要求:掌握和理解特殊矩阵(比如对称矩阵,三角矩阵等)的压缩方法,掌握和理解稀疏矩阵的压缩存储方法。
未经允许不得转载:东莞理工学院2023年全国硕士研究生入学考试《数据结构》考试大纲