考研 408 数据结构 · 背诵清单
这张图讲什么
「考研 408 数据结构 · 背诵清单」是 SeekFlaw 编辑团队整理的思维导图,分 8 个一级分支:必背 · 考点清单:数据结构分五块背;必背 · 线性表、栈、队列与串;必背 · 树与二叉树;必背 · 图;必背 · 查找;必背 · 排序;常见 · 易混辨析:四组概念;必背 · 一页纸速记:数据结构压缩版,共 116 个节点、115 张记忆卡,含 6 张配图。
这张图是 408 数据结构的背诵清单,按「线性表与串、树与二叉树、图、查找、排序」的顺序只取要背的性质、公式、复杂度和遍历排序要点,分【必背】【常见】两档。考前 7 天:先背必背的枝(线性表栈队列串、树与二叉树、图、查找、排序),每张卡只背一件事;考前 3 天:补易混辨析;考前 1 天:只看最后一枝「一页纸速记」,看正面说背面。
5 个要点
- 必背 · 考点清单:数据结构分五块背——【必背】先分清五块各背什么,再定先后:按「线性表、树、图、查找、排序」的顺序背最稳。
- 必背 · 线性表、栈、队列与串:【必背】先背顺序表与链表的对照和移动次数,再背栈与队列的要点(出栈序列数、表达式求值、栈满条件、循环队列),然后是数组与特殊矩阵的地址公式…
- 必背 · 树与二叉树:【必背】先背二叉树的结点数、空指针数性质和完全二叉树的编号,再背遍历、还原与线索,然后是树和森林的转换、树的存储结构、树的结点数与度数、并查集…
- 必背 · 图:【必背】先背度与边数的公式和连通所需的最少边数,再背邻接矩阵与邻接表的对照、遍历,然后是最小生成树与最短路径,最后背拓扑排序与关键路径。
- 必背 · 查找:【必背】先背顺序、折半、分块三种查找的 ASL,再背二叉排序树的删除、AVL 和红黑树的性质,最后背 B 树的阶与关键字范围、插入删除…
适用:考研备考。用法:点开任一节点先自己答,再翻面核对。
配图:模式 abaabc 的 next 与 nextval 对照表,两处不同的格用橙…;同一棵七结点二叉树的前序、中序、后序和层序遍历序列;权值 1、2、3、4 的哈夫曼树,左边记 0、右边记 1,带各叶子的编码;七个元素的折半查找判定树,标出每层的比较次数;AVL 树 LL、RR、LR、RL 四种失衡类型对应的插入位置与调整方法;九种内部排序的平均时间、最坏时间、空间复杂度与稳定性对照表。
发布于
一句话:这张图把「考研 408 数据结构 · 背诵清单」整理成 116 个节点、115 张记忆卡;点开节点翻面就能看答案。
408 数据结构考前背诵清单:线性表、树、图、查找、排序的性质公式与复杂度,遍历和排序要点,附一页纸速记。点开任一节点翻面看答案,登录后可存进自己的空间,按遗忘曲线复习。
SeekFlaw 求瑕是面向初中、高中、考研、考公考前速记的思维导图与记忆卡平台:把课件、讲义变成思维导图,节点翻面就是记忆卡,按遗忘曲线安排复习。
116 个节点 · 115 张记忆卡。作者:SeekFlaw 编辑团队;发布于 2026-11-20。
先看这 3 条
- 数据结构背诵分哪几块?:分五块:线性表、栈、队列与串,树与二叉树,图,查找,排序。
- 图的度数之和与完全图的边数怎么记?:无向图所有顶点的度之和等于边数的 2 倍 ;有向图的入度之和与出度之和都等于边数。
- 线性表与栈队列压缩成一句?:顺序表查得快、插入删除慢,链表找到位置后插入删除快、按位序查得慢;各位置等概率时顺序表插入平均移动 $n/2$ 个、删除平均移动 $(n-1)/2$ 个;出栈序列数是 卡特兰数 …
必背 · 考点清单:数据结构分五块背
- 数据结构背诵分哪几块?:分五块:线性表、栈、队列与串,树与二叉树,图,查找,排序。每块背 性质公式、复杂度和固定步骤 ,不背代码。 记法 线性、树、图、查找、排序。
- 线性表、栈、队列与串这一块背什么?:背顺序表与链表的对照和操作代价、顺序表插入删除的移动次数、头结点、 出栈序列的个数 、栈与队列的应用、中缀转后缀与后缀求值、顺序栈与共享栈的栈满条件、循环队列的公式、数组与特殊矩阵的地址公式,以及 KMP 的复杂度与 next、nextv…
- 树与二叉树这一块背什么?:背二叉树的结点数与空指针数性质($n_0=n_2+1$ 等)、完全二叉树的编号、四种遍历与由遍历还原二叉树、线索二叉树、树与森林和二叉树的转换、树的存储结构、树的结点数与度数的关系、并查集,以及 哈夫曼树 的构造与编码。
- 图这一块背什么?:背度与边数的关系、连通所需的最少边数、邻接矩阵与邻接表的对照、DFS 与 BFS 的复杂度、Prim 与 Kruskal、Dijkstra 与 Floyd、拓扑排序和 关键路径 。
- 查找这一块背什么?:背顺序、折半与分块查找的 ASL、二叉排序树的删除、AVL 的旋转与最少结点数、红黑树的性质、B 树的阶与关键字范围、B 树的插入删除、B 树与 B+ 树的对照,以及 散列的冲突处理和装填因子 。
- 排序这一块背什么?:背各内部排序的时间复杂度、空间复杂度和稳定性,插入、希尔、快速、堆(含插入删除)、归并排序的要点,以及 外部排序的归并趟数和最佳归并树 。
必背 · 线性表、栈、队列与串
- 顺序表和链表怎样对照着记?:顺序表是 随机存取 ,按位序取元素 $O(1)$,插入删除要移动元素 $O(n)$,要连续空间;链表是 顺序存取 ,按位序取元素 $O(n)$,找到位置后插入删除只改指针 $O(1)$,空间不必连续,但每个结点多一个指针域。 易错 链表的…
- 顺序表插入和删除平均要移动多少个元素?:各位置等概率时,长度为 $n$ 的顺序表:插入位置有 $n+1$ 种, 平均移动 $n/2$ 个元素;删除位置有 $n$ 种,平均移动 $(n-1)/2$ 个元素。最坏情况(在表头操作)分别移动 $n$ 个和 $n-1$ 个,最好情况(在…
- 单链表和双链表的常用操作各要多少时间?:已知结点 $p$,在 $p$ 之后插入新结点、删除 $p$ 的后继,单链表都是 $O(1)$;删除 $p$ 自己,单链表要先找 前驱 ,需要 $O(n)$,双链表有前驱指针,只要 $O(1)$;按位序或按值找结点都是 $O(n)$。 考法…
- 链表为什么要设头结点?:头结点放在第一个元素结点之前,使第一个结点的插入、删除与其他结点一致,不必单独处理, 空表与非空表 的处理也统一。头指针是指向第一个结点的指针,不论有没有头结点都存在。 区分 带头结点的空表是头结点的指针域为空,不带头结点的空表是头指针为…
- n 个不同元素依次入栈,合法的出栈序列有多少种?:有 卡特兰数 种:$\dfrac{1}{n+1}\mathrm{C}_{2n}^{n}$。同样的数也是 $n$ 个结点能构成的不同形态二叉树的个数。 例 $n=3$ 时是 5 种,$n=4$ 时是 14 种。
- 栈和队列各用在哪些地方?:栈用于括号匹配、表达式求值、递归调用和 深度优先搜索 ;队列用于 层序遍历 、 广度优先搜索 和缓冲区。两者的入、出、判空等基本操作的时间都是 $O(1)$。 记法 后进先出的用栈,先进先出的用队列。
- 中缀表达式怎样转成后缀表达式?:从左到右扫描:操作数直接输出;遇运算符,先把栈顶 优先级不低于 它的运算符依次弹出输出,再让它入栈;遇左括号入栈,遇右括号就弹出到左括号为止;扫完后栈里剩下的全部弹出。 例 $a+b\times c$ 转成 $abc\times+$。
- 后缀表达式怎样求值?:从左到右扫描:遇 操作数 就入栈;遇 运算符 就连续弹出两个操作数,先弹出的是 右操作数 ,算出结果再压回栈;最后栈里只剩一个数,就是结果。 例 3 4 + 2 * :先算 $3+4=7$,再算 $7\times2=14$。
- 顺序栈和共享栈的栈满条件是什么?:顺序栈:约定 $top$ 初值为 $-1$(指向栈顶元素)时,栈空为 $top=-1$,栈满为 $top=\text{MaxSize}-1$;约定 $top$ 初值为 0(指向下一个空位)时,栈空为 $top=0$,栈满为 $top=\t…
- 循环队列的入队、出队和元素个数怎么算?:设循环队列的数组长度为 $\text{MaxSize}$, 队头 指针 $front$ 指向队头元素, 队尾 指针 $rear$ 指向队尾元素的下一个位置:入队时把元素存入 $rear$ 处再令 $rear=(rear+1)\%\text…
- 二维数组按行优先存放,元素地址怎么算?:设数组为 $A[m][n]$,下标从 0 起,每个元素占 $L$ 个单元,首地址为 $\text{LOC}$:$\text{LOC}(A[i][j])=\text{LOC}+(i\times n+j)\times L$;按 列优先 则为 …
- 对称矩阵和下三角矩阵怎样压缩存储?:对称矩阵只存 下三角 (含主对角线)共 $n(n+1)/2$ 个元素,按行优先存入一维数组;下标从 0 起时 $a_{ij}$($i\ge j$)的位置是 $k=\dfrac{i(i+1)}{2}+j$,$i\lt j$ 的元素用 $a_…
- 三对角矩阵怎样压缩存储?:只存 带状区域 $|i-j|\le1$ 内的元素,共 $3n-2$ 个,按行优先存放。下标从 0 起时,$a_{ij}$ 的位置是 $k=2i+j$。 例 $a_{12}$ 的位置是 $k=2\times1+2=4$:前面依次是 $a_{…
- KMP 算法的时间复杂度是多少,比朴素匹配好在哪?:主串长 $n$、模式串长 $m$:朴素匹配最坏 $O(nm)$, KMP 为 $O(n+m)$(求 next 数组 $O(m)$,匹配 $O(n)$)。KMP 的关键是匹配失败时 主串指针不回退 ,只让模式串指针按 next 数组回退。
- next 数组怎么求?:下标从 1 起:$\text{next}[1]=0$,$\text{next}[2]=1$,其余 $\text{next}[j]$ 等于 $p_1\cdots p_{j-1}$ 的 最长相等前后缀长度加 1 。 例 模式 abaabc 的…
- nextval 数组怎么由 next 数组修正?:从左向右算,$\text{nextval}[1]=0$;若 $p_j=p_{\text{next}[j]}$,则 $\text{nextval}[j]=\text{nextval}[\text{next}[j]]$,否则 $\text{n…
必背 · 树与二叉树
- 二叉树各层与整棵树的结点数范围是多少?:以根为第 1 层:第 $i$ 层最多有 $2^{i-1}$ 个结点;高度为 $h$ 的二叉树最多有 $2^{h}-1$ 个结点,最少有 $h$ 个;高度为 $h$ 的 完全二叉树 结点数范围是 $2^{h-1}\sim2^{h}-1$。 …
- 二叉树的叶子数 $n_0$ 和度为 2 的结点数 $n_2$ 是什么关系?:$n_0=n_2+1$。推导只需一句:总结点数 $n=n_0+n_1+n_2$, 总分支数 $n-1=n_1+2n_2$,两式相减即得。 易错 这个关系只适用于二叉树;一般的树要用「结点数等于总度数加 1」去列式。
- 完全二叉树的结点编号有什么规律?:按层序从 1 起编号:结点 $i$ 的左孩子是 ${2i}$,右孩子是 $2i+1$,双亲是 $\lfloor i/2\rfloor$;有 $2i\le n$ 才有左孩子,有 $2i+1\le n$ 才有右孩子;编号 $i\gt \lfl…
- n 个结点的完全二叉树,高度和叶子数是多少?:高度为 $\lceil\log_2(n+1)\rceil$,等价于 $\lfloor\log_2 n\rfloor+1$(根为第 1 层);叶子数为 $\lceil n/2\rceil$,分支结点数为 $\lfloor n/2\rfloo…
- 二叉链表里有多少个空指针域?:$n$ 个结点的二叉链表共有 ${2n}$ 个指针域,其中 $n-1$ 个指向孩子,所以有 $n+1$ 个 空指针域 ;线索二叉树正是用这 $n+1$ 个空指针域存放线索。
- 二叉树的前序、中序、后序和层序遍历怎么记?:前序:根、左、右;中序:左、根、右;后序:左、右、根;层序:按层从上到下、每层从左到右,用 队列 实现。三种深度优先遍历的非递归写法都用栈,时间 $O(n)$,空间 $O(h)$($h$ 为树高)。 图:前序 ABDECFG,中序 DBE…
- 哪些遍历序列的组合能唯一确定一棵二叉树?:前序加中序、后序加中序、 层序加中序 都能唯一确定;前序加后序不能,因为分不出左右子树(只有不含度为 1 的结点时才能确定)。 例 前序 AB 、后序 BA 对应两棵树:B 是 A 的左孩子或右孩子都符合。 记法 前序或后序定根,中序分左…
- 前序、中序、后序遍历得到的序列有什么对应关系?:三种遍历中 叶子结点的相对次序相同 ,都是从左向右。对于任意结点,前序序列里它排在子孙之前,后序序列里它排在子孙之后,中序序列里它夹在左右子树之间。
- 三种线索二叉树各方便找前驱还是后继?:三种线索树里, 中序线索树 的前驱、后继都方便找:不用栈也不用双亲,沿孩子指针或线索走即可;前序线索树方便找后继,找前驱要用到双亲;后序线索树方便找前驱,找后继要用到双亲。 记法 线索二叉树用 ltag、rtag 标记指针是孩子还是线索,…
- 树和森林怎样转成二叉树?:树转二叉树用 左孩子右兄弟 :每个结点的左指针指向它的第一个孩子,右指针指向它的下一个兄弟;森林转二叉树时,把各棵树对应的二叉树依次作为前一棵树根的右子树连起来。 记法 树的先根遍历对应二叉树的前序,树的后根遍历对应二叉树的中序;森林的先…
- 树的三种存储结构怎样对照着记?:三种表示法的取舍在于找双亲快还是找孩子快。 双亲表示法 :用数组存结点,每个结点记双亲的下标,找双亲 $O(1)$,找孩子要扫整个数组; 孩子表示法 :每个结点带一个孩子链表,找孩子快,找双亲要扫所有链表; 孩子兄弟表示法 :左指针指第一…
- 树的结点数和度数有什么关系,叶子数怎么算?:树的结点数等于 所有结点的度数之和加 1 。设度为 $i$ 的结点有 $n_i$ 个,则 $n=1+\sum i\cdot n_i$,叶子数 $n_0=n-\sum_{i\ge1}n_i$。 例 度为 4、3、2、1 的结点分别有 2、1…
- 并查集的两种操作和优化是什么?:Find 找到元素所在集合的根, Union 把两个集合的根连起来;用树存储,双亲下标放在数组里。两种优化:路径压缩(Find 时把经过的结点直接挂到根上)和按秩合并(把小树并到大树下),优化后的复杂度几乎是常数。
- 哈夫曼树怎样构造,带权路径长度怎么算?:每次从森林里选 权值最小的两棵树 合并成一棵新树,新根权值是两者之和,重复到只剩一棵树。带权路径长度 $\text{WPL}=\sum w_i l_i$,即每个叶子的权值乘它到根的路径长度,再求和。 例 权值 1、2、3、4:先合并 1、…
- 哈夫曼树有什么结构特点?:有 $n$ 个叶子的哈夫曼树共有 $2n-1$ 个结点, 没有度为 1 的结点 ,度为 2 的结点有 $n-1$ 个;权值较大的叶子离根较近。哈夫曼树的形状不唯一,但带权路径长度唯一,并且是最小的。
- 哈夫曼编码有什么特点?:左分支记 0、右分支记 1(也可相反,以题目约定为准),从 根到叶子 的路径上依次读出的 0/1 串就是该叶子的编码。哈夫曼编码是 前缀编码 :没有一个字符的编码是另一个字符编码的前缀,所以译码没有二义性;它是平均码长最短的前缀编码,出现…
必背 · 图
- 图的度数之和与完全图的边数怎么记?:无向图所有顶点的度之和等于边数的 2 倍 ;有向图的入度之和与出度之和都等于边数。 记法 无向完全图有 $n(n-1)/2$ 条边,有向完全图有 $n(n-1)$ 条边。
- 图保持连通至少要几条边?:$n$ 个顶点的无向图要连通,至少需要 $n-1$ 条边; 有向图强连通 至少需要 $n$ 条边(一个有向环)。无向图在不连通的情况下最多有 $\dfrac{(n-1)(n-2)}{2}$ 条边,再多一条就一定连通。
- 邻接矩阵和邻接表怎样对照着记?:邻接矩阵:空间 $O(n^2)$,适合 稠密图 ,判断两点是否相邻 $O(1)$,求某点的度要扫一行 $O(n)$;邻接表:空间 $O(n+e)$,适合 稀疏图 ,找邻接点方便。无向图的邻接矩阵是对称矩阵。 易错 有向图的邻接表求入度不方…
- 深度优先和广度优先遍历的复杂度与所用的数据结构是什么?:DFS 用栈(或递归),BFS 用 队列 。时间复杂度:邻接表存储时是 $O(n+e)$,邻接矩阵存储时是 $O(n^2)$;辅助空间都是 $O(n)$。 易错 无向图不连通时,要对每个未访问的顶点各调用一次,调用次数等于连通分量数;有向…
- Prim 和 Kruskal 算法怎样对照着记?:Prim 从一个顶点出发,每次选连接已选顶点集和未选顶点集的权值最小边,用邻接矩阵时间 $O(n^2)$,适合稠密图; Kruskal 把边按权值从小到大排序,依次选不构成回路的边,时间 $O(e\log e)$,适合稀疏图。
- Dijkstra 算法怎么做,复杂度和限制是什么?:求单源最短路径:每次从未确定的顶点中选 距离源点最近 的一个,确定它的最短路径,再用它去松弛其他顶点。时间 $O(n^2)$(用堆可以优化), 边权不能为负 。 易错 有负权边时,Dijkstra 可能得出错误的结果。
- Floyd 算法的递推式和复杂度是什么?:求 任意两点 间的最短路径:$A_k[i][j]=\min\{A_{k-1}[i][j],\ A_{k-1}[i][k]+A_{k-1}[k][j]\}$,$k$ 表示允许经过前 $k$ 个顶点作中转。时间 $O(n^3)$,空间 $O(…
- 三种最短路径方法各适用什么情形?:BFS 适用于无权图(或边权都相同)的单源最短路径,邻接表下 $O(n+e)$; Dijkstra 适用于边权非负的单源最短路径; Floyd 适用于求各顶点之间的最短路径,也允许负权边。 记法 无权用 BFS,非负权用 Dijkstra…
- 拓扑排序怎么做,复杂度是多少?:反复做两步:从有向图中选一个 入度为 0 的顶点输出,再删去它和它发出的所有边,直到图空或没有入度为 0 的顶点。若输出的顶点数小于 $n$,说明图中有环。时间复杂度:邻接表 $O(n+e)$,邻接矩阵 $O(n^2)$。
- 拓扑序列什么时候唯一?:每一步入度为 0 的顶点都 只有一个 时,拓扑序列唯一;等价于有向无环图中存在一条经过全部顶点的路径。 易错 邻接矩阵是主对角线为 0 的三角矩阵,只说明图 无环 ,拓扑序列不一定唯一。
- 关键路径里的 ve、vl、e、l 各怎么求?:在 AOE 网(顶点表示事件,边 $\langle j,k\rangle$ 表示活动,边权 $w(j,k)$ 是活动的持续时间)中,事件最早发生时间 $ve(k)=\max\{ve(j)+w(j,k)\}$,从源点($ve=0$)向后递推…
必背 · 查找
- 顺序查找的平均查找长度是多少?:查找 $n$ 个等概率元素:成功时 $\text{ASL}=(n+1)/2$;失败时,不设哨兵比较 $n$ 次,设哨兵比较 $n+1$ 次,以题目约定为准。顺序查找对顺序表和链表都适用,对关键字有序与否 没有要求 。
- 折半查找的前提和比较次数是多少?:前提是表 有序且顺序存储 。判定树是平衡的,成功查找最多比较 $\lfloor\log_2 n\rfloor+1$ 次,时间复杂度 $O(\log n)$;判定树是满树($n=2^h-1$)时 $\text{ASL}=\dfrac{n+1…
- 分块查找的 ASL 怎么算?:块间 有序 、块内可以无序,先查索引表再查块。$\text{ASL}$ 等于查索引表的 ASL 加查块内的 ASL。索引表和块内都用顺序查找,共 $b$ 块、块长 $s$ 时:$\text{ASL}=\dfrac{b+1}{2}+\dfr…
- 二叉排序树的删除与性质怎么记?:删 叶结点 :直接删;删 只有一个孩子 的结点:用孩子顶替它;删 有两个孩子 的结点:用它的中序后继(右子树最左结点)或中序前驱的值替换它,再删掉那个后继或前驱结点。 易错 二叉排序树的查找效率与形态有关:最好 $O(\log n)$,最…
- AVL 树失衡后怎么旋转?:平衡因子(左右子树高度差)的绝对值超过 1 就失衡,从 最小失衡子树 调整,共四种:LL 右单旋、RR 左单旋、LR 先左后右双旋、RL 先右后左双旋。插入后最多调整 一次 ,删除后可能要沿路径向上调整多次。 图:LL 右单旋,RR 左单…
- AVL 树的最少结点数怎么算?:高度为 $h$ 的 AVL 树 最少结点数 $N_h=N_{h-1}+N_{h-2}+1$,$N_0=0$,$N_1=1$,之后依次是 2、4、7、12、20……反过来,$n$ 个结点的 AVL 树高度是 $O(\log n)$。 例 2…
- 红黑树有哪五条性质?:①结点是红色或黑色;② 根结点是黑色 ;③叶子(外部空结点)是黑色;④ 红结点的孩子都是黑色 ,即不能有两个连续的红结点;⑤从任一结点到它每个后代叶子的路径上, 黑结点的个数相同 。由此,从根到叶子的最长路径不超过最短路径的 2 倍。
- m 阶 B 树的结点和关键字个数有什么限制?:每个结点最多 $m$ 棵子树、$m-1$ 个关键字;除根外,每个带关键字的结点至少 $\lceil m/2\rceil$ 棵子树、$\lceil m/2\rceil-1$ 个关键字(含最底层的结点);根结点至少 2 棵子树(至少 1 个关…
- B 树给定高度,关键字个数范围是多少?:高度为 $h$(不含失败叶子)的 $m$ 阶 B 树:关键字 最多 $m^h-1$ 个(每个结点都装满); 最少 $2\lceil m/2\rceil^{h-1}-1$ 个(根只有 2 棵子树,其余结点刚好满足下限)。 例 3 阶 B 树…
- B 树插入和删除时怎样调整结点?:插入后关键字个数达到 $m$ 就 分裂 ;删除后非根结点的关键字个数低于 $\lceil m/2\rceil-1$,先向相邻兄弟借,借不了再 合并 。 步骤 插入:先把关键字放进最底层结点,达到 $m$ 个时把这 $m$ 个关键字中的第 …
- B 树和 B+ 树怎样对照着记?:两者差在关键字个数与叶子的内容。 B+ 树 :$n$ 个关键字对应 $n$ 棵子树(B 树是 $n+1$ 棵);叶子结点包含 全部关键字 ,并按顺序连成链表,支持范围查找;非叶结点只起索引作用,所以查找不论成功与否都要走到叶子。 B 树 …
- 散列表怎样处理冲突?:冲突处理分两大类。 开放定址法 :线性探测(易产生堆积)、平方探测(表长为 $4k+3$ 型质数时能探测整个表)、再散列; 拉链法 :把同义词链成单链表,不产生堆积。 记法 散列函数常用除留余数法 $H(key)=key\bmod p$,…
- 装填因子和散列查找的 ASL 有什么关系?:装填因子 $\alpha$ 等于表中记录数除以表长。$\alpha$ 越大,冲突越多,ASL 越大;所以散列查找的 ASL 主要取决于 $\alpha$(也与冲突处理方法有关), 不直接 取决于记录个数 $n$ 或表长,$\alpha$ …
必背 · 排序
- 各内部排序的平均时间复杂度怎么分档?:$O(n^2)$:直接插入、折半插入、冒泡、简单选择;$O(n\log n)$:快速、堆、二路归并; 希尔排序 介于两者之间,依赖增量序列; 基数排序 为 $O(d(n+r))$,$d$ 是关键字位数,$r$ 是基数。 图:不稳定的四种用…
- 内部排序的空间复杂度怎么记?:直接插入、冒泡、简单选择、希尔、堆排序都是 $O(1)$; 快速排序 是 $O(\log n)$(递归栈,最坏 $O(n)$); 归并排序 是 $O(n)$;基数排序是 $O(r)$。
- 哪些排序算法是不稳定的?:不稳定的有 快速、希尔、简单选择、堆 四种,其余(直接插入、折半插入、冒泡、归并、基数)稳定。 例 简单选择排序 2 2 1 :把最小的 1 和第一个 2 交换,得到 1 2 2 ,两个 2 的先后次序变了。 记法 「快希选堆」。
- 各排序最好、最坏时间复杂度有哪些要记?:直接插入和冒泡(冒泡需带「本趟无交换即停」的标志):最好 $O(n)$(已有序)、最坏 $O(n^2)$; 快速排序 :最好和平均 $O(n\log n)$,最坏 $O(n^2)$(枢轴取首或尾元素、序列已有序或逆序时,划分极不均匀);堆…
- 直接插入排序和折半插入排序的差别在哪?:折半插入用折半查找定位,把 比较次数 降到 $O(n\log n)$,但 移动次数 仍是 $O(n^2)$,所以时间复杂度还是 $O(n^2)$;两者都稳定。直接插入在序列 基本有序 时接近 $O(n)$。
- 希尔排序的要点是什么?:先取增量 $d_1$ 把序列分组,各组分别做直接插入排序,再逐步缩小增量,直到增量为 1。 最后一个增量必须是 1 ;希尔排序 不稳定 ,只适用于顺序存储,时间复杂度依赖增量序列。
- 快速排序一趟划分得到什么结果?:一趟划分把 枢轴 放到最终位置,左边的关键字都不大于它,右边的都不小于它,但左右两边内部不一定有序。递归深度最好为 $\log n$,最坏为 $n$(枢轴取首或尾元素、序列有序或逆序时);通常认为是基于比较的内部排序中 平均性能最好 的。
- 堆排序的建堆和调整要点是什么?:大根堆用于升序, 小根堆 用于降序。建堆从最后一个分支结点 $\lfloor n/2\rfloor$ 开始向前逐个向下调整,时间 $O(n)$;每次取走堆顶再调整需要 $O(\log n)$,总时间 $O(n\log n)$;向下调整时每…
- 堆怎样插入元素、删除堆顶?:插入:把新元素放在堆尾,再 向上调整 ,与双亲比较,不满足堆的性质就交换,每上一层比较 1 次,时间 $O(\log n)$。删除堆顶:用堆尾元素顶替堆顶,再 向下调整 ,每下一层比较 2 次,时间 $O(\log n)$。 记法 向上每…
- 二路归并排序的趟数和空间怎么算?:$n$ 个元素需要 $\lceil\log_2 n\rceil$ 趟归并,每趟 $O(n)$,总时间 $O(n\log n)$,空间 $O(n)$, 稳定 ,最好、最坏、平均时间复杂度都是 $O(n\log n)$;也适合链表和外部排序。
- 外部排序怎样算归并趟数?:先用内部排序把文件分成若干 初始归并段 ,再做 $k$ 路归并。有 $r$ 个初始归并段时,归并趟数为 $\lceil\log_k r\rceil$;增大 $k$、减少 $r$ 都能减少趟数。 败者树 让 $k$ 路归并每次选最小值只需 …
- 外部排序的最佳归并树怎么构造?:把 $r$ 个初始归并段当作叶子、段的长度当作权值,构造 $k$ 叉 哈夫曼树 ,带权路径长度越小,磁盘读写次数越少。当 $(r-1)\%(k-1)\ne0$ 时,要补 $k-1-(r-1)\%(k-1)$ 个长度为 0 的 虚段 ;等于…
常见 · 易混辨析:四组概念
- 满二叉树、完全二叉树、二叉排序树、平衡二叉树和堆怎样区分?:五种结构的区别: 满二叉树 :每层都是满的; 完全二叉树 :只有最后一层可以缺,且缺在右边; 二叉排序树 :左子树的关键字都小于根、右子树的都大于根;平衡二叉树:任一结点左右子树高度差不超过 1,且本身是二叉排序树;堆:是完全二叉树,且父…
- 树的高度、深度和层次怎样区分?:结点的 深度 从根往下累加,结点的 高度 从叶往上累加;树的高度(深度)等于 最大层次 。 易错 有的教材规定根是第 0 层,有的规定根是第 1 层,用到高度、层次的公式前先看题目的约定。
- 最小生成树、最短路径和拓扑排序各解决什么问题?:三者解决的问题不同。 最小生成树 :在连通的无向带权图中,用 $n-1$ 条边连通全部顶点,使边权总和最小; 最短路径 :求某顶点到其他顶点的路径权值和最小的路径,最小生成树上两点间的路径不一定是最短路径; 拓扑排序 :给有向无环图的顶点…
- 查找成功的 ASL 和查找失败的 ASL 怎样区分?:查找 成功 的 ASL 是各元素查找长度的平均值,对判定树按每个结点所在层数求平均;查找 失败 的 ASL 是各个 失败结点 的查找长度的平均值,即走到失败结点时的比较次数。 例 7 个元素的折半查找判定树是 3 层满树,有 8 个失败结…
必背 · 一页纸速记:数据结构压缩版
- 线性表与栈队列压缩成一句?:顺序表查得快、插入删除慢,链表找到位置后插入删除快、按位序查得慢;各位置等概率时顺序表插入平均移动 $n/2$ 个、删除平均移动 $(n-1)/2$ 个;出栈序列数是 卡特兰数 ;牺牲一个单元且 $front$ 指队头元素、$rear$ …
- 数组与串压缩成一句?:行优先地址 $\text{LOC}+(i\times n+j)\times L$;下三角按行存 $k=i(i+1)/2+j$,三对角 $k=2i+j$(这三个公式的下标都从 0 起); KMP 为 $O(n+m)$,next 数组下标从 …
- 二叉树性质压缩成一句?:$n_0=n_2+1$;第 $i$ 层最多 $2^{i-1}$ 个,高 $h$ 最多 $2^h-1$ 个;完全二叉树结点 $i$ 的左孩子是 ${2i}$、右孩子是 $2i+1$,高度 $\lceil\log_2(n+1)\rceil$;…
- 遍历与线索压缩成一句?:前序根左右、中序左根右、后序左右根; 前加中、后加中、层加中 能还原二叉树,前加后不能;三种遍历的叶子次序相同;中序线索树的前驱和后继都方便。
- 树、森林与并查集压缩成一句?:树有双亲、孩子、孩子兄弟三种存储结构;树转二叉树是 左孩子右兄弟 ,森林转二叉树是把各棵树的二叉树依次作前一棵树根的右子树;树的先根遍历对应其二叉树的前序,后根遍历对应中序;树的结点数等于总度数加 1;并查集用 路径压缩 和按秩合并优化。
- 哈夫曼树压缩成一句?:每次合并权值最小的两棵树;$n$ 个叶子共 $2n-1$ 个结点, 没有度为 1 的结点 ;$\text{WPL}=\sum w_il_i$,也等于所有非叶结点权值之和;哈夫曼编码是前缀编码。
- 图的性质与存储压缩成一句?:无向图度之和是边数的 2 倍;完全图有 $n(n-1)/2$ 条边(有向图 $n(n-1)$);连通至少 $n-1$ 条边,强连通至少 $n$ 条;矩阵 $O(n^2)$ 适合 稠密图 ,邻接表 $O(n+e)$ 适合稀疏图;DFS 与 …
- 图的算法压缩成一句?:Prim $O(n^2)$、Kruskal $O(e\log e)$; Dijkstra $O(n^2)$ 且边权不能为负;Floyd $O(n^3)$;拓扑排序 $O(n+e)$,输出不足 $n$ 个顶点说明有环;关键活动满足 $l=e…
- 查找压缩成一句?:顺序查找成功 $\text{ASL}=(n+1)/2$;折半查找最多比较 $\lfloor\log_2n\rfloor+1$ 次;分块查找块间有序;二叉排序树 中序递增 ;AVL 最少结点 $N_h=N_{h-1}+N_{h-2}+1$;…
- B 树与散列压缩成一句?:$m$ 阶 B 树结点最多 $m$ 棵子树、非根最少 $\lceil m/2\rceil$ 棵、叶子同层; B+ 树 叶子存全部关键字并连成链;散列用除留余数法,开放定址法删除一般要打标记;ASL 主要取决于装填因子 $\alpha$,也…
- 排序的复杂度压缩成一句?:$O(n^2)$:插入、冒泡、选择;$O(n\log n)$:快速、堆、归并;空间多为 $O(1)$,快速 $O(\log n)$,归并 $O(n)$; 不稳定 的是快速、希尔、选择、堆;基于比较的排序,最坏情况下比较次数的下界是 $\O…
- 排序的要点压缩成一句?:折半插入只减少比较;希尔最后一个增量是 1;快速排序一趟确定 枢轴 的位置;建堆 $O(n)$、从 $\lfloor n/2\rfloor$ 向下调整;二路归并 $\lceil\log_2n\rceil$ 趟;外部排序 $\lceil\l…
本图由 SeekFlaw 编辑团队整理。发现错误,欢迎到学习论坛指出。