广度优先搜索，需要用到的数据结构是()

A. 链表

B. 队列

C. 栈

D. 散列表

参考答案 B

广度优先搜索借助队列，深度优先搜索借助栈。

对图进行深度优先搜索遍历时，需要用到的数据结构是( )

A. 链表

B. 队列

C. 栈

D. 散列表

参考答案 C

无向图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,b,e,d,f,c

参考答案 D

• 先构造图结构

• 再深度优先遍历算法

画图演算

( )方法可以判断一个有向图是否有环(回路)

A. 深度优先遍历

B. 广度优先遍历

C. 求最短路径

D. 求关键路径

参考答案 A

答案比较明显，深度优先遍历。

以a为起点，对右边的无向图进行深度优先遍历，则 b,c,d,e四个点中有可能作为最后一个遍历到的点的个数为( )

A. 1

B. 2

C. 3

D. 4

参考答案 B

c和d都是不可能作为最后一个遍历到的结点的。

设G是有n个结点、m条边(n≤m)的连通图，必须删除G的( )条边，才能使G变成一棵树

A. m-n+1

B. m-n

C. m+n+1

D. n-m+1

参考答案 A

直接用具体的数字代入n=4，m=5；排除法A正确。所以是 m-n+1 。

设简单无向图 G 有16条边，且每个顶点的度数都是2，则图G有( )个顶点

A. 10

B. 12

C. 8

D. 16

参考答案 D

每个顶点的度数是2，说明每个顶点都连接其他两个顶点。2条边2个顶点，16条边就是16个顶点。

或者画一下3条边的图，是3个顶点，依次类推。

有向图中每个顶点的度等于该顶点的( )

A. 入度

B. 出度

C. 入度和出度之和

D. 入度和出度之差

参考答案 C

有向图度=入度+出度

无向完全图是指图中每个顶点之间都恰好有一条边的简单图。已知无向完全图G有7个顶点，则它共有( )条边

A. 7

B. 21

C. 42

D. 49

参考答案 B

每个顶点可以与6个顶点相连，所以6条边 * 7 = 42条边；

每条边两个顶点共用，所以42/2=21