数据结构第7章 图习题

第7章 图

一、单项选择题

1．在一个无向图G中，所有顶点的度数之和等于所有边数之和的______倍。 A．l/2 C．2

B．1 D．4

2．在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的______倍。 A．l/2 C．2

B．1 D．4

3．一个具有n个顶点的无向图最多包含______条边。 A．n C．n-1

B．n＋1 D．n(n-1)/2

4．一个具有n个顶点的无向完全图包含______条边。 A．n(n-l) C．n(n-l)/2

B．n(n+l) D．n(n-l)/2

5．一个具有n个顶点的有向完全图包含______条边。 A．n(n-1) C．n(n-l)/2

B．n(n+l) D．n(n+l)/2

6．对于具有n个顶点的图，若采用邻接矩阵表示，则该矩阵的大小为______。A．n C．n-1

7．无向图的邻接矩阵是一个______。 A．对称矩阵 C．上三角矩阵

B．零矩阵 D．对角矩阵 B．n×n D．(n-l) ×(n-l)

8．对于一个具有n个顶点和e条边的无(有)向图，若采用邻接表表示，则表头向量的大小为______。

A．n C．2n

B．e D．2e

9．对于一个具有n个顶点和e条边的无(有)向图，若采用邻接表表示，则所有顶点邻接表中的结点总数为______。

A．n C．2n

B．e D．2e

10．在有向图的邻接表中，每个顶点邻接表链接着该顶点所有______邻接点。A．入边

C．入边和出边

B．出边

D．不是入边也不是出边

11．在有向图的逆邻接表中，每个顶点邻接表链接着该顶点所有______邻接点。 A．入边

C．入边和出边

B．出边

D．不是人边也不是出边

12．如果从无向图的任一顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是______。

A．完全图 C．有回路

B．连通图 D．一棵树

13．采用邻接表存储的图的深度优先遍历算法类似于二叉树的______算法。 A．先序遍历

B．中序遍历

C．后序遍历 D．按层遍历

14．采用邻接表存储的图的广度优先遍历算法类似于二叉树的______算法。 A．先序遍历 B．中序遍历 C．后序遍历 D．按层遍历

15．如果无向图G必须进行二次广度优先搜索才能访问其所有顶点，则下列说

法中不正确的是______。 A．G肯定不是完全图

B．G一定不是连通图

C．G中一定有回路 D．G有二个连通分量 16．下列有关图遍历的说法不正确的是______。 A．连通图的深度优先搜索是一个递归过程

B．图的广度优先搜索中邻接点的寻找具有“先进先出”的特征 C．非连通图不能用深度优先搜索法 D．图的遍历要求每一顶点仅被访问一次 17．下列说法中不正确的是______。

A．无向图中的极大连通子图称为连通分量

B．连通图的广度优先搜索中一般要采用队列来暂存刚访问过的顶点 C．图的深度优先搜索中一般要采用栈来暂存刚访问过的顶点 D．有向图的遍历不可采用广度优先搜索方法

18．一个有向图G的邻接表存储如下图7-1所示，现按深度优先搜索遍历，从顶点v1出发，所得到的顶点序列是______。

A．v1，v2，v3，v4，v5 B．v1，v2，v3，v5，v4 C．v1，v2，v4，v5，v3 D．v1，v2，v5，v3，v4

v1 v2 v3 v4 ∧ v5 2 3 5 ∧ 3 5 ∧ 4 ∧ 4 ∧ 图7-1 一个有向图的邻接表

19．对图7-2所示的无向图，从顶点1开始进行深度优先遍历，可得到顶点访问

序列______。

A．1，2，4，3，5，7，6 B．1，2，4，3，5，6，7 C．1，2，4，5，6，3，7 D．1，2，3，4，5，7，6

1 3 2 4 6 5 7 图7-2 一个无向图

20．对图7-2所示的无向图，从顶点1开始进行广度优先遍历，可得到顶点访问

序列______。

A．1，3，2，4，5，6，7

B．1，2，4，3，5，6，7

C．1，2，3，4，5，7，6 D．2，5，1，4，7，3，6 21．一个无向连通图的生成树是含有该连通图的全部顶点的______。

A．极小连通子图 C．极大连通子图

B．极小子图 D．极大子图

22．设无向图 G=(V, E) 和G’= (V’, E’)，如果 G’为G的生成树，则下列说法中

不正确的是______。

A．G’为G的连通分量 B．G’为G的无环子图

C．G’为G的子图 D．G’为G的极小连通子图且V’＝V 23.任意一个无向连通图______最小生成树。 A．只有一棵 C．一定有多棵

B．有一棵或多棵 D．可能不存在

24．对于含有n个顶点的带权连通图，它的最小生成树是指图中任意一个

________。

A．由n-1条权值最小的边构成的子图。 B．由n-1条权值之和最小的边构成的子图。 C．由n-1条权值之和最小的边构成的连通子图。 D．由n个顶点构成的边的权值之和最小的生成树。

25．若一个有向图中的顶点不能排成一个拓扑序列，则可断定该有向图_______。 A．是个有根有向图 B．是个强连通图

C．含有多个入度为0的顶点 D．含有顶点数目大于1的强连通分量 26．判定一个有向图是否存在回路除了可以利用拓扑排序方法外，还可以用____。

A．求关键路径的方法 B．求最短路径的Dijkstra算法 C．广度优先遍历算法 D．深度优先遍历算法 27．求最短路径的Dijkstra算法的时间复杂度为______。 A．O(n)

B．O(n+e)

C．O(n2) D．O(ne) 28．求最短路径的Floyd算法的时间复杂度为______。 A．O(n) C．O(n2) 29．关键路径是事件结点网络中______。 A．从源点到汇点的最长路径

B．O(ne) D．O(n3)

B．从源点到汇点的最短路径

C．最长的回路 30．下面说法不正确的是______。

D．最短的回路

A．在AOE网中，减少任一关键活动的权值后，整个工期也就相应减少 B．AOE网工程工期为关键活动的权值和

C．在关键路径上的活动都是关键活动，而关键活动也必须在关键路径上 D．A和B

31．下面说法不正确的是______。

A．关键活动不按期完成就会影响整个工程的完成时间 B．任何一个关键活动提前完成，将使整个工程提前完成 C．所有关键活动都提前完成，则整个工程提前完成 D．某些关键活动若提前完成，将使整个工程提前完成

二、填空题

1．对于具有n个顶点的无向图G最多有_________条边。 2．对于具有n个顶点的强连通有向图G至少有_________条边。 3．对于具有n个顶点的有向图，每个顶点的度最大可达___________。 4．若无向图G的顶点度数最小值大于___________时，G至少有一条回路。 5．对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表头向量的大小为___________，所有邻接表中的结点总数是__________。

6．已知一个有向图的邻接矩阵表示，删除所有从第i个结点出发的弧的方法是____________。

7．对于n个顶点的无向图，采用邻接矩阵表示，求图中边数的方法是__________，判断任意两个顶点i和j是否有边相连的方法是__________，求任意一个顶点的度的方法是___________。

8．对于n个顶点的有向图，采用邻接矩阵表示，求图中边数的方法是_________，判断任意两个顶点i和j是否有边相连的方法是__________，求任意一个顶点的度的方法是__________。

9．无向图的连通分量是指___________。

10．已知图G的邻接表如图7-3所示，从顶点v1出发的深度优先搜索序列为________，从顶点1出发的广度优先搜索序列为_____________。

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库数据结构第7章 图习题在线全文阅读。