第9节图

您的姓名：



一、单项选择题（共23题，每题5分，共计115分;每题有且仅有一个正确选项）

1.Lucia 和她的朋友以及朋友的朋友都在某社交网站上注册了账号。下图是他们之间的关系图，两个人之间有边相连代表这两个人是朋友，没有边相连代表不是朋友。这个社交网站的规则是:如果某人A 向他(她)的朋友B 分享了某张照片，那么B 就可以对该照片进行评论;如果B 评论了该照片，那么他(她)的所有朋友都可以看见这个评论以及被评论的照片，但是不能对该照片进行评论(除非A 也向他(她)分享了该照片)。现在Lucia 已经上传了一张照片，但是她不想让Jacob 看见这张照片，那么她可以向以下朋友（）分享该照片。
*

A. Dana, Michael, Eve

B. Dana, Eve, Monica

C. Michael, Eve, Jacob

D. Micheal, Peter, Monica

2.有向图中每个顶点的度等于该顶点的（）。

A.入度

B.出度

C.入度与出度之和

D.入度与出度之差

3.在无向图中，所有顶点的度数之和是边数的（）倍。

A.0.5

B.1

C.2

D.4

4.设简单无向图G 有16 条边且每个顶点的度数都是2，则图G 有（）个顶点。

A. 10

B. 12

C. 8

D. 16

5.关于拓扑排序，下面说法正确的是（）。

A. 所有连通的有向图都可以实现拓扑排序

B. 对同一个图而言，拓扑排序的结果是唯一的

C. 拓扑排序中入度为 0 的结点总会排在入度大于 0 的结点的前面

D. 拓扑排序结果序列中的第一个结点一定是入度为 0 的点

6.设T是一棵有n个顶点的树，下列说法不正确的是（）。

A. T有n条边

B. T是连通的

C. T是无环的

D. T有n-1条边

7.设G 是有n 个结点、m 条边(n ≤ m)的连通图，必须删去G 的（）条边，才能使得G 变成一棵树。

A. m – n + 1

B. m - n

C. m + n + 1

D. n – m + 1

8.6个顶点的连通图的最小生成树，其边数为（）。

A.6

B.5

C.7

D.4

9.设G是有6个结点的完全图，要得到一棵生成树，需要从G中删去（）条边。

A.6

B.9

C.10

D.15

10.已知n个顶点的有向图，若该图是强连通的(从所有顶点都存在路径到达其他顶点)，则该图中最少有（）多少条有向边?

A. n

B. n+1

C.n-1

D.n*(n-1)

11.无向完全图是图中每对顶点之间都恰有一条边的简单图。已知无向完全图G有7个顶点，则它共有（）条边。

A. 7

B. 21

C. 42

D. 49

12.对一个有向图而言，如果每个节点都存在到达其他任何节点的路径，那么就称它是强连通的。例如，右图就是一个强连通图。事实上，在删掉边（）后，它依然是强连通的。

A. a

B. b

C. c

D. d

13.在一个无向图中，如果任意两点之间都存在路径相连，则称其为连通图。下图是一个有4个顶点、6条边的连通图。若要使它不再是连通图，至少要删去其中的（）条边。

A.1

B.2

C.3

D.4

14.在一个无向图中，如果任意两点之间都存在路径相连，则称其为连通图。右图是一个有5个顶点、8条边的连通图。若要使它不再是连通图，至少要删去其中的（）条边。

A.2

B.3

C.4

D.5

15.二分图是指能将顶点划分成两个部分，每一部分内的顶点间没有边相连的简单无向图。那么，12个顶点的二分图至多有（）条边。

A.18

B.24

C.36

D.66

16.对图G中各个结点分别指定一种颜色，使相邻结点颜色不同，则称为图G的一个正常着色。正常着色图G所必需的最少颜色数，称为G的色数。那么下图的色数是（）。

A.3

B.4

C.5

D.6

17.G 是一个非连通简单无向图，共有28 条边，则该图至少有（）个顶点。

A. 10

B. 9

C. 8

D. 7

18.由四个不同的点构成的简单无向连通图的个数是（）。

A. 32

B. 35

C. 38

D. 41

19.由四个没有区别的点构成的简单无向连通图的个数是（）。

A. 6

B. 7

C. 8

D. 9

20.以A0作为起点，对下面的无向图进行深度优先遍历时，遍历顺序不可能是（）。

A.A0, A1, A2, A3

B.A0, A1, A3, A2

C.A0, A2, A1, A3

D.A0, A3, A1, A2

21.具有n个顶点，e条边的图采用邻接表存储结构，进行深度优先遍历和广度优先遍历运算的时间复杂度均为（）。

A.Θ(n2)

B.Θ(e2)

C.Θ(ne)

D.Θ(n + e)

22.对一个n个顶点、m条边的带权有向简单图用Dijkstra算法计算单源最短路时，如果不使用堆或其它优先队列进行优化，则其时间复杂度为（）。

A.O(mn + n3)

B.O(n2)

C.O((m + n) log n)

D.O((m + n2) log n)

23.左图给出了一个加权无向图，从顶点V0开始用prim算法求最小生成树。则依次加入最小生成树的顶点集合的顶点序列为（）:

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

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

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

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

二、不定项选择题（共6题，每题5分，共计30分;每题有一个或多个正确选项，多选或少选均不得分）

1.以下哪些结构可以用来存储图（）。【多选题】

A.邻接矩阵

B.栈

C.邻接表

D.二叉树

2.若3个顶点的无权图G的邻接矩阵用数组存储为{{0，1，1}，{1，0，1}，{0，1，0}}，假定在具体存储中顶点依次为: v1，v2，v3。关于该图，下面的说法哪些是正确的（）。【多选题】

A.该图是有向图。

B.该图是强连通的。

C.该图所有顶点的入度之和减所有顶点的出度之和等于1。

D.从v1开始的深度优先遍历所经过的顶点序列与广度优先的顶点序列是相同的。

3.已知带权有向图G上的所有权值均为正整数，记顶点u到顶点v的最短路径的权值为d(u, v)。若v1, v2, v3, v4, v5是图G上的顶点，且它们之间两两都存在路径可达，则以下说法正确的有（）。【多选题】

A.v1到v2的最短路径可能包含一个环

B.d(v1, v2) = d(v2, v1)

C.d(v1, v3) ≤ d(v1, v2) + d(v2, v3)

D.如果v1→v2→v3→v4→v5是v1到v5的一条最短路径，那么v2→v3→v4是v2到v4的一条最短路径

4.以下图中一定可以进行黑白染色的有（）。(黑白染色:为各个结点分别指定黑白两种颜色之一，使相邻结点颜色不同。)【多选题】

A.二分图

B.完全图

C.树

D.连通图

5.下列关于最短路算法的说法正确的有（）。【多选题】

A. 当图中不存在负权回路但是存在负权边时，Dijkstra 算法不一定能求出源点到所有点的最短路。

B. 当图中不存在负权边时，调用多次Dijkstra 算法能求出每对顶点间最短路径。

C. 图中存在负权回路时，调用一次Dijkstra 算法也一定能求出源点到所有点的最短路。

D. 当图中不存在负权边时，调用一次Dijkstra 算法不能用于每对顶点间最短路计算。

6.对右图使用Dijkstra算法计算S点到其余各点的最短路径长度时，到B点的距离d[B]初始时赋为8，在算法的执行过程中还会出现的值有（）。

【多选题】

A. 3

B. 7

C. 6

D. 5

第9节 图

第9节图