软考指点——数据结构与算法.ppt

数据结构与算法; 数据结构与算法概述;考 点 分 析;数据结构与算法概述;第一部分 线性表;第一部分 线性表;第一部分 线性表;第一部分 线性表;第一部分 线性表;第一部分 线性表;第一部分 线性表;第一部分 线性表;第一部分 线性表;分值：0 ~ 1分 （每年） 分数比重：0% ~ 10% 重要知识点： 1、栈的结构特点 2、队列的结构特点 3、双端队列与循环队列 4、串的存储结构、基本操作和模式匹配;栈;队列;循环队列;双端队列;串的存储结构;串的基本操作——难掌握的部分;串的模式匹配;串的模式匹配;真题 ;真题 ;真题 ;真题 ;真题 ;分值：0 ~ 1分 （每年） 分数比重：0% ~ 10% 重要知识点： 1、数组的地址计算 2、数组的压缩存储 3、广义表的表示 4、广义表的表头、表尾;数组;数组的地址计算;a11;带状矩阵：在矩阵A中，所有的非零元素都集中在以主对角线为中心的带状区域中。最常见的是三对角带状矩阵。 ;1. 确定存储该矩阵所需的一维向量空间的大小：; row col value;数组的压缩存储;1、A = ( );广义表的长度定义为最外层包含元素个数。 广义表的深度定义为所含括弧的重数; “原子结点”的深度为 0 ; “空表”的深度为 1 。;真题 ;真题 ;真题 ;分值：1 ~ 17分 （每年） 分数比重：2% ~ 20% 重要知识点： 1、树和二叉树的定义 2、二叉树的重要性质 3、二叉树的遍历、线索二叉树 4、树与二叉树的转换 5、二叉树的应用——哈夫曼树;树和二叉树的定义 ;二叉树的重要性质;二叉树的遍历;例：已知结点的先序序列和中序序列 先序序列：A B D E J C F I G 中序序列：D B J E A F I C G 则可按上述分解求得整棵二叉树。 ;线索二叉树;树、森林与二叉树的转换;带权路径长度： 设二叉树有n个带权值的叶子结点，定义从二叉树的根结点到二叉树中所有叶子结点的路径长度li与相应叶子结点权值wi的乘积之和称作该二叉树的带权路径长度。;5;真题 ;真题 ;真题 ;真题 ;真题 ;真题 ;真题 ;真题 ;真题 ;分值：0 ~ 5分 （每年） 分数比重：6% 重要知识点： 1、图的基本概念和存储结构 2、图的遍历 3、拓扑排序和最小???成树 4、关键路径 5、最短路径;图的基本概念和存储结构;图的遍历;拓扑排序;最小生成树;关键路径;第五部分 图 ;第五部分 图 ;最短路径;最短路径;真题 ;真题 ;真题 ;真题 ;真题 ;真题 ;真题 ;真题 ;真题 ;真题 ;分值：5 ~ 15分 （每年） 分数比重：10% 重要知识点： 1、静态表查找——顺序查找、折半查找 2、动态表查找——二叉排序树、平衡二叉树 3、哈希表 4、插入类排序 5、交换类排序 6、选择类排序 7、分配类排序;查找;静态查找;动态查找——二叉排序树;动态查找——二叉排序树;动态查找——二叉排序树的删除;动态查找——平衡二叉树;动态查找——平衡二叉树的构造;动态查找——平衡二叉树的构造;第六部分 排序与查找 ;动态查找——平衡二叉树; 哈希表; 哈希表; 哈希表; 基本概念; 插入类排序;第六部分 排序与查找 ; 交换类排序; 选择类排序;归并排序;分配类排序;分配类排序;数据元素的关键字序列为{710,342,045,686,006,841,429,134,068,264};排序方法;真题 ;真题 ;真题 ;真题 ;真题 ;真题 ;真题 ;真题 ;真题 ;分值：2 ~ 16分 （每年） 分数比重：22% 重要知识点： 1、时间复杂度 2、穷举法、迭代法、递推法、递归法、 分治法、动态规划法、回溯法、贪心法 分支限界法; 蛮力法（穷举法）; 迭代法; 递推法; 递归法; 分治法; 动态规划法; 回溯法; 回溯法; 贪心法; 分支限界法;真题 ;真题 ;真题 ;真题 ;真题 ;真题 ;真题 ;真题 ;真题 ;真题 ;真题 ;Thank You!