数据结构第六章图练习题详细解析

数据构造第六章图练习题及答案详尽分析(精髓版)数据构造第六章图练习题及答案详尽分析(精髓版)数据构造第六章图练习题及答案详尽分析(精髓版)图1.填空题⑴设无向图G中极点数为n，那么图G起码有〔〕条边，至多有〔〕条边；假定条边，至多有〔〕条边。【解答】0，n(n-1)/2，0，n(n-1)

G为有向图，那么起码有〔

〕【剖析】图的极点会合是有穷非空的，而边集能够是空集；边数抵达最多的图称为完整图，在完整图中，随意两个极点之间都存在边。⑵任何连通图的连通重量只有一个，即是〔〕。【解答】其自己⑶图的储存构造主要有两种，分别是〔〕和〔〕。【解答】毗邻矩阵，毗邻表【剖析】这是最常用的两种储存构造，别的，还有十字链表、毗邻多重表、边集数组等。⑷无向图G的极点数为n，边数为e，其毗邻表表示的空间复杂度为〔〕。【解答】Ｏ(n+e)【剖析】在无向图的毗邻表中，极点表有n个结点，边表有2e个结点，共有为Ｏ(n+2e)=Ｏ(n+e)。⑸一个有向图的毗邻矩阵表示，计算第j个极点的入度的方法是〔〕。【解答】求第j列的所有元素之和

n+2e个结点，其空间复杂度⑹有向图G用毗邻矩阵

A[n][n]

储存，其第

i行的所有元素之和等于极点

i

的〔〕。【解答】出度⑺图的深度优先遍历近似于树的〔的〔〕遍历，它所用到的数据构造是〔

〕遍历，它所用到的数据构造是〔〕。

〕；图的广度优先遍历近似于树【解答】前序，栈，层序，行列⑻对于含有n个极点e条边的连通图，利用Prim算法求最小生成树的时间复杂度为〔算法求最小生成树的时间复杂度为〔〕。【解答】Ｏ(n2)，Ｏ(elog2e)【剖析】Prim算法采纳毗邻矩阵做储存构造，合适于求浓密图的最小生成树；Kruskal做储存构造，合适于求稀少图的最小生成树。

〕，利用Kruskal算法采纳边集数组⑼假如一个有向图不存在〔〕，那么该图的所有极点能够摆列成一个拓扑序列。【解答】回路⑽在一个有向图中，假定存在弧、、，那么在其拓扑序列中，极点【解答】vi,vj,vk【剖析】对由极点vi,vj,vk构成的图进行拓扑排序。

vi,vj,vk

的相对序次为〔

〕。2.选择题⑴在一个无向图中，所有极点的度数之和等于所有边数的〔

〕倍。A1/2B1C2D4【解答】C【剖析】设无向图中含有

n个极点

e条边，那么

。⑵

n

个极点的强连通图起码有〔

〕条边，其形状是〔

〕。AnBn+1Cn-1Dn

×(n-1)E无回路

F有回路

G环状

H树状【解答】

A，G⑶含

n

个极点的连通图中的随意一条简单路径，其长度不行能超出〔

〕。A1Bn/2Cn-1Dn【解答】C【剖析】假定超出n-1，那么路径中必存在重复的极点。⑷对于一个拥有n个极点的无向图，假定采纳毗邻矩阵储存，那么该矩阵的大小是〔〕。AnB(n-1)2Cn-1Dn2【解答】D⑸图的生成树〔〕，n个极点的生成树有〔〕条边。A独一B不独一C独一性不可以确立DnEn+1Fn-1【解答】C，F⑹设无向图G=(V,E)和G'=(V',E')，假如G'是G的生成树，那么下边的说法中错误的选项是〔〕。AG'为G的子图BG'为G的连通重量CG'为G的极小连通子图且V=V'DG'是G的一个无环子图【解答】B【剖析】连通重量是无向图的极大连通子图，此中极大的含义是将依赖于连通重量中极点的所有边都加上，所以，连通重量中可能存在回路。⑺G是一个非连通无向图，共有28条边，那么该图起码有〔〕个极点。A6B7C8D9【解答】D【剖析】n个极点的无向图中，边数e≤n(n-1)/2，将e=28代入，有n≥8，现无向图非连通，那么n=9。⑻最小生成树指的是〔〕。由连通网所获得的边数最少的生成树由连通网所获得的极点数相对较少的生成树连通网中所有生成树中权值之和为最小的生成树连通网的极小连通子图【解答】C⑼判断一个有向图能否存在回路除了能够利用拓扑排序方法外，还能够用〔〕。A求重点路径的方法B求最短路径的方法C广度优先遍历算法D深度优先遍历算法【解答】D【剖析】当有向图中无回路时，从某极点出发进行深度优先遍历时，出栈的次序〔退出即为逆向的拓扑序列。

