数据结构
2021-09-02 00:14:02 209 举报AI智能生成
含有对应代码注解,考研和面试均可使用
作者其他创作
大纲/内容
结点高度
树的高度
高度
结点深度
树的深度
层数/深度
祖先、子孙、兄弟、双亲；堂兄弟
结点的度
树的度
度
分支结点
叶子结点
结点
有序树与无序树
路径
路径长度
路径和路径长度
森林
基本概念
结点数(m)=非叶子结点数+叶子节点数
结点数 = Σ 度 x 个数 + 1【根】
结点与度数
sp: 高 h 的二叉树结点至多为
高度为 h 的 m 叉树至(最)多结点数
偶数个结点的二叉树，其 度数为1 的结点个数必然为奇数
结点个数
n 个结点的 m阶树/m叉树/完全 m 叉树 的高度 【必背】
最小高度
n个结点，度为m的树最大高度
最大高度
性质
如果某结点只有一个子结点，则必为左孩子
结点个数 span class=\"equation-text\" contenteditable=\"false\" data-index=\"0\" data-equation=\"n\\geq 0\
定义
叶子结点个数
第k层最多结点数
高度为h至多结点个数
个数相关
i 结点的左孩子编号 = 2i
i 结点的右孩子编号 = 2i+1
左右孩子
下标相关
结点所在深度
完全二叉树】深度
(n+1)/2
严格二叉树的最大深度
深度相关
n个节点的二叉链存储节点空指针个数为 n+1
指针个数
次序合法性
访问序确定二叉树形状
左必在右的前面被访问
前中后序的访问序列，叶子结点序列不变
高度等于其结点数时，先序和后序遍历序列相反
遍历访问序
定义span class=\"equation-text\" data-index=\"0\" data-equation=\
满二叉树
层都是满的，同时第 层按照从左往右顺序填结点
每个结点都与高为 的满二叉树编号为 的结点位置一一对应
若一个结点没有左孩子，则其必然是叶结点
叶子结点的双亲的左兄弟（若存在）则必然不是叶子结点
高度为 h 的完全二叉树，节点个数最小为
最后一个分支 (非叶) 结点序号为
若某完全二叉树有 个结点，则其叶子节点个数为
结点个数最少为：结点个数最多为：
第 x 层有 k 个叶子结点，求结点个数max/min情况
计算
完全二叉树
类型
顺序存储
链式存储
存储结构
先/前序(NLR)
中序(LNR)
后序(LRN)
遍历
二叉树
度为m的树 m叉树
顺序存储；存储地址=逻辑地址
双亲表示法
邻接表存储；有向图存储结构
孩子表示法
孩子兄弟/二叉树表示法
已知森林边和结点数，求森林中包含的树的个数
森林结点数
右孩子指针为空的结点个数
森林左子树结点数=森林第一棵树结点树
森林和二叉树关系
二叉树：先序
森林：先序
树：先根
二叉树：中序
森林：后序
树：后根
遍历以及有序树
树、森林和二叉树转换
树和森林
复杂度分析
生成树与生成森林
BFS广度优先搜索
遍历与连通性
DFS深度优先搜索
递归 = 栈
递归与非递规转换
辅助队列
层次遍历
中序(必须)+先序/后续
遍历序列构造二叉树
后序遍历
线索树遍历需要栈
求祖先到子孙的路径可以使用先/中序遍历
已知次序求二叉树异构个数
带权路径长度
带权路径长度(WPL)最小的二叉树；也称最优二叉树
度为 m 的哈夫曼树，为严格的 m 叉树
贪心，每次取两个权值最小的结点作为新结点的左右子树新结点权值为左右子树和，并放入到可选择的结点集合中
构造
初始结点均为叶子结点
权值越小到根节点路径越长
新建了n-1个结点，结点 总数 为 2n-1
度为m的哈夫曼树中，叶子结点为n，则其非叶子节点个数为
叶子结点个数即为不同符号的编码数
哈夫曼树
每个字符用相等长度二进制位表示
固定长度编码
没有一个编码是另一个编码的前缀
前缀编码
哈夫曼编码
物理/存储结构
span class=\"equation-text\" contenteditable=\"false\" data-index=\"0\" data-equation=\
标志域含义
线索
线索化
概念
线索化后的空链个数
仍需要栈支持的遍历为 后序线索树
不是每个结点都能通过线索查找其前驱后继
已知后序线索二叉树，求后序后继仍不能完全求解
相关问题
线索二叉树
插入
递归实现
非递归实现
查找
叶结点直接删除
x 只有一个左/右子树子结点接上其父节点
x 有左右两棵子树补前驱后继
删除
操作
删除某节点后将其插入，则前后排序树有可能不同
成功查找长度
失败查找长度
ASL(平均查找长度）
递增序列遍历=中序遍历
非法查找路径序列
题目计算
二叉搜索树 BST
平衡因子
平衡机制
插入/删除
调整最小不平衡子树
左重顺旋减轻左深，右重逆旋减轻右深
根连前驱后继【按照数值大小比较连接】
旋转要点
左子树旋转，降低一层就平衡
LL(左孩子左子树)
RR(右孩子右子树)
LR(左孩子右子树)
RL(右孩子左子树)
旋转方式
旋转
操作原理
构造一棵高为 h 的 AVL 所需要的最少结点数
已知共有 n 个结点的 AVL，求其最大深度
平衡二叉树AVL
合并 Union
初始化 Init(S)
并查集
应用
树
弧头(顶点)
弧尾(顶点)
有向图
无向图
简单图：无自环，无重复边
多重图：有自环，重复边
简单图、多重图
简单图的边数达到上限
完全图
边和顶点均为子集且能够形成一张图
子图
连通图：图中任意两点均连通
连通分量：无向图中极大连通子图
连通、连通图和连通分量
强连通图：有向图中任意两点互相可达
强连通分量：有向图中极大墙连通子图
强连通、强连通分量
生成树：包含图中全部顶点的一个极小连通子图
生成森林：非连通图中连通分量的生成树构成了生成森林
极小连通子图：保持图的联通性，又使得边数尽可能少
生成树、生成森林
顶点度：无向图中顶点所连边数
顶点度，入度和出度
网：带权图
边的权和网
稠密图、稀疏图
路径：顶点序列【由顶点和相邻顶点序偶构成的边所形成的序列】
回路/环：路径中第一个和最后一个顶点相同
路径、路径长度和回路
简单路径、简单回路
距离
有向树
n个顶点，e条边的无向图森林树的个数
无向图森林
相关概念
十字链表
邻接表法
邻接多重表
稀疏矩阵
邻接矩阵
稠密矩阵
广搜bfs
深搜dfs
Prim算法
Kruskal算法
最小生成树
Dijkstra
Floyd
最短路径
有向无环图表达式
AOV网
有序序列个数
拓扑排序
AOE网
事件最早发生时间
事件最迟发生时间
活动最早开始事件
活动最晚开始时间
时间余量
关键路径
图
关键字有序过程
稳定性
具体元素未知，至少比较次数
排序过程中，对尚未确定最终位置的所有元素进行一遍处理
趟
时间复杂度
稳定排序
每一次排序完后，前i位有序，i位以后也可能存在使得原i位发生改变的值
特点
直接插入
对已排好序列查找部分使用折半搜索
折半插入
算法描述选定增量d，将原序列分成几个部分，然后对每个部分进行插入排序
空间复杂度
不稳定排序【分组原因】
希尔排序
插入排序
算法描述【最大泡泡冒起来】每一次排序将最小/最大的元素，通过依次遍历比较交换，放到序列末尾/队首最终位置
前i位或者后i位(根据顺序或逆序)为最终有序排序
冒泡排序
基于分治思想【二分】
空间复杂度【栈深】
时间复杂度【与递归栈的深度有关】
某个值的左边均为小于它的值，右边均为大于它的值
当序列基本有序或者逆序情况下，效率最低：受不平衡划分影响
2014) 对 15 个元素进行快排，则比较元素次数最少是
真题
快速排序
交换排序
算法描述每趟找到后n-i个元素中，关键字最小的元素，并与第i个元素进行交换
不稳定排序【多个最小取最后遍历位置】
简单选择
算法描述二叉堆：完全二叉树，左右子树均小于/大于根结点【小/大顶堆】
建堆时间【计算补充】
最后一个非叶子结点位置为len/2【根结点下标为1】
不稳定排序【调整时可能调节后面位置到根】
堆排序
选择排序
算法描述二路归并算法：初始每个子表长度为1，然后不断两两合并排序，最终合并成长为n的有序序列
时间复杂度 【与序列初始状态无关】
当有足够大到内存装不下的文件进行排序时，采用分治的归并排序
归并排序
算法描述基于关键字位上数字大小进行逐一排序
最高位优先 MSD
最低位优先 LSD
常见关键字排序
基数排序
常见类型
直接插入、冒泡排序
快排
有序情况下
简单选择、直接插入、冒泡排序
堆排，快排、归并
无序情况下【平均】
时间复杂度
简单选择、插入、冒泡、希尔、堆排
归并
空间复杂度
不稳定排序
算法稳定性
存储结构影响
堆排序，快速排序、简单选择、冒泡排序
【每趟排序能够得到至少一个最终有序序】
无关二路归并排序、简单选择排序、基数排序
有关快速排序、直接插入排序、冒泡排序、堆排序、希尔排序
【比较次数与初始序列】
无关直接插入排序、折半插入排序、希尔排序、简单选择排序、归并排序、基数排序
有关冒泡排序、快速排序
【排序趟数与初始序列】
算法过程特征
排序比较
内部排序
一般方法归并排序法
外部排序总时间 = 内存排序时间 + 外存信息读写时间 + 内部归并所需时间
归并躺数 = 树的高度 =
归并总比较次数 ==
I/O 操作次数读入归并段，写入归并段（以块为单位）
初始序列为12个无序数据
把内存数据划分为多个块，首先对块内进行排序，形成有序字串
将两个已经排序好的子块进行归并成一个更大的块【二路归并】
继续将小的归并段合并为更大的归并段
图解
最多只能有 k 个段归并为一个
每一趟中，若有m个块进行归并，则一趟处理得到个块
k 路平衡归并
胜者树
利用败者树加快排序
败者树
胜者树/败者树
多路平衡归并与败者树
原理
每组划分6个元素，则初始组数至少划分4组
选择出第一个 MINIMAX 29
选择比初始段中更大的 MINIMAX 38
同理
直到无 MINIMAX 选出，此时认为初始段已经完成
初始段建立图解
败者树利用
置换-选择排序
额外补充虚断数
附加虚短的最佳归并树
最佳归并树
外部排序
排序
typedef 关键字
不带 typedef 标签
带 typedef 标签
错误语法
语法
自引用
相互引用
结构体嵌套
C与C++中 struct 区别
struct 结构体
地址与值
& 取地址/引用(别名)
指针 T *t
C11语法
问题求解步骤描述
算法定义
有穷性
确定性
可行性
输入
输出
五个特性
加法规则span class=\"equation-text\" data-index=\"0\" data-equation=\
乘法规则
常见渐进时间复杂度span class=\"equation-text\" data-index=\"0\" data-equation=\"1\\log_2n【即\\log n】nn\\log nn^2n^32^nn!
等差等比公式
定义辅助空间大小与原数据量之间的关系
原地工作
递归算法
递归调用
递归公出口
递推公式
列方程法
求解问题
复杂度计算
算法
数据对象
(个体)基本单位
(个体)属性
数据项
数据元素
原子类型
结构类型
抽象数据类型(ADT)
数据类型
数据
一般线性表
栈
队列
串
受限线性表
数组
线性表推广
线性结构
多叉树
图/网
集合
非线性结构
逻辑结构
索引存储
散列存储/哈希存储
数据运算(操作)
三要素
数据结构
绪论
存储空间大小相同
有限个数据元素，相同数据类型，且有序
表头元素；表尾元素；位序； 前驱；后继
定义/概念
静态分配
动态分配
创建/销毁
增删改查
属性获取
随机存取[物理顺序和逻辑顺序相同]
删除和插入时间复杂度高
特性
C语言数组方式分配
静态
C语言指针方式分配
动态
分配方式
初始化
健壮性判断
移动
属性修改
返回函数状态
实现逻辑
最好O(1)
最坏O(n)
平均 = 概率 移动次数 = 期望
健壮性
平均
顺序寻找
返回位序
按值查找
合并
SqList顺序表
2010】408整数数组循环左移
2011】408找出两个等长升序序列的中位数
2013】408找出序列中的主元素主元素：个数 > 序列总个数/2
2018】408求最小未出现整数
2020】408求三元组最小距离
sequential mapping顺序存储
头插法
尾插法
时间复杂度O(n)
判空
单链表
双链表
单向循环链表
双向循环链表
循环链表
静态链表
跳跃表
头结点
头指针
链表头
首元结点
尾指针
2009】408查找只含头结点的单链表中倒数第k位置的结点值
2012】408求出某两个链表共同后缀起始位置
2019】408对单链表进行重排
指针
随机访问，链式则只能顺序访问
顺序
分配灵活，无需占用连续空间，插入删除时间复杂度低
链式
优缺点
栈顶(top)
栈低(Bottom)
空栈(Empty)
特性LIFO 后进先出
数学性质 [ 卡特兰数 ]n 个不同元素进栈，出栈元素不同的排列个数为
销毁Destroy(&S)
初始化Init (&S)
判空IsEmpty
顺序栈
共享栈
表头结点
表尾结点
属性
链栈
括号匹配
前缀/波兰表达式
中缀
后缀/逆波兰表达式
转换方法
计算方法
表达式树
表达式求值
时间复杂度计算
dfs广搜
不可能序列
卡特兰数:
序列种类数
可能序列
出栈序列
数值转换
栈的最小深度
函数局部变量存储
应用题型
栈(Stack)
FIFO
销毁
出队
入队
读取队头元素
基本操作
队头指针
队尾指针
循环队列
双端队列
二叉树层次遍历
做题时可标注左右进入的序列
出队序列计算
OS缓冲区
CPU资源分配
页面替换算法
FIFO性质
队列/Queue
行优先
列优先
下标转换公式span class=\"equation-text\" data-index=\"0\" data-equation=\
对称矩阵
下标转换span class=\"equation-text\" data-index=\"0\" data-equation=\
三角矩阵
下标转换
三对角矩阵
三元组
疏密矩阵
特殊矩阵
方阵
矩阵元素下表与一位数组下标换算
地址求行长
数组矩阵
子串
主串
位置
定长顺序存储
堆分配存储
块链存储
暴力匹配
next数组
next手工算法
KMP算法
模式匹配
相等判断
求子串
连接
长度
相关运算
Linear List线性表
查找成功
查找失败
平均查找长度
效率指标
查找特定元素
检查满足条件元素属性
插入元素
删除元素
查找表/查找结构
折半
散列
静态查找表
二叉排序树
AVL平衡二叉树
B树
动态查找表
同义词之间冲突
不可能避免
冲突/碰撞
同义词与非同义词发生冲突
主要与冲突探测方法有关
聚集/堆积
直接定址法
除留余数法
数字分析法
平方取中法
散列函数
线性探测再散列
二次探测再散列
伪随机探测再散列
开放定址法
链地址法/拉链法
再哈希(散列)法
冲突处理
a= 表中记录数/散列表长度
装填因子
散列结构
一般顺序表查找
有序表顺序查找
顺序查找(链式限制)
适用于有序顺序存储结构
类型：平衡二叉树
n 个元素时的树高 h
判定树是否复合规则判断
折半查找判定树
最多查找次数
最少查找次数
折半(二分)查找
理想块长
顺序分块查找
最优优化
分块(索引顺序)查找
B树的阶
span class=\"equation-text\" data-index=\"0\" data-equation=\
非叶结点结构
所有结点平衡因子为 0 【高度平衡】
最高
最低
最多
最少
关键字数
非根结点关键字个数
根节点为非终端结点时，至少有两个孩子.
非根结点子树个数
严格平衡查找树，所有节点子树高度一致叶子处于同一层且用NULL表示
非叶结点的结构
分裂
图示
已知阶、层数、某层关键字数，求最多结点数
B与B+树区别
B+树
变色
插入调整
删除调整
红黑树
索引结构/树表
2021】一、线性表 (一) 线性表的定义和基本操作 (二) 线性表的实现 1. 顺序存储结构 2. 链式存储结构 3. 线性表的应用 二、栈、队列和数组 (一) 栈和队列的基本概念 (二) 栈和队列的顺序存储结构 (三) 栈和队列的链式存储结构 (四) 栈和队列的应用 (五) 特殊矩阵的压缩存储 三、树与二叉树 (一) 树的基本概念 (二) 二叉树 1. 二叉树的定义及其主要特征 2. 二叉树的顺序存储结构和链式存储结构 3. 二叉树的遍历 4. 线索二叉树的基本概念和构造 (三) 树、森林 1. 树的存储结构 2. 森林与二叉树的转换 3. 树和森林的遍历(四) 树和二叉树的应用1. 二叉排序树 2. 平衡二叉树 3. 哈夫曼(Huffman)树和哈夫曼编码 三、图 (一) 图的概念 (二) 图的存储及基本操作 1. 邻接矩阵法 2. 邻接表法 (三) 图的遍历 1. 深度优先搜索 2. 广度优先搜索(四) 图的基本应用 1. 最小(代价)生成树 2. 最短路径 3. 拓扑排序 4. 关键路径 四、查找 (一) 查找的基本概念 (二) 顺序查找法 (三) 折半查找法 (四) B-树及其基本操作、B+树的基本概念(五) 散列(Hash)表 (六) 查找算法的分析及应用 五、内部排序 (一) 排序的基本概念 (二) 插入排序 1. 直接插入排序 2. 折半插入排序 (三) 冒泡排序(bubble sort) (四) 简单选择排序 (五) 希尔排序(shell sort) (六) 快速排序 (七) 堆排序 (八) 二路归并排序(merge sort) (九) 基数排序 (十) 各种内部排序算法的比较 (十一) 内部排序算法的应用
2022】一、线性表 (一) 线性表的定义和基本操作 (二) 线性表的实现 1. 顺序存储结构 2. 链式存储结构 3. 线性表的应用 二、栈、队列和数组 (一) 栈和队列的基本概念 (二) 栈和队列的顺序存储结构 (三) 栈和队列的链式存储结构 (四) 栈和队列的应用 (五) 【多维数组的存储】和特殊矩阵的压缩存储 三、树与二叉树 (一) 树的基本概念 (二) 二叉树 1. 二叉树的定义及其主要特征 2. 二叉树的顺序存储结构和链式存储结构 3. 二叉树的遍历 4. 线索二叉树的基本概念和构造 (三) 树、森林 1. 树的存储结构 2. 森林与二叉树的转换 3. 树和森林的遍历(四) 树和二叉树的应用1. 二叉搜索树 2. 平衡二叉树3. 哈夫曼(Huffman)树和哈夫曼编码4. 【并查集】 三、图 (一) 图的概念 (二) 图的存储及基本操作 1. 邻接矩阵法 2. 邻接表法 (三) 图的遍历 1. 深度优先搜索 2. 广度优先搜索(四) 图的基本应用 1. 最小(代价)生成树 2. 最短路径 3. 拓扑排序 4. 关键路径 四、查找 (一) 查找的基本概念 (二) 顺序查找法(三) 【分块查找法】(四) 折半查找法 (五) B-树及其基本操作、B+树的基本概念(六) 散列(Hash)表 (七) 查找算法的分析及应用 五、排序 (一) 排序的基本概念 (二) 插入排序 1. 直接插入排序 2. 折半插入排序 (三) 冒泡排序(bubble sort) (四) 简单选择排序 (五) 希尔排序(shell sort) (六) 快速排序 (七) 堆排序 (八) 二路归并排序(merge sort)(九) 基数排序(十) 【外部排序】 (十一) 各种排序算法的比较 (十二) 排序算法的应用
935考纲对比
0 条评论
回复 删除
下一页
