(严蔚敏)第7章图习题答案.ppt

第7章图习题答案,一、单项选择题（）1.有8个结点的无向图最多有条边。A14B.28C.56D.112（）2.有8个结点的连通图最少有条边。A5B.6C.7D.8,B,C,（）3.无向图的邻接矩阵是一个。A.对称矩阵B.零矩阵C.上三角矩阵D.对角矩阵（）4.一个带权的无向连通图的最小生成树。A有一棵或多棵B只有一棵C一定有多棵D可能不存在,A,A,（）5如果无向图G必须进行二次广度优先搜索才能访问其所有顶点，则下列说法中不正确的是。AG不是完全图BG不是连通图CG中一定有回路DG有2个连通分量,C,()6.从V1出发，对题10图按广度优先搜索遍历，则可能得到的一种顶点序列为。A.V1,V2,V3,V5,V4,V6B.V1,V2,V3,V5,V6,V4C.V1,V5,V2,V3,V6,V4D.V1,V3,V6,V4,V5,V2,B,（）7.设图的邻接表如下图所示，则该图的边的数目是。A.4B.5C.10D.20,B,（）8.下列说法中不正确的是A.无向图的极大连通子图称为连通分量B.连通图的广度优先搜索中一般要采用队列来暂存刚访问过的顶点C.连通图的深度优先搜索中一般要采用栈来暂存刚访问过的顶点D.有向图的遍历不可采用广度优先搜索算法,D,二、填空题1.若图的邻接矩阵是一个对称矩阵，则该图一定是一个。2.设有稠密(边较多)图G,则G采用存储结构较省空间。设有稀疏(边较少)图G，则G采用存储结构较省空间。3.一个有向图G中若有弧、和，则在图G的拓扑序列中，顶点Vi，Vj和Vk的相对位置为。,无向图,邻接矩阵,邻接表,Vi，Vj，Vk,4.用Dijkstra算法求某一顶点到其余各顶点间的最短路径是按路径长度的次序来得到最短路径的。,递增,三、应用题1.画出以下无向图的邻接矩阵，并写出每个顶点的度。,V1,V2,V4,V5,V3,解:A=,TD(V1)=2,TD(V2)=3,TD(V3)=2,TD(V4)=3,TD(V4)=2。,2.画出以下有向图的邻接矩阵，并写出每个顶点的入度、出度。,V1,V2,V4,V5,V3,解:A=,ID(V1)=0,OD(V2)=3；ID(V2)=3,OD(V2)=0；ID(V3)=3,OD(V3)=0；ID(V4)=1,OD(V4)=2；ID(V5)=0,OD(V5)=2；,3.对应下图，写出从V1出发的深度优先查找遍历和广度优先查找遍历的所有结果。,V1,V2,V4,V5,V3,解：(1)深度优先查找遍历和广度优先查找遍历均有以下顶点访问序列：123451243513245134251423514325(2)深度优先查找遍历还有以下顶点访问序列：1352413542,4.求下图的连通分量。,V6,V7,V3,V4,V5,V1,V2,解：有以下2个连通分量,V6,V7,V3,V4,V5,V1,V2,5.求下列连通图的最小生成树。,1,2,4,5,3,2,3,2,2,3,1,1,5,解：最小生成树为：,1,2,4,5,3,2,2,1,1,6.写出下图的拓扑排序序列。,1,2,4,5,6,3,解：拓扑排序的序列为：（3，1，4，5，2，6）,7.采用Dijkstra算法求图中从顶点a到其他各顶点间的最短路径及路径长度。,a,b,c,d,e,f,g,15,6,4,9,2,8,4,10,12,5,3,解：最短路径的终点的集合为：S=（a,c,f,e,d,g,b）,