建设工程相关合同管理概述

图练习图练习1一、选择题1.一个有n个顶点的无向图最多有（ ）条边。 A.nB.n(n-1)C.n(n-1)/2D.2nC一、选择题C22.具有6个顶点的无向图至少应有（ ）条边才能确保是一个连通图。 A.5B.6C.7D.8

AA33.具有n个顶点且每一对不同的顶点之间都有一条边的图被称为（ ） A.线性图 B.无向完全图 C.无向图 D.简单图BB44.具有4个顶点的无向完全图有（ ）条边。 A.6B.12C.16D.20A4.具有4个顶点的无向完全图有（ ）条边。A55.G是一个非连通无向图，共有28条边，则该图至少有（ ）个顶点。 A.6B.7C.8D.9D5.G是一个非连通无向图，共有28条边，则该图至少有（ ）个66.存储稀疏图的数据结构常用的是（ ） A.链接矩阵 B.三元组 C.链接表 D.十字链表CC77.对一个具有n个顶点的图，采用链接矩阵表示则该矩阵的大小为（ ） A.n B.(n-1)2

C.(n+1)2 D.n2DD88.设连通图G的顶点数为n，则G的生成树的边数为（ ） A.n-1B.nC.2nD.2n-1A8.设连通图G的顶点数为n，则G的生成树的边数为（ ）A99.N个顶点的无向图的链接表中结点总数最多有（ ）个。 A.2nB.nC.n/2D.n(n-1)DD1010.对于一个具有n个顶点和e条边的无向图，若采用链接表表示，则表向量的大小为（），所有顶点链接表的结点总数为（）。A.n B.n+1 C.n-1 D.2nE.e/2 F.e G.2e H.n+eAGAG1111.从链接矩阵可以看出，该图共有（ ）个顶点。如果是有向图，该图共有（ ）条弧；如果是有向图，则共有（ ）条边。A.9 B.3 C.6 D.1E.5 F.4 G.2 H.0BFGBFG1212.在有向图的链接表存储结构中，顶点V在表结点中出现的次数是（） A.顶点v的度 B.顶点v的出度 C.顶点v的入度 D.依附于顶点v的边CC1313.在用链接表表示图的情况下，建立图的算法的时间复杂度为（ ） A.O(n+e) B.O(n2) C.O(n*e) D.O(n3)A13.在用链接表表示图的情况下，建立图的算法的时间复杂度为1414.用DFS遍历一个无环有向图，并在DFS算法退栈返回时，打印出相应的顶点，则输出的顶点序列是（ ）。A.逆拓扑有序的B.拓扑有序的C.无序的A14.用DFS遍历一个无环有向图，并在DFS算法退栈返回时1515.已知一个图如图7-13所示，若从顶点a出发按深度优先搜索法进行遍历，则可能得到的是一种顶点序列为（ ）；按广度优先搜索法进行遍历，则可能得到的一种顶点序列为（ ）。 (1)

A.abecdfB.acfebdC.acebfdD.acfdeb (2)A.abcedfB.abcefdC.abedfcD.acfdebDBabcedf图7-1315.已知一个图如图7-13所示，若从顶点a出发按深度优先搜1616.采用链接矩阵时，遍历图时的顶点所需时间为（ ），采用链接表时，遍历图的顶点所需时间为（ ）（注：设图有n个顶点，e条边） A.O(n) B.O(n2)C.O(e) D.O(n*e) E.O(n+e)

BE16.采用链接矩阵时，遍历图时的顶点所需时间为（ ），采用1717.采用链接表存储的图的深度优先搜索遍历算法类似于二叉树的（ ）A.中序遍历 B.先序遍历C.后序遍历 D.按层遍历B17.采用链接表存储的图的深度优先搜索遍历算法类似于二叉树1818.采用链接表存储的图的广度优先搜索遍历算法类似于二叉树的（ ）A.中序遍历 B.先序遍历C.后序遍历 D.按层遍历D18.采用链接表存储的图的广度优先搜索遍历算法类似于二叉树1919.已知一有向图的链接表存储结构如图7-14（见下页）所示。（1）根据有向图的深度优先搜索遍历算法，从顶点V1出发，所得到的顶点序列是（ ）。 A.v1,v2,v3,v5,v4B.v1,v2,v3,v4,v5C.v1,v2,v3,v5,v4D.v1,v4,v3,v5,v2（2）根据有向图的广度优先搜索遍历算法，从顶点V1出发，所得到的顶点序列是（ ）。A.v1,v2,v3,v5,v4B.v1,v3,v2,v4,v5C.v1,v2,v3,v5,v4D.v1,v4,v3,v5,v2CB19.已知一有向图的链接表存储结构如图7-14（见下页）所20v1v2^v3v4^v5213

