超星 - 第8章-图-作业 - 查题吧

单选题

【单选题】图的BFS生成树的树高比DFS生成树的树高( )。

A. 小或相等
B. 小
C. 大或相等
D. 大

单选题

【单选题】无向图G=(V,E),其中:V={a,b,c,d,e,f},E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)},对该图进行深度优先遍历,得到的顶点序列正确的是( )。

A. a,b,e,c,d,f
B. a,c,f,e,b,d
C. a,e,b,c,f,d
D. a,e,d,f,c,b
E. 无
F. 无2

单选题

【单选题】判断有向图是否有回路,除了可以用拓扑排序外,还可以用( )。

A. 求关键路径的方法
B. 广度优先遍历算法
C. 求最短路径的算法
D. 深度优先遍历算法

单选题

【单选题】在具有n个顶点的图G中,若最小生成树不唯一,则( )。

A. G的边数一定大于n-1
B. G的权值最小的边一定有多条
C. G的最小生成树的代价不一定相等
D. 上述选项都不对

单选题

【单选题】已知有向图G=(V,E),其中V={V1,V2,V3,V4,V5,V6,V7},E={<V1,V2>,<V1,V3>,<V1,V4>,<V2,V5>,<V3,V5>,<V3,V6>,<V4,V6>,<V5,V7>,<V6,V7>},G的拓扑序列是( )。

A. V1,V3,V4,V6,V2,V5,V7
B. V1,V3,V2,V6,V4,V5,V7
C. V1,V3,V4,V5,V2,V6,V7
D. V1,V2,V5,V3,V4,V6,V7

单选题

【单选题】在有向图G的拓扑序列中,若顶点Vi在顶点Vj之前,下列情形不可能出现的是( )。

A. G中有弧<Vi,Vj>
B. G中有一条从Vi到Vj的路径
C. G中没有弧<Vi,Vj>
D. G中有一条从Vj到Vi的路径

单选题

【单选题】在下列网中,( )是边不带权值的图。

A. 邮电图
B. AOV网
C. 公路网
D. AOE网

单选题

【单选题】关键路径是AOE网中( )。

A. 从始点到终点的最短路径
B. 从始点到终点的最长路径
C. 从始点到终点的边数最多的路径
D. 从始点到终点的边数最少的路径

单选题

【单选题】下列有关图的说法错误的是( )。

A. 有向图中,出度为0的结点称为叶子
B. 用邻接矩阵表示图,容易判断任意两个顶点之间是否有边相连,并秋的各顶点的度
C. 按深度方向遍历图和先根次序遍历树类似,得到的结果是唯一的
D. 若有向图G中从顶点Vi到顶点Vj有一条路径,则在图G的顶点的线性序列中顶点Vi必在顶点Vj之前的话,则称为一个拓扑序列

单选题

【单选题】具有n个顶点的有向完全图有( )条边。

A. n(n-1)/2
B. n(n-1)
C. n(n+1)/2
D. n(n+1)

1