考研数据结构
2021-09-14 12:22:01 1 举报AI智能生成
考研数据结构重难点考点+思考方法全总结
作者其他创作
大纲/内容
树
二叉搜索树=二叉排序树=二叉查找树
二叉树
h=log2n(向下)+1
h=log2(n+1)(向上)
h=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*递归深度
空间复杂度
递归深度
选择排序
简单(直接)选择
从左到右找出min放在第一个位置
时间复杂度0(n^2)
堆排序
大根堆
找根节点保证大于等于左右
子主题
小根堆
归并排序(一般是2路)
m路归并每选出一个元素最少需要对比关键字m-1次
空间复杂度为：数组B的空间o(n)+递归开辟的(log2n)=O(n)
基数排序
时间复杂度
关键字对比次数
与比较趟数有关
与比较趟数有关
每趟时间复杂度×趟数
空间复杂度
申请空间
查找
折半查找（二分查找）
定义low high mid
指的是下标
key对比mid
小于mid
high=mid-1
再次计算新mid
大于mid
low=mid+1
再次计算新mid
B树
根节点
关键字
子树个数
其他结点
子树
关键字
关键字的值
左中右
分块
散列表
散列函数
直接定址法
数字分析法
除留余数法
平方取中法
处理冲突
开发定址法
线性探测
再散列
平方探测
拉链法
图
遍历
时间空间复杂度
时间
邻接表
O(|V|+|E|)
领阶矩阵
O(|V|^2)
空间
存储顶点的队列
O(|V|)
AOV
结点=事件
边=活动
数据结构
逻辑结构
线性结构
数组/栈和队列
线性表
顺序表
链表
串
类似线性表
非线性结构
树图
存储结构
顺序存储
串/数组/顺序表
连式存储
串/链表
散列存储
索引存储
串、广义表、稀疏矩阵
广义表
元素可为空
可为空
稀疏矩阵
顺序存储
三元组表表示法
data
非零元素
行
列
伪地址表示法
链式存储
十字链表表示法
邻接表表示法
三元组的顺序和链式存储
三元组表
十字链表
串
特殊的线性表
基础计算知识
取模=取余=%
1%5=1
0 条评论
下一页