^34

^13^01234图7-14v1213^34^13^0图7-12120.已知有8个顶点值为A，B，C，D，E，F，G，H的无向图，其邻接矩阵的存储结构如图7-15所示（见下页）。由此结构，从A顶点开始深度优先搜索遍历，得到的顶点序列是（ ）。

A.ABCDGHFEB.ABCDGFHEC.ABGHFECDD.ABFHEGDC

E.ABEHFGDCF.ABEHGFCDB20.已知有8个顶点值为A，B，C，D，E，F，G，H的无22

A

B

C

D

E

F

G

H

A01010000

B10101110

C01010000

D10100010

E01000001

F01000011

G01010101

H00001110图7-15

ABCDEFGHA02321.已知一个图如图7-16（见下页）所示，在该图的最小生成树中各条边上权值之和为（ ），在该图的最小生成树中，从顶点V1到顶点V6的路径为（ ）

A.31 B.38C.36 D.43E.v1,v3.v6 F.v1,v4,v6G.v1,v5,v4,v6 H.v1,v4,v3,v6CG21.已知一个图如图7-16（见下页）所示，在该图的最小生24图7-1631254612152010988645图7-16312546121520109886452522.已知一个图如图7-17所示，则依据迪杰斯特拉算法将按照（ ）顶点次序依次求出从顶点V1到其余各顶点的最短路径。A.v2,v5,v4,v6,v3B.v2,v5,v4,v3,v6C.v2,v3,v5,v4,v1D.v5,v4,v6,v3,v2B图7-17312546312756151022.已知一个图如图7-17所示，则依据迪杰斯特拉算法将按2623.在一个有n个顶点的无向网中，有 条边，则应该选用( )算法来求这个网的最小生成树，从而使计算时间较少。A.PrimB.KruskalB23.在一个有n个顶点的无向网中，有2724.关键路径是事件结点网络中的（）A.从源点到汇点的最长路径B.从源点到汇点的最短路径C.最长回路D.最短回路A24.关键路径是事件结点网络中的（）A2825.正确的AOE网而言，必须是（ ），AOE中，某边权值应当是（ ）权值为零的边表示（ ）（1） A.完全图 B.哈密尔顿图 C.无环图 D.强连通图（2） A.实数 B正整数 C.正数 D.非负数（3） A.为决策而增加的活动 B.为计算方便而增加的活动 C.表示活动间的时间顺序关系 D.该活动为关键活动CDB25.正确的AOE网而言，必须是（ ），AOE中，某边权2926.当各边上权值（ ）时，BFS算法可以用解决单源点最短路径的问题。A.均相等

B.均不相等

C.不一定相等

A26.当各边上权值（ ）时，BFS算法可以用解决单源点最短3027.已知一个图如图7-18所示，则由该图得到的一种拓扑序列为（ ）A.v1,v4,v6,v2,v5,v3B.v1,v2,v3,v4,v5,v6 C.v1,v4,v2,v3,v6,v5D.v1,v2,v4,v6,v3,v5

A图7-1831254627.已知一个图如图7-18所示，则由该图得到的一种拓扑序列3128.判断一个有向图是否存在回路，除了可以利用拓扑排序方法外，还可以利用（ ）。A.求关键路径的方法B.求最短路径的Dijksra方法C.深度优先搜索遍历算法D.广度优先搜索遍历算法C28.判断一个有向图是否存在回路，除了可以利用拓扑排序方法3229.下面结论中正确的是（ ）A.在无向图中，边的条数是结点度数之和。B.在图结构中，结点可以没有任何前趋和后继.。C.在n个结点的无向图中，若边数大于n-1，则该图必是连通图。D.图的链接矩阵必定是对称矩阵B29.下面结论中正确的是（ ）B3330.下面结论中正确的是（ ）A.若有向图的链接矩阵中对角线以下元素均为零，则该图的拓扑排序必定存在B.网络的最小代价生成树是惟一的C.在拓扑排序序列中，任意两个相继结点vi和vj都存在从vi到vj的路径D.在有向图中，从一个结点到另一个结点的最短路径是惟一的

A30.下面结论中正确的是（ ）A3431.下面结论中不正确的是（ ） A.

无向图的连通分量是该图的极大连通子图 B.

