数据结构期末 · 图、查找与排序
这张图讲什么
「数据结构期末 · 图、查找与排序」是 SeekFlaw 编辑团队整理的思维导图,分 6 个一级分支:图的存储与遍历;最小生成树;最短路径;拓扑排序与关键路径;查找:折半、散列与 B 树;内部排序,共 79 个节点、78 张记忆卡。
这张图分六块:图的存储与遍历、最小生成树、最短路径、拓扑排序与关键路径、查找(折半、散列、B 树)、内部排序。建议按这个顺序复习:先熟悉邻接矩阵与邻接表和两种遍历,再把 Prim、Kruskal、Dijkstra、Floyd 各手算一遍,随后练散列表的 ASL 和 B 树插入,最后用最后一枝的趟结果与稳定性、复杂度对照表收尾。
5 个要点
- 图的存储与遍历:先分清图的基本概念和两种存储结构的空间、适用场合,再掌握 DFS 与 BFS 的过程和复杂度。
- 最小生成树:生成树是含全部顶点的极小连通子图, 有 n-1 条边。
- 最短路径:单源最短路用 Dijkstra(边权非负),任意两点间用 Floyd。
- 拓扑排序与关键路径:AOV 网(顶点表示活动)用来排先后顺序,AOE 网(边表示活动)用来求最短工期。
- 查找:折半、散列与 B 树——折半查找要会算比较次数和 ASL,散列表要会按冲突规则填表并算 ASL,B 树要会判断结构约束并做插入分裂。
适用:大学期末复习。用法:点开任一节点先自己答,再翻面核对。
更新于
一句话:这张图把「数据结构期末 · 图、查找与排序」整理成 79 个节点、78 张记忆卡;点开节点翻面就能看答案。
覆盖图的存储与遍历、最小生成树、最短路径、拓扑排序与关键路径、折半查找、散列表、B 树和各种排序算法,带自编算例,适合本科期末复习。点开任一节点翻面看答案,登录后可存进自己的空间,按遗忘曲线复习。
SeekFlaw 求瑕是面向初中、高中、考研、考公考前速记的思维导图与记忆卡平台:把课件、讲义变成思维导图,节点翻面就是记忆卡,按遗忘曲线安排复习。
79 个节点 · 78 张记忆卡。作者:SeekFlaw 编辑团队;发布于 2026-11-17。
先看这 3 条
- 路径、回路、连通分量等术语怎么区分:路径是顶点序列,相邻顶点间有边; 顶点不重复 的叫简单路径;起点终点相同的路径是回路(环)。
- Dijkstra 算法怎么做:维护已确定最短路的顶点集 S 和每个顶点的当前最短距离 dist:每轮从 S 外取 dist 最小的顶点 u 加入 S,再用 u 松弛它的出边(若 dist[u]+w 更小则更新…
- 直接插入排序的过程、复杂度和稳定性:把第 i 个元素插入前面已排好的有序部分,从后往前比较并移动。
图的存储与遍历
- 路径、回路、连通分量等术语怎么区分:路径是顶点序列,相邻顶点间有边; 顶点不重复 的叫简单路径;起点终点相同的路径是回路(环)。无向图的极大连通子图叫连通分量,有向图的 极大强连通子图 叫强连通分量。 例 7 个顶点的无向图分成 {1,2,3}、{4,5}、{6}、{7} …
- 图的度与边数有什么关系,完全图有多少条边:无向图所有顶点的 度之和等于边数的 2 倍 ;有向图 入度之和等于出度之和 ,都等于弧数。n 个顶点的无向完全图有 $\frac{n(n-1)}{2}$ 条边,有向完全图有 $n(n-1)$ 条弧。 例 6 个顶点的无向完全图有 15 条…
- 连通图至少几条边,不连通图至多几条边:n 个顶点的无向连通图 至少 n-1 条边 ;n 个顶点的无向图若不连通,最多有 $\frac{(n-1)(n-2)}{2}$ 条边(n-1 个顶点构成完全图,另有一个孤立点)。n 大于等于 2 的强连通有向图 至少 n 条弧 (一个有向…
- 邻接矩阵有哪些特点:用 n 阶方阵存边,空间 O($n^2$), 与边数无关 。无权图的 0/1 矩阵中, 无向图矩阵对称 ,第 i 行非零元个数就是顶点 i 的度(不含自环);有向图第 i 行是出度,第 i 列是入度。判断两点有无边 O(1),找某点所有邻…
- 邻接表有哪些特点:每个顶点一条边结点链表。无向图每条边存两次,共 2e 个边结点 ;有向图 e 个。空间 O(n+e)。求出度方便, 求入度要扫描整个表 (或另建逆邻接表)。 区分 邻接表不唯一 ,边结点的链接顺序不同,遍历序列也随之不同;适合稀疏图。
- 十字链表与邻接多重表各用于什么图:十字链表用于有向图: 每条弧一个结点 ,同时挂在弧尾的出弧链和弧头的入弧链上,既容易求出度也容易求入度。邻接多重表用于无向图: 每条边只有一个结点 ,同时属于它两个端点的链,便于对边做删除或标记。 区分 邻接表中无向图的一条边出现两次,邻…
- 邻接矩阵与邻接表怎样选择:稠密图、 经常判断两点之间有无边 ,用邻接矩阵; 稀疏图、经常遍历邻接点 ,用邻接表。 例 n=1000、e=2000 的无向图:邻接矩阵要 100 万个单元,邻接表只需 1000 个头结点加 4000 个边结点。 考法 遍历复杂度:邻接…
- 深度优先搜索的过程和特点:从起点出发,访问后依次递归访问它的 未访问邻接点 ,走到头再回退(回溯)。 用递归或栈实现 ,时间:邻接矩阵 O($n^2$),邻接表 O(n+e)。 易错 遍历序列依赖邻接点的顺序 ,题目没规定时按顶点编号或邻接表顺序。
- 广度优先搜索的过程和特点:从起点出发,先访问起点所有邻接点,再逐层向外; 用队列实现 ,时间复杂度与 DFS 相同。BFS 可求无权图中从起点到各点的最短路径( 按边数 )。 区分 DFS 用栈、BFS 用队列; 二者的生成树不同 。
- 例:写出 DFS 和 BFS 序列:无向图顶点 A 到 F,边为 AB、AC、BD、CD、DE、EF, 邻接点按字母序 ,从 A 出发:DFS 序列为 A B D C E F,BFS 序列为 A B C D E F。 步骤 DFS:A 先到 B,B 的邻接点 A 已访问,到…
- 图不连通时遍历怎么做,调用几次:从一个起点遍历 只能访问到它所在的连通分量 ;对非连通图,要依次检查每个未访问顶点并再调用一次遍历。调用主遍历函数的次数等于无向图的 连通分量数 。 例 无向图 10 个顶点分成 3 个连通分量,则遍历需要调用 3 次。
最小生成树
- 最小生成树的定义和性质:带权连通无向图的生成树中, 边权之和最小 的一棵。含 n 个顶点, 恰有 n-1 条边 ,无回路;再加一条边必成回路,去掉一条边则不连通。 易错 最小生成树 不一定唯一 ;若各边权值互不相同,则唯一。
- Prim 算法的过程:从任一顶点出发,每次选一条一端在已选顶点集内、另一端在集外的 权值最小的边 ,把集外顶点并入,重复 n-1 次。朴素实现时间 O($n^2$), 与边数无关 。 条件 要求连通图,求的是无向图的最小生成树。 记法 边「生长」,每次 只往现…
- Kruskal 算法的过程:把边按权值从小到大排序,依次考察每条边:若它的 两个端点在不同连通分量 就选取,否则会成回路而舍去,直到选够 n-1 条边。时间 O(e log e), 用并查集判环 。 记法 边「聚合」,先看全局最小的边,把森林并成树。
- Prim 与 Kruskal 各适合什么图:Prim 的复杂度主要由顶点数决定, 适合边多的稠密图 ;Kruskal 的复杂度主要由边数决定, 适合边少的稀疏图 。 例 顶点 1000、边 5000 时,Kruskal 的排序代价较小;顶点 1000、边近 50 万时,Prim 更…
- 例:求一个小图的最小生成树:带权无向图顶点 A 到 E,边:AB=2,AC=4,BC=1,BD=7,CD=3,CE=5,DE=6。最小生成树 权和为 11 ,边为 BC、AB、CD、CE。 步骤 Kruskal:按权排序 BC1、AB2、CD3、AC4、CE5、DE…
- 最小生成树什么时候唯一:若 各条边权值互不相同 ,最小生成树一定唯一;有等权边时 不一定唯一 ,可能有多棵,但它们的 权和相等 。 例 带权无向图边:AB=2,AC=4,BC=1,BD=7,CD=3,CE=5,DE=5(CE 与 DE 同权)。Kruskal 依…
最短路径
- Dijkstra 算法怎么做:维护已确定最短路的顶点集 S 和每个顶点的当前最短距离 dist:每轮从 S 外取 dist 最小的顶点 u 加入 S,再用 u 松弛它的出边(若 dist[u]+w 更小则更新)。重复 n-1 轮。 条件 所有边权非负 。 记法 先取离…
- 例:用 Dijkstra 求单源最短路:有向图边:A→B=10,A→C=3,C→B=4,B→D=2,C→D=8,D→E=7,从 A 出发,最短距离为 A=0,C=3,B=7,D=9,E=16,到 E 的最短路径是 A→C→B→D→E。 步骤 1. 取 A:B=10,C=3 2.…
- Dijkstra 的复杂度和局限是什么:朴素实现(邻接矩阵)时间 O($n^2$);求任意两点间最短路可对每个顶点各做一次,共 O($n^3$)。 边权可以为负时 Dijkstra 可能得出错误结果 。 例 边 A→B=2,A→C=3,C→B=-2:Dijkstra 先确定 B…
- Floyd 算法的递推公式是什么:设 $A_k[i][j]$ 为只允许经过编号不超过 k 的中间顶点时,i 到 j 的最短路长度,则 $A_k[i][j]=\min(A_{k-1}[i][j],\,A_{k-1}[i][k]+A_{k-1}[k][j])$。时间 O($n…
- 例:Floyd 算法手算:3 个顶点,边 1→2=4,1→3=11,2→3=2,3→1=3。依次考虑中间点 1、2、3,最终得到距离矩阵:第 1 行 0 4 6;第 2 行 5 0 2;第 3 行 3 7 0。 步骤 1. k=1:3→1→2 得 d(3,2)=3…
- 求最短路径,BFS 与 Dijkstra 有什么区别:BFS 只适用于无权图 (或所有边权相同),按边数最少求最短路;有权图要用 Dijkstra(非负权)或 Floyd 等。 例 边权全为 1 时,Dijkstra 的结果与 BFS 的层数一致。 易错 带权图中「边数最少」的路径 不一定「…
拓扑排序与关键路径
- 拓扑排序怎么做:在 AOV 网(有向无环图)中:每次选一个入度为 0 的顶点输出,并删去它和它发出的所有边,重复到不再有入度为 0 的顶点。若 输出的顶点数少于 n ,说明图中有回路。 条件 只有有向无环图才有拓扑序列 。 考法 邻接表实现时间 O(n+…
- 例:写出一个拓扑序列:AOV 网有边 A→B、A→C、B→D、C→D、D→E,入度分别为 A=0、B=1、C=1、D=2、E=1。拓扑序列有 ABCDE 和 ACBDE 两个。 步骤 1. 输出 A,B、C 入度变为 0 2. 输出 B 或 C 之一,输出另一…
- 拓扑序列什么时候唯一:每一步入度为 0 的顶点 恰好只有一个 时,序列唯一。此时序列中 相邻两个顶点之间一定有边 (否则它们可以互换)。 例 边为 A→B、B→C 的网只有 ABC 一个序列;边为 A→B、A→C 的网,B、C 之间无边,有 ABC 与 ACB…
- AOE 网与关键路径各指什么:AOE 网是带权有向无环图,边表示活动、边权表示活动持续时间,顶点表示事件。从源点到汇点的路径中 长度最大的称关键路径 ,其长度是 完成整个工程的最短时间 ;关键路径上的活动是关键活动。 区分 AOV 网用顶点表示活动、没有权;AOE 网…
- ve、vl、e、l 怎么求:事件最早发生时间 ve:源点为 0, ve(j)=max{ve(i)+w(i,j)} (正向);事件最迟发生时间 vl:汇点等于其 ve, vl(i)=min{vl(j)-w(i,j)} (反向)。活动 a=(i,j) 的最早开始 e=v…
- 例:求关键路径:事件 v1 到 v5,活动:a1=v1→v2(3),a2=v1→v3(2),a3=v2→v4(2),a4=v3→v4(4),a5=v4→v5(3),a6=v2→v5(6)。ve 为 0、3、2、6、9,工期 9,关键活动是 a1、a2、a…
- 缩短关键活动的时间,工期一定变短吗:不一定。有多条关键路径时, 只缩短其中一条上的活动 ,另一条路径长度不变, 工期不变 ;缩短过多还会使别的路径变成新的关键路径, 工期的缩短有下限 。 例 活动 a1=v1→v2(3),a2=v1→v3(2),a3=v2→v4(2),a4…
查找:折半、散列与 B 树
- 折半查找的前提和过程:前提: 线性表有序 ,且为 顺序存储 (可随机访问)。每次取 mid=(low+high)/2 (向下取整),把关键字 k 与 a[mid] 比较:相等则成功;k 小于 a[mid] 则 high=mid-1 ;k 大于 a[mid] 则…
- 折半查找判定树怎么求 ASL:判定树是平衡的, 第 i 层结点比较 i 次 。成功的 ASL 等于各结点层数之和除以 n;比较次数最多为 $\lfloor\log_2 n\rfloor+1$。 例 n=11 时判定树前三层各有 1、2、4 个结点,第四层有 4 个: …
- 分块查找怎么进行,ASL 怎么算:分块查找把表分成若干块, 块内无序、块间有序 ,另建索引表(记录每块的最大关键字和起始地址)。 先在索引表中查块 ,再在块内顺序查找;ASL 等于索引查找的 ASL 加块内查找的 ASL。 例 100 个记录分成 10 块,每块 10 个…
- 顺序查找、折半查找的 ASL 与适用条件如何比较:顺序查找对表无要求(顺序、链式都可),等概率时成功的 ASL 为 (n+1)/2;折半查找 要求有序顺序存储 ,查找 O(log n),但插入删除需移动元素, 不适合经常变动的表 。 区分 链表只能顺序查找; 折半查找不能用于链式存储 。
- 常用散列函数有哪些,除留余数法怎么取模数:常见有直接定址法、除留余数法、数字分析法、平方取中法。除留余数法 H(k)=k mod p ,p 取 不大于表长 m 的质数 (常取最接近 m 的质数)。 例 表长 11, H(k)=k mod 11 ,关键字 23 的地址是 1。 易错…
- 开放定址法怎么处理冲突:冲突时按探测序列找下一个空位:$H_i=(H(k)+d_i)\bmod m$。线性探测 $d_i=i$(1,2,3…);二次探测 $d_i=1^2,-1^2,2^2,-2^2,\dots$;还有再散列等。 区分 线性探测易产生「堆积」 ,…
- 例:线性探测法建散列表并求 ASL:表长 11, H(k)=k mod 11 ,依次插入 23、34、15、26、37、9:23 放 1;34 冲突放 2;15 放 4;26 冲突放 5; 37 冲突(4、5 已占)放 6 ;9 放 9。成功的 ASL 为 (1+2+1+2…
- 拉链法怎么处理冲突:同义词放进同一个单链表, 散列表只存各链表头 。 没有堆积现象 , 装填因子可大于 1 ,插入删除方便。 例 表长 11, H(k)=k mod 11 ,依次插入 23、34、15、26、37、9,按插入先后尾插:链 1 为 23→34,…
- 散列表的装填因子是什么:装填因子 $\alpha=\frac{n}{m}$,n 为已存关键字数,m 为表长; α 越大,冲突越多,查找越慢 。 开放定址法的 α 不超过 1 , 拉链法的 α 可以大于 1 。 例 表长 11 存了 6 个关键字,α=6/11;拉…
- 开放定址法删除元素要注意什么:不能直接把该位置清空,而要 做「已删除」标记 ,否则会 截断其后同义词的查找路径 ,导致本来存在的关键字查不到。 例 线性探测表中 23 在位置 1、34 因冲突放在位置 2;若删除 23 后把位置 1 置空,查找 34 时从位置 1 开…
- m 阶 B 树有哪些约束:每个结点 最多 m 棵子树 (m-1 个关键字); 根结点(非叶)至少 2 棵子树 ;其他非叶结点至少 $\lceil m/2\rceil$ 棵子树; 所有叶子在同一层 ;结点内关键字有序,且子树关键字落在相邻关键字之间。 例 4 阶 B…
- 给定层数,B 树最少与最多有多少个关键字:这里的「3 层」 只计含关键字的结点 ,不含叶子下面的失败结点。3 层的 4 阶 B 树: 最少时根 1 个关键字 ,第二层 2 个结点各 1 个,第三层 4 个结点各 1 个,共 7 个;最多时每个结点 3 个关键字,共 3+12+48…
- B 树插入新关键字怎么做:先找到最底层的结点插入;若该结点 关键字个数超过 m-1 ,就把 中间关键字上移到双亲 ,其余分成两个结点;双亲也可能溢出,继续向上分裂, 根分裂则树高加 1 。 例 3 阶 B 树(每结点最多 2 个关键字)依次插入 10、20、30:…
- B 树删除关键字后怎么调整:若删后结点关键字数仍不少于 $\lceil m/2\rceil-1$ 则不需调整;否则先看 相邻兄弟是否有多余关键字 :有则通过双亲「借」;没有则 与兄弟及双亲中的分隔关键字合并 ,合并可能向上传递。 易错 删除非叶结点中的关键字时, 先…
- B 树和 B+ 树的主要区别:B+ 树的 n 个关键字对应 n 棵子树 ; 所有关键字都出现在叶子结点 ,内部结点只做索引;叶子结点用指针连成链,便于范围查询和顺序遍历。B 树内部结点也存关键字及对应记录,且无叶链。 区分 B+ 树查找总是走到叶子; B 树可能在内部…
内部排序
- 直接插入排序的过程、复杂度和稳定性:把第 i 个元素插入前面已排好的有序部分,从后往前比较并移动。 最好(已有序)O(n) ,最坏和平均 O($n^2$),空间 O(1),稳定。 例 序列 6、2、8、4、1 每趟后:2 6 8 4 1;2 6 8 4 1;2 4 6 8 …
- 折半插入排序改进了什么:用折半查找找插入位置,比较次数降为 O(n log n),但 元素移动次数不变 ,总时间仍 O($n^2$),仍稳定。 易错 折半插入的比较次数 与初始序列无关 ,只与元素个数有关。
- 希尔排序的思想和稳定性:取增量 d,把 相隔 d 的元素分为一组 ,组内做直接插入;逐步缩小 d, 最后 d=1 。空间 O(1), 不稳定 ,时间与增量序列有关,优于直接插入。 例 序列 23、8、15、4、42、16、9,取 d=3 排一趟后:4 8 15 …
- 哪些排序每一趟都能确定一个元素的最终位置:冒泡、简单选择、快速排序(每趟枢轴就位)、 堆排序(每趟堆顶就位) 每趟都能确定一个元素的最终位置; 插入类、希尔、归并、基数排序不能 。 考法 常据此判断某个中间序列是哪种排序的 第几趟结果 。
- 冒泡排序的过程、复杂度和稳定性:相邻元素比较,逆序就交换, 每趟使最大元素到达末尾 。最好( 已有序,加标志位 )O(n),最坏和平均 O($n^2$),空间 O(1),稳定。 例 序列 5、3、8、1、2 第一趟:3 5 1 2 8;第二趟:3 1 2 5 8。
- 快速排序怎样划分,复杂度与稳定性如何:取一个枢轴( 本图取第一个元素 ),左右指针交替扫描,使左边元素小于枢轴、右边大于枢轴, 枢轴落到最终位置 ,再递归两边。平均 O(n log n),最坏 O($n^2$)(序列已有序时),栈空间平均 O(log n),不稳定。 易错 已…
- 例:快排一趟划分的结果:序列 5、3、8、1、2、9、4,枢轴 5,一趟划分后为 4 3 2 1 5 9 8, 枢轴 5 到了最终位置 (下标 5)。 步骤 1. 右指针找小于 5 的数:4,移到左端位置 2. 左指针找大于 5 的数:8,移到右指针处 3. 右…
- 简单选择排序的复杂度与稳定性:每趟在无序部分选最小元素放到有序部分末尾, 比较次数固定 n(n-1)/2,时间 O($n^2$),空间 O(1),不稳定。 例 序列 2a、2b、1 第一趟把 1 与 2a 交换,得 1、2b、2a, 两个 2 的相对次序变了 ,所以不…
- 堆排序的过程和复杂度:先把序列建成大根堆( 升序用大根堆 ),然后重复: 堆顶与末尾元素交换 ,缩小堆,再向下调整。 建堆 O(n) ,排序总时间 O(n log n),空间 O(1),不稳定。 条件 大根堆:每个结点的值不小于其孩子;用数组存储时,下标从 1…
- 大根堆怎样插入和删除堆顶:插入:新元素放在末尾,与双亲比较, 比双亲大就交换 ,逐层上移(上滤)。删除堆顶:用最后一个元素放到堆顶,再 与较大的孩子比较交换 ,逐层下移(下滤)。 两者都是 O(log n) 。 例 大根堆 9、7、5、1、3 插入 8:放末尾,与…
- 例:建大根堆与一次输出:序列 3、9、5、1、7(下标 1 起)建大根堆得 9、7、5、1、3。再把 堆顶 9 与末尾交换 得 3、7、5、1、9,调整前 4 个元素得 7、3、5、1、9。 步骤 1. 从 i=⌊n/2⌋=2 向下到 1 逐个调整 2. i=2…
- 堆排序中从根向下调整最多比较几次:大根堆从根向下调整时, 每下沉一层最多比较 2 次 ( 先在两个孩子中选大者 ,再与父结点比较),最多下沉 $\lfloor\log_2 n\rfloor$ 层,所以最多比较 $2\lfloor\log_2 n\rfloor$ 次,单个结…
- 二路归并排序的过程、复杂度与稳定性:先把每个元素看作 长为 1 的有序段 ,两两归并成长为 2、4、…的有序段,共 $\lceil\log_2 n\rceil$ 趟。每趟 O(n),总时间 O(n log n), 空间 O(n),稳定 。 例 序列 5、2、8、1、9、3 …
- 基数排序的过程、复杂度与稳定性:按关键字的各位 从低位到高位 依次「 分配、收集 」,每趟稳定地按一位分配到 r 个队列。时间 O(d(n+r)), 空间 O(r),稳定 ;d 为位数,r 为基数。 例 对 53、17、41、36 按个位分配收集后:41、53、36、1…
- 各排序算法的稳定性怎么记:稳定的:直接插入、折半插入、冒泡、归并、基数。不稳定的: 简单选择、希尔、快速、堆 (口诀「 快希选堆 」)。 例 2a、2b、1:简单选择第一趟把 1 与 2a 交换,2a 排到 2b 之后,不稳定。 区分 稳定性只与算法有关 ,对同一…
- 各排序算法的时间复杂度和空间复杂度对照:直接插入、冒泡、简单选择平均 O($n^2$)(冒泡、直接插入最好 O(n),选择恒为 O($n^2$)); 希尔与增量有关 ;快速平均 O(n log n),最坏 O($n^2$),辅助栈平均 O(log n)、最坏 O(n);堆、归并…
- 外部排序是什么,归并趟数怎么算:数据量大到内存放不下时用外部排序:先把数据分段读入内存排序,生成若干初始归并段,再做多路归并。m 个初始归并段做 k 路平衡归并,趟数为 $\lceil\log_k m\rceil$。 败者树 用来减少 k 路归并中选最小值的比较次数;置…
- 基于比较的排序,时间复杂度下界是多少:任何基于比较的排序, 最坏情况下至少需要 $\Omega(n\log n)$ 次比较:n 个元素有 n! 种排列,判定树至少有 n! 个叶子,高度至少为 $\lceil\log_2 n!\rceil$。 例 n=4 时,4!=24,所以最…
本图由 SeekFlaw 编辑团队整理。发现错误,欢迎到学习论坛指出。