DFSTraverse

算法〕⑽下边对于工程方案的AOE网的表达中，不正确的选项是〔工程的达成时间

〕?br/>A

重点活动不如期达成就会影响整个任何一个重点活动提早达成，那么整个工程将会提早达成所有的重点活动都提早达成，那么整个工程将会提早达成某些重点活动假定提早达成，那么整个工程将会提早完【解答】B【剖析】AOE网中的重点路径可能不只一条，假如某一个重点活动提早达成，还不可以提早整个工程，而一定同时提升在几条重点路径上的重点活动。判断题⑴一个有向图的毗邻表和逆毗邻表中的结点个数必定相等。【解答】对。毗邻表和逆毗邻表的差别仅在于出边和入边，边表中的结点个数都等于有向图中边的个数。⑵用毗邻矩阵储存图，所占用的储存空间大小只与图中极点个数相关，而与图的边数没关。【解答】对。毗邻矩阵的空间复杂度为Ｏ(n2)，与边的个数没关。⑶图G的生成树是该图的一个极小连通子图【解答】错。一定包括所有极点。⑷无向的接矩必定是称的，有向的接矩必定是不称的【解答】。有向的接矩不必定称，比若有向完整的接矩就是称的。⑸随意一个，从某点出行一次深度先或广度先遍，可的所有点。【解答】。只有通从某点出行一次遍，可的所有点。⑹在一个有向的拓扑序列中，假定点【解答】。只好明从点a到点

a在点b以前，中必有一条弧。b有一条路径。⑺假定一个有向的接矩中角以下元素均零，的拓扑序列必然存在。【解答】。参第11的明。⑻在AOE网中必定只有一条关路径?br/>【解答】。AOE网中可能有不只一条关路径，他的路径度同样4．n个点的无向，采纳接表存，回复以下?br/>⑴中有多少条？⑵随意两个点i和j能否有相？⑶随意一个点的度是多少?br/>【解答】⑴表中的点个数之和除以2。⑵第i个表中能否含有点j。⑶点所的表中所含点个数。5．n个点的无向，采纳接矩存，回复以下：⑴中有多少条？⑵随意两个点i和j能否有相？⑶随意一个点的度是多少？【解答】⑴接矩中非零元素个数的和除以2。⑵当接矩A中A[i][j]=1〔或A[j][i]=1〕，表示两点之有相。⑶算接矩上点对应的行上非零元素的个数。6．明：生成中最路径的起点和点的度均１。【解答】用反法明。v1,v2,⋯,vk是生成的一条最路径，此中，v1起点，vk点。假定vk的度2，取vk的另一个接点v，因为生成中无回路，所以，v在最路径上，然v1,v2,⋯,vk,v的路径最，与假矛盾。所以生成中最路径的点的度1。同理可起点v1的度不可以大于1，只好1。7．一个通如6-6所示，出的接矩和接表存表示，假定从点v1出行遍，分出一个按深度先遍和广度先遍的点序列。【解答】毗邻矩阵表示以下：深度优先遍历序列为：

v1v2v3v5v4v6广度优先遍历序列为：

