2021宁波大学数据结构与算法（科教融合学院）研究生考试大纲及参考书目

2021年宁波大学硕士研究生招生考试初试科目

考　试　大　纲

科目代码、名称:916数据结构与算法

一、考试形式与试卷结构

（一）试卷满分值及考试时间

本试卷满分为150分，考试时间为180分钟。

（二）答题方式

答题方式为闭卷、笔试。试卷由试题和答题纸组成；答案必须写在答题纸（由考点提供）相应的位置上。

（三）试卷内容结构

数据结构与基本算法。

（四）试卷题型结构

1.选择题

2.简答题

3.算法和程序设计填空题

4.应用题

二、考查目标

重点考查学生对数据结构、计算机算法、基本理论、基础知识的掌握程度。考生应熟练掌握数据结构的基本概念、设计方法和实际应用；熟练掌握重要计算机算法的基本思想、算法设计基本策略、算法复杂度分析；考生应能熟练掌握一些基本数据结构，并解决实际问题。

三、考查范围或考试内容概要

（一）基础

1.计算机中算法的角色

2.算法复杂度分析

3.递归

（二）线性表

1.基于顺序存储的定义和实现

2.基于链式存储的定义和实现

3.线性表的应用

(三)特殊线性表（栈、队列、字符串、数组）

1.栈、队列、字符串、数组的基本概念、特点

2.栈和队列基于顺序存储的定义与实现

3.栈和队列基于链式存储的定义与实现

4.稀疏矩阵的压缩存储及转置算法实现

（四）树与二叉树

1.二叉树

①二叉树的定义、主要特征

②二叉树基于顺序存储和链式存储的实现

③二叉树重要操作的实现

④线索二叉树的基本概念和构造

2.树、森林

①树的存储结构

②森林与二叉树的相互转换

③树和森林的遍历

3.特殊二叉树及应用

①哈夫曼（Huffman）树

②二叉排序树

③平衡二叉树

④堆（堆的构造和调整过程）

(五)图

1.基本的图算法

2.最小生成树

3.单源最短路径

4.最短路径

5.最大流

(六)查找

1.顺序查找法

2.折半查找法

3.B树及其基本操作、B+树的基本概念

4.散列（Hash）表

（七）排序

1.排序的基本概念

2.基于"插入"思想的排序方法

①直接插入排序

②折半插入排序

③希尔排序

3.基于"交换"思想的排序方法

①冒泡排序

②快速排序

4.基于"选择"思想的排序方法

①简单选择排序

②堆排序

5.基于"归并"思想的排序方法

二路归并排序

6.各种常用内部排序算法的特点及应用

(八)高级的设计与分析技术

1.动态规划

2.贪婪算法

3.分摊分析

四、参考教材或主要参考书：

《C程序设计》(第4版)，谭浩强，清华大学出版社，2010年。

《数据结构（C语言版）》，严蔚敏、吴伟民，清华大学出版社，2007年。

《算法导论》，ThomasH.Cormen、CharlesE.Leiserson,潘金贵译，机械工业出版社出版（第二版）2006年。