第五章练习题

1．有n个结点的无向图的边数最多为（ B ）。

A．n+1 B．n(n-1)/2 C．n(n+1) D．2n(n+1) 2．广度优先遍历图类似于二叉树的（D ）。

A．先序遍历 B．中序遍历 C．后序遍历 D．层次遍历

3．设有一稠密图G，则G采用 存储较省空间。设有一稀疏图G，则G采用 存储较省空间。邻接矩阵、邻接链表

4．已知世界六大城市为：北京（B）、纽约（N）、巴黎（P）、伦敦（L）、东京（T）、墨西哥城（M）。试在由下表给出的交通网中确定最小生成树，并说明所使用的方法及其时间复杂度。

表 世界六大城市交通里程网络表（单位：100km） B N P L T M B 109 82 81 21 124 N 109 58 55 108 32 P 82 58 3 97 92 L 81 55 3 95 89 T 21 108 97 95 113 M 124 32 92 89 113 最小生成树如图所示。使用普里姆（Prim）算法的时间复杂度为O（n2），n为顶点数，使用克鲁斯卡尔（Kruskal）算法的时间复杂度为O（eloge），e为边数。

5．采用邻接表存储的图的广度优先遍历算法类似于二叉树的（ C ）。 A．中序遍历 B．前序遍历 C．后序遍历 D．按层次遍历 6．有n个结点的有向完全图的边数是（C ）。

A．n2 B．2n C．n（n-1） D．2n（n+1）

7．图的深度优先遍历类似于二叉树的（ A ）。 A．先序遍历 B．中序遍历 C．后序遍历

D．层次遍历

8．n个顶点e条边的图采用邻接表存储，深度优先遍历算法的时间复杂度为 ；n个顶点e条边的图采用邻接矩阵存储，广度优先遍历算法的时间复杂度为 。O（n+e）、O（n）

9．在图形结构中，直接前驱和直接后继结点之间分别存在着 的联系，在树型结构中，直接前驱和直接后继结点之间分别存在着 的联系。

M：N（或者M对N）、１：N（或者1对N）

10．图G=（V，E），V={0，1，2，3，4，5}，E={<0，1>，<0，2>，<1，4>，

<2，5>，<5，4>，<4，3>，<5，3>}。画出图G的邻接矩阵，并写出图G中的所有的拓扑排序序列。

2

000000100000100000000011010001001 000拓扑排序序列：（0，1，2，5，4，3），（0，2，1，5，4，3）,（0，2，5，1，4，3）

01011．设含有三个顶点v1,v2,v3的图的邻接矩阵为001，则该图中顶点v1的出 010度为（ B ）

A. 0 B. 1 C. 2 D. 3 12. 采用邻接表存储的图的广度优先遍历算法类似于二叉树的（D ）

A. 中根遍历 B. 前根遍历 C.后根遍历 D. 按层次遍历 13.下列说法中不正确的是（ D ）

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

B.连通图的广度优先搜索中一般要采取队列来暂存刚访问过的顶点 C.图的深度优先搜索中一般要采用栈来暂存刚访问过的顶点

D.有向图的遍历不可采用广度优先搜索方法 14．已知某图的邻接表存储结构如下：

A B D ^ B A C ^ C B D E F ^ D A C ^ E C F H ^ F C E G ^ G F H ^ H E G ^ 写出针对该邻接表的图的广度优先遍历结果 ABDCEFHG

15．在一个图中，所有顶点的度数之和与图的边数的比是（C ） A．1：2 B．1：1 C．2：1 D．4：1 16．在一个具有n个结点的无向完全图中，包含有（ A ）条边。 A. n(n-1)/2 B.n(n-1) C. n(n+1)/2 D. (n-1)/2 17．设图的邻接链表如下图所示，则该图有（ B ）条边。 1 V1 2 3 4 ^ 2 V2 1 3 4 ^ 3 V3 1 2 ^ 4 V4 1 2 ^

A. 4 B. 5 C. 10 D. 20 18.下列说法中不正确的是（ A ）

A. 有向图的遍历不可采用广度优先搜索方法

