河北工程大学数据结构2011年考研大纲

　　河北工程大学数据结构硕士研究生招生考试初试自命题科目考试大纲

　　课程名称：数据结构

　　课程编码：812

　　适用专业(领域)：计算机技术

　　一、考试性质

　　数据结构是河北工程大学为招收计算机技术领域工程硕士研究生而设置的全国研究生招生考试业务课程考试科目，属学校自行命题的性质。它的评价标准是高等学校优秀本科毕业生能达到的及格或及格以上水平，以保证被录取者具有基本的数据结构知识并有利于招生学校在专业上择优选拔。

　　二、考试的学科范围

　　应考范围包括：数据结构的基本概念、线性表、栈与队列、串、数组和广义表、树和二叉树、图、查找、内部排序等内容

　　三、评价目标

　　数据结构考试的目标在于考查考生对数据结构的基础知识、基本理论和基本技能的掌握情况，考察考生综合运用所学知识分析和解决问题的能力。考生应能：

　　1.系统地理解数据结构的基本概念;

　　2.掌握各种基本数据结构(线性结构、树形结构、图形结构)的定义、应用和实现;

　　3.掌握常用的两种数据处理技术：查找和排序;

　　4.掌握在不同的存储结构上实现算法的设计思想，从中体会和掌握选择数据结构的方法和算法设计的思考方式及技能，提高分析问题和解决问题的能力。

　　四、考试形式与试卷结构

　　1.答卷方式：闭卷，笔试;试卷中的所有题目按试卷要求回答。

　　2.试卷分数：满分为150分。

　　3.试卷结构及题型比例：

　　试卷主要分为三大部分，即：基本概念和知识、基本理论分析题，约占40%;应用作图方法或简单计算，使用给定数据建立或操作一些数据结构的试题，约占40%题;综合算法设计题约占20%。

　　五、考试内容要点

　　1.绪论

　　数据结构的基本概念，包括逻辑结构、物理结构的基本概念、两者之间的区别与联系。

　　算法的基本概念和性质。 算法的复杂度的基本概念，并掌握对非递归代码的复杂度计算的基本方法。

　　2.线性表

　　线性表的逻辑结构定义。线性表的顺序结构实现，以及顺序结构下的基本操作的实现，

　　并能写出操作代码。线性表的链式结构实现，以及链式结构下的基本操作的实现，并能写出操作代码。能够设计针对顺序结构和链式结构线性表的一般应用问题的算法，并编写算法代码。

　　栈的基本概念、栈的性质。 栈的顺序结构和链式结构实现，以及相应的操作的实现，能够写出操作代码。栈与递归的关系，能够编写递归算法，能够将递归算法转换为非递归形式。栈的应用方法，能够运用栈解决相关问题，并编写出算法代码。队列的基本概念和性质。队列的顺序结构和链式结构实现，以及相应操作的实现，能够写出操作代码。

　　3.串

　　串的概念，串与一般线性表的差别。串的基本操作的实现。串的朴素模式匹配算法。改进KMP算法的思想和步骤，能够手工计算出模式串的nextval向量。

　　4.数组、稀疏矩阵和广义表

　　了解多维数组的概念，以及多维数组的一维数组实现。掌握多维下标向一维下标的换算算法，并能进行手工计算。掌握稀疏矩阵的三元组结构。了解广义表的概念。

　　5.树和二叉树

　　树的定义和性质。

　　二叉树的概念。二叉树的基本性质，并能够进行描述和证明。掌握二叉树的二叉链结构的实现。掌握二叉树的前序遍历、中序遍历、后序遍历和层次遍历规则，能够手工写出二叉树的遍历序。掌握二叉树的遍历性质，能够根据前序+中序或中序+后序还原出二叉树。掌握二叉树的前序、中序和后序递归遍历算法、前序、中序非递归遍历算法，并能够写出算法代码。

　　了解线索化二叉树的概念、遍历算法和线索化算法。

　　了解哈夫曼树的概念。掌握哈夫曼算法的思想和步骤，能够手工计算哈夫曼树。了解哈夫曼编码的概念，能够手工计算哈夫曼编码。

　　了解树、森林和二叉树的关系。

　　6.图

　　了解图的定义。掌握图的邻接矩阵、邻接表的实现方法。掌握图的深度优先和广度优先遍历算法，能够手工计算图的深度优先遍历序和广度优先遍历序。掌握图的连通性问题的求解算法，包括生成树/森林计算、比较小生成树计算(Prim算法和Kruskal算法)。掌握关键路径问题的求解算法，并能够进行手工计算。掌握单源起点比较短路径算法(Dijkstra算法)和任两点间比较短路径算法(Floyd算法)，并能够进行手工计算。

　　7.查找

　　掌握静态表的概念和折半查找算法，并能够进行手工计算。掌握散列表的基本概念，散列函数的基本设计技巧。掌握二叉排序树的概念，以及二叉排序树上的查找、插入、删除算法，并能够进行手工计算。掌握平衡二叉树的概念，以及平衡二叉树的插入和调整算法，并能够进行手工计算。了解B-、B+树的概念，以及B-树的插入和删除算法。

　　8.内排序

　　掌握简单排序法(选择排序、插入排序、交换排序)的算法思想和步骤，能够写出排序过程。掌握快速排序的算法思想和步骤，能够写出排序过程。掌握堆排序的算法思想和步骤，能够写出排序过程(建堆过程、排序过程)。掌握归并排序的算法思想和步骤，能够写出排序过程。掌握基数排序的算法思想和步骤，能够写出排序过程。

　　了解各种排序方法的特点，能够针对特定问题背景选择适当的排序方法。

　　六、主要参考教材

　　1. 严蔚敏，吴伟民.数据结构(C语言版).北京：清华大学出版社，2002

　　2. 严蔚敏，吴伟民.数据结构习题集.北京：清华大学出版社