(1)求从指定源点到其余各顶点的迪杰斯特拉(Dijkstra)最短路径算法中弧上权不能为负的原因是在实
际应用中无意义;
(2)利用 Dijkstra 求每一对不同顶点之间的最短路径的算法时间是O(n3);(图用邻接矩阵表示)
(3)Floyd 求每对不同顶点对的算法中允许弧上的权为负,但不能有权和为负的回路。
A、(1),(2),(3) B、(1) C、(1),(3) D、(2),(3)
11. 当各边上的权值(A)时,BFS 算法可用来解决单源最短路径问题。
A、均相等 B、均互不相等 C、不一定相等
12. 若一个有向图具有拓扑排序序列,那么它的邻接矩阵必定为(C)。
A、对称矩阵 B、稀疏矩阵 C、三角矩阵 D、一般矩阵
13. 在有向图 G 的拓扑序列中,若顶点 Vi 在顶点 Vj 之前,则下列情形不可能出现的是(D)。
A、G 中有弧<Vi,Vj> B、G 中有一条从 Vi 到 Vj 的路径
C、G 中没有弧<Vi,Vj> D、G 中有一条从 Vj 到 Vi 的路径
A、从始点到终点的最短路径 B、从始点到终点的最长路径
C、人始点到终点的边数最多的路径 D、从始点到终点的边数最少的路径
15. 下面关于求关键路径的说法不正确的是(C)。
B、一个事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同
C、一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的差
D、关键活动一定位于关键路径上
1. 设无向连通图 G 含 n 个顶点 e 条边,则 G 的生成树含
3. 对稀疏图而言,在邻接矩阵和邻接表这两种存储结构中选择
4. 设无向图 G 含 n 个顶点 e 条边,则 G 的邻接表表示中含
5. 设有向图 G 含 n 个顶点 e 条弧,则 G 的邻接表表示中含