数据结构与算法
2022-07-17 14:05:03 2 举报AI智能生成
登录查看完整内容
2023考研数据结构预算法完整详细思维导图
作者其他创作
大纲/内容
简单模式匹配
最大相同前后缀
计算机表达算法 P117
next数组的求法
nextval数组的求法
KMP算法
串的模式匹配
顺序查找
有序表的顺序查找
折半查找（只适用于顺序结构）
分块查找
线性结构
二叉排序树
LL平衡旋转
RR平衡旋转
LR平衡旋转
RL平衡旋转
插入
删除
查找
平衡二叉树
定义和性质
插入的3种情况
删除的4种情况
红黑树
插入（分裂结点）
删除（合并结点）
B树
与B树的区别
B+树（用于数据库）
树形结构
直接定址法
除留余数法
数字分析法
平方取中法
散列函数构造方法
线性探测法
平方探测法
双散列法
伪随机序列法
只能逻辑删除元素，并且需要定期维护散列表
开放定址法
拉链法
解决冲突的方法
平均查找长度ASL
填装因子
散列表性能分析
散列表
查找算法
直接插入排序
折半插入排序
希尔排序
插入排序
冒泡排序
快速排序
交换排序
简单选择排序
堆排序
选择排序
归并排序
基数排序
内部排序
时间复杂度
空间复杂度
算法稳定性
算法的比较次数 与 序列初态的关系
算法的排序趟数 与 序列初态的关系
每趟结束是否有一元素可以到达最终位置
算法的过程特征
内部排序算法的比较
1、生成初始归并段
2、归并归并段
步骤
S = h-1 = ⌈ logk(r) ⌉
归并趟数
减少内部排序时的比较次数
败者树
减小 r
生成初始归并段
置换-选择排序
最佳归并树
外部排序
排序算法
算法
顺序表
单链表
双链表
循环单链表
循环双链表
循环链表
静态链表
链表
线性表
顺序栈
共享栈
顺序存储
链栈
链式存储
进制转换
迷宫求解
递归
表达式求值
括号匹配
应用
栈
顺序队列（存在\"假溢出\"）
循环队列
单链表队列
循环单链表队列
循环双链表队列
循环表队列
输入受限的双端队列
输出受限的双端队列
双端队列
树的层次遍历
缓冲池SPOOLING技术
资源竞争的进程队列
页面替换算法
广度优先搜索图
队列
对称矩阵
三角矩阵
三对角矩阵
稀疏矩阵
特殊矩阵
递归算法
非递归算法
先序遍历
中序遍历
访问结点p时，栈内结点为p的所有祖先，可以用于查找根结点到p的路径
后续遍历
需要借助队列
层次遍历
二叉树的遍历
先序序列 和 后序序列不能够唯一确定一个二叉树
由遍历序列构建唯一二叉树
二叉树
线索二叉树的构造
线索二叉树的遍历
线索二叉树（物理存储结构）
区别 双亲表示法 和 二叉树的顺序存储
双亲表示法
孩子表示法
孩子兄弟表示法
存储结构
先根遍历（与二叉树的先序遍历相同）
后根遍历（与二叉树的中序遍历相同）
遍历方式
二叉链表
森林与二叉树的转换
先序遍历（与二叉树的先序遍历相同）
中序遍历（与二叉树的中序遍历相同）
森林
不存在度为0的结点
哈夫曼树的构建
哈弗曼编码
哈夫曼树
并查集
树的应用
树
有向图与无向图
连通图和强联通图
图的定义
适合稠密图
邻接矩阵
邻接表
十字链表（有向图）
邻接多重表（无向图）
图的存储
空间复杂度O(|V|)
邻接矩阵 O(|V|2)
邻接表 O(|V|+|E|)
性能分析
广度优先 BFS
深度优先 DFS
图的遍历
时间复杂度O(|V|2)
Prim算法(适合稠密图)
时间复杂度(|E|log|E|)
Kruskal算法(适合稀疏图)
最小生成树（贪心算法）
适用于正权值有向图
Dijkstra算法(贪心算法)
时间复杂度O(|V|3)
适用于 无带负权值 的有向图
Floyd算法
最短路径(有向图)
有向无环图描述表达式 DAG图
深度优先也可以实现拓扑排序，栈中元素为逆拓扑排序
每个顶点有唯一的前驱后继关系，则拓扑排序唯一
若邻接矩阵是三角矩阵，则存在拓扑排序
两个充分不必要
拓扑排序 AOV网
关键路径不唯一
关键路径 AOE网
图的应用
数据结构
数据结构与算法
收藏
职业：本科
0 条评论
回复 删除
下一页
