数据结构与算法【含答案】CH6 图 图测验

(1)单选题

​有n个结点,e条边且使用邻接表存储的有向图进行广度优先遍历,其算法时间复杂度是()


​A. O(n+e)

B. O(n)

C. O(n*e)

D. O(e)

(2)单选题

‍设无向图的顶点个数为n,则该图最多有( )条边。

​A. n(n-1)/2

B. n*n

C. n(n+1)/2

D. n-1

(3)单选题

‎一个有向图,共有n条弧,则所有顶点的度的总和为( )。


​A. n

B. n-1

C. 2n

D. n/2

(4)单选题

​用邻接表存储图所用的空间大小( )。

‏A. 只与边数的平方有关

B. 只与图的顶点个数有关

C. 与图的顶点和边的个数都有关

D. 只与图的边数有关

(5)单选题

‎当各边的权值( )时,BFS算法可以用来解决单源最短路径问题。


‎A. 权值都为1

B. 不一定相等

C. 均互不相等

D. 均相等

(6)单选题

‍关键路径是AOE网中( )。

​A. 从始点到终点的最长路径

B. 从始点到终点的边数最少的路径

C. 从始点到终点的边数最多的路径

D. 从始点到终点的最短路径

(7)单选题

‎已知图的邻接表如下所示,则从顶点0出发按深度优先遍历的结点序列是(    )。

‎ 


‍A. 0,3,1,2

B. 0,1,2,3

C. 0,1,3,2

D. 0,3,2,1

(8)单选题

‏下面哪一种情况的图最适合采用邻接矩阵进行存储?(     )



‏A. 10000个顶点,500条边的图

B. 1000个顶点,1200条边的图

C. 10000个顶点,100000条边的图

D. 100个顶点,4000条边的图

(9)单选题

‌设有一个有向图如下所示,请指出下列(   )序列不是该图的拓扑排序序列?

‌A. V0,V2,V5,V3,V1,V4,V6

B. V0,V2,V5,V1,V3,V4,V6

C. V0,V1,V2,V4,V5,V6,V3

D. V0,V2,V5,V1,V4,V3,V6

(10)单选题

‌对以下无向图进行prim建立最小生成树的过程是( )


‎A. (V1,V2)(V3,V4)(V2,V6)(V2,V4)(V5,V4)

B. (V1,V2)(V2,V6)(V5,V6)(V6,V3)(V4,V3)

C. (V1,V2)(V2,V6)(V6,V5)(V5,V4)(V4,V3)

D. (V1,V2)(V2,V6)(V5,V6)(V4,V3)(V6,V3)

获取答案请阅读全文

未经允许不得转载!数据结构与算法【含答案】CH6 图 图测验