数据结构和算法分析的基础知识zdnd

《数据结构和算法分析的基础知识zdnd》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、数据结构和算法分析的基础知识[考核目的]：考核学员对有关数据、数据结构、抽象数据类型、面向对象思想的基本概念的理解、算法及简单的算法分析的掌握情况[考核的知识点]：什么是数据结构抽象数据类型及面向对象概念：数据类型；数据抽象与抽象数据类型；面向对象的概念；用于描述数据结构的语言数据结构的抽象层次算法定义性能分析与度量：算法的性能标准；算法的后期测试；算法的事前估计；空间复杂度度量；时间复杂度度量；时间复杂度的渐进表示法；渐进的空间复杂度[考核要求]：理解：数据结构基本概念及数据结构的抽象层次理解：抽象数据

2、类型及面向对象概念理解：算法的定义及算法的特性掌握：算法的性能分析与度量方法数组[考核目的]：考核学员对数组抽象数据类型及利用数组实现的顺序表、字符串等数据结构的基本理解和掌握程度[考核的知识点]：作为抽象数据类型的数组：数组的定义和初始化；作为抽象数据类型的数组的相关操作的实现顺序表：顺序表的定义和特点；顺序表的类定义；顺序表的查找、插入和删除；使用顺序表的事例字符串：字符串的抽象数据类型；字符串操作的实现；字符串的简单模式匹配[考核要求]：理解：作为抽象数据类型的数组的定义理解：顺序表的定义方式及实现

3、掌握：应用顺序表作为集合的简单操作理解：字符串的定义及实现综合应用：应用字符串实现简单的文本编辑中的操作链接表5[考核目的]：考核学员对链接表抽象数据类型（包括单链表、循环链表、双向链表）的理解及用链表实现并求解应用问题（如多项式操作）的应用能力。[考核的知识点]：单链表：单链表的结构；单链表的类定义；单链表中的插入与删除；带表头结点的单链表；用模板定义的单链表类；静态链表循环链表：循环链表的类定义；用循环链表解约瑟夫问题多项式及其相加：多项式的类定义；多项式的加法双向链表[考核要求]：掌握：单链表、循环

4、链表及双向链表的定义及实现理解：多项式类的定义及其加法运算栈与队列[考核目的]：考核学员对栈、队列、优先级队列等限制存取点的表的掌握程度和应用它们解决应用问题的能力。[考核的知识点]：栈：栈的抽象数据类型；栈的顺序存储表示；栈的链接存储表示；栈的应用队列：队列的抽象数据类型；队列的顺序存储表示；队列的链接存储表示；队列的应用举例优先级队列：优先级队列的定义；优先级队列的存储表示[考核要求]：理解：栈的定义及实现掌握：表达式求值理解：队列的定义及实现掌握：按层次输出二项展开式的系数（杨辉三角形）理解：优先级

5、队列的定义及链表实现算法递归与广义表[考核目的]：考核学员对递归问题求解方法的掌握情况以及对广义表的递归解法的掌握程度，并考察学员应用递归方法求解应用问题的能力。[考核的知识点]：递归概念：递归的定义、递归的数据结构、递归问题的解法迷宫问题：递归求解思路5递归过程与递归工作栈：递归过程实现的机制及递归工作栈的引用；用栈实现的迷宫问题非递归解法广义表：广义表的概念；广义表的表示及操作；广义表存储结构的实现；广义表的建立、访问、求深度、删除等算法[考核要求]：理解：递归的概念、递归问题的递归求解方法理解：递归

6、过程的机制与利用递归工作栈实现递归的方法掌握：利用栈实现迷宫问题的非递归解法理解：广义表的定义及其实现方法掌握：广义表的递归算法树与森林[考核目的]：考核学员对树、二叉树等重要数据结构的理解程度和特定的应用（如堆、霍夫曼树等）的掌握情况。[考核的知识点]：树和森林的概念：树的定义；树的术语；树的抽象数据类型二叉树：二叉树的定义；二叉树的性质；二叉树的抽象数据类型二叉树的表示：数组表示；链表存储表示二叉树遍历：中序遍历；前序遍历；后序遍历；应用二叉树遍历的事例；不用栈的二叉树中序遍历算法线索化二叉树：线索；

7、中序线索化二叉树；前序与后序的线索化堆：堆的定义；堆的建立；堆的插入与删除树与森林：树的存储表示；森林与二叉树的转换；树的遍历；森林的遍历二叉树的计数霍夫曼树：路径长度；霍夫曼树；霍夫曼编码[考核要求]：理解：树和森林的概念理解：二叉树的概念、性质及二叉树的表示掌握：二叉树的遍历算法及其它应用算法理解：线索化二叉树的特性及寻找某结点的前驱和后继的方法掌握：堆的定义及其实现的方法，以及用来实现优先级队列的算法掌握：树与森林的实现和树的遍历算法理解：二叉树的计数方法及从二叉树的前序和中序遍历结果得到二叉树的方

8、法掌握：霍夫曼树的实现方法及霍夫曼编码的概念集合与搜索[考核目的]：5考核学员对集合结构、集合的应用、与集合相关的搜索方法和简单的性能分析方法的理解和掌握情况。[考核的知识点]：集合及其表示：集合基本概念；以集合为基础的抽象数据类型；用向量实现集合抽象数据类型；用有序链表实现集合的抽象数据类型等价类：等价关系与等价类；确定等价类的链表方法；并查集简单的搜索结构：搜索的概念；静态搜索结构；顺序搜索；基于有序顺序表的折半搜索二叉搜