考研数据结构
2021-09-14 12:22:01 1 举报AI智能生成
考研数据结构重难点考点+思考方法全总结
作者其他创作
大纲/内容
二叉搜索树=二叉排序树=二叉查找树
h=log2n(向下)+1h=log2(n+1)(向上)
二叉树
给出结点能快速找出父节点
当完全二叉树来存储
层次遍历
空的补0
顺序存储
不平衡(结点)的左孩子右旋
同时左孩子的右孩子连到结点的左边
LL
不平衡的右孩子的左孩子进行RL
RL
旋转
结点左子树和右子树高度差
平衡因子
平衡二叉树
子主题
线索二叉树
给出中序和另一个序能还原唯一一个
遍历
左孩子有兄弟原则
二叉树->树
树
1<=i<=length+1
插入
1<=i<=length
删除
顺序表
线性表
最坏(2+..+n)次比较次数
有哨兵
最坏(1+..+n-1)次比较次数
吴少兵
直接插入
折半插入
希尔排序(缩小增量排序)
插入排序
临时变量
空间复杂度O(1)
flag记录是否排好
冒泡
最坏n蹭
最好log2n(向下)+1
递归次数参考二叉树深度
n*递归深度
时间复杂度
递归深度
空间复杂度
快速排序
交换排序
时间复杂度0(n^2)
从左到右找出min放在第一个位置
简单(直接)选择
找根节点保证大于等于左右
大根堆
小根堆
堆排序
选择排序
每次堆排序完成后将最大/小元素交换后接在堆最后不管进行下一次排序
m路归并每选出一个元素最少需要对比关键字m-1次
空间复杂度为：数组B的空间o(n)+递归开辟的(log2n)=O(n)
归并排序(一般是2路)
基数排序
分类
每趟时间复杂度×趟数
关键字对比次数与比较趟数有关
申请空间
内部排序
指的是下标
定义low high mid
high=mid-1
再次计算新mid
小于mid
low=mid+1
大于mid
key对比mid
折半查找（二分查找）
关键字
子树个数
根节点
子树
其他结点
左中右
关键字的值
B树
分块
直接定址法
数字分析法
除留余数法
平方取中法
散列函数
线性探测
再散列
平方探测
开发定址法
拉链法
处理冲突
散列表
查找
做题时不用不用推理midhigh直接分两边手演示画出
O(|V|+|E|)
邻接表
O(|V|^2)
领阶矩阵
时间
O(|V|)
存储顶点的队列
空间
时间空间复杂度
考虑访问顶点和找各条边
结点=事件
边=活动
AOV
图
数组/栈和队列
链表
类似线性表
串
线性结构
树图
非线性结构
逻辑结构
串/数组/顺序表
串/链表
连式存储
散列存储
索引存储
存储结构
数据结构
元素可为空
可为空
广义表
非零元素
data
行
列
三元组表表示法
伪地址表示法
十字链表表示法
邻接表表示法
链式存储
三元组表
十字链表
三元组的顺序和链式存储
稀疏矩阵
特殊的线性表
串、广义表、稀疏矩阵
1%5=1
取模=取余=%
基础计算知识
DS
0 条评论
回复 删除
下一页
