导图社区 数据结构
- 59
- 5
- 0
- 举报
数据结构
王道考研计算机408计算机数据结构完整导图（含所有概念，且针对每个概念附带小题考察）学习整本书，靠这个导图就够啦~
提示: 本内容由社区用户上传并分享。平台不对内容的真实性、合法性、知识产权归属及是否侵害第三方权利进行事前审核或保证。本内容可能包含受版权保护的图片、字体或其他第三方素材，使用前请自行确认授权范围。
- 王道
- 计算机408
- 整本书
- 附带题目
- 相似推荐
- 大纲
数据结构
绪论
数据结构
基本概念
数据
信息的载体，所有数据元素的集合
数据元素
数据中的一个个体
数据项
数据元素中的若干个部分
数据对象
具有相同性质数据元素的集合，是数据的一个子集
数据类型
原子类型
不可以再拆分的数据类型，比如int、string等
结构类型
还可以再拆分的类型
抽象数据类型
抽象数据组织以及其相关的操作
三要素
逻辑结构
线性结构
线性表
受限
栈
队列
推广
数组
非线性结构
集合结构
元素在同一个集合，之间没有关系
树型结构
一般树
二叉树
图状结构
有向图
无向图
物理结构（存储结构）
顺序存储
链式存储
索引存储
建立索引表进行存储。
优点
速度更快
缺点
占用额外的空间
散列存储（哈希表）
通过关键字计算该元素的存储地址
数据运算
增删改查、销毁创建等等
概要
算法
算法定义
解决问题的一系列步骤
特性
有穷
有限时间内完成
确定
相同的输入产生相同的输出
可行性
可以用已有的基本操作 实现算法
输入
丢给算法处理的数据（零或多个）
输出
算法处理的数据（一或多个）
好算法的特性
正确性
能解决问题
可读性
要让别人看得懂
健壮性
算法能解决一些异常状况
高效率和低存储需求
算法效率
算法时间复杂度：T(n)
主要是n的数量级，即n的最高次数
算法空间复杂度:S(n)
主要是存入变量的个数
数据、数据元素、数据项、数据对象的区别是什么？ 四者的包含关系为？ 数据里的最小单位是？最大单位是？ 数据类型包含哪三个？ 其中可以拆分的是哪个类型？ 不可以拆分的是哪个类型？ 抽象数据类型除了包含数据之外，还包含？ 逻辑结构包含哪两种？ 线性结构包含哪四种结构？ 由于受限产生的数据结构是? 因为推广得到的数据结构是？ 非线性结构包含哪三种？ 集合结构的元素之间是什么关系？ 树形结构包含哪两种？ 图状结构包含？ 数据结构三要素包含？ 物理结构包含哪四种存储结构？ 索引存储的特点是什么?优点是什么？缺点是什么？ 散列存储又叫做？ 散列存储的原理是？ 数据运算包含哪些部分？ 什么是算法？ 算法有哪五大特性？分别是什么？ 有穷是指时间还是空间？ 什么是确定性？ 什么是可行性？ 输入的数据可以为零个吗？ 输出的数据可以为零个吗？ 好算法有哪五大特性？ 解释什么是可读性、健壮性、高效率和地存储需求 时间复杂度主要跟什么因素有关？ 空间复杂度主要跟什么因素有关？ 数据机构整本书主要探究哪两个概念？
线性表
定义
n个相同的数据类型 有序、有限的排列的数据结构
基本操作
存储结构
顺序表
存储结构
算法实现
标注
实现方式
静态数组
标注
使用动态数组
标注
L.data = (ElemType *) malloc (sizeof(ElemType)* size);
顺序表存满时，可再用malloc动态拓展顺序表的最大容量
需要将数据元素复制到新的存储区域，并用free函数释放原区域
基本操作
插入
标注
删除
标注
按位查找
标注
时间复杂度
标注
链表（链式存储
单链表
定义
代码实现
标注
两种实现
不带头节点
首元素为第一个元素 空表判断：L==NULL
带头节点
第一个元素为空 空表判断：L——>next==NULL
操作
创建
头插法
标注
尾插法
标注
插入
按位插入
带头结点
不带头结点
指定节点的前后插入
删除
按位删除
指定节点的删除
查找
按位查找
注意与“顺序表”对比
按值查找
key
三种基本操作的时间复杂度都是O(n)
如何写循环扫描各个节点的代码逻辑
注意边界条件的处理
单链表的节点结构为 单链表的两种实现方式为 两种方式如何实现 创建单链表的两种方法 讲述单链表插入、删除、查找的算法思想 单链表插入、删除、查找的时间复杂度为
双链表
初始化
头节点的poior、next都指向NULL
插入
标注
删除
标注
遍历
定义
标注
循环链表
标注
代码问题
如何判空
头节点的prior和next的域都为L
如何判断节点p是否表尾/表头节点
尾节点时，p_>next=L
如何在表头/表尾插入/删除一个节点
静态链表
标注
顺序表和链表的比较
读写方式
顺序表：顺序或随机存储 链表：只能顺序存储
逻辑结构和物理结构
顺序存储：逻辑相邻，物理也相邻 链表：逻辑相邻，物理未必相邻
查找、插入和删除
查找：线性表：O（1） 链表O（n） 插入、删除 线性表：n 链表：1
空间分配
线性表的定义是？ 线性表一定有序吗 线性表可以无限元素 线性表的基本操作包含（列举10个） 顺序表逻辑相邻时，物理结构相邻吗 顺序表有哪两种实现方式 静态数组和动态数组的区别是 讲解顺序表插入、删除、按位查找的思想 顺序表按位查找的时间复杂度为？ 单链表的节点结构为 单链表的两种实现方式为 两种方式如何实现 创建单链表的两种方法 讲述单链表插入、删除、查找的算法思想 单链表插入、删除、查找的时间复杂度为 双链表如何初始化 双链表的插入、删除的算法思想是什么 循环列表如何判空 循环链表如何判断是否为表尾/头节点 如何在表头/表尾插入、删除一个元素 静态链表使用链表结构了吗 讲述静态链表的思想 静态链表的定义为 顺序表和链表的区别主要体现在哪四个方面 顺序表和链表关于顺序存储和随机存储的特性如何 顺序存储和链式存储哪个未必有物理相邻 顺序表、链表的查找、增删的时间复杂度如何
栈、队列和数组
操作受限
栈
栈的定义
只能在一端插入或者删除的线性表
栈顶
被增加或者删除的一端
栈底
空栈
逻辑结构
基本操作
创建销毁、增删改查（push\pop）、销毁栈
存储结构
顺序栈
定义
本质是个数组
栈顶指针
s.top
初始时
s.top=-1
栈顶元素
s.data[s.top]
进栈操作
栈顶指针+1，添加元素
栈空条件
s.top=-1
栈满条件
s.top=maxsize-1
操作
初始化
标注
子主题
判空
标注
子主题
进栈
标注
出栈
标注
读取栈顶操作
标注
链栈
定义
链式方式存储实现的栈
基本操作
共享栈
原理
一个向上走，一个向下走
栈满判定
top1 -top0=1时，表示栈满
空栈
top 0=1时，1号栈是空的 top1=max时，2号栈是空的
栈的应用
括号匹配问题
表达式求值问题
用栈实现中缀转后缀
用栈实现后缀表达式的计算
用栈实现中缀表达式的计算
队列在层次遍历中的作用
队列在计算机系统中的应用
队列
定义
先进先出
基本操作
标注
存储结构
顺序队列
初始条件
初始状态（队空条件):Q.front==Q.rear==0。
进入队列
进队操作:队不满时，先送值到队尾元素，再将队尾指针加1。
出队
队不空时，先取队头元素值，再将队头指针加1。
循环队列
定义
性质
标注
操作
初始化
标注
判对空
标注
入队
标注
出队
标注
链式队列
定义
标注
子主题
基本操作
初始化
标注
判对空
标注
入队
标注
出队
标注
队列的变种
双端队列
允许从两端插入、两端删除的队列
输入受限的双端队列
允许从两端删除、从一端插入的队列
输出受限的双端队殆∈
允许从两端插入、从一端删除的队列
考点:对输出序列合法性的判断
推广
数组
一维数组
定义
n个相同类型的数据元素组成的有限序列，每个元素是一个数组元素
存储结构
一维数组
按照顺序即可
多维数组
根据列进行存储
多维数组
压缩矩阵
对称矩阵
标注
三角矩阵
标注
三对角矩阵
标注
稀疏矩阵
个数很少的矩阵，可以直接用坐标表示很方便
什么是栈 栈是如何增加、删除操作？算法思想 栈有哪三种常见类型，三者的区别是什么 顺序栈如何初始化、判空、判满、进栈、出栈、读取栈顶？解释其算法思想 什么是链栈 共享栈的原理是？ 如何判断共享栈的站控和栈满？ 什么是队列 队列的增加、删除操作的思想是? 队列有哪三种常见的形式 顺序队列如何判空、判满、初始化、入队、出队 链式队列如何判空、判满、初始化、入队、出队 双端队列的算法思想是？ 什么是输入受限的双端队列 什么是输出首先的双端队列 数组的定义是 一维数组、多维数组是如何存入计算机当中的（解释其原理） 多维数组包含哪些类型 压缩存储包含哪三种矩阵，解释其原理 什么是稀疏矩阵，其如何用数据结构表示
拓展题库
1. 什么是栈？
2. 栈是如何增加、删除操作？算法思想是什么？
3. 栈有哪三种常见类型，三者的区别是什么？
4. 顺序栈如何初始化、判空、判满、进栈、出栈、读取栈顶？解释其算法思想。
5. 什么是链栈？
6. 共享栈的原理是什么？
7. 如何判断共享栈的站控和栈满？
8. 什么是队列？
9. 队列的增加、删除操作的思想是什么？
10. 队列有哪三种常见的形式？
11. 顺序队列如何判空、判满、初始化、入队、出队？
12. 链式队列如何判空、判满、初始化、入队、出队？
13. 双端队列的算法思想是什么？
14. 什么是输入受限的双端队列？
15. 什么是输出首先的双端队列？
16. 数组的定义是什么？
17. 一维数组、多维数组是如何存入计算机当中的？解释其原理。
18. 多维数组包含哪些类型？
19. 压缩存储包含哪三种矩阵？解释其原理。
20. 什么是稀疏矩阵？其如何用数据结构表示？
串
数据结构
逻辑结构
串，即字符串(String)是由零个或多个字符组成的有限序列。 是特殊的线性表，但是元素是字母
基本操作
标注
字符集编码
每个字符在计算机中对应一个二进制数，比较字符的大小其实就是比较二进制数的大小
存储结构
顺序存储
静态数组
标注
动态数组
标注
链式存储
标注
基本操作
标注
算法
模式匹配算法
朴素模式匹配算法
标注
算法思想
主串长度n，模式串长度m
将主串中所有长度为m的子串与模式串对比
找到第一个与模式串匹配的子串，并返回子串起始位置
若所有子串都不匹配，则返回0
KMP算法
求next数组
求nextval数组
参考主串该值一定不等于某个值进行移动
串和线性表的区别是 串的逻辑结构属于 串中的每个元素本质都是二进制数吗？ 比较字符的大小本质就是比较？ 串的顺序存储包含哪两种形式？他们的区别是 什么是链式存储？其包含哪些常见操作？ 什么是模式匹配算法，其有哪两种常见类型 朴素模式匹配的算法思想是？ KMP算法相对朴素匹配的优点是？ KPM算法在计算之前需要求出___？
树
基本概念
结点
一个点
根节点
最顶端的定点
分支节点
度数不为0的节点
叶子节点
度数为0的节点
节点的深度
从上往下累加
节点的高度
从下向上累加
节点的度
一个节点所有孩子的个数
树的度
树中所有节点的孩子的最大的度
边
两个节点之间的联系
有序树和无序树
如果节点的子树从左到右是有序的，则是有序树 反正是无序树
路径和路径长度
路径是两个节点之间的边 路径长度是边的个数
森林
森林
m棵不相交的树
常考性质
结点数=总度数+1
2)度为m的树中第i层上至多有m'-1个结点(i≥ 1)。
度为m的树
至少有一个结点度=m
一定是非空树
m叉树
允许所有结点的度都<m
可以是空树
3)高度为h的m叉树至多有(m'- 1)(m- 1)个结点。
4)具有n个结点的m叉树的最小高度为logm(n(m-1)+ 1)1。
存储结构
双亲表示法
顺序存储结点数据，结点中保存父节点在数组中的下标优点:找父节点方便;缺点∶找孩子不方便
孩子表示法
顺序存储结点数据，结点中保存孩子链表头指针（顺序+链式存储)优点:找孩子方便;缺点:找父节点不方便
孩子兄弟表示法
标注
森林与二叉树的转换
将树转化为二叉树 再将森林转化为二叉树
树和森林的遍历
标注
树的遍历
先根遍历
中序遍历
后根遍历
先序遍历
森林遍历
先序遍历
中序遍历
二叉树
基本概念
每个节点最多有两个子树
特殊二叉树
满二叉树
高度为h，含有2^h - 1个结点的二叉树
完全二叉树
叶子未必全满的树
二叉排序树
左子树关键字<根节点关键字<右子树关键字
平衡二叉树
左右子树深度差不超过1
性质
二叉树
1)非空二叉树上的叶子结点数等于度为2的结点数加1，即no=n2+ 1。
)非空二叉树上第k层上至多有2-1个结点(k≥1)。
3)高度为h的二叉树至多有2h-1个结点(h≥1)。
子主题
子主题
完全二叉树
具有n个(n >0）结点的完全二叉树的高度h为[ log,(n +1)或Llogzn]+1
对于完全二叉树，可以由的结点数n推出为0、1和2的结点个数为no、n1和n2(突破点:完全二叉树最多只会有一个度为1的结点)
存储结构
顺序二叉树： 用数组来表示二叉树
i的左孩子
—2i
i的右孩子
一-2i+1
i的父节点
一-li/2]
对于非完全二叉树来说，通过设置空可以转化为完全二叉树。 但浪费空间，因此顺序二叉树只适合存储完全二叉树
链式二叉树
标注
线索二叉树
what
标注
几个概念
线索
指向前驱/后继的指针称为线索
中序前驱/中序后继;先序前驱/先序后继;后序前驱/后序后继
三种线索二叉树
中序线索二叉树
以中序遍历序列为依据进行"线索化"
先序线索二叉树
以先序遍历序列为依据进行"线索化”
后序线索二叉树
以后序遍历序列为依据进行"线索化”
how
存储结构
在普通二叉树结点的基础上，增加两个标志位ltag和rtag
ltag=时，表示Ichild指向前驱;ltag==0时，表示lchild指向左孩子
rtag==1时，表示rchild指向后继;rtag==O时，表示rchild指向右孩子
如何手画线索二叉树
标注
why
作用:方便从一个指定结点出发，找到其前驱、后继;方便遍历
代码实现
先序
中序
后序
如何基于线索二叉树找前驱和后继
哈夫曼树
基本概念
带权路径长度
节点的权
节点的数值
节点的带权路径长度
树的根到该节点的长度 * 该节点的权值
树的带权路径长度
每个节点的带权路径长度之和
哈夫曼树定义
带权路径长度最小的树
哈夫曼树的构造
每次选两个根节点权值最小的树合并，并将二者权值之和作为新的根节点的权值
哈夫曼编码
每个节点在该哈夫曼树中的编码
将字符频次作为字符结点权值，构造哈夫曼树，即可得哈夫曼编码，可用于数据压缩
并查集
三要素
逻辑结构——元素之间为“集合”关系
基本操作
Find (S[ ],x)——“查”，找到元素x所属集合
初始化——初始化并查集，将所有数组元素初始化为-1
Union (s[ ], root1, root2)——“并”，将两个集合
存储结构——顺序存储，每一个集合组织成一棵树，采用“双亲表示法”
优化
用根节点的绝对值表示一棵树(集合)的结点总数
Union操作合并两棵树时，小树并入大树
算法
二叉树的遍历
先序
左中右
中序
中左右
后序
右中左
层次遍历
上中下（队列思想）
由遍历树构造出二叉树
前序+中序遍历序列
后序+中序遍历序列
层序+中序遍历序列
key
1.先找根节点
2.根据中序确定左右子树群
解释什么是节点、根节点、分支节点、叶节点 解释什么是节点深度、节点高度，二者本质区别是什么？内容是否有所不同 什么是节点的度和树的度 在树中，什么是边 什么是有序树和无序树 什么是路径和路径长度 森林的概念是 树中，节点数和度数的关系是 度数为m的数中，第i层最多有多少个节点 高度为h的m叉树最多有多少个节点 具有n个节点的m叉树的最小高度为 什么是双亲表示法，解释其算法思想和优缺点 什么是孩子表示法，解释其算法思想和优缺点 什么是孩子兄弟表示法，解释其算法思想和优缺点 树如何转化为二叉树、森林如何转化为二叉树 二叉树、树、森林的遍历分别有哪些？ 三者有什么样的对应关系 什么是二叉树 什么是满二叉树 什么是完全二叉树 什么是二叉排序树 什么是平衡二叉树 二叉树的叶子节点数 和 度数为2的节点数有什么关系 非空二叉树上的第K层最多有多少个节点 高度为h的二叉树最多有多少个节点 知道两个节点的坐标i,和n，如何判断两者的左右孩子关系 具有n个节点的完全二叉树的高度为 什么是顺序二叉树 顺序二叉树的存储容器是 如何判断两个节点是否为父子关系 链式二叉树的算法思想是 线索二叉树的意义是 什么是线索 线索二叉树有几种类型，分别是 线索二叉树和链式二叉树的区别是？通过哪个元素将二者区分开 如何手画线索二叉树（哪两步） 解释节点的权、节点的带权路径长度、树的带权路径长度 什么是哈夫曼树 如何根据节点构造哈夫曼树 什么是哈夫曼编码 如何构造哈夫曼编码 并查集是针对哪种逻辑结构设计的？使用哪种数据结构实现的？ 并查集有三种常见操作分别是？ 二叉树的四种遍历方案分别是 四种方案的算法思想是 四种遍历是否都有递归和非递归实现思路 如何由遍历得到对应的二叉树（针对三种情况，逐个讨论) 共性的方法是
图
基本概念
定义
定义:G=(V,E)，顶点集V，边集E
常见术语
有向图
每条边都有方向
无向图
每条边都没有方向
简单图
不存在重复边 定点到自己的边
多重图
与简单图相对，存在重复到自己的边
顶点的度、入读、出度
（无向图）顶点的度：依附于该顶点边的条数 入度：到达该顶点的度 出度：从该顶点离开的度数
边的权
每条边都有一个数值，该数值称为权值
权图（网）
边带权值的图称为权图（网）
无向图（无向边/边)、有向图（有向边/弧)顶点的度、出度、入度（无向图?有向图? )边的权、带权图/网
点到点的关系
路径
一个点到另一个点的路径
路径长度
路径上的边的数量
回路
第一个定点和最后一个顶点相同的路径，称之为环
简单路径
路径中，定点不重复出现的路径是简单路径
简单回路
除了第一个和最后一个定点之外，其他顶点不重复出现的回路称为简单回路
距离
两个顶点之间的最短路径。如果不存在路径，则是∞
图的局部
子图
一个图的子集
联通
两个点之间存在路径，则称之为联通
连通图
任意两个点都是联通的，则称之为连通图
连通分量
无向图中的极大连通子图
强连通
v到w，w到v都存在有向边，则两个点强连通
强连通图
任意两个点都是强连通的，称之为强连通图
强连通分量
有向图的极大强连通图
生成树
包含了图中全部定点的极小连通子图。砍掉任何一条边都会变成非连通图
生成森林
非连通图的连通分量共同构成了一个生成森林
连通无向图的生成树——包含全部顶点的极小连通子图
非连通无向图的生成森林——各连通分量的生成树
几种特殊形态的图
完全图
任意两个点之间都存在边
稠密图
边很多的图
稀疏图
边很少的图b
树、森林
有向树
一个顶点入度为0，其他所有顶点入度都是1的树
图的存储
邻接矩阵法
用一个一维数组表示点，二维数组表示边
要点
定义
标注
邻接表
当稀疏图的时候，邻接矩阵太浪费空间，因此使用邻接表。每个点对应指针
定义
标注
十字链表
邻接多重表
图的应用
图的遍历
广度优先算法（BFS）
先遍历某个顶点的所有孩子，接着遍历所有孩子的孩子
广度优先生成树
性能分析
标注
子主题
深度优先算法（DFS）
性能分析
最小生成树
Prim算法 （从点开始寻找）
标注
kruskal算法 （从边开始寻找）
标注
最短路径问题
单源最短路径
BFS算法（无权图）
Dijkstra算法（带权图，无权图）
标注
各顶点间最短路径
Floyd算法（带权图、无权图）
标注
有向无环图
有向图不存在环，则是有向无环图，DAG图
求表达式
标注
拓扑排序（AOV网）
定义
标注
步骤
标注
关键路径
所有项目完成所需要的最短时间
举个例子，假设我们要建造一栋房子，该项目包括多个任务，如设计平面图、挖掘基础、砌墙、安装水电、装修等。我们可以将每个任务表示为一个节点，将它们之间的依赖关系表示为边，构建成一个项目网络图。 在这个项目网络图中，每个任务的时间和前置任务都已经确定。通过计算每个任务的最早开始时间（EST）和最晚开始时间（LST），我们可以得出每个任务的总时长和它们之间的依赖关系。最终，我们可以找出整个项目的关键路径，这条路径上的任务必须按照严格的顺序完成，否则整个项目的完成时间就会延迟。
AOE网
图的定义是 图跟两个变量有关，分别是哪两个，符号是什么 有向图和无向图的区别是 简单图和多重图的区别是 顶点的度是否等于入度+出度 什么是边的权 什么是权图？权图又称为？ 什么是路径？路径长度？ 什么是回路？又称之为？ 什么是简单路径和简单回路 什么是距离？不相连的点之间的距离为？ 子图一定包含于原图是吗？ 什么是联通？什么是连通图？什么是连通分量？ 什么是强连通？什么是强连通图？什么是强连通分量？ 什么是生成树和生成森林？ 什么是完全图？ 稠密图和稀疏图的区别是 什么是有向树？ 图的存储有几种方法？最常用的两种是？ 解释邻接矩阵的思想？ 邻接矩阵法的点用什么表示？边用什么表示？ 邻接表法的本质是？ 解释邻接表法的算法思想 十字链表和临界多重表的本质相同，对吗？ 图的遍历有哪两种方法，英文名是？ 解释两种方法的算法思想？ 广度优先是否可以用来生成树 最小生成树有哪两种算法？其主要区别是？ 最短路径问题有几种算法，分别是？ 解释Dijkstra算法的思想？ 解释Floyd算法的思想？ 什么是有向无环图？ 有向无环图有哪个应用？其核心思想是? 拓扑排序和关键路径分别称为___网？ 什么是拓扑排序？其核心算法思想是？ 什么是关键路径？其在现实中有什么应用
查找
基本概念
查找
在数据集合中寻找满足某种条件的数据元素的过程称为查找
查找长度
需要对比关键词的次数
平均查找长度
所有查找过程中进行关键字的比较次数的平均值
算法
顺序查找
按照顺序一个一个的对比着找
优化方法
标注
时间复杂度
n
折半查找
标注
正常查找
折半查找判定树
标注
构造特定
右边一定比左边多0或1
时间复杂度
分块查找
标注
平均查找长度
标注
二叉排序树
左<中<右
查
类似折半查找，对半着找就好
增
标注
构造
删
零子节点
直接删除
单子节点
直接替换
双子节点
右子节点的第一个孩子上位 或者左子节点的最右边孩子上位
时间复杂度
标注
平衡二叉树
任意子树的左右高低只差不大于一
插入操作
调整平衡二叉树
左旋树（LL）
左子树的左节点插入
右旋树（RR）
右子树的右节点插入
左右旋（LR）
左子树的右节点插入
右左旋（RL）
右子树的左节点插入
删除操作
保持树的平衡
红黑树
why
为了更好的插入和排序，引入了红黑树
定义
标注
性质
①每个结点或是红色，或是黑色的。 ②根结点是黑色的。 ③叶结点（虚构的外部结点、NULL结点）都是黑色的。 ④不存在两个相邻的红结点(即红结点的父结点和孩子结点均是黑色的)。⑤对每个结点，从该结点到任一叶结点的简单路径上，所含黑结点的数量相同。
结论1:从根到叶结点的最长路径不大于最短路径的2倍。 结论2:有n个内部结点的红黑树的高度h≤2logz(n + 1)。
插入操作
在平衡二叉树的基础上，再更改一下颜色即可
B树类
B树
标注
基本概念
B树，又称多路平衡查找树，B树中所有结点的孩子个数的最大值称为B树的阶，通常用m表示。一棵m阶B树或为空树，或为满足如下特性的m叉树:
:
插入
删除操作
B树的高度
标注
1）因为B树中每个结点最多有m棵子树，m-1个关键字，所以在一棵高度为h的m阶B树中关键字的个数应满足n≤(m- 1)(1 +m+m2+…+m)=mh-1，因此有h ≥ logm(n+1)
2）若让每个结点中的关键字个数达到最少，则容纳同样多关键字的B树的高度达到最大。由B树的定义:第一层至少有1个结点;第二层至少有2个结点;除根结点外的每个非终端结点至少有「m/2]棵子树，则第三层至少有2「ml/21个结点……第h+1层至少有2(「m/27)午1个结点，注意到第h+1层是不包含任何信息的叶结点。对于关键字个数为n的B树，叶结点即查找不成功的结点为n+1，由此有n+122([m/2l)1，即h ≤logTm2((n+ 1)/2)+1。 例如，假设一棵3阶B树共有8个关键字，则其高度范围为2≤h≤3.17。
B树的查找
B树的插入
标注
B树的删除
标注
B+树
特点
1）每个分支结点最多有m棵子树（孩子结点)。 2）非叶根结点至少有两棵子树，其他每个分支结点至少有「m/2棵子树。3）结点的子树个数与关键字个数相等。 4)）所有叶结点包含全部关键字及指向相应记录的指针，叶结点中将关键字按大小顺序排列， 并且相邻叶结点按大小顺序相互链接起来。 5）所有分支结点（可视为索引的索引）中仅包含它的各个子结点《即下一级的索引块）中 关键字的最大值及指向其子结点的指针。
B树和B+树的区别
1)在B+树中，具有n个关键字的结点只含有n棵子树，即每个关键字对应一棵子树;而在 B树中，具有n个关键字的结点含有n+1棵子树。 2)在B+树中，每个结点(非根内部结点）的关键字个数n的范围是「m/27≤n≤m(根结点: 2≤nsm);在B树中，每个结点（非根内部结点）的关键字个数n的范围是「m21-1snsm-1(根结点:1≤n≤m- 1)。 3)在B+树中，叶结点包含信息，所有非叶结点仅起索引作用，非叶结点中的每个索引项只 含有对应子树的最大关键字和指向该子树的指针，不含有该关键字对应记录的存储地址。4）在B+树中，叶结点包含了全部关键字，即在非叶结点中出现的关键字也会出现在叶结点中; 而在B树中,叶结点(最外层内部结点)包含的关键字和其他结点包含的关键字是不重复的。
解释什么是查找 什么是查找长度 什么是平均查找长度 对于一般的数组查找，给出一个算法的思路 解释顺序查找、折半查找、分块查找的算法思想 解释折半查找树的算法思想 如何计算折半查找和分块查找的时间复杂度 什么是二叉排序树 二叉排序树和折半查找树一样吗？ 解释二叉排序树如何查找数据 解释二叉排序树如何增加数据 解释二叉排序树如何删除数据 解释二叉排序树在删除数据时，零子节点、单子节点、双子节点如何实现 什么是平衡二叉树 调整平衡二叉树有哪四种操作 解释四种操作的算法思想 删除操作的调整应满足什么特点 什么是红黑树，其和平衡二叉树的区别是 为什么引入红黑树 红黑树的每个节点可能是哪几种颜色 根节点是什么颜色，虚构的叶节点是什么颜色 不存在两个相邻的___色节点 对每个节点，从该节点到任意一个叶节点的简单路径上，所含__色节点数量相同 什么是B树、其和二叉树有什么区别 B树如何增删数据 B+树和B树的区别是
排序
基本概念
排序
就是重新排列表中的元素，使表中的元素满足按关键字有序的过程。
评价指标
稳定性
关键字相同的元素经过排序后相对顺序是否会改变
时间复杂度、空间复杂度
排序分类
内部分类
元素都在都存之内的排序
外部分类
数据太多，无法全部放在内存里
分类
插入排序
每次把最大的放在最后面
优化——折半插入排序
标注
折半算法
举例
假设我们要对数组 [5, 2, 4, 6, 1, 3] 进行排序，那么插入排序的过程如下： 第一轮排序 将数组中第一个元素 5 当做已排好序的序列，将第二个元素 2 插入到已排好序的序列中，得到 [2, 5, 4, 6, 1, 3]。 第二轮排序 将数组中前两个元素 2, 5 当做已排好序的序列，将第三个元素 4 插入到已排好序的序列中，得到 [2, 4, 5, 6, 1, 3]。 第三轮排序 将数组中前三个元素 2, 4, 5 当做已排好序的序列，将第四个元素 6 插入到已排好序的序列中，得到 [2, 4, 5, 6, 1, 3]。 第四轮排序 将数组中前四个元素 2, 4, 5, 6 当做已排好序的序列，将第五个元素 1 插入到已排好序的序列中，得到 [1, 2, 4, 5, 6, 3]。 第五轮排序 将数组中前五个元素 1, 2, 4, 5, 6 当做已排好序的序列，将第六个元素 3 插入到已排好序的序列中，得到 [1, 2, 3, 4, 5, 6]。
希尔排序
标注
交换排序
冒泡排序
标注
算法
性能
快速排序
标注
基本概念
举例
快速排序是一种高效的排序算法，它的基本思想是通过不断地选取基准元素，将待排序序列分成两个子序列，其中一个子序列的元素都比基准元素小，另一个子序列的元素都比基准元素大，然后对这两个子序列进行递归排序，最终得到一个有序序列。下面举一个简单的例子来讲解快速排序的过程： 假设我们要对数组 [5, 2, 4, 6, 1, 3] 进行排序，那么快速排序的过程如下： 选择基准元素 选择数组中的第一个元素 5 作为基准元素。 分割数组 将数组中的元素按照大小分成两个子序列，一个子序列的元素都比基准元素小，另一个子序列的元素都比基准元素大，得到 [2, 4, 1, 3] 和 [6] 两个子序列。 递归排序 对两个子序列分别进行递归排序，得到 [1, 2, 3, 4] 和 [6] 两个有序子序列。 合并数组 将两个有序子序列合并，得到 [1, 2, 3, 4, 6]。
选择排序
简单选择排序
第i趟排序即从L[ i...n]中选择关键字最小的元素与L(i)交换
每一趟把最小的值放在最前面
性能
堆排序
大根堆
父母比孩子要大
小根堆
父母比孩子要小
排序思想
堆排序是一种非常高效的排序算法，它的基本思想是利用堆这种数据结构进行排序。堆是一种特殊的树形数据结构，它的每个节点都比其子节点大或小，具有非常好的特性，可以用来实现高效的排序算法。下面举一个简单的例子来讲解堆排序的过程： 假设我们要对数组 [5, 2, 4, 6, 1, 3] 进行排序，那么堆排序的过程如下： 建立堆 将待排序的数组构建成一个大根堆，也就是保证每个节点的值都比其子节点的值大，得到 [6, 5, 4, 2, 1, 3]。 排序 将堆顶元素 6（最大值）与堆底元素 3（最后一个元素）进行交换，得到 [3, 5, 4, 2, 1, 6]，此时数组的最后一个元素 6 已经排好序了。 重新调整堆 对堆顶元素 3 进行向下调整操作，重新构建大根堆，得到 [5, 3, 4, 2, 1]。 排序 将堆顶元素 5（最大值）与堆底元素 1（最后一个未排序的元素）进行交换，得到 [1, 3, 4, 2, 5]，此时数组的最后两个元素 5 和 1 都已经排好序了。 重新调整堆 对堆顶元素 1 进行向下调整操作，重新构建大根堆，得到 [4, 3, 1, 2]。 排序 将堆顶元素 4（最大值）与堆底元素 2 进行交换，得到 [2, 3, 1, 4]，此时数组的最后三个元素 5, 1 和 4 都已经排好序了。 重新调整堆 对堆顶元素 2 进行向下调整操作，重新构建大根堆，得到 [3, 2, 1]。 排序 将堆顶元素 3（最大值）与堆底元素 1 进行交换，得到 [1, 2, 3]，此时数组的所有元素都已经排好序了。
归并排序
将数组切分成很多个小数组，然后不断归并小数组进行排序
思路
标注
1. 假设我们要对数组 [9, 3, 7, 2, 8, 1, 5, 4, 6] 进行排序，那么归并排序的过程如下：
2. 分割 将数组从中间划分为两个子数组，左边的子数组为 [9, 3, 7, 2]，右边的子数组为 [8, 1, 5, 4, 6]。
3. 递归分割 对左右两个子数组分别进行递归分割，将左边的子数组继续划分为 [9, 3] 和 [7, 2]，将右边的子数组继续划分为 [8, 1]、[5, 4] 和 [6]。
4. 合并 将两个子数组 [9, 3] 和 [7, 2] 合并为一个有序数组 [2, 3, 7, 9]，将三个子数组 [8, 1]、[5, 4] 和 [6] 合并为一个有序数组 [1, 4, 5, 6, 8]。
5. 归并 将左右两个有序数组 [2, 3, 7, 9] 和 [1, 4, 5, 6, 8] 归并为一个有序数组 [1, 2, 3, 4, 5, 6, 7, 8, 9]。
基数排序
标注
思想
从个位到最高位进行排列
性能
解释基数排序的算法思想 基数排序是从个位开始还是最高位开始
外部排序
背景
数据规模较大，无法在内存中排序。需要在外部进行排序
原理
划分块 将文件划分为若干个大小相等的块，每个块的大小可以适当调整，以便于能够将其全部读入内存中进行排序。 对每个块进行排序 对每个块进行内部排序，可以使用任意一种排序算法，例如快速排序、归并排序等。 合并块 将排好序的块进行合并，可以使用归并排序等算法，将排好序的块进行合并，得到一个有序的文件。
什么是排序 排序有哪些评价指标 什么是排序的稳定性 什么是时间复杂度、和空间复杂度 什么是内部排序和外部排序 解释插入排序的思想 解释希尔排序的思想 交换排序有哪两种 解释冒泡排序的思想 解释快排的思想 选择排序有哪两种 解释简单选择排序的思想 解释堆排序的算法思想 解释归并排序的算法思想 解释外部排序的算法思想
浮动主题
查漏补缺
队列的应用
KMP算法深究