北京化工大学07年硕士生考试-大纲(数据结构)考研

文章作者 100test 发表时间 2009:01:02 18:46:37
来源 100Test.Com百考试题网

一．适用的招生专业
计算机科学与技术；计算机应用；信息科学与技术；信息工程等。
二．考试的基本要求
　要求考生系统地理解数据结构的基本概念，掌握各种基本数据结构的定义和实现，掌握各种基本算法。要求考生具有抽象思维能力、逻辑推理能力、和综合运用所学的知识分析问题和解决问题的能力。
　1．理解有关数据结构的基本概念，理解算法的基本概念，了解算法复杂度的一般计算方法。
　2．掌握线性表的逻辑结构、物理结构和基本操作的实现以及应用（含栈、队列）。
　3．掌握串的概念、物理结构和基本操作（含KMP算法）的实现。
　4．掌握数组、稀疏矩阵的概念、物理结构和基本操作的实现，理解广义表的基本概念。
　5．掌握二叉树的逻辑结构、物理结构和基本操作的实现，理解二叉树、树、森林之间的关系，掌握哈夫曼算法。
　6．掌握图的逻辑结构、物理结构和基本操作的实现，掌握图的遍历、连通性问题、关键路径、最短路径问题的相关算法。
　7．掌握静态表和动态表的查找算法和相关技术（折半查找、散列表、二叉排序树、平衡二叉树、B 、B-树）。
　8． 掌握内排序的基本方法（选择、插入、交换、快速、堆、归并、基数）。
　9.．理解外排序的基本技术（多路归并、置换选择、最优归并）。
三．考试的方法和考试时间
　考试为闭卷笔试，可以使用无字典和编程功能的电子计算器；考试时间为3小时。
四．考试的主要内容与要求
　1．数据结构和算法的基本概念
　了解数据结构的基本概念，包括逻辑结构、物理结构的基本概念、两者之间的区别与联系。
　了解算法的基本概念和性质。
　了解算法的复杂度的基本概念，并掌握对非递归代码的复杂度计算的基本方法。
　2．线性表
　了解线性表的逻辑结构定义。
　掌握线性表的顺序结构实现，以及顺序结构下的基本操作的实现，并能写出操作代码。
　掌握线性表的链式结构实现，以及链式结构下的基本操作的实现，并能写出操作代码。
　能够设计针对顺序结构和链式结构线性表的一般应用问题的算法，并编写算法代码。
　掌握栈的基本概念、栈的性质。
　掌握栈的顺序结构和链式结构实现，以及相应的操作的实现，能够写出操作代码。
　了解栈与递归的关系，能够编写递归算法，能够将递归算法转换为非递归形式。
　掌握栈的应用方法，能够运用栈解决相关问题，并编写出算法代码。
　掌握队列的基本概念和性质。
　掌握队列的顺序结构和链式结构实现，以及相应操作的实现，能够写出操作代码。
　3．串
　了解串的概念，串与一般线性表的差别，以及串的常用物理实现。
　掌握串的基本操作的实现。
　掌握串的朴素模式匹配算法。
　掌握改进KMP算法的思想和步骤，能够手工计算出模式串的nextval向量。
　4．数组、稀疏矩阵和广义表
　了解多维数组的概念，以及多维数组的一维数组实现。
　掌握多维下标向一维下标的换算算法，并能进行手工计算。
　掌握稀疏矩阵的三元组结构。
　掌握三元组结构下的矩阵转置算法。
　掌握带行向量的三元组结构下的和矩阵乘法。
　了解广义表的概念。
　 5．树和二叉树
　了解树的定义和性质。
　了解二叉树的概念。
　掌握二叉树的基本性质，并能够进行描述和证明。（包括深度与最大结点数的关系性质、每层最大结点数性质、结点数与最小深度的关系性质、n2=n0-1性质、完全二叉树序号与结点关系性质）
　掌握二叉树的二叉链结构的实现。
　掌握二叉树的前序遍历、中序遍历、后序遍历和层次遍历规则，能够手工计算二叉树的遍历序。
　掌握二叉树的遍历性质，能够根据前序 中序或中序 后序还原出二叉树。
　掌握二叉树的前序、中序和后序递归遍历算法、前序、中序非递归遍历算法，并能够写出算法代码。
　了解线索化二叉树的概念、遍历算法和线索化算法。
　了解哈夫曼树的概念。
　掌握哈夫曼算法的思想和步骤，能够手工计算哈夫曼树。
　了解哈夫曼编码的概念，能够手工计算哈夫曼编码。
　了解树、森林和二叉树的关系。
　6．图
　了解图的定义。
　掌握图的邻接矩阵、邻接表的实现方法。
　掌握图的深度优先和广度优先遍历算法，能够手工计算图的深度优先遍历序和广度优先遍历序。
　掌握图的连通性问题的求解算法，包括生成树/森林计算、最小生成树计算(Prim算法和Kruskal算法)、强连通分量计算、关节点计算，并能够进行手　工计算。
　掌握最小生成树的MST性质，并能够进行描述和证明。
　掌握关键路径问题的求解算法，并能够进行手工计算。
　掌握单源起点最短路径算法(Dijkstra算法)和任两点间最短路径算法(Floyd算法)，并能够进行手工计算。
　7．查找
　掌握静态表的概念和折半查找算法，并能够进行手工计算。
　掌握散列表的基本概念，散列函数的基本设计技巧。
　掌握二叉排序树的概念，以及二叉排序树上的查找、插入、删除算法，并能够进行手工计算。
　掌握平衡二叉树的概念，以及平衡二叉树的插入和调整算法，并能够进行手工计算。
　了解B-、B 树的概念，以及B-树的插入和删除算法。
　8．内排序
　掌握简单排序法（选择排序、插入排序、交换排序）的算法思想和步骤，能够写出排序过程。
　掌握快速排序的算法思想和步骤，能够写出排序过程。
　掌握堆排序的算法思想和步骤，能够写出排序过程（建堆过程、排序过程）。
　掌握归并排序的算法思想和步骤，能够写出排序过程。
　掌握基数排序的算法思想和步骤，能够写出排序过程。
　了解各种排序方法的特点，能够针对特定问题背景选择适当的排序方法。
　9．★外排序
　了解外排序与内排序的区别和联系。
　了解多路归并排序技术的思想。
　了解置换-选择排序技术的思想
　了解最优多路归并技术的思想。
五．试卷结构
　试卷满分150分，全部为解答题。
　六．主要参考书
　严蔚敏．数据结构（C语言版）．北京：清华大学出版社，2002