2021年南通大学数据结构专业研究生考研考试大纲

发布时间：2020-10-26 编辑：考研派小莉推荐访问：

2021年南通大学数据结构专业研究生考研考试大纲内容如下，更多考研资讯请关注我们网站的更新！敬请收藏本站，或下载我们的考研派APP和考研派微信公众号（里面有非常多的免费考研资源可以领取，有各种考研问题，也可直接加我们网站上的研究生学姐微信，全程免费答疑，助各位考研一臂之力，争取早日考上理想中的研究生院校。）

+南通大学研究生
微信,为你答疑,送资源

2021南通大学911学前教育学研究生考试大纲 2021南通大学910发展心理学研究生考试大纲 2021南通大学907小学课程与教学研究生考试大纲 2021南通大学708心理学综合研究生考试大纲 2021南通大学708心理学综合研究生考试大纲 2021南通大学706教育学科综合研究生考试大纲 95%的同学还阅读了： 南通大学研究生招生目录南通大学研究生分数线南通大学王牌专业排名南通大学考研难吗南通大学考研调剂信息南通大学研究生导师名单南通大学研究生学费南通大学研究生奖学金

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

南通大学

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