2018年宁波大学数据结构考研大纲

第 1 页，共 3 页
2018 年宁波大学硕士研究生招生考试复试科目
考 试 大 纲
科目名称: 数据结构
一、考试形式与试卷结构
（一）试卷满分及考试时间
本试卷满分为 100 分，考试时间为 120 分钟。
（二）答题方式
答题方式为闭卷、笔试。
（三）试卷题型结构
1.选择题； 2.填空题； 3.简答题； 4.算法设计题。
二、考查目标（复习要求）
《数据结构》是计算机程序设计的重要理论技术基础，通过本课程学习，理解计算机加
工的数据结构的特性，掌握各类数据结构的灵活应用，为应用涉及的数据选择适当的逻辑结
构、存储结构及其相应的算法，并掌握算法的时间复杂度和空间复杂度的简要分析技术。重
点掌握以下内容：复杂度分析、链表、栈和队列、递归、二叉树、B-树、图、堆与优先级队
列、排序、哈希方法等。深透地理解数据结构的基本概念以及有关算法，进行复杂程序设计
的训练，提高抽象设计能力。培养良好的程序设计技能，编写的程序正确高效、结构清晰易
读，提高解决实际问题的能力。
三、考查范围或考试内容概要
（一）数据结构和算法简介
1. 数据结构、逻辑结构、存储结构和抽象数据类型的基本概念。
2. 了解各种算法描述方法和算法设计的基本要求。
3. 掌握对算法的复杂度分析方法。
（二）线性结构
1. 理解线性表的概念、定义、逻辑结构和存储结构。
2. 熟练掌握线性表的顺序结构及其各种基本运算。
3. 熟练掌握单链表、循环链表、双向链表的存储结构及其各种基本运算，
理解链表的应用。
4. 掌握栈的定义、表示、实现和应用。
第 2 页，共 3 页
5. 掌握递归的概念和递归的实现过程。
6. 掌握队列的定义以及顺序和链式存储结构的实现。
7. 了解串的基本概念及顺序和链式存储结构，掌握串的各种基本运算，
了解串的模式匹配算法。
8. 掌握数组的顺序存储结构。
9. 理解稀疏矩阵的三元组存储结构和基本运算，十字链表存储结构。
10. 理解广义表的基本概念，掌握广义表的存储结构。
（三）树结构
1. 理解树的基本概念及其存储结构。
2. 熟练掌握二叉树的定义、性质以及各种存储结构和遍历算法。
3. 掌握线索二叉树的概念、存储结构及线索化算法。
4. 掌握树和森林与二叉树间的转换，掌握树和森林的遍历算法。
5. 掌握 B-树的概念、存储结构、B-树的插入与删除等操作
6. 掌握哈夫曼树的概念、存储结构和应用。
（四）图结构
1. 理解图的基本概念，掌握图的邻接矩阵和邻接表的存储结构。
2. 了解十字链表，邻接多重表等存储结构。
3. 熟练掌握图的深度优先和广度优先遍历算法。
4. 理解图的连通性、最小生成树的概念。
5. 掌握求最小生成树算法。
6. 理解有向无环图的概念，掌握拓扑排序和关键路径算法。
7. 理解带权最短路径的概念，掌握求最短路径的算法。
8. 了解加权图的最大流最小割算法。
（五）查找
1. 理解查找的概念及其效率的评价方法。
2. 理解静态查找表的概念，熟练掌握顺序、折半和分块查找算法。
3. 理解动态查找表和二叉排序树的概念。
4. 了解平衡二叉树的概念。
5. 理解哈希表的含义，掌握哈希函数的构造和处理冲突的基本方法。
（六）排序
1. 掌握插入类排序的算法：直接插入排序、希尔排序。
第 3 页，共 3 页
2. 掌握交换类排序的算法：冒泡排序、快速排序。
3. 掌握选择类排序的算法：简单选择排序、堆排序。
4. 了解归并排序、基数排序的思想，了解外排序的概念。
参考教材或主要参考书：
《数据结构》(C 语言版)，严蔚敏、吴伟民，清华大学出版社，2011。