一、单选

1.握手定理

无向图G有23条边，度为4的顶点有5个，度为3的顶点有4个，其余都是度2的顶点，则图G最多有( )个顶点。

• 关键依据：握手定理

  ==无向图中所有顶点的度数之和等于边数的 2 倍。==

  已知边数为 23，因此总度数之和为 23×2=46。

  计算过程

  1. 先算已知度数的顶点贡献的总度数：度为 4 的 5 个顶点总度数为 4×5=20，度为 3 的 4 个顶点总度数为 3×4=12，两者相加共 32。
  2. 剩余总度数为 46-32=14，由度为 2 的顶点承担。
  3. 度为 2 的顶点数量为 14÷2=7。
  4. 总顶点数为 5（度 4）+4（度 3）+7（度 2）=16。

4.邻接表 边表结点

若邻接表中有奇数个边表结点，则一定是( )。

A.图中有奇数个结点

B.图中有偶数个结点

C.图为无向图

D.图为有向图

• 边表结点的定义

  在图的邻接表存储结构中，每个顶点会对应一个链表（称为边表），链表中的每个结点就是边表结点。所以是D

5.迪杰斯特拉

对如下有向带权图，若采用迪杰斯特拉算法求从源点a到其他各顶点的最短路径，则得到的第一条最短路径的目标顶点是b，第二条最短路径的目标顶点是c，后续得到的其余各最短路径的目标顶点依次是( )。

答案：fde

选出一个最短的（此时就是最短路径），从该顶点出发(小的就替换)

再选一个短的

6.BFS最短路径

当各边上的权值（ ）时，BFS算法可用来解决单源最短路径问题。

A.相等

B.互不相等

C.部分相等部分不相等

D.相等不相等都可以

• A

  解析：

  BFS（广度优先搜索）的核心是 “按层遍历”，即先访问距离源点 1 步的顶点，再访问 2 步的顶点……

  当图中各边的权值相等时，“步数” 就等价于 “路径长度”，此时 BFS 遍历的顺序恰好对应从源点到各顶点的最短路径顺序。

  若边权值不相等，BFS 无法保证找到的是最短路径（例如某顶点通过长权值的边先被访问，但存在更短权值的路径）。

7.关键路径

关键路径是（　　）。

A.AOE网中从源点到汇点的最长路径

B.AOE网中从源点到汇点的最短路径

C.AOV网中从源点到汇点的最长路径

D.AOV网中从源点到汇点的最短路径

• A

  解析：

  • AOE 网（Activity On Edge，边表示活动的网）是带权的有向无环图，边的权值表示活动的持续时间，顶点表示事件。
  • 关键路径是 AOE 网中从源点（起始事件）到汇点（结束事件）的最长路径，它决定了整个工程的最短完成时间（因为最长路径上的活动总持续时间最长，工程必须等这条路径上的所有活动完成才能结束）。
  • AOV 网（Activity On Vertex，顶点表示活动的网）仅表示活动的先后顺序，无时间权值，因此不存在 “关键路径” 的概念。

9.最小生成树

给定有权无向图的邻接矩阵如下，其最小生成树的总权重是：

最小生成树有两个算法：

1. 普里姆（Prim）算法

• 思路：从一个顶点开始，逐步将 “与当前生成树距离最近的顶点” 加入生成树（类似 “贪心扩展顶点”）。
• 适用场景：顶点数较少、边数较多的稠密图。

2. 克鲁斯卡尔（Kruskal）算法

• 思路：先将所有边按权值排序，再依次选权值最小的边，若加入后不形成环则保留（类似 “贪心选边”）。
• 适用场景：边数较少、顶点数较多的稀疏图。

我选择第二种：克鲁斯卡尔：

若用普里姆：

