数据结构的收官篇讲图——树的高级形态树是边没有回路的图。这块在上午题占 2 分左右考点四件套邻接矩阵还是邻接表、DFS 和 BFS 用什么数据结构、Prim 和 Kruskal 的区别、拓扑排序的基本规则。全是记住就得分的题。一、图的两种存储稠密用矩阵稀疏用表邻接矩阵n×n 的二维数组A[i][j] 1表示 i 到 j 有边带权图存权值。优点判断i 和 j 之间有没有边一步到位O(1)缺点无论边多边少空间都是O(n²)——边少时大片浪费性质无向图的邻接矩阵一定对称i-j 有边则 j-i 有边顶点 i 的度 第 i 行元素之和。邻接表每个顶点挂一条链表把它的所有邻接点串起来。空间O(ne)e 是边数边少时极省无向图每条边在两个端点的链表里各出现一次 → 表节点总数 2e有向图则是 e 个只存在出边那一端。记忆口诀稠密矩阵稀疏表——边多稠密图用矩阵不心疼边少稀疏图用邻接表省空间。二、DFS 与 BFS一个用栈一个用队列深度优先 DFS认准一条路走到底撞墙了再回头换路。像走迷宫的一根筋玩家。实现靠栈递归的本质就是系统栈——回头时按后进先出的顺序退回。广度优先 BFS从起点一层层向外扩散先访遍所有邻居再访邻居的邻居。像水波纹。实现靠队列——先到的邻居先被扩展先进先出。高频考点一句话DFS 用栈BFS 用队列——别记反。联想记忆栈深后进先出新元素压在顶上越走越深队列广排队扩散。三、最小生成树两个算法两头生长n 个顶点的连通图最小生成树MST 选出 n−1 条边连通所有顶点且权值之和最小。n 个顶点 n−1 条边本身就是高频填空。两个经典算法思路正好相反Prim普里姆从顶点长。任选一个起点放进已选集合然后不断重复在一头在集合内、一头在集合外的边里挑最短的那条把它和对面的顶点一起拉进集合。像摊大饼从一个点往外摊。Kruskal克鲁斯卡尔从边挑。把所有边按权值从小到大排序从小到大依次考虑不构成环就收入构成环就跳过直到选够 n−1 条。像捡便宜先捡最便宜的只要别围出圈。记忆口诀普里姆拉点克鲁斯卡尔挑边避环。适用场景Prim 以点为主适合稠密图Kruskal 以边为主适合稀疏图——正好和存储的选择呼应。四、拓扑排序AOV 网的施工顺序AOV 网顶点表示活动、有向边表示先后关系的有向无环图DAG。比如选课关系数据结构必须先于编译原理修完。拓扑排序就是给所有活动排一个合法的先后顺序方法朴实无华反复执行选一个入度为 0 的顶点输出然后删除它和它的所有出边。入度为 0 没有先修课了可以马上学。两个考点性质拓扑序列不唯一同时有好几门课入度为 0先学哪门都行若最终输出的顶点数 n说明图里有环——互相先修死锁了工程没法开工。这和软件工程篇讲的关键路径是一家人AOV 网管先后顺序拓扑排序AOE 网管工期计算关键路径。五、10 道练习题基础题1~51.存储稠密图时更适合的存储结构是 。A. 邻接表 B. 邻接矩阵 C. 边集数组 D. 哈希表2.图的深度优先遍历DFS通常借助 实现。A. 队列 B. 数组 C. 栈 D. 堆3.图的广度优先遍历BFS通常借助 实现。A. 队列 B. 栈 C. 树 D. 图4.含 n 个顶点的连通图其最小生成树的边数为 。A. n B. n-1 C. n1 D. 2n5.拓扑排序针对的图是 。A. 无向图 B. 带权图 C. 完全图 D. 有向无环图进阶题6~10带坑6.Prim 算法构造最小生成树的过程是 。A. 从边出发按权值从小到大依次选边 B. 从最长边出发逐步删边 C. 随机选择边 D. 从顶点出发逐步扩张已选顶点集合7.某无向图有 n 个顶点、e 条边采用邻接表存储其表节点总数为 。A. e B. 2e C. n D. ne8.关于拓扑排序下列说法正确的是 。A. 任何有向图都存在拓扑序列 B. 拓扑序列一定是唯一的 C. 有向图存在拓扑序列的前提是无环且拓扑序列可能不唯一 D. 拓扑排序需借助最小生成树实现9.Kruskal 算法在选边时必须判断 。A. 该边是否最长 B. 顶点是否已被访问 C. 加入该边是否构成回路 D. 该边是否在邻接矩阵中10.某无向图用邻接矩阵存储则顶点 i 的度等于 。A. 矩阵第 i 行元素之和 B. 矩阵第 i 列的元素个数 C. 矩阵全部元素之和 D. 矩阵对角线元素之和六、答案与详解1. B口诀稠密矩阵稀疏表稠密图边多O(n²) 的矩阵空间利用率高还能 O(1) 查边。2. CDFS 走到底再回头 →栈后进先出原路退回。递归实现时用的就是系统栈。3. ABFS 层层扩散 →队列先进先出先到的邻居先扩展。和第 2 题是固定搭配考题D 栈 B 队别记反。4. B生成树连通 n 个顶点且不含环边数恰好n-1——多一条成环少一条不连通。5. D拓扑排序的前提是有向无环图DAG / AOV 网——有环就互相等待谁也排不进序列。6. DPrim从顶点出发已选点集不断把最近的邻居拉进来摊大饼。选 A 的是 Kruskal 的思路——两算法方向正好相反普里姆拉点克鲁斯卡尔挑边。7. B坑无向图的每条边在两个端点的链表中各登记一次i 的表里有 jj 的表里有 i→ 表节点总数2e。选 A 的是按有向图算了有向图才是 e只存在出边端。8. CA 错有环的有向图没有拓扑序列B 错多个入度为 0 的点可任意选择序列不唯一C 对——无环才有拓扑序列且可能不唯一D 是无中生有。9. CKruskal 从小到大连边唯一的检查动作是这条边加进来会不会围成环——成环就跳过同一棵树上再加边必成环所以用并查集判断两端是否已连通。10. A无向图邻接矩阵中第 i 行记录了顶点 i 与所有顶点的邻接关系行元素之和 顶点 i 的度矩阵对称第 i 列之和也一样。有向图则要区分行和 出度列和 入度。七、五句话带走存储稠密矩阵稀疏表无向图矩阵对称行和 度邻接表无向图2e个节点遍历DFS 用栈一根筋走到底BFS 用队列水波纹层层扩最小生成树n 顶点 n−1 边Prim 拉点、Kruskal 挑边避环拓扑排序DAG 专属反复选入度为 0 的点序列不唯一输出不足 n 个则有环AOV 管先后拓扑AOE 管工期关键路径见软件工程篇。收官寄语写到这篇软件设计师上午题的知识版图全部点亮整个系列共 18 篇计算机组成原理 6 篇进制转换、原反补移码、浮点数规格化、校验码、流水线、存储系统操作系统 4 篇PV 操作、死锁、存储管理、文件管理数据库 2 篇基础与范式、SQL 与事务软件工程 2 篇开发模型与测试、耦合内聚与关键路径面向对象 / 网络 / 安全 / 知识产权 / 编译原理 / 数据结构各 1~2 篇。下一篇最终篇预告软件设计师上午题全景地图与答题策略——各模块分值分布、哪些题该秒、哪些题该战略放弃、英语题怎么捞分、考场时间分配。知识讲完了最后一篇讲怎么把知识变成分数。