华中科技大学研究生考试软件工程答案数据结构“名词解释”部分数据结构与算法分析

华中科技大学研究生考试软件工程答案数据结构“名词解释”部分数据结构与算法分析内容摘要：

算法 — 在顶点集合中逐渐归并当前权值最小的边。 9. Prim 算法 —— 在当前最小边集合 中逐渐归并相关的顶点。 10. 如果一个有向图恰有一个顶点的入度为 0，其余顶点的入度均为 1，则是一棵 有向树。 一个 有向图的生成森林 由若干棵有向树组成，含有图中全部顶点，但只有足以构成若干棵不相交的有向树的弧。 11. 图的存储结构 有邻接矩阵、邻接表、逆邻接表以及十字链表等。 12. 图的遍历 ：指从图中某一顶点出发访遍图中其余顶点，且使每一个顶点仅被访问一次。 13. 通常有两条遍历图的路径： 1） 深度优先搜索 ：类似于树的先序遍历，假设从图中某顶点 v出发，在访问了 v 之后依次从 v 的未被访问的邻接点出发深度优先遍历图，直到图中所有和 v有路径相通的顶点 都被访问到。 若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点做为起始点，重复上述过程，直至图中所有顶点都被访问到为止。 2） 广度优先搜索 ：类似于村的层序遍历，假设从图中某顶点 v出发，在访问了 v 之后依次访问它们的邻接点，并使先被访问的顶点的邻接点先于后访问的顶点的邻接点，直到图中所有已被访问的顶点的邻接点都被访问到。 若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作为起始点，重复上述过程，直到图中所有顶点都被访问到为止。 14. 假若在删去顶点 v以及和 v相关联的各边之后，将图的一个连通分量分割成两个或 两个以上的边通分量，则称顶点 v为该图的一个 关节点。 一个没有关节点的图称为重 连通图。 若在连通图上至少删去 k 个顶点才能破坏图的连通性，则称此图的 连通度 为 k。 15. 对于无向图来说，若深度优先搜索过程中遇到回边，则必定存在环，而对于有向图来说，这条回边有可能是指向深度优先生成森林中另一棵生成树上顶点的弧。 16. 拓扑排序 (Topological Sort)：指由某个集合上的一个偏序得到该集合上的一个全序。 17. AOV网 ：指用顶点表示活动，用弧表示活动间的优先关系的有向图称为顶点表示活动的网。 AOV网 (Activity On Vertices)—用顶点表示活动的网络。 若用有向图表示一个工程，在图中用顶点表示活动，用弧（即有向边）表示活动间的优先关系。 Vi 必须先于活动 Vj 进行。 则这样的有向图叫做用顶点表示活动的网络，简称 AOV。 18. AOE网 ： 在带权有向无环网中， 用有向边表示一个工程中的活动，用边上权值表示活动持续时间，用顶点表示事件，则这样的有向图叫做用边表示活动的网络，简称 AOE。 常用于大型工程的计划管理。 19. 在正常的情况（无环）下，网中只有一个入度为零的点，称做 源点 和一个出度为零的4 点，称为 汇点。 20. 关键路径 ： AOE 网中有 些活动可以并行进行，所以完工的最短时间是从开始点到完成点的最长路径的长度（即沿途各活动持续时间之和）。 路径长度最长的路径叫做关键路径 ， 关键路径上的所有活动 （ l(i) = e(i)的活动 ） 都是 关键活动。 21. 最早发生时间 ： 假设开始点是 V1，从 V1 到 Vi 的最长路径长度叫做事件 Vi 的最早发生时间 [ e(i) ]。 22. 最迟开始时间 ： 不推迟整个工程完成的前提下，活动 ai最迟必须开始进行的时间 [ l(i) ]。 23. Dijkstra（迪杰斯特拉）算法 ： 先找出从源点 v0到各终点 vk 的直达路径（ v0,vk），即通过一条弧到达的路 径。 从这些路径中找出一条长度最短的路径（ v0,u） ,然后对其余各条路径进行适当调整：若在图中存在弧（ u,vk），且（ v0,u） +（ u,vk） （ v0,vk） ， 则以路。