• 步骤 1：初始化

  选择起始顶点（比如顶点 1），生成树顶点集合 (S = {1})，未加入顶点集合 (U = {2,3,4,5,6})，记录各顶点到生成树的最小距离（即顶点与 S 中顶点的边权最小值）：

  • 顶点 2：(1→2) 的权 3
  • 顶点 3：(1→3) 的权 1
  • 顶点 4：(1→4) 的权 15
  • 顶点 5：(1→5) 的权 1
  • 顶点 6：(1→6) 的权 9

  步骤 2：选择距离最小的顶点加入 S

  未加入顶点中，距离最小的是顶点 3（权 1）和顶点 5（权 1），任选一个（比如顶点 3）：

  • 加入 (S = {1,3})，总权重 += 1
  • 更新(U = {2,4,5,6})中顶点到S的最小距离（对比 “原距离” 和 “顶点到 3 的边权”）：
    • 顶点 2：原 3，(3→2) 权 3 → 保持 3
    • 顶点 4：原 15，(3→4) 权 1 → 更新为 1
    • 顶点 5：原 1，(3→5) 权 1 → 保持 1
    • 顶点 6：原 9，(3→6) 权 2 → 更新为 2

  步骤 3：再次选择距离最小的顶点

  未加入顶点中，距离最小的是顶点 4（权 1）和顶点 5（权 1），选顶点 5：

  • 加入 (S = {1,3,5})，总权重 += 1（累计 2）
  • 更新(U = {2,4,6})的最小距离：
    • 顶点 2：原 3，(5→2) 无直接边（权∞）→ 保持 3
    • 顶点 4：原 1，(5→4) 权 18 → 保持 1
    • 顶点 6：原 2，(5→6) 权 2 → 保持 2

  步骤 4：选择下一个距离最小的顶点

  未加入顶点中，距离最小的是顶点 4（权 1）：

  • 加入 (S = {1,3,5,4})，总权重 += 1（累计 3）
  • 更新(U = {2,6})的最小距离：
    • 顶点 2：原 3，(4→2) 权 13 → 保持 3
    • 顶点 6：原 2，(4→6) 无直接边 → 保持 2

  步骤 5：选择下一个距离最小的顶点

  未加入顶点中，距离最小的是顶点 6（权 2）：

  • 加入 (S = {1,3,5,4,6})，总权重 += 2（累计 5）
  • 更新(U = {2})的最小距离：
    • 顶点 2：原 3，(6→2) 权 8 → 保持 3

  步骤 6：加入最后一个顶点

  未加入顶点只有 2（距离 3）：

  • 加入 (S = {1,3,5,4,6,2})，总权重 += 3（累计 8）

  最终，最小生成树的总权重为 (1+1+1+2+3 = 8)，与之前的结果一致。

11.拓扑序列

下图为一个AOV网，其可能的拓扑有序序列为：

A.ABCDFEG

B.ADFCEBG

C.ACDFBEG

D.ABDCEFG

选D

AOV 网（顶点表示活动的网）是有向无环图，用于表示活动的先后顺序；拓扑序列是将所有顶点排成一个序列，使得任意一条有向边的起点在序列中都早于终点

从做题角度

==把入度为0的写上，把从该点出发的箭头擦掉，选择一个入度为0的==

从算法角度

1. 计算各顶点的入度：
   • 入度：指向该顶点的边的数量。
   • 本题中各顶点入度：
     • A：0（无入边）；B：1（仅 A→B）；C：2（A→C、D→C）；D：1（A→D）；E：2（B→E、A→E）；F：1（D→F）；G：2（E→G、F→G）。
2. 初始化队列：将入度为 0 的顶点（本题只有 A）加入队列。
3. 循环处理队列：
   • 取出队首顶点，加入拓扑序列；
   • 删除该顶点的所有出边，同时将出边指向的顶点的入度减 1；
   • 若某顶点入度减为 0，加入队列。

12.拓扑排序算法时间复杂度

若将n个顶点e条弧的有向图采用邻接表存储，则拓扑排序算法的时间复杂度是：

A.O(n)

B.O*(n+*e)

C.O*(*n^2)

D.O(n×e)

拓扑排序的 “入度法” 时间复杂度由两部分组成：

1. 初始化入度与队列：需遍历所有顶点（时间 O (n)），并遍历所有边以统计入度（时间 O (e)）；
2. 处理队列：每个顶点会被取出一次（O (n)），每条边会被删除一次（O (e)）。

因此，总时间复杂度是 O (n + e)（顶点数 n 与边数 e 的线性和）。

二、填空题

1.最早最迟发生时间

对下图所示的AOE网，求各顶点代表的事件的最早和最迟发生时间，以及指定弧代表的活动的最早和最迟开始时间。

