2021年南通大学硕士研究生入学考试复习大纲

    培养单位:信息科学技术学院2020年6月

    科目名称数据结构科目代码905

    考试范围及要点

    数据结构研究生考试大纲

    1.绪论

    （1）掌握数据结构的基本概念，包括数据、数据项、数据元素、数据的逻辑结构和存储结构；掌握典型的逻辑结构、存储结构。

    （2）理解算法特性，掌握算法的描述方法，包括伪码、类语言描述方法。

    （3）掌握算法时间和空间复杂度概念及分析方法。

    2.线性表

    （1）掌握线性表的相关概念、特点和基本操作（包括：创建、销毁、插入、删除、查找等）定义。

    （2）掌握线性表顺序存储的实现：

    ①顺序表的定义和特性；

    ②基本操作的实现及算法复杂度分析；

    （3）掌握线性表链式存储的实现：

    ①各种形式链表的定义和特性，包括有或无头结点的单向或双向链表、循环链表、静态链表；

    ②各种链表形式的基本操作的实现及算法复杂度分析。

    （4）能够从时间和空间复杂度的角度综合比较线性表两种存储结构的不同特点，了解各自适宜场景，能够针对具体问题选择合适的结构。

    （5）掌握有序表的定义、特点和高效算法设计方法。

    3.栈

    （1）掌握栈的相关概念、特点和基本操作（入栈、出栈等）定义。

    （2）掌握顺序栈、链栈、共享栈的实现。

    （3）掌握栈的典型应用：

    ①递归算法；

    ②表达式求值。

    4.队列

    （1）掌握队列的相关概念、特点和基本操作（入队、出队等）定义。

    （2）掌握队列的顺序存储和链式存储的实现。

    （3）了解双端队列的概念。

    5.数组

    （1）掌握数组的定义，理解它们是线性表的扩展。

    （2）掌握多维数组到一维存储的映射方法。

    （3）掌握特殊矩阵（包括：稀疏矩阵、对称矩阵、上（下）三角矩阵、对角矩阵等）的压缩存储方法。

    6.树与二叉树

    （1）掌握树的定义和术语，包括：树根、孩子、双亲、祖先、子孙、兄弟、堂兄、路径、路径长度等。

    （2）掌握树的各种逻辑结构表示、树的各种存储结构表示、树的性质、树的遍历

    方法。

    （3）掌握二叉树的定义、术语、递归特性、5种基本形态和性质。

    （4）掌握二叉树的两种存储结构：顺序存储和二叉链表存储，掌握它们各自优缺点和适用场合。

    （5）掌握二叉树的四种遍历方法：先序、中序、后序和层次遍历；理解递归遍历和非递归遍历算法的执行过程；重点掌握各种遍历算法在求解实际问题中的应用，例如：求结点个数、复制二叉树、结点查找等。

    （6）掌握基于两种遍历序列构造二叉树的过程。

    （7）掌握树或森林与二叉树之间的相互转换过程。

    （8）掌握线索二叉树的实质、二叉树线索化过程、线索二叉树的遍历算法。

    （9）掌握哈夫曼树的定义、性质、构造过程和产生哈夫曼编码的方法与过程。

    7.图

    (1)掌握图的基本概念。

    (2)掌握图的邻接矩阵和邻接表两种存储结构及其特点。

    (3)掌握图的深度优先遍历和广度优先遍历算法。

    (4)掌握图的生成树和最小生成树的概念、采用普里姆算法和克鲁斯卡尔算法构造图的最小生成树的过程。

    (5)掌握图的最短路径问题求解方法--狄杰斯特拉算法和弗洛伊德算法的原理与过程。

    (6)掌握拓扑排序的概念和求解拓扑序列算法。

    (7)掌握关键路径的概念以及求解关键路径的过程。

    8.查找

    (1)掌握静态查找和动态查找的含义及区别；成功情况下和不成功情况下平均查找长度ASL的概念。

    (2)掌握线性表上的顺序查找、折半查找算法，了解分块查找原理，能够分析些算法的特点和计算平均查找长度ASL。

    （3）掌握二叉排序树的定义、特点、存储方法、创建、结点删除和插入、查找等操作过程，并能针对具体的二叉排序树分析其成功和不成功的平均查找长度ASL。

    （4）掌握平衡二叉树的定义和调整过程。

    (5)了解B-、B+树概念。

    (6)掌握哈希表的概念、解决冲突的方法及构造，能够计算哈希查找的ASL。

    9.排序

    (1)掌握排序的基本概念。

    (2)掌握插入排序的思路和各种插入排序算法进行排序的过程，包括直接插入排序、二分插入排序和希尔排序等。

    (3)掌握交换排序的思路和各种交换排序算法进行排序的过程，包括冒泡排序、快速排序等。

    (4)掌握选择排序的思路和各种选择排序算法进行排序的过程，包括简单选择排序、树型选择排序和堆排序等。

    (5)掌握归并排序的思路和二路归并排序算法进行排序的过程。

    (6)掌握基数排序的思路以及排序过程。

    (7)掌握各种排序算法的优缺点和性能，特别是各种排序方法的时间复杂度和空间复杂度的比较。

    试题结构

    1.是非判断题：20分

    2.简答题：30分

    3.综合应用题：70分

    4.算法分析与设计：30分

    参考书目名称编者出版单位版次年份

    数据结构（C语言）严蔚敏清华大学出版社第二版2011

    数据结构管致锦清华大学出版社第一版2010

添加南通大学学姐微信，或微信搜索公众号“考研派小站”，关注[考研派小站]微信公众号，在考研派小站微信号输入[南通大学考研分数线、南通大学报录比、南通大学考研群、南通大学学姐微信、南通大学考研真题、南通大学专业目录、南通大学排名、南通大学保研、南通大学公众号、南通大学研究生招生）]即可在手机上查看相对应南通大学考研信息或资源。