B. 连通图的广度优先搜索中一般要采取队列来暂存刚访问过的顶点 C. 图的深度优先搜索中一般要采用栈来暂存刚访问过的顶点 D. 无向图中的极大连通子图称为连通分量

19．第一个顶点和最后一个顶点相同的路径称为 。除第一个顶点和最

后一个顶点相同外，其余顶点不重复的回路，称为 。环或回路；简单回路或简单环

20．在有n个顶点的无向图中，每个顶点的度最大可达 。n-1

21．对于有n个顶点的无向图，采用邻接矩阵表示，如何判断以下问题：图中有多少条边？

任意两个顶点i和j之间是否有边相连？任意一个顶点的度是多少？

用邻接矩阵表示无向图时，因为是对称矩阵，对矩阵的上三角部分或下三角部分检测一遍，统计其中的非零元素个数，就是图中的边数。如果邻接矩阵中A[i][j]不为零，说明顶点i和j之间有边相连。此外统计出矩阵第i行或第j列的非零元素个数，就可得到顶点i的度

数。

22．n个顶点的无向图若采用邻接矩阵存储，则该矩阵的大小是( D ) A．n B．（n-1）2 C．n+1 D．n2 23.说法不正确的是( D )

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

B.连通图的广度优先搜索中一般要采取队列来暂存刚访问过的顶点 C.图的深度优先搜索中一般要采用栈来暂存刚访问过的顶点 D.图的广度优先搜索类似树的前根遍历

24. 一个有向图中所有顶点的度之和等于所有弧的( C )

A．4倍 Ｂ．2倍 Ｃ．1倍 Ｄ．0.5倍 25．对于有向无环图：

（1）叙述求拓扑有序序列的步骤；

（2）对于如下所示的图，写出它的4个不同的拓扑有序序列。

图 有向无环图

(1）拓扑排序算法的步骤为：

1）在有向图中选择一个没有前驱的顶点且输出之； 2）在图中删除该顶点和所有以该顶点为尾的弧； 3）重复1）和2），直至图中设有前驱的顶点为止。 （2）它的4个拓扑有序序列为：

12347856 13247856 13427856 13527846

26．给定如下所示无向图，（1）写出其邻接矩阵；（2）写出一种以顶点A为起点的深度优

先搜索顶点序列。

G D E F H B A C 011000011001100010000100010000100100001000100000000110001000 0000AHBDGECF; ABEGDCF; ABDGEHCF等等(只写其中一个)

27.下列说法中不正确的是（ D ）

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

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

28．有向图G用邻接矩阵A[1...n，1...n]存储，其第i列的所有元素之和等于顶点i的 。入度

29．在有n个顶点的有向图中，每个顶点的度最大可达 。n-1

30．对于下图，试给出： （1）邻接表； （2）邻接矩阵；

（1） 其邻接矩阵如图1所示。其邻接表如图2所示。

000101000000110010100100000111001 0001 2 3 4 ∧ 5 6 4 ∧ 1 4 3 ∧ 5 6 ∧ 图1 邻接矩阵

1 2 2 5 ∧ 4 ∧ 图2 邻接表

31. 采用邻接表存储的图的深度优先遍历算法类似于二叉树的（B ）。

A. 中序遍历 B. 前序遍历 C. 后序遍历 32.下列说法中不正确的是（ D ）。

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

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

33．设有向图G的邻接矩阵为A，如果图中不存在弧，则A[i，j]的值为 ，如果图中存在弧，则A[i，j]的值为 。0、1

34．在一个具有n个顶点的无向完全图中，包含 条边；在一个具有n个顶点的有向完

全图中，包含 条边。n(n-1)/2、n(n-1)

35．用邻接矩阵表示图时，矩阵元素的个数与顶点个数是否相关？与边的条数是否相关？ 用邻接矩阵表示图，矩阵元素的个数是顶点个数的平方，与边的条数无关。矩阵中非零元素的个数与边的条数有关。

D. 按层次遍历

36．写出下图所示的AOV网的所有拓扑有序序列。

共有8种：

ADBECF ADBEFC ADEBCF ADEBFC DABECF

DABEFC DAEBCF DAEBFC