数据结构基础知识(考纲重点).doc

数据结构和算法分析基础知识考核目的：对有关数据、数据结构、抽象数据类型、面向对象思想的基本概念的理解、算法及简单的算法分析的掌握情况考核的知识点：什么是数据结构抽象数据类型及面向对象概念：数据类型；数据抽象与抽象数据类型；面向对象的概念；用于描述数据结构的语言数据结构的抽象层次算法定义性能分析与度量：算法的性能标准；算法的后期测试；算法的事前估计；空间复杂度度量；时间复杂度度量；时间复杂度的渐进表示法；渐进的空间复杂度考核要求：理解：数据结构基本概念及数据结构的抽象层次理解：抽象数据类型及面向对象概念理解：算法的定义及算法的特性掌握：算法的性能分析与度量方法数 组考核目的：考核学员对数组抽象数据类型及利用数组实现的顺序表、字符串等数据结构的基本理解和掌握程度考核的知识点：作为抽象数据类型的数组：数组的定义和初始化；作为抽象数据类型的数组的相关操作的实现顺序表：顺序表的定义和特点；顺序表的类定义；顺序表的查找、插入和删除；使用顺序表的事例字符串：字符串的抽象数据类型；字符串操作的实现；字符串的简单模式匹配考核要求：理解：作为抽象数据类型的数组的定义理解：顺序表的定义方式及实现掌握：应用顺序表作为集合的简单操作理解：字符串的定义及实现综合应用：应用字符串实现简单的文本编辑中的操作链 接 表考核目的：考核学员对链接表抽象数据类型（包括单链表、循环链表、双向链表）的理解及用链表实现并求解应用问题（如多项式操作）的应用能力。考核的知识点：单链表：单链表的结构；单链表的类定义；单链表中的插入与删除；带表头结点的单链表；用模板定义的单链表类；静态链表循环链表：循环链表的类定义；用循环链表解约瑟夫问题多项式及其相加：多项式的类定义；多项式的加法双向链表考核要求：掌握：单链表、循环链表及双向链表的定义及实现理解：多项式类的定义及其加法运算 栈与队列考核目的：考核学员对栈、队列、优先级队列等限制存取点的表的掌握程度和应用它们解决应用问题的能力。考核的知识点：栈：栈的抽象数据类型；栈的顺序存储表示；栈的链接存储表示；栈的应用队列 ：队列的抽象数据类型；队列的顺序存储表示；队列的链接存储表示；队列的应用举例优先级队列：优先级队列的定义；优先级队列的存储表示考核要求：理解：栈的定义及实现掌握：表达式求值理解：队列的定义及实现 掌握：按层次输出二项展开式的系数（杨辉三角形）理解：优先级队列的定义及链表实现算法递归与广义表考核目的：考核学员对递归问题求解方法的掌握情况以及对广义表的递归解法的掌握程度，并考察学员应用递归方法求解应用问题的能力。考核的知识点：递归概念：递归的定义、递归的数据结构、递归问题的解法迷宫问题：递归求解思路递归过程与递归工作栈：递归过程实现的机制及递归工作栈的引用；用栈实现的迷宫问题非递归解法广义表：广义表的概念；广义表的表示及操作；广义表存储结构的实现；广义表的建立、访问、求深度、删除等算法考核要求：理解：递归的概念、递归问题的递归求解方法理解：递归过程的机制与利用递归工作栈实现递归的方法掌握：利用栈实现迷宫问题的非递归解法理解：广义表的定义及其实现方法掌握：广义表的递归算法树与森林考核目的：考核学员对树、二叉树等重要数据结构的理解程度和特定的应用（如堆、霍夫曼树等）的掌握情况。考核的知识点：树和森林的概念：树的定义；树的术语；树的抽象数据类型二叉树：二叉树的定义；二叉树的性质；二叉树的抽象数据类型二叉树的表示：数组表示；链表存储表示二叉树遍历：中序遍历；前序遍历；后序遍历；应用二叉树遍历的事例；不用栈的二叉树中序遍历算法线索化二叉树：线索；中序线索化二叉树；前序与后序的线索化堆：堆的定义；堆的建立；堆的插入与删除树与森林：树的存储表示；森林与二叉树的转换；树的遍历；森林的遍历二叉树的计数霍夫曼树：路径长度；霍夫曼树；霍夫曼编码考核要求：理解：树和森林的概念理解：二叉树的概念、性质及二叉树的表示掌握：二叉树的遍历算法及其它应用算法理解：线索化二叉树的特性及寻找某结点的前驱和后继的方法掌握：堆的定义及其实现的方法，以及用来实现优先级队列的算法掌握：树与森林的实现和树的遍历算法理解：二叉树的计数方法及从二叉树的前序和中序遍历结果得到二叉树的方法掌握：霍夫曼树的实现方法及霍夫曼编码的概念集合与搜索考核目的：考核学员对集合结构、集合的应用、与集合相关的搜索方法和简单的性能分析方法的理解和掌握情况。考核的知识点：集合及其表示：集合基本概念；以集合为基础的抽象数据类型；用向量实现集合抽象数据类型；用有序链表实现集合的抽象数据类型等价类：等价关系与等价类；确定等价类的链表方法；并查集 简单的搜索结构：搜索的概念；静态搜索结构；顺序搜索；基于有序顺序表的折半搜索二叉搜索树：定义；二叉搜索树上的搜索；二叉搜索树的插入；二叉搜索树的删除AVL树：AVL树的定义；平衡化旋转；AVL树的插入和删除；AVL树的结点个数与高度的关系考核要求：掌握：集合及其表示方法，包括数组及有序链表的表示及其相关操作的实现算法掌握：等价类的链表实现与利用并查集实现的方法掌握：静态搜索表的顺序搜索和折半搜索算法及其性能分析方法掌握：二叉搜索树的表示、搜索、插入、删除算法及其性能分析方法掌握：AVL树的构造、插入、删除时的调整方法及其性能分析图考核目的：考核学员对图和网络结构的存储表示、图的遍历、最小生成树、活动网络等重要应用求解方法的理解和掌握情况。考核的知识点：图的基本概念：图的基本概念；图的抽象数据类型图的存储表示：邻接矩阵；邻接表；邻接多重表，典型操作，如构造、求根、找第一个邻接顶点、找下一个邻接顶点等操作的实现算法图的遍历与连通性：深度优先搜索和广度优先搜索算法；连通分量；重连通分量最小生成树：克鲁斯卡尔算法；普里姆算法活动网络：用顶点表示活动的网络；用边表示活动的网络考核要求：理解：图的基本概念掌握：图的存储表示掌握：图的两种遍历算法与求解连通性问题的方法理解：求解关节点及构造重连通图的方法掌握：构造最小生成树的Prim算法和Kruskal方法掌握：活动网络的拓扑排序算法掌握：求解关键路径的方法排 序考核目的：考核学员对各种典型排序方法及其性能分析方法的理解和掌握情况。考核的知识点：概念：排序的定义、排序的时间代价、排序方法的稳定性插入排序：直接插入排序；折半插入排序；链表插入排序；希尔排序交换排序：起泡排序；快速排序选择排序：直接选择排序；链表选择排序；锦标赛排序；堆排序归并排序：归并；迭代的归并排序算法；递归的链表归并排序基数排序：多关键码排序；链式基数排序外排序：外排序的基本过程；k路平衡归并；初始归并段的生成；最佳归并树考核要求：理解：排序的基本概念和性能分析方法掌握：插入排序（直接插入排序；折半插入排序；链表插入排序）、交换排序（起泡排序；快速排序）、选择排序（直接选择排序；链表选择排序；锦标赛排序；堆排序）、归并排序等内排序的方法、算法及其性能分析方法理解：基数排序方法及其性能分析方法理解：多路平衡归并等外排序方法及败者树构造方法理解：生成初始归并段及败者树构造方法理解：最佳归并树的建立方法索引与散列结构考核目的：考核学员对索引与散列结构（即用于外部搜索的文件结构）的了解程度和掌握情况。考核的知识点：静态索引结构：线性索引；倒排表；m路静态搜索树动态索引结构：动态的m路搜索树；B_树；B_树的插入；B_树