《数据结构》-第七章

习题71选择题1、在一个图中，所有顶点的度数之和等于所有边数的（B）倍。A、1B、2C、3D、42、对于有N个顶点和E条边的有向图和无向图，若采用边集数组表示，则存于数组的边数为（D）条。A、N，NB、N，EC、2N，2ED、E，E3、对用邻接矩阵表示的图进行任一种遍历时，其时间复杂度为（A）。A、O（N2）B、O（E）C、O（N）D、O（NE）4、N个顶点的强连通图至少有（A）边。A、NB、N1C、N1D、NN15、在一个无向图中，所有顶点的度数之和等于所有边数的（B）倍；在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（C）倍。A、1/2B、2C、1D、472填空题1、设无向图G的顶点数为N，图G最少有（0）边；最多有（NN1/2）条边。若G为有向图，则图G最少有（0）边，最多有（NN1）边。具有N个顶点的无向完全图，边的总数为（NN1/2）；而具有N个项点的有向完全图，边的总数为（NN1）。2、在一个图G的邻接表表示中，每个顶点的邻接表中所含的结点数，对于有向图而言等于该顶点的（出度）；而对于无向图而言等于该顶点的（度）。3、采用邻接表存储的图的深度优先遍历算法类似于二叉树的（先根）遍历；广度优先遍历算法类似于二叉树的（按层）遍历。4、一个具有N个顶点的无向图中，要连通全部顶点至少需要（N1）条边；若是有向图，至少需要（N）条边。5、在无向图G的邻接矩阵A中，若AIJ1，则AJI（1）。73应用题1、对于下面所示的图（A）和（B），求出0341241230（A）（B）图720（1）每一个图的二元组表示，对于带权图，可将边的权写在该边的后面；答（A）图GAV,EV0,1,2,3,4E0,1,0,2,0,3,0,4,2,1,2,3,3,4（B）图GBV,EV0,1,2,3,4E,（2）在（A）中的每个顶点的度，以及每个顶点的所有邻接点和所有边；答0度为4；邻接点1，2，3，4；边0,1,0,2,0,3,0,41度为2；邻接点0，2；边0,1,1,22度为3；邻接点0，1，3；边0,2,1,2,3,23度为3；邻接点0，2，4；边0,3,3,2,3,44度为2；邻接点0，3；边0,4,3,4（3）在（B）中的每个顶点的入度、出度和度，以及每个顶点的所有入边和出边；答0入度2；出度2；度4；入边,；出边,1入度2；出度1；度3；入边,；出边2入度0；出度4；度4；入边无；出边,3入度2；出度1；度3；入边,；出边4入度2；出度0；度2；入边,；出边无（4）在（A）中从0到4的所有简单路径及相应路径长度；答（04）1，（034）2，（0234）3，（01234）4（5）在（B）中从0到4的所有简单路径及相应的带权路径长度；答（034）22、如图所示有向图，采用DIJKSTRA算法求出从顶点0到其它顶点的最短路径，并说明整个计算过程。图721解142350646614235064627（1）选4（2）选11423506462741423506462748（3）选4（4）选6142350646274814235064627486（5）选7（6）选8或选63、写出上图的一种拓扑序列，若在它的邻接表存储结构中，每个顶点邻接表中的边结点都是按照终点序号从大到小链接的，则按此给出惟一一种拓扑序列。解任意的拓扑序列为0312456惟一拓扑序列为01324564、对图722中所示图分别写出深度优先遍历和广度优先遍历的项点序列。如果确定图以邻接矩阵存储，则得到的遍历顶点序列是什么解深度优先遍历（A）0123402341（B）0134203412广度优先遍历（A）0123404321（B）0134203142邻接矩阵存储时深度优先遍历（A）01234（B）01342广度优先遍历（A）01234（B）013425、对图721中所示图分别用克鲁斯卡尔算法和普里姆算法（从顶点2开始）求出其最小生成树。解用克鲁斯卡尔算法142023002415253155324646112445666678用普里姆算法142350661462142350641462初始状态（1）选1,21，进行修改142350641462142350641462（2）选2,32，无需修改（3）选1,04，无需修改14235064141281423506414126（4）选2,54，进行修改（5）选4,51，进行修改（6）选4,66，结束142350641412674算法题（不做要求）1、在邻接表的存储结构上，实现图的深度优先搜索和广度优先搜索。（可做为上机实践题目）2、假定图采用邻接矩阵表示，编写出进行深度优先搜索遍历的非递归算法。3、根据下图，编写一个完整的程序实现下列功能（1）建立图的邻