前言
2021 年宁波大学硕士研究生招生考试初试科目
考 试 大 纲
科目代码、名称: 916 数据结构与算法
考试形式与试卷结构
（一）试卷满分值及考试时间
本试卷满分为 150 分，考试时间为 180 分钟。
（二）答题方式
答题方式为闭卷、笔试。试卷由试题和答题纸组成；答案必须写在答题纸（由考点提供）
相应的位置上。
（三）试卷内容结构
数据结构与基本算法。
（四）试卷题型结构
选择题
简答题
算法和程序设计填空题
应用题
考查目标
重点考查学生对数据结构、计算机算法、基本理论、基础知识的掌握程度。
考生应熟练掌握数据结构的基本概念、设计方法和实际应用；熟练掌握重要计算机算法的基本思想、算
法设计基本策略、算法复杂度分析；
-考生应能熟练掌握一些基本数据结构，并解决实际问题。
考查范围或考试内容概要
（一）基础
计算机中算法的角色
算法复杂度分析
递归
（二）线性表
基于顺序存储的定义和实现
基于链式存储的定义和实现
线性表的应用
(三)特殊线性表（栈、 队列、 字符串、 数组）
栈、 队列、 字符串、 数组的基本概念、 特点
栈和队列基于顺序存储的定义与实现
栈和队列基于链式存储的定义与实现
稀疏矩阵的压缩存储及转置算法实现
（四） 树与二叉树
二叉树
①二叉树的定义、 主要特征
②二叉树基于顺序存储和链式存储的实现
③二叉树重要操作的实现
④线索二叉树的基本概念和构造
树、 森林
①树的存储结构
②森林与二叉树的相互转换
③树和森林的遍历
特殊二叉树及应用
①哈夫曼（Huffman） 树
②二叉排序树
③平衡二叉树
④堆（堆的构造和调整过程）
(五) 图
1.基本的图算法
2.最小生成树
3.单源最短路径
4.最短路径
5.最大流
(六) 查找
顺序查找法
折半查找法
B 树及其基本操作、 B+树的基本概念
散列（Hash） 表
（七）排序
排序的基本概念
基于"插入"思想的排序方法
①直接插入排序
②折半插入排序
③希尔排序
基于"交换"思想的排序方法
①冒泡排序
②快速排序
基于"选择"思想的排序方法
①简单选择排序
②堆排序
基于"归并"思想的排序方法
二路归并排序
各种常用内部排序算法的特点及应用
(八) 高级的设计与分析技术
动态规划
贪婪算法
分摊分析
四、参考教材或主要参考书：
《C 程序设计》(第 4 版)，谭浩强，清华大学出版社，2010 年。
《数据结构（C 语言版）》，严蔚敏、 吴伟民，清华大学出版社，2007 年。
《算法导论》，Thomas H.Cormen、Charles E.Leiserson,潘金贵译，机械工业出版社出版（第二版）2006年。