搜索
第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。