v1v2v4v6v3v5毗邻表表示以下：8．图6-7所示是一个无向带权图，请分别按Prim算法和Kruskal算法求最小生成树。【解答】按Prim算法求最小生成树的过程以下：按Kruskal算法求最小生成树的过程以下：9．对于图6-8所示的带权有向图，求从源点v1到其余各极点的最短路径。【解答】从源点v1到其余各极点的最短路径以下表所示。源点终点最短路径最短路径长度v1v7v1v77v1v5v1v511v1v4v1v7v413v1v6v1v7v4v616v1v2v1v7v222v1v3v1v7v4v6v32510．如图6-9所示的有向网图，利用Dijkstra算法求从极点v1到其余各极点的最短路径。【解答】从源点v1到其余各点的最短路径以下表所示。源点点最短路径最短路径度v1v3v1v315v1v5v1v515v1v2v1v3v225v1v6v1v3v2v640v1v4v1v3v2v44511．明：只需合适地摆列点的序次，就能使有向无的接矩中主角以下的元素所有0。【解答】随意n个点的有向无都能够获得一个拓扑序列。拓扑序列v0v1v2⋯vn-1，我来明此的接矩A上三角矩。明采纳反法。假此的接矩不是上三角矩，那么，存在下i和j〔i>j〕，使得A[i][j]不等于零，即中存在从vi到vj的一条有向。由拓扑序列的定可知，在随意拓扑序列中，vi的地点必定在vj以前，而在上述拓扑序列v0v1v2⋯vn-1中，因为i>j，即vi的地点在vj以后，致矛盾。所以命正确。12.算法⑴算法，将一个无向的接矩接表。【解答】先置一个空的接表，而后在接矩上找不零的元素，找到后在接表的表中插入相的表点。接矩存构定以下：constintMaxSize=10;templatestructAdjMatrix{Tvertex[MaxSize];//寄存中点的数intarc[MaxSize][MaxSize];//intvertexNum,arcNum;//

寄存中的数的点数和数};接表存构定以下：constintMaxSize=10;structArcNode//定表点{intadjvex;//接点域ArcNode*next;};templatestructVertexNode//定点表点{Tvertex;ArcNode*firstedge;};structAdjList{VertexNodeadjlist[MaxSize];intvertexNum,arcNum;//图的极点数和边数};详细算法以下：⑵设计算法，将一个无向图的毗邻表变换成毗邻矩阵。【解答】在毗邻表上次序地取每个边表中的结点，将毗邻矩阵中对应单元的值置为1。毗邻矩阵和毗邻表的储存构造定义与上题同样。详细算法以下：⑶设计算法，计算图中出度为零的极点个数。【解答】在有向图的毗邻矩阵中，一行对应一个极点，每行的非零元素的个数等于对应极点的出度。所以，当某行非零元素的个数为零时，那么对应极点的出度为零。据此，从第一行开始，查找每行的非零元素个数能否为零，假定是那么计数器加1。详细算法以下：⑷以毗邻表作储存构造，设计按深度优先遍历图的非递归算法。【解答】拜见6.2.1。⑸一个有向图的毗邻表，编写算法成立其逆毗邻表。【解答】在有向图中，假定毗邻表中极点vi有毗邻点vj，在逆毗邻表中vj必定有毗邻点vi，由此获得本题算法思路：第一将逆毗邻表的表头结点firstedge域置空，而后逐行将表头结点的毗邻点进行转变。⑹分别鉴于深度优先搜寻和广度优先搜寻编写算法，判断以毗邻表储存的有向图中能否存在由极点vi到极点vj的路径〔i≠j〕。【解答】⑴鉴于深度优先遍历：⑵鉴于广度优先遍历：学习自测及答案1．某无向图的毗邻矩阵A=A3B6C9D以上答案均不正确

，能够看出，该图共有〔

〕个极点。【解答】

A2．无向图的毗邻矩阵是一个〔

〕，有向图的毗邻矩阵是一个〔

〕A上三角矩阵B下三角矩阵C对称矩阵D无规律【解答】C，D3．以下命题正确的选项是〔〕。一个图的毗邻矩阵表示是独一的，毗邻表表示也独一一个图的毗邻矩阵表示是独一的，毗邻表表示不独一一个图的毗邻矩阵表示不独一的，毗邻表表示是独一一个图的毗邻矩阵表示不独一的，毗邻表表示也不独一【解答】B4．十字链表合适储存〔

〕，毗邻多重表合适储存〔

〕。【解答】有向图，无向图5.在一个拥有

n个极点的有向完整图中包括有〔

〕条边：An(n-1)/2Bn(n-1)Cn(n+1)/2Dn2【解答】

B6．n个极点的连通图用毗邻矩阵表示时，该矩阵起码有〔

〕个非零元素。【解答】

2(n-1)7．表示一个有

100个极点，

1000条边的有向图的毗邻矩阵有〔

〕个非零矩阵元素。【解答】

10008．一个拥有

n个极点

k条边的无向图是一个丛林〔

n>k〕，那么该丛林中必有〔

〕棵树。Ak

Bn

Cn-k

D1【解答】

C9．用深度优先遍历方法遍历一个有向无环图，并在深度优先遍历算法中按退栈序次打印出相应的极点，那么输出的极点序列是〔〕。A逆拓扑有序B拓扑有序C无序D深度优先遍历序