有向图用链接矩阵表示，容易实现求结点度数的操作。 C.

无向图用邻接矩阵表示，图中的边数等于邻接矩阵元素之和的一半 D.

有向图的邻接矩阵必定不是对称矩阵D31.下面结论中不正确的是（ ）D3532.下面结论中正确的是（ ） A.

按深度优先搜索遍历图时，与始点相连的结点先于不在始点相连的结点访问。 B.

一个图按深度优先搜索法遍历的结果是唯一的。 C.

若有向图G中包含一个环，则G的结点间不存在在拓扑序列。 D.

图的拓扑排序序列是唯一的。C32.下面结论中正确的是（ ）C3633.下面结论中不正确的是（ ） A．

按广度优先搜索遍历图时，与始点相连的结点先于不于始点相连的结点访问。 B．

一个图按广度优先搜索法遍历的结果是唯一的。 C．无向图的链接表表示法中，表中结点的数目是图中边的条数2倍。 D．图的多重链接表表示法中，表中结点的数目是图中边的条数。B33.下面结论中不正确的是（ ）B3734.下面结论中正确的是（ ） A.在无向图中，边的条数是结点度数之和。 B．

用Prim算法和Kruskal算法求得的图最小生成树相同。 C．

在图的连接多重表表示中，任意一条边，只用一个表目表示。 D．在拓扑排序序列中，任意两个相距结点Vi和Vj之间都存在一条路径。C34.下面结论中正确的是（ ）C38二、填空题1.N个顶点的连通图至少_____条边。

n-1二、填空题n-1392.一个无向图有n个顶点和e条边，则所有顶点的度数之和即Σdi（di表示顶点I的度）=_____。

2e2e403.在图形结构中，每个结点的前趋结点数和后续结点数可以_______________。

任意多个任意多个414.若无向图G的顶点度数的最小值大于或等于____时，G至少有一条回路。

2

4.若无向图G的顶点度数的最小值大于或等于____时，G至少425.设无向图G的顶点数为n,图G最少有_____边，最多有_________条边，若G为有向图，有n个顶点，则图G最少______条边，最多有_________条边。具有n个顶点的无向完全图，边的总数为_____________条，而具有n个顶点的有向完全图中，边数有__________条。

0n(n-1)/20n(n-1)n(n-1)/2n(n-1)5.设无向图G的顶点数为n,图G最少有_____边，最多有436.在无权图G的链接矩阵A中，若（Vi,Vj）或<Vi,Vj>属于图G的边集合，则对应元素A[i][j]等于_____，否则等于_____。

1010447.在无向图G的链接矩阵A中，若A[i][j]等于1，则A[j][i]等于_____。

1

1458.已知一个图的链接矩阵表示，计算第i个结点的入度的方法是_____。

求矩阵第i列非零元素之和求矩阵第i列非零元素之和469.在一个图G的链接表表示中，每个顶点的链接表中所含的结点数，对于有向图而言等于该顶点的_____，而对于无向图而言等于该顶点的_____。

出度数度数出度数度数4710.假定一个无向图，有n个顶点e条边，则在链接矩阵表示中，求任一个顶点度数的时间复杂度为_____；用链接表表示中，访问一个顶点的所有链接点的时间复杂度为________。

O(n)O(e*n)O(n)O(e*n)4811.已知图G的链接表如图7-19(见下页)所示，其从顶点V1出发的深度优先搜索序列为___________________________，其从顶点V1出发的广度优先搜索序列为________________________________。

v1,v2,v3,v6,v5,v4v1,v2,v5,v4,v3,v6

v1,v2,v3,v6,v5,v4v1,v2,v5,v4,v49图7-19v1v2v3v4^v5v6^143

^24^0123455

^352

^图7-19v1143^24^055012.设图G有n个顶点和e条边，以链接表作存储结构时，进行深度优先搜索遍历的时间复杂度为_________；以链接矩阵作存储结构时，进行广度优先搜索遍历的时间复杂度为_____。

O(n+e)

O(n2)

O(n+e)O(n2)5113.对用链接矩阵表示的图进行深度优先或广度优先搜索遍历的时间复杂度为_____，对用链接表表示的图进行深度优先或广度优先搜索遍历时是时间复杂度为_________，图的深度优先或广度优先搜索遍历的空间复杂度为_____。

O(n+e)

O(n2)

O(n)

O(n+e)O(n2)O(n)5214.n个顶点的弱连通有向图G，最多有________条边，最少有_____条边。

n(n-1)n-1n(n-1)n-15315.在n个顶点、e条