• 【注意】

  • 如果一个空需要填写多个整数时，按顺序将整数之间用减号( - )连接，首尾及中间均没有空格。例如某个空需要从左到右依次填写1，2，3，4，5，6共6个整数，则填写1-2-3-4-5-6即可。
  • 弧的填写方法：弧尾在前，弧头在后，中间用减号-隔开。
  • 如果一个空需要填写多条弧时，按弧尾从小到大有序，弧尾相同的弧头从小到大有序，弧之间用/分开。例如某个空需要填写6条弧，分别是<A，C>，<C，D>，<C，E>，<D，F>，<E，F>，<F，H>，则填写A-C/C-D/C-E/D-F/E-F/F-H。

  （1）将该AOE网的拓扑序列视为字符串，那么表示拓扑序列的最大字符串是（ ）。
  （2）顶点B，C，D，E所代表的事件的最早发生时间依次是（ ），顶点G，H，I，J所代表的事件的最早发生时间依次是（ ）。
  （3）顶点B，C，D，E所代表的事件的最迟发生时间依次是（ ），顶点G，H，I，J所代表的事件的最迟发生时间依次是（ ）。
  （4）有向弧<B，C>，<D，G>，<E，F>所代表的活动的最早开始时间依次是（ ），有向弧<G，F>，<H，J>，<I，J>所代表的活动的最早开始时间依次是（ ）；
  （5）有向弧<B，C>，<D，G>，<E，F>所代表的活动的最迟开始时间依次是（ ），有向弧<G，F>，<H，J>，<I，J>所代表的活动的最迟开始时间依次是（ ）；
  （6）按顺序写出所有的关键活动：（ ）。

  一、（1）最大拓扑序列字符串的思路

  拓扑序列的核心要求：所有前驱事件必须出现在后继事件之前；“最大字符串” 是指每次选择 “当前入度为 0 的顶点中字典序最大的顶点”。

  步骤：

  1. 先确定各顶点的初始入度：

     • A：0；B：1（仅 A→B）；C：3（B→C、A→C、D→C）；D：1（A→D）；E：1（B→E）；F：3（C→F、E→F、G→F）；G：1（D→G）；H：1（E→H）；I：1（G→I）；J：3（H→J、F→J、I→J）。

  2. 依次选入度为 0 的最大顶点：

     • 选 A（唯一入度 0 的顶点），更新 B（入度 1→0）、C（入度 3→2）、D（入度 1→0）；
     • 选 D（B、D 入度为 0，D 字典序更大），更新 C（入度 2→1）、G（入度 1→0）；
     • 选 G（B、G 入度为 0，G 字典序更大），更新 F（入度 3→2）、I（入度 1→0）；
     • 选 I（B、I 入度为 0，I 字典序更大），更新 J（入度 3→2）；
     • 选 B（唯一入度 0 的顶点），更新 E（入度 1→0）、C（入度 1→0）；
     • 选 E（C、E 入度为 0，E 字典序更大），更新 H（入度 1→0）、F（入度 2→1）；
     • 选 H（C、H 入度为 0，H 字典序更大），更新 J（入度 2→1）；
     • 选 C（唯一入度 0 的顶点），更新 F（入度 1→0）；
     • 选 F（唯一入度 0 的顶点），更新 J（入度 1→0）；
     • 选 J。

     最终，正确的最大拓扑序列是：ADGIBEHCFJ

  二、（2）事件最早发生时间（ve）的思路

  事件的最早发生时间（ve）是 “等所有前驱活动完成后，事件才能发生的最早时间”，需**从源点 A（ve (A)=0）==正向推导== **：

  

  每个事件的 ve(当前事件) = max(所有前驱事件的ve + 对应活动的持续时间)。

  以题目中顶点为例：

  • ve (B) = ve (A) + A→B 的时长 = 0+10=10；
  • ve (C) = max (ve (B)+B→C 的时长，ve (A)+A→C 的时长，ve (D)+D→C 的时长) = max (10+5, 0+13，10+6)=16；
  • ve (D) = ve (A)+A→D 的时长 = 0+10=10；
  • ve (E) = ve (B)+B→E 的时长 = 10+12=22；
  • 后续顶点（G、H、I、J）同理，取前驱 ve + 活动时长的最大值，最终得到对应结果。

  三、（3）事件最迟发生时间（vl）的思路

  

  事件的最迟发生时间（vl）是 “不延误整个工程的前提下，事件能发生的最迟时间”，需**从汇点 J（vl (J)=ve (J)，汇点的最早 / 最迟时间一致）==反向推导== **：

  每个事件的 vl(当前事件) = min(所有后继事件的vl - 对应活动的持续时间)。

  以题目中顶点为例：

  • 先确定 ve (J)=45（正向推导的结果），故 vl (J)=45；
  • vl (H) = vl (J) - H→J 的时长 = 45-9=36；
  • vl (F) = vl (J) - F→J 的时长 = 45-18=27；
  • vl (E) = min (vl (H)-E→H 的时长，vl (F)-E→F 的时长) = min (36-10, 27-3)=24；
  • 后续顶点同理，取后继 vl - 活动时长的最小值，最终得到对应结果。

  四、（4）活动最早开始时间（e）的思路

  ==活动的最早的 = 起始的最早==

  活动是 “弧”，弧的尾是事件 i，头是事件 j，活动的最早开始时间是 “弧尾事件发生后，活动才能开始的最早时间”，即：

  活动的e = 弧尾事件的ve。

  以题目中活动为例：

  • 活动 <B,C> 的尾是 B，故 ==e=ve (B)===10；
  • 活动 <D,G> 的尾是 D，故 ==e=ve (D)===10；
  • 活动 <E,F> 的尾是 E，故 ==e=ve (E)===22。

  五、（5）活动最迟开始时间（l）的思路

  ==活动的最迟 = 终点的最迟 - 权==

  活动的最迟开始时间是 “不延误弧头事件最迟发生时间的前提下，活动能开始的最迟时间”，即：

  活动的l = 弧头事件的vl - 活动的持续时间。

  以题目中活动为例：

  • 活动 <B,C> 的头是 C，故 l=vl (C) - B→C 的时长 = 16-5=11；
  • 活动 <D,G> 的头是 G，故 l=vl (G) - D→G 的时长 = 23-10=13；
  • 活动 <E,F> 的头是 F，故 l=vl (F) - E→F 的时长 = 27-3=24。

  六、（6）关键活动的思路

  ==活动的e（最早开始时间）= l（最迟开始时间）==

  关键活动是 “没有空闲时间的活动”，判断标准：活动的e（最早开始时间）= l（最迟开始时间）。

  顶点	ve	vi	活动	e	l	相同
  A	0	0	A→B	0	1
  B	10	11	A→C	0	3
  C	16	16	A→D	0	0	√
  D	10	10	B→C	10	11
  E	22	24	B→E	10	12
  F	27	27	C→F	16	16	√
  G	20	23	D→C	10	10	√
  H	32	36	D→G	10	13
  I	28	39	E→H	22	26
  J	45	45	E→F	22	24
  			G→F	20	23
  			G→I	20	31
  			F→J	27	27	√
  			H→J	32	36
  			I→J	28	39

  因为这类活动一旦延迟，会直接延误整个工程的完成时间，因此筛选所有 e=l 的活动，即为关键活动。

5.深度优先生成树和广度优先生成树

已知图的邻接表如下所示，分别画出自顶点A出发进行遍历所得的深度优先生成树和广度优先生成树，回答下列问题。

（1）自顶点A出发的深度优先遍历序列为：（ ）。
【注意】假如深度优先遍历序列是A，B，C，D，E，则填空时填写ABCDE即可。首尾及中间均没有空格，后面类似空格均按此方法填写。
（2）自顶点A出发的深度优先生成树中，树的高度是（ ）；从顶点A到顶点F，每个顶点的度分别是（ ）；顶点B，C，D，E，F的双亲结点分别是（ ）。
【注意】假如每个顶点的度分别是1，2，3，4，5，则填空时填写1-2-3-4-5即可，数字之间用减号(-)连接。如果各顶点的双亲结点分别是A，B，C，D，则填写ABCD即可。首尾及中间均没有空格，后面类似空格均按此方法填写。
（3）自顶点A出发的广度优先遍历序列为：（ ）。
（2）自顶点A出发的广度优先生成树中，树的高度是（ ）；从顶点A到顶点F，每个顶点的度分别是（ ）；顶点B，C，D，E，F的双亲结点分别是（ )。

其中的树就是根据推导的顺序写出来的