考研二战-DS整理复习
2023
04-01
DS第一章节绪论部分。
04-02
DS第一章节绪论部分。
06-06
完蛋了,感觉自己进度落后太多了,加油啊!!
[toc]
DS再复习
第一章
绪论部分的基本概念
- 数据:一个很宽泛的概念 他是数据元素的集合
- 数据元素:组成数据的基本元素。通常作为一个整体考虑。用来表示一个对象,例如学生数据中 的一条学生信息(包含id,姓名……)
- 数据项:组成数据元素的最小不可分割单元。不可分割是逻辑意义上的,例如上述学生数据中的基本组成就是 id 姓名…… 这些单独拿出来就是一个数据项。
- 数据对象:数据的一个子集,由多个数据元素组成。是具有相同性质的数据元素的集合(这里的相同性质的解释如下:例如整数集合,也就是组成该数据对象的数据元素都是整数;或者混合类型:例如上述的学生信息表,但是组成整个数据对象的数据元素的“类型”都是一样的)
- 数据类型:一个值的==集合==以及定义在这个集合上的==一系列操作==。
- 数据结构:相互之间存在==一种或多种关系的数据元素的集合== 数据的“结构”就是这里的数据元素之间的关系。
- 逻辑结构:从逻辑关系上描述数据,是从具体问题中抽象出来的数学模型。 通常有四类:集合、线性、树、图结构
graph TD 逻辑结构-->线性结构 逻辑结构-->非线性结构 线性结构-->一般线性表 线性结构-->特殊线性表 线性结构-->线性表的推广 非线性结构-->树结构 非线性结构-->图结构 非线性结构-->集合 树结构-->树 树结构-->二叉树 图结构-->有向图 图结构-->无向图 一般线性表-->线性表 线性表-->顺序存储:顺序表 线性表-->随机存储:链表 特殊线性表-->栈与队列 特殊线性表-->字符串 线性表的推广-->广义表 线性表的推广-->数组
markdown mermaid 代码部分
1 | graph TD |
- 物理结构: ==数据对象==在计算机中的==存储表示==。()
- 通常有两种结构:顺序存储和链式存储。(严书第二版只提到两种存储结构,其实是四种。)
graph TD 存储结构-->顺序存储 存储结构-->随机存储 随机存储-->链式存储 随机存储-->索引存储 随机存储-->散列存储Hash
1 | graph TD |
一个表示 数据、数据元素、数据项、数据对象之间的关系的图:
存储结构\存取结构
- 存取结构
- ==随机存取==, 重点在”取”上,指访问指定单元的速度与其位置无关,
- ==非随机存取(顺序存取)==: 取第i个位置上的元素必须遍历前面的i-1个元素, 链表
- 存储结构,如上 四种
- ==顺序存储==: 指的是计算机开辟一个连续的空间来存储他们.重点在于物理上的存储空间的”开辟”.
- ==随机存储==: 不是开辟一段连续的物理空间.
- 索引存储
- 散列存储
- 链式存储
存取结构描述的是啥?
存储结构是数据结构中的一个重要的组成
算法和算法分析
算法的定义和要求
定义:是为了解决某一问题而设计的一系列的(有穷)有限长度的操作(步骤)序列。
一个合格的算法应该具备下列的性质:
- 有穷性
- 确定性:算法过程中遇到的所有情况都有特定的解决方案,==不会产生二义性==
- 可行性:可以由已经定义的所有基本操作实现。
- 输入:有0个或者多个输入。
- 输出:有一个或者多个输出。
评价算法的指标
- 可读性
- 高效性
- 健壮性
- 正确性
时间复杂度和空间复杂度
- 问题规模:算法输入量的大小,输入规模的大小
- 语句频度:一条语句执行的次数
算法的效率分析并不是单纯的计算程序从编译到执行所用的所有时间,而是计算程序中所有的语句频度之和而得出的一个估计。
因而一个算法的执行时间可以用该算法内部所有的语句频度之和来表示。
时间复杂度
衡量一个算法的时间复杂度用其基本语句的执行频度。(基本语句:指的是其在算法中执行次数与算法的运行时间成正比的语句)从而得出算法的运行时间的函数 而程序的时间复杂度记为 其定义是:
故O的含义是当输入规模趋近于无穷的时候问题的执行时间的上限不会超过 (定义了算法执行时间的上限)。
- 最好时间复杂度、最坏时间复杂度、平均时间复杂度。
这个和概率相关。后面的实例会遇到。
普通循环结构的时间复杂度的分析
1 | for(int i = 0;i<n;++i){ |
第一章小结
- 弄清楚考察重点在哪:时间复杂度和空间复杂度的估计。
- 递归函数的时间复杂度计算。
- 某些特定算法的时间复杂度 例如 2013年的题目:
- 构建起对后面将要学习的内容的一个框架。
2013年计算时间复杂度的题目个人理解
需要用到时间复杂度的定义,可以粗略计算出当前的相对准确的语句频度,然后在选项中找到其乘以一个系数一定大于这个频度的
2013统考的这道题目的正确解法:
先想出最坏的情况:连续上升元素交替出现在两个链表中。故最坏的频度是m+n 又 所以根据时间复杂度的定义
只有答案 符合定义。
时间复杂度的计算中三次连续的求和的最终值为
线性表
个人感觉,这一章没啥好讲的,线性表的存储。重点在于最后的线性表的应用相关的算法。
线性表的定义1
由n个数据特性相同的元素构成的有限序列称为线性表;n为其线性表的长度。
一个非空的线性表或者线性结构具有以下特点:
- 存在唯一一个头
- 存在唯一一个尾
- 除尾元素外,每个元素都有一个直接后继
- 除头元素外,每个元素都有一个直接前驱。
线性表的顺序存储表示(也称作:顺序表)
特点:逻辑上相邻的数据元素其物理次序也是相邻的。
线性表的链式存储表示(链表)
单链表
- 头插
- 尾插
- 插入
- 删除
双链表
循环链表
判空条件
双循环链表
判空条件
链表的两种存储方式的比较
- 顺序存储
读写:可顺序存取、可随机存取
按值查找:顺序查找On 有序时可 log
按序号查找:O 1
删除增加 :O(n)
- 链式存储
读写:顺序存取
按值查找:O n
按序号查找: O n
删除增加: 快
栈队列与数组
栈
先进后出? 后进先出
卡特兰数
卡特兰数的常见应用:n个节点的不同构的二叉树个数 = $C{n}$、$2n+1$个节点的不同构的满二叉树的个数 = $C{n}$
计算n个不同的数入栈有多少个不同的出栈序列?===$C{n} = \frac{1}{n+1} C{2n}^{n}$
为什么卡特兰数给出的合法出栈顺序数能保证出栈顺序的唯一:栈的特性,出栈的数必定是栈顶元素(当前最后一个入栈的数字。所以只要入栈出栈的操作序列不同那么出栈的元素顺序一定不相同
队列
循环队列的判空,判满
双端队列的判空、判满
栈和队列的应用
王道课后习题速查
第二章线性表
2.1 线性表的定义和基本操作
- c
- b
- a
2.2 线性表的顺序表示
A (D 存疑)
A (存储结构.)
B
==B —正解- >D== :存取操作—插入删除操作
随机存取\顺序存取 顺序存储\随机存储(上面有介绍)
本题的重点在于存取操作,而不是插入删除操作. 需要明确对于顺序表来说,插入&删除操作所需要的时间复杂度高.
A
C
C
C
C
B
D
2.3线性表的链式表示
- B\D ==B==
- B
- C
- D/C 不确定5是不是正确的 ==D==
- A
- C
- B ==D== 最低时间复杂度!并不是最好情况!
- C
- C
- B
- B; A
- C
- D
- A
- B
- D
- D
- A
- C
- C
- C
- B
- D
- D
- D
- D
第三章 栈、队列与数组
==卡特兰数==
3-1
- B
- C
- B
- C
- A
- A
- D ==C== 需要执行删除第一个元素的操作,需要找到第一个元素的前一个元素!
- C
- D
- B ==A==
- B 计算不同的出栈序列个数:为什么出栈序列数=卡特兰数
- D 简单模拟
- D
- D
- D
- C 简单模拟
- C
- C
- A ==C==
- B\D 共享栈 上溢 下溢 ==B==
- A ==共享栈判断==
- C 简单模拟
- D
- B 观察出栈的序列特性
- C
- C
- B
- D
- D
3-2 队列
- D
- B
- D
- B
- D
- C
- B
- C
- A / B ==B==
- A
- A
- A ==D==
- D
- B ==A==
- C 枚举
- C
- B
- C ==A==
- C
- C
- D
3-3 栈和队列的应用
- B ==D==
- B
- C
- B
- A ==B==
- D ==B==
- C
- B
- A
- B
- A 表达式转换==中缀表达式转后缀表达式。
- B
- A
3-4 数组索引
- 行优先、列优先
- 三角矩阵
- 普通矩阵
- 三对角阵— k对角阵
- D
- C
- A
- D
- B
- C
- B
- B
- B ==A==
- A
- C
- B
第四章 串
4-1 KMP算法
如何计算next数组?
需要搞清楚:前缀、后缀和部分匹配值。前缀
next数组和nextval数组有什么区别?
- C
- B
- C D
- A
- C
- C
- D ==C==
- C
- A ==B==
第五章 树
5-1 哈夫曼树
树的所有节点度之和为多少
- 节点之间的关系:双亲、兄弟、子孙、祖先、堂兄弟节点
- 节点的度:该节点的子树个数
- 分支节点(非终端节点)、叶节点(终端节点)
- 节点的深度、高度、层次
- 节点深度从根节点开始
- 节点高度从叶节点开始
- 树的高度:最大节点高度、最大节点深度
- 路径:
- 节点到节点之间的路径
- 树的路径长度:根到每一个节点的路径总和
- D
- A
- C ==A== 树的路径长度
- A
- A
- C
- B
5-2 完全二叉树 节点数 与 节点度
已知节点数如何去计算当前完全二叉树的高度:
节点i所在的深度:
- C
- A
- B
- B
- C
- C
- C
- C
- C
- A
- A
- D
- C
- B
- B
- A
- C
- D
- C
- C
- A
- A
5-3 线索二叉树 二叉树的遍历
什么是线索二叉树
树的三种遍历之间的关系
- 若先序遍历和后续遍历序列正好相反,那么这个树的高度和节点数一致,就是每一层只有一个节点,每个节点要么缺少右子树 要么缺少左子树。
- 线索二叉树不能解决:先序求先驱,后续求后驱
- 在三种线索二叉树的遍历中需要使用栈辅助:后序线索树
- C
- C
- C
- C/D ==C==
- A? ==C==
- ? ==B==
- C
- B ==D==
- C
- C
- C
- B
- D
- D
- A
- B
- A
- B ==C== 线索二叉树是一种物理结构?
- C
- C
- D
- D
- ? ==D==
- D ==C== X是父亲节点
- D ==C==
- B
- D
- D
- C
- A
- A
- D
- B
- B
- B
- B
5-4 树、森林
树的存储结构
- 双亲表示法:序号、类似并查集的做法
- 孩子表示法
- 孩子兄弟表示法 就是树的二叉树化,一层中的最左孩子节点的兄弟节点作为右孩子。
森林与二叉树的转换
- 树转二叉树:右兄弟节点转为右孩子,自己的第一个孩子就是自己的左孩子。
- 树转二叉树中:
- 二叉树的遍历和树的遍历关系:
- 树的==先序== \==二叉树的==先序== \== 森林的==先序==
- 树的==后序== \==二叉树的==中序== \== 森林的==中序==
- 树的==层序== \==二叉树的==后序== \==
- 二叉树的遍历和树的遍历关系:
- 树转二叉树后 节点性质的对应关系。
D
A ==D== 个人理解:将森林转二叉树,根节点是第一个树的根,根节点右指针指向第二棵树的根节点
森林的定义:森林是 m (m>=0)棵互不相交的树的集合。每棵树去除根节点后,其子树就组成了森林。
D
A
B
? ==C==
D ==B==
C
D
B
B
B ??==D==
D ? ? ==C==
C
B
C
C
C
5-5 哈夫曼树
前缀码:若没有一个编码是另一个编码的前缀,则称这样的编码为前缀编码。
哈夫曼编码集、定长编码集合:
定长编码集就是固定长度例如有n个字符那么每个编码长度就是
如何从哈夫曼树得到一个可变长度前缀编码?
- A
- C
- B ==
- B 不会 ==C==
- A ==B==
- D
- C
- B
- C
- D
- A
- D
- D
- D
- A
- C
- B
- D
第六章 图
模糊的概念:
- 【有向图概念】强连通(两个点之间是强连通的)、强连通图、强连通分量。
完全图:
- 无向完全图 get
- 有向完全图 任意两个点双向都有弧
路径长度:边的个数
- 回路、环。
- 环存在的充分条件:有n个顶点,有大于n-1条边。
- 简单回路、简单路径(不重复)
- 图的遍历:??
- 每个节点只被访问一次!
- 有向图中的弧:??单独的连向两个点的一条有向边
- 连通分量:??
6-1 图的基本概念
- A
- D
- B
- D ==C== 无向图的极大连通子图成为
- C
- C
- A
- D
- C 自环?==D== 数据结构中只讨论简单图,所以不考虑自环!
- D 完全图+一个点
- D
- B
- 不会 ==C==
- A
- C
- C
- C
- B
- D
6-2 图的存储
十字链表
节点域
边域
十字链表的作用,简化存储、容易计算有向图任意一点的出度和入度。
邻接多重表:简化邻接表中对边的删除等操作。
- B
- C
- D
- D
- C D ==1、B==
- B
- _
- B
- B
- D
- B
- A
- D
- C
- B
- C
- D
- A
- B
6-3 图的遍历
- DFS的生成树
- BFS的生成树:在所有的搜索生成的生成树中最低。
BFS算法复杂度:
- 空间复杂度:
- 时间复杂度:
- 邻接矩阵:
- 邻接表:
DFS算法复杂度:
- 空间复杂度:
- 时间复杂度:
- 邻接矩阵:
- 邻接表:
判环算法:
- DFS
- 拓扑排序
- A
- C
- C A ==C A C A==
- A A
- C ==D==
- B ==D==
- B ==B D==
- A B
- D
- D ==C==
- A
- C ==B==
- A
- A ==C==
- D
- C ==D==
- D
6-4 最短路径问题、最小生成树问题
拓扑序列:
- 若有向图的拓扑有序序列唯一,图中的节点入度和出度不一定都为1,(完全图)
- 拓扑序列唯一,不能唯一确定该图,想想一条线和完全图
有向无环图:
只要无向连通图中没有权值相同的边,则其最小生成树唯一
最短路径一定是简单路径
求最短路径无法判定有向图中是否出现环。!!
- A
- C
- B ==A==
- C ==A==
- B
- C 如何判环:拓扑排序和DFS可以 ==A==
- D
- C ==D==
- D
- A ==C==
- C
- B 拓扑序列唯一=就一个方向一条直线?。 ==C==
- C
- D ? C ==C== D:关键活动不一定在关键路径上,
- C
- A
- B
- B ==A== B 错在“所有权值最小的边一定会出现在所有的最小生成树中”
- C
- C
- C
- D
- C
- B
- B
- D
- B ==C==
- A
- A
- B
- B
- A
- C
- B
第七章 查找
7-1 顺序查找与折半查找
平均查找长度:
- 顺序查找
- 无序线性表的平均成功查找长度、失败查找长度
- 有序线性表的平均成功查找长度、失败查找长度
- 折半查找
- 分块查找
- 顺序查找
二叉排序树会退化
表长度为n的有序表所进行的二分查找的树的高度为
折半查找时候,判定次数:
查找成功时的查找长度:为从==根结点到目的结点的路径上的结点数==
查找不成功时的查找长度:为从==根结点到对应失败结点的父结点==的路径上的==结点数==
最后到达不成功节点的父节点的时候进行了对其父节点的比较就可以知道到底查找成不成功,所以无需再比较一次。
- A
- B
- B
- A
- D
- C
- B
- B
- B
- B
- A
- A B
- A D
- B
- A
- B
- C 对索引和块中数据都用二分查找
- B
- A
- B
- A
7-2 树型查找
红黑树:
- 从根到叶结点的最长路径不大于最短路径的2倍。
- 有n个内部结点的红黑树的高度
红黑树和AVL树的平衡差别:
- 可见,红黑树的“适度平衡”,由AVL树的“高度平衡”,降低到“==任意一个结点左右子树
的高度,相差不超过2倍==”,也降低了动态操作时调整的频率。- 因为黑路同所以每一个节点的左右子树到叶节点路径上的黑节点数量都相同,但是红节点数量不相同,并且红节点最多和黑节点个数一样,所以左右子树的高度差最多是两倍关系。
AVL树删除一个点再插入同一个点可能不变吗?:==可能不变!==
AVL树的层数对应的最少节点:1、2、4、7、12、20…… 。
AVL树的最多节点情况:满二叉树
- C
- B
- A
- B
- C
- C
- A
- D
- D
- B ==C==
- B
- A ==D== 红黑树的查询效率和AVL差不多,但是插入删除效率比AVL树高。
- B ==C==
- ? ==B==
- C
- D
- B
- C
- A
- B
- C
- D
- D
- C
- A
- B
- D
7-4 B 树和B+树
B- B+树种节点和关键字是两个不同的东西。
B-树的特性:
- 非叶节点
- 叶节点
- 非叶节点也存储内容,非叶节点中有数据
- 节点内部关键字有序
B-树的相关应用:磁盘存取次数
- B-树高度定义:(不包括最后一层的下面的不带任何信息的叶节点)
- B-树之间的关系:(==高度下界==)
- B-树最高的情况:(每一层的节点都只有最少孩子节点)(==高度上界==)
- B-树种最后一层的下面的查找失败的叶节点个数和节点个数有什么关系:
B树中的大部分操作所需的磁盘存取次数与B树的高度成正比。
B-树查找特性:
- B树查找失败的查找次数和查找成功的次数:
- 失败次数要是最下面一层+1(最后的叶节点所在的层)
B-树的插入:
当元素满当前节点能接受的最大个数后,分裂选择的是向上提一级。
B+树的特性:
与B树不一样的地方:
- 每个节点的关键字个数和其子树个数一致。
- 最后一层有单独一串链接
- 节点只记录最后孩子的索引
B+树的应用:数据库索引查找,B-树也可以(MangoDB用的就是B-树)
==随机查找?顺序查找==:
- A
- C
- B
- B
- A
- B A 看清楚问的是节点还是关键字
- D
- C B
- A B
- D
- D
- C
- A
- D
- A
- C
- D
7-5 散列表
散列表的组成
- 散列函数
- 散列方法
- 直接定址
- 除留余数
- 数字分析
- 平方取中
- 处理冲突方法
- 开放定址
- 线性再探
- 平方再探
- 伪随机序列
- 双散列
- 拉链
- 开放定址
- 散列方法
- 散列表
第八章 排序
总结:
选择排序
| 算法 | 时间复杂度 | 最坏时间复杂度 | 空间复杂度 | 稳定性 |
| —————— | ——————————————— | ——————— | ————— | ——— |
| 简单选择排序 | | | | 不稳定 |
| 堆排序 | MAX(建堆,排序) = | | | 不稳定 |堆排序中 堆的初始化为,每对一个元素进行排序,就是将顶部元素拿出将底部元素放入再调整的时间为 一共是
插入排序
| 算法 | 时间复杂度 | 最坏时间复杂度 | 空间复杂度 | 稳定性 |
| —————— | ———————————————- | ——————— | ————— | ——— |
| 插入排序 | 最好: 平均: | | | 稳定 |
| 折半插入排序 | | | | 稳定 |
| 希尔排序 | | | | 不稳定 |
交换排序
| 算法 | 时间复杂度 | 最坏时间复杂度 | 空间复杂度 | 稳定性 |
| —— | ———————————————- | ——————— | —————————————— | ——— |
| 冒泡 | 最好: 平均: | | | 稳定 |
| 快排 | | | 最好 最坏 | 不稳定 |
归并排序
| 算法 | 时间复杂度 | 最坏时间复杂度 | 空间复杂度 | 稳定性 |
| ———— | —————————————————- | ——————— | ————— | ——— |
| 归并排序 | 最好: 平均: | | | 稳定 |
基数排序
| 算法 | 时间复杂度 | 最坏时间复杂度 | 空间复杂度 | 稳定性 |
| ———— | ————— | ——————— | ————— | ——— |
| 基数排序 | | | | 稳定 |
8-1 排序的基本概念
- C
- A
- B
- A
8-2
在判断sheir排序的时候一定要注意 跟着题目要求做一遍排序,不然仅仅凭借前两个元素很难判断选项中的序列是不是一遍之后 的结果
折半插入排序的时间复杂度:比较次数改变了,但是没有改变移动次数,还是
- B
- A
- D A
- C
- B
- C
- A
- B
- C
- D ==A==
- B ==C==
- A
- C
- C
- B
- D
- B
- A
- D
8-3 交换排序
- A
- C
- D
- C
- D
- D
- A
- C
- A D ==基准数到序列中间==
- B
- C
- B C
- A
- ? ==D==
- A
- C
- D
8-4 选择排序
堆如何初始化:
- 从最底层开始向上调整(大根或者小根)
- 调整的时候从左右孩子节点中选一个最合适的与父节点交换。
- 调整完,再检查子树,调整子树,最后再向下一个节点
堆中的数据与其位置的关系:
堆排序的时间复杂度:
- 构建堆:
- 排序+重构堆:
堆的删除:
- 将最后一个节点放到第一个元素上
- 调整
堆的添加:
- 将待加入节点放到最后一个位置上
- 向上调整。(不必和初始化一样调整所有)
- C ==A==
- C
- ? ==D==
- D
- D
- C
- B
- C C
- A D
- D
- A
- B
- A
- C
- A
- C
- B
8-5 归并排序、基数排序
归并排序(2路归并):
- 最小的归并段含有两个元素。
- 归并趟数:
- 时间复杂度:
- 空间复杂度:
- 稳定
基数排序:
LSD MSD
- lsd:从最低位开始,分配 - 回收 - 分配 - 回收……
- MSD:就是LSD的从高位开始分配 - 回收的版本。
时间复杂度
- 空间复杂度
- 稳定
- C
- C
- C ==D C==
- C ==A==
- B
- B
- A B
- B
- D
- B ==C==
- C
- D
- B
- C
- A
8-6
各类算法总结:
- B ==A==
- C
- C
- DUO
- 1 4 6
- 2 6 7
- 1 4
- A
- B
- A
- C
- C
- A
- C
- D
- D
- A
- D
8-8 外部排序
顺序?按照什么来排序?
内外来看:可以分为内部和外部
先后来看:构建初始归并段、对归并段进行k路归并(含有内部归并操作)
- 原始数据得到初始归并段,全部数据完成了一次读内存和写出外存操作 (一次完整读写)
- 如何优化:
- 置换选择排序
- 如何优化:
- 对归并段进行归并,读写次数取决于归并树的高度。(带权路径长度)
- 如何优化:
- 去除外部k路对于内部排序的影响:使用败者树
- 对于减少归并树的高度:最佳归并树 (添加虚段)
- 如何优化:
一般以磁盘块为单位进行读写。
归并树为严格k叉树
归并树的高度和归并趟数的关系:树的高度-1 = 归并趟数S。
==多路平衡归并与败者树==:
为什么提出败者树?为了使得内部归并不受外部归并的路数k的影响
败者树的最高高度:
==最佳归并树==:
为什么要添加虚段(通过n个初始归并段构造k路最佳归并树是有条件的:树的基本特性和哈夫曼树的基本特性限制了这一点):即只有初始节点(度=0的节点满足和k路归并之间的数量条件)
- 如果 则需要添加个虚段
- B
- DUO
- C
- B
- A
- B
- D
- ==对缓冲区的概念不熟悉==
- ==D==
- ==A==
- B
- B
考点
第一章
时间复杂度和空间复杂度
学习过程中发现模糊的点
程序从编译到执行的过程。
计组中的边界对齐
关键词
弄清楚顺序表、静态链表不是一回事儿
1. 数据结构 C语言版 (第二版)(严蔚敏、李冬梅、吴伟民) ↩