发布时间：2020-10-26 编辑：考研派小莉 推荐访问：
2021年南通大学数据结构专业研究生考研考试大纲

2021年南通大学数据结构专业研究生考研考试大纲的内容如下，更多考研资讯请关注我们考研派网站的更新！敬请收藏本站。或下载我们的考研派APP和考研派微信公众号（里面有非常多的免费考研资源可以领取哦）[2021年南通大学药学综合专业研究生考研参考书目] [2021年南通大学地理学科基础专业研究生考研参考书目] [2021年南通大学体育科学研究方法专业研究生考研参考书目] [2021年南通大学体育概论专业研究生考研参考书目] [2021年南通大学卫生综合（专硕）专业研究生考研参考书目] [2021年南通大学卫生综合（学硕）专业研究生考研参考书目]

南通大学学姐微信
为你答疑,送资源

95%的同学还阅读了： [2021南通大学研究生招生] [南通大学研究生分数线[2013-2020]] [南通大学王牌专业排名] [南通大学考研难吗] [南通大学研究生院] [南通大学考研群] [南通大学研究生学费] [南通大学研究生奖学金] [南通大学研究生辅导] [南通大学在职研究生招生简章] [考研国家线[2006-2020]] [2021年考研时间：报名日期和考试时间]

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
 

本文来源：http://m.okaoyan.com/nantongdaxue/cankaoshumu_364015.html