登录免费注册



考研数据结构

首页  思维导图  详情



考研数据结构

2021-09-14 12:22:01   1  举报





AI智能生成

考研数据结构重难点考点+思考方法全总结

考研专题

数据结构

王道

考研408，学霸笔记

考研

大学教育

模版推荐

作者其他创作

大纲/内容

树

二叉搜索树=二叉排序树=二叉查找树

二叉树

h=log2n(向下)+1<br>h=log2(n+1)(向上)

顺序存储

当完全二叉树来存储

给出结点能快速找出父节点

层次遍历

空的补0<br>

平衡二叉树

旋转

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)

基数排序

时间复杂度

关键字对比次数<br>与比较趟数有关

<font color="#c41230">每趟时间复杂度×趟数</font>

空间复杂度

申请空间

查找

折半查找（二分查找）

定义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

 Collect

Get Started

考研数据结构知识框架笔记

 Collect

Get Started

数据结构图__1

 Collect

Get Started

0402 - 数据结构

 Collect

Get Started

理发店系统数据结构













评论

0 条评论

下一页



图形选择

思维导图

主题

补充说明

AI生成





修改AI描述

去编辑

重新生成

提示 

关闭后当前内容将不会保存，是否继续？

取消

确定

Document