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年。

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