《数据结构》部分.doc

《数据结构》部分最珍贵的财富是时间,最大的浪费是虚度流年。《数据结构》考试大纲本《数据结构》考试大纲适用于中国科学院研究生院软件学院软件工程以及计算机等专业的硕士研究生入学考试。数据结构是计算机科学与技术及相关学科的重要基础, 要求考生系统地理解数据结构的基本概念, 掌握各种数据结构的定义和实现算法。要求考生具有抽象思维能力, 逻辑推理能力, 和综合运用所学的知识分析问题和解决问题的能力。一、绪论 1. 数据结构的基本概念,数据的逻辑结构、存储结构。 2. 算法的定义、算法的基本特性以及算法分析的基本概念。要求: 建立有关数据结构最基本的概念, 包括数据的逻辑结构、存储结构和算法,算法分析的基本概念与基本方法。二、线性表 1. 线性关系、线性表的定义,线性表的基本操作。 2. 线性表的顺序存储结构与链式存储结构( 包括单链表、循环链表和双向链表) 的构造原理。 3. 在以上两种存储结构上对线性表实施的最主要的操作( 包括三种链表的建立、插入和删除、检索等) 的算法设计。要求: 掌握线性表的基本概念以及两种存储结构的构造原理, 掌握在各种存储结构下对线性表进行的基本操作的算法设计。三、堆栈与队列 1. 堆栈与队列的基本概念、基本操作。 2. 堆栈与队列的顺序存储结构与链式存储结构的构造原理。 3. 在不同存储结构的基础上对堆栈与队列实施插入与删除等基本操作对应的算法设计。要求: 掌握堆栈和队列的基本概念与特征, 掌握在两种存储结构下如何对堆栈和队列进行插入和删除等操作, 以及利用堆栈与队列解决实际问题的基本方法。四、串 1 、串的基本概念、串的基本操作和存储结构。 2 、串的模式匹配算法和改进的 KMP 算法要求: 充分了解串的基本概念、掌握串的存储结构和相关的操作算法。五、数组和广义表 1 、数组的概念、多维数组的实现 2 、对称矩阵和稀疏矩阵的压缩存储 3 、广义表的基本概念要求: 掌握数组、广义表和稀疏矩阵的基本概念, 物理结构和基本操作的实现。六、树与二叉树 1. 树的定义和性质 2. 二叉树的概念、性质和实现 3. 遍历二叉树和线索二叉树 4. 树和森林 5. 赫夫曼树及其应用 6. 树的计数要求: 充分了解树型结构的逻辑特征, 掌握各种存储结构的构造原理, 能够熟练地利用常用的三种遍历方法, 掌握利用二叉树的遍历操作解决实际问题的方法, 掌握二叉排序树的建立以及在二叉排序树中查找一个结点存在与否的过程。七、图 1. 图的定义,基本概念,图的分类,常用名词术语。 2. 图的邻接矩阵存储方法、邻接表存储方法的构造原理。 3. 图的遍历操作。 4. 最小生成树,最短路径, AOV 网与拓扑排序。要求:充分了解图的逻辑结构的特点,掌握常用的两种存储方法,掌握最小生成树(Prim 算法和 Kruskal 算法) 、最短路径、拓扑排序的具体求解