2019年宁波大学917数据结构与程序设计（计算机技术）考研大纲硕士研究生入学考试大纲

第 1 页，共 4 页
2019 年宁波大学硕士研究生招生考试初试科目
考 试 大 纲
科目代码、名称: 917 数据结构与程序设计
一、考试形式与试卷结构
（一）试卷满分值及考试时间
本试卷满分为 150 分，考试时间为 180 分钟。
（二）答题方式
答题方式为闭卷、笔试。试卷由试题和答题纸组成；答案必须写在答题纸（由考点提供）
相应的位置上。
（三）试卷内容结构
考试内容主要包括 C 语言程序设计（30%-40%）和数据结构（70%-60%）。
（四）试卷题型结构
1.选择题
2.简答题
3.算法和程序设计填空题
4.应用题
二、考查目标
在考查基本概念、基本知识、基本方法的基础上，注重考查学生运用基本知识来分析和
解决实际问题的能力，注重考查数据结构算法和程序设计的能力。
三、考查范围或考试内容概要
（一）C 语言程序的基本结构
1. 数据类型及表达式
2. 基本语句、选择结构、循环结构
3. 数组：掌握一维数组和二维数组的定义、初始化和数组元素的引用。
4. 函数：掌握函数的定义、参数和返回值的定义、函数原型声明。掌握形参和实
第 2 页，共 4 页
参的定义和传递。掌握递归函数的使用。理解和使用局部变量、静态变量、全
局变量。掌握变量的存储类别和使用，变量的作用域和生存期。
5. 指针：理解地址与指针变量的概念，掌握指针的定义、使用和相关运算符。掌
握数组指针和字符串的指针操作、能用指针作为函数参数和返回值。理解和掌
握指针数组，指向指针的指针
6. 结构体与共同体：掌握结构体和共用体类型数据的定义使用，掌握结构体相关
的运算符的使用。能熟练使用结构体构成链表，掌握链表的建立、删除、插入
与查找，掌握内存的动态分配和释放。
（二）一般线性表
1. 基于顺序存储的定义和实现
2. 基于链式存储的定义和实现
3. 线性表的应用
(三)特殊线性表（栈、 队列、 字符串、 数组）
1. 栈、 队列、 字符串、 数组的基本概念、 特点
2. 栈和队列基于顺序存储的定义与实现（方式、 特点）
3. 栈和队列基于链式存储的定义与实现（方式、 特点）
4. 稀疏矩阵的压缩存储及转置算法实现
（四） 树与二叉树
1. 二叉树
①二叉树的定义、 主要特征及相关特征的证明
②二叉树基于顺序存储和链式存储的实现
③二叉树重要操作的实现（建立、 遍历、 计算叶子结点、 结点、 深度等）
④线索二叉树的基本概念和构造
2. 树、 森林
①树的存储结构（重点掌握子女-兄弟表示）
②森林与二叉树的相互转换
③树和森林的遍历
第 3 页，共 4 页
3. 特殊二叉树及应用
①哈夫曼（Huffman） 树和哈夫曼编码的构造过程
②二叉排序树
③平衡二叉树
④堆（堆的构造和调整过程）
(五) 图
1. 图的基本概念
2. 图的存储及基本操作
①邻接矩阵存储（无向图、 有向图、 无向带权图、 有向带权图）
②邻接表存储（无向图、 有向图、 无向带权图、 有向带权图）
③各种存储方式下操作的算法实现（图的建立、 遍历、 插入边、 删除边等）
3. 图的遍历
①深度优先遍历（思想、 过程及算法实现）
②广度优先遍历（思想、 过程及算法实现）
4. 图的基本应用（掌握算法的思想、 过程）
①最小生成树问题
②最短路径问题
③有向图与工程（AOV 网与拓扑排序， AOE 网与关键路径）
(六) 查找
1. 查找的基本概念
2. 顺序查找法（监视哨法的思想和算法）
3. 折半查找法（思想和算法）
4. B 树及其基本操作、 B+树的基本概念（思想和过程）
5. 散列（Hash） 表（Hash 函数和解决冲突的方法的思想和过程）
6. 查找算法的时间复杂度、 平均查找长度的分析
（七）排序
1. 排序的基本概念
第 4 页，共 4 页
2. 基于"插入"思想的排序方法
①直接插入排序
②折半插入排序（思想和过程）
③希尔排序（思想和过程）
3. 基于"交换"思想的排序方法
①冒泡排序（思想、 过程和算法）
②快速排序（思想、 过程和算法）
4. 基于"选择"思想的排序方法
①简单选择排序（思想、 过程和算法）
②堆排序（思想和过程）
5. 基于"归并"思想的排序方法
二路归并排序（思想、 过程）
6. 各种常用内部排序算法的特点及应用
四、参考教材或主要参考书：
《C 程序设计》(第 4 版)，谭浩强，清华大学出版社，2010。
《数据结构（C 语言版）》，严蔚敏、 吴伟民编著， 清华大学出版社.2007。