习题七
一、选择题
1．在一个无向图G中，所有顶点的度数之和等于所有边数之和的（ ）倍。 A．l/2 B．1 C．2 D．4
2．在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（ ）倍。 A．l/2 B．1 C．2 D．4 3．一个具有n个顶点的无向图包含（ ）条边。
A．n B．n＋1 C．n-1 D．n/2 4．一个具有n个顶点的无向完全图包含（ ）条边。
A．n(n-l) B．n(n+l) C．n(n-l)/2 D．n(n-l)/2 5 一个具有n个顶点的有向完全图包含（ ）条边。
A．n(n-1) B．n(n+l) C．n(n-l)/2 D．n(n+l)/2
6．对于具有n个顶点的图，若采用邻接矩阵表示，则该矩阵的大小为（ ）。 A．n B．n2 C．n-1 D．(n-l)2
7．对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表头向量的大小为（ ）。
A．n B．e C．2n D．2e
8．对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则所有顶点邻接表中的结点总数为（ ）。
A．n B．e C．2n D．2e
9．在有向图的邻接表中，每个顶点邻接表链接着该顶点所有（ ）邻接点。 A．入边 B．出边
C．入边和出边 D．不是入边也不是出边
10．在有向图的逆邻接表中，每个顶点邻接表链接着该顶点所有（ ）邻接点。 A．入边 B．出边
C．入边和出边 D．不是人边也不是出边 11．下列说法中不正确的是（ ）。
A．无向图中的极大连通子图称为连通分量
B．连通图的广度优先搜索中一般要采用队列来暂存刚访问过的顶点 C．图的深度优先搜索中一般要采用栈来暂存刚访问过的顶点 D．有向图的遍历不可采用广度优先搜索方法
12．设无向图 G=(V, E) 和G’= (V’, E’)，如果 G’为G的生成树，则下列说法中不正确的是（ ）。
A．G’为G的连通分量 B．G’为G的无环子图
C．G’为G的子图 D．G’为G的极小连通子图且V’＝V
13．如果无向图G必须进行二次广度优先搜索才能访问其所有顶点，则下列说法中不正确的是（ ）。
A．G肯定不是完全图 B．G一定不是连通图 C．G中一定有回路 D．G有二个连通分量 14．邻接表是图的一种（ ）。
A．顺序存储结构 B． 链式存储结构 C．索引存储结构 D． 散列存储结构 15．如果从无向图的任一顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一
25
定是（ ）。
A．完全图 B．连通图 C．有回路 D．一棵树 16．下列有关图遍历的说法不正确的是（ ）。 A．连通图的深度优先搜索是一个递归过程
B．图的广度优先搜索中邻接点的寻找具有“先进先出”的特征 C．非连通图不能用深度优先搜索法
D．图的遍历要求每一顶点仅被访问一次
17． 一个无向连通图的生成树是含有该连通图的全部顶点的（ ）。 A．极小连通子图 B．极小子图 C．极大连通子图 D．极大子图 18．无向图的邻接矩阵是一个（ ）。
A．对称矩阵 B．零矩阵 C．上三角矩阵 D．对角矩阵 二、填空题
1．在图中，任何两个数据元素之间都可能存在关系，因此图的数据元素之间是一种________________的关系。
2．在图G中，如果代表边的顶点偶对是_____________，则称G为无向图。 3．在图G中，如果代表边的顶点偶对是_____________，则称G为有向图。
4．在图G中，＜vi，vj＞表示从vi到vj的一条边，在有向图中又称为一条____，且称vi为______或_________，称vj为_________或__________。显然在有一向图中
5．具有n (n-1)/2条边的无向图称为__________，简称为_________，其中n表示无向图中顶点的个数，n(n-1)/2是具有n个顶点无向图所拥有边的___________。
6．具有n个定点的有向图，如果它同时具有n(n-1)条狐，则称该图为____________，其中n(n-1)是具有n个顶点有向图所拥有弧的___________________。
7． 有很少条边或弧（如边数少于nlogn）的图称为________________。 8． 如果图中的边或弧带有权，则称这种图为_______________。
9． 如果有两个网G=(V, E)，G’=(V’,E’)，若满足V(G’) V(G)，并且E(G’) E(G)，则称图G’为图G的__________。
10． 在无向图中，若存在一条边(v, w)，则称v和w这两个端点互为___________，同时称边(v,w)__________顶点v和w，或者说边(v,w)和顶点v和w_______________。
11．在有向图中，若存在一条弧
12．顶点v的度定义为_________________的数目，记为D(v)。
13．在有向图中，顶点v的度又分为_____________和_________，__________是以顶点v为头的弧的数目，或者说是以该顶点为终点的边的数目，记为ID(v)；____________是以顶点v为尾的弧的数目，或者说是以顶点为起点的边的数目，记为OD(v)；顶点v的度是它的___________和__________之和，即D(v)=ID(v)＋OD(v)。 14．____________是指一条路径上所经过的边或弧的数目。
15．若一条路径上除开始结点和结束结点外(开始结点和结束结点也可以为不同顶点），其余顶点均不相同，则称该路径为_____________。
16． 若一条路径上的开始结点和结束结点为同一个顶点，则称该路径为________或_______。同时除了第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路称_________或__________。
17．在无向图G中，如果从顶点v到顶点v’有路径，则称v和v’是______________的。
26
如果对于图中任意两个顶点v和v’都是连通的，则称图G是________，否则称为__________。无向图中，极大的连通子图称为___________________。
18．在有向图中，若任意两个顶点vi，vj∈V，vi≠vj，从vi到vj和从vj到vi都存在路径，则称该图是____________。有向图中的极大强连通子图称为有向同的___________。 19．一个连通图的生成树是一个__________，它含有图中全部以点，但只有构成一棵树的__________条边。如果在一棵生成树添加一条边，必定构成一个___________，因为新添加的这条边使得依附在它两端的两个顶点有了____________。
20．如果有一个有向图恰有一个顶点的人度_______，其余以顶点的人度均________，则该有向图是一棵有向树。一个有向图的___________由若干棵有向树构成，含有图中全部顶点，但只有构成若干棵不相交的有向树的弧。
21．图的邻接矩阵（Adjacency Matrix）表示法是用一个________来表示图中顶点之间的相邻关系。
22．邻接表(Adjacency List)是图的一种_______存储结构。在邻接表中，对图中每个顶点建立一个_________，第i个单链表中的结点表示依附于顶点vi的边(对无向图)或弧（对有向图）。 23．逆邻接表只有______图才具有。是为了便于确定有向图中顶点的_______而建立的。 24．一个图的邻接矩阵的表示是_________，但是图的邻接表的表示并_____________。这是因为邻接表中各边结点的连接次序取决于建立邻接表时输入的次序，由于输入的时候是随机的，所以图的邻接表建立的结果也有可能____________。
25．从邻接表的定义可以看到，若无向图有n个结点和e条边，则它的邻接表需要________个头结点和______________个表结点。
26．图的遍历(Traversing Graph)是从图的某一顶点出发访问图中___________，并且使每一个顶点___________________的过程。
27．图的深度优先搜索的基本思想是：从中某个顶点v出发，首先访问_________，然后访问_________顶点w，接着访问一个_____________的顶点，依此类推，直到图中所有和v有路径相通的顶点都被访问到；若此时图中仍有顶点未被访问，则选择图中未被访问的顶点作为___________，重复上述过程，直到图中所有顶点_______________为止。 28．图的深度优先搜索遍历类似于树的__________________遍历。
29．图的广度优先搜索的基本思想是：从某个顶点v出发，首先访问此顶点，然后按广度优先搜索依次访问所有v的__________，接着从这些___________出发仍然进行广度优先搜索依次访问其他结点，直至图中所有已被访问的顶点的_________全部被访问到。若此时图中依然有未被访问的顶点。则另选一个图中____________作为起始点，重复上述过程，直到图中所有顶点___________为止。
30．图的广度优先搜索类似于树的_______________遍历。
31．如果连通图是一个网络，生成树的_______称为这棵生成树的代价，则称该网络中所有生成树中权值最小的生成树为____________，简称为__________。
32．构造一棵最小生成树往往都要利用最小生成树的一种简称为MST的性质。常见的构造最小生成树的______________算法和___________算法都利用了MST性质。
33． 路径上的第一个顶点称为____________，最后一个顶点称为____________。 34． 迪杰斯特拉算法是求____________的最短路径，弗洛伊德（Floyd）算法是求_________的最短路径。
35．一个____________称为有向无环图，简称为DAG图。
36．DAG图比有向树更一般，因为在有向树中不允许出现____________的结点，而在DAG图中则可以；另外DAG图不允许_____________，因此又是一种特殊的图。
27
37．用顶点表示_________，用弧表示活动之间________的有向图，称为顶点表示活动的网（Activity On Vertex Network），简称 AOV网。
38．在AOV网中不可以出现有向环或回路，如果出现环或回路，这意味着某项活动是_________，这样的工程无法进行，对于计算机中的程序流程图来说就是_____________，也相当于操作系统中的______________。
39．检测AOV网是否有回路的方法是构造_________。从构造拓扑序列过程中可以发现是否有______________。
40．拓扑排序是对AOV网构造一个__________，使得所有结点的________在序列中得以体现，即在序列中某个结点的前驱必须在后继之前。拓扑排序的序列__________。 41．如果用数学上的术语进行描述，拓扑排序是由某个集合上的一个__________关系得到该集合上的一个__________的操作。 42．构造拓扑有序序列的过程可以发现有向图中________，同时构造拓扑有序序列的过程就是利用拓扑排序算法进行________________的过程。
43．拓扑排序的结果使得当前图中_________全部被输出，但仍然有结点未被输出，这说明有向图中存在_______________。
44．如果含n个顶点的图形成一个环，则它有___________棵生成树。 45．有n个结点的无向图的边数最多为____________。
46．有n个顶点的强连通有向图G至少有___________条边。
47．用邻接矩阵存储有向图G，其第i行的所有元素之和等于顶点i的_________。 48．设有向图G的邻接矩阵为 A，图中i和j之间不存在弧，则A[i,j］的值为______。
49．有n个顶点的连通图的边数至少为____________。
50．在有n个顶点的有向图中，每个顶点的度最大可达___________。 51．在无向图G的邻接矩阵A中，若(vi,vj)属于图G的边集，则对应元素A[i,j]为______，否则等于_____________（用逗号分开）。
52．已知一个有向图用邻接矩阵表示，计算第i个结点的人入度的方法是__________。 53．对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表头向量的大小为________________，所有邻接表中的结点总数是________________。 三、判断题
1．有n个结点的无向图中，若边数大于n-1，则该图是连通的。 （ ） 2．若一个有向图的邻接矩阵中对角线以下元素均为零，则该图的拓扑有序序列必定存在。 （ ） 3．AOV网拓扑排序的结果是惟一的。 （ ） 4．图的广度优先搜索序列是惟一的。 （ ） 5．具有n个顶点的无向图采用邻接矩阵表示，图中的边数等于邻接矩阵中非零元素之和的一半。 （ ） 6．若连通图上各边权值均不相同，则该图的最小生成树是惟一的。 （ ） 7．无向图的邻接矩阵一定是对称的。（ ） 8．有向图的邻接矩阵一定是非对称的。（ ）
9．用邻接矩阵存储图的时候，占用空间大小不但与图的结点个数有关还与图的边数有关。（ ）
10．图的连通分量是无向图的极小连通子图。（ ） 11．图的强连通分量是无向图的极大连通子图。（ ） 12．对任意一个图从它的某个顶点出发进行一次深度优先或广度优先搜索遍历可访问到该图的每个顶点。（ ）
28