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

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。