数据结构知识点数据结构知识点计算机13级 201302学期内容内容要求要求线性表的概念和特点熟练掌握线性表的抽象数据类型定义基本掌握顺序表和链表的定义和组织形式掌握线性表的顺序存储方式的实现熟练掌握线性表（单链表、循环链表）的链式存储方式的实现熟练掌握线性表（双向链表）的链式存储方式的实现掌握比较顺序表与链表的优缺点，掌握其各自适用的场合掌握应用线性结构解决基本的问题掌握利用STL中的vector,list解决基本的问题掌握一元多项式的表示和相加课外阅读线性表线性表 要求：内容内容要求要求栈和队列的概念和结构特点 熟练掌握栈和队列的抽象数据类型定义 掌握栈的顺序存储方式的实现熟练掌握栈的链式存储方式的实现基本掌握链式队列和循环队列的实现熟练掌握栈的应用（进制转换，括号匹配）熟练掌握栈与递归（递归实现回溯法）掌握队列的应用（事件模拟）基本掌握利用STL中的stack,queue解决问题掌握栈和队列栈和队列 要求：内容内容要求要求串的概念掌握串的抽象数据类型定义 基本掌握串的基本操作及模式匹配BF算法基本掌握利用STL中的string解决基本的问题掌握数组的定义，如何理解它们是线性表的扩展掌握多维数组的结构特点和在内存中的两种顺序存储方式 掌握多维数组中某数组元素的Location求解（按行存储或按列存储）：给出数组元素的首元素地址和每个元素占用的地址空间，并给出多维数组的维数，要求出该数组中的某个元素所在的位置熟练掌握特殊矩阵的压缩存储了解广义表的概念掌握求广义表的表头、表尾、长度、深度熟练掌握串串,数组和广义表数组和广义表 要求：内容内容要求要求树的定义和基本术语掌握树的各种存储结构 了解二叉树的定义和性质熟练掌握完全二叉树的顺序存储表示基本掌握二叉树的二叉链表存储表示熟练掌握二叉树的先序、中序、后序遍历的递归算法熟练掌握二叉树的层次遍历算法（自学）熟练掌握二叉树遍历的非递归算法了解运用遍历算法实现二叉树的其它操作（求树高、叶子总数等）熟练掌握线索二叉树的概念基本掌握线索化二叉树的方法 了解二叉树二叉树 要求：内容内容要求要求树、森林与二叉树的转换方法基本掌握树与森林的常用遍历方法基本掌握最优二叉树（哈夫曼树）的概念的特性基本掌握建立最优树和哈夫曼编码的方法熟练掌握哈夫曼树和哈夫曼码的构造算法基本掌握利用二叉树的中序和先序（或后序）构造二叉树的方法熟练掌握利用二叉树的中序和先序（或后序）构造二叉树的算法了解链式二叉树的递归创建方法基本掌握树的双亲表示法（可用来快速解决简单问题）基本掌握二叉树二叉树 要求(续)：内容内容要求要求图的定义和基本术语掌握图的邻接矩阵存储方法熟练掌握图的邻接表存储方法熟练掌握图的深度优先搜索与广度优先搜索的方法熟练掌握图的深度优先搜索与广度优先搜索的算法 基本掌握求图的连通分量的方法 了解构造图的最小生成树的2种方法熟练掌握图的最小生成树Prim算法 (采用邻接矩阵)掌握图的最小生成树Kruscal算法实现了解AOV网和拓扑排序的概念掌握图的拓扑排序的方法掌握图图 要求：内容内容要求要求图的拓扑排序的算法(采用邻接表)了解图的最短路径的概念 掌握求图的单源最短路径的Dijkstra方法 掌握图的单源最短路径的Dijkstra算法基本掌握AOE网和关键路径的概念以及求关键路径方法掌握图的任意两个顶点间最短路径的Floyd方法及算法基本掌握图图 要求（续）：内容内容要求要求顺序查找的方法掌握二分查找的方法熟练掌握顺序查找、二分查找的算法 熟练掌握计算顺序查找、二分查找的平均查找长度熟练掌握分析顺序查找、二分查找的时间复杂度掌握静态查找树表课外了解二叉排序树的概念熟练掌握二叉排序树插入节点的方法熟练掌握二叉排序树删除节点的方法基本掌握二叉排序树的查找方法和算法熟练掌握插入二叉排序树中结点的算法基本掌握删除二叉排序树中结点的算法了解查找查找 要求：内容内容要求要求平衡二叉树的的概念掌握平衡化二叉树的方法掌握B树、B+树、键树课外了解哈希查找的概念 掌握常用的哈希函数的构造方法 掌握用线性探测法和链地址法解决冲突的方法熟练掌握计算线性探测法和链地址法的平均查找长度（含查找失败）熟练掌握哈希表的查找算法和插入算法(开放定址)基本掌握查找查找 要求（续）内容内容要求要求排序的有关概念 掌握对常用排序算法的时间复杂度、空间复杂度进行分析掌握常用排序算法的时间复杂度、空间复杂度的结论掌握直接插入排序、冒泡排序、简单选择排序的方法、算法 熟练掌握快速排序、堆排序、归并排序的方法 熟练掌握希尔排序、基数排序的方法 基本掌握折半插入排序了解排序排序 要求：