假设一个有n个顶点和e条弧的有向图用邻接表表示，则删除与某个顶点vi相关的所有弧的时间复杂度是（ ）。
A.O(n) B.O(e) C.O(n+e) D.O(n*e)
在有向图G的拓扑序列中，若顶点vi在顶点vj之前，则下列情形不可能出现的是（ ）。
A．G中有弧<vi，vj> B．G中有一条从v i到v j的路径
C．G中没有弧<vi，vj> D．G中有一条从v j到v i的路径
上面是一张带权的无向图的网，如果用Prim算法，从4号点开始来找其对应的最小生成树，产生的第4条边的权值是：
A. 4
B. 5
C. 6
D. 8
如果从无向图的任一顶点出发进行一次深度优先搜索可访问所有顶点，则该图一定是 ( )
A.完全图
B.有回路的图
C.连通图
D.一棵树
下列关于AOE网的叙述中，不正确的是（ ）。
A．关键活动不按期完成就会影响整个工程的完成时间
B．任何一个关键活动提前完成，那么整个工程将会提前完成
C．所有的关键活动提前完成，那么整个工程将会提前完成
D．某些关键活动提前完成，那么整个工程将会提前完成
下面（ ）算法适合构造一个稠密图G的最小生成树。
A． Prim算法 B．Kruskal算法 C．Floyd算法 D．Dijkstra算法
下列关于AOE网的叙述中，不正确的是（ ）
A.关键活动不按期完成就会影响整个工程的完成时间
B.任何一个关键活动提前完成，那么整个工程将会提前完成
C.所有的关键活动提前完成，那么整个工程将会提前完成
D.某些关键活动若提前完成，那么整个工程将会提前完成
在上面的DAG中，从顶点b开始做拓扑排序（当同时有多个选择时，优先选择顶点值编号较小的）的结果序列的第5个 ( b是第1个 )顶点的值是：
A. f
B. c
C. e
D. d
图的BFS生成树的树高比DFS生成树的树高（ ）
A．小 B．相等 C．小或相等 D．大或相等
在上面的DAG中，从顶点b开始做拓扑排序（当同时有多个选择时，优先选择顶点值编号较小的）的结果序列的第4个 ( b是第1个 )顶点的值是：
上面是一张带权的无向图的网，如果用Kruskal算法来找其对应的最小生成树，产生的第3条边的权值是：
上图用改进的邻接表来表示了一张DAG图。基于这张邻接表结构来做拓扑排序，结果序列的第5个顶点 ( 出发点是第1个 ) 的值是：
A. c
B. d
C. a
D. e
A. b
B. a
C. d
D. c
上面是一张带权的无向图的网，如果用Prim算法，从4号点开始来找其对应的最小生成树，产生的第6条边的权值是：
A. 7
B. 10
C. 5
我们用一个有向图来表示航空公司所有航班的航线。下列哪种算法最适合解决找给定两城市间最经济的飞行路线问题？ ( )
A.Dijkstra算法
B.Kruskal算法
C.深度优先搜索
D.拓扑排序算法
在上面的DAG中，从顶点b开始做拓扑排序（当同时有多个选择时，优先选择顶点值编号较大的）的结果序列的第5个 ( b是第1个 )顶点的值是：
D. a
在上面的DAG中，从顶点b开始做拓扑排序（当同时有多个选择时，优先选择顶点值编号较大的）的结果序列的第4个 ( b是第1个 )顶点的值是：
A. a
C. g
D. f
上图用改进的邻接表来表示了一张DAG图。基于这张邻接表结构来做拓扑排序，结果序列的第4个顶点 ( 出发点是第1个 ) 的值是：
上图用改进的邻接表来表示了一张DAG图。基于这张邻接表结构来做拓扑排序，结果序列的第6个顶点 ( 出发点是第1个 ) 的值是：
判断有向图是否存在回路，除了可以利用拓扑排序方法外，还可以利用的是( )。
A．求关键路径的方法
B．求最短路径的迪杰斯特拉方法
C．深度优先遍历算法
D．广度优先遍历算法
如图给出了一个具有15个活动、11个事件的工程的AOE网，求关键路径。（事件表示、活动表示均可）
v1 v2 v3 v4 v5 v6 v7 v8 v9 v10 v11
0 3 4 5 7 9 15 11 21 22 28
0 6 4 15 7 19 21 11 21 22 28
请使用迪杰斯特拉算法，求A到C的最短路径。请写出该路径的顶点序列。要求必须写出算法过程，只写结果者不给分。