资源描述：
《(严蔚敏)第7章图习题答案.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第7章图习题答案一、单项选择题（）1.有8个结点的无向图最多有条边。A．14B.28C.56D.112（）2.有8个结点的连通图最少有条边。A．5B.6C.7D.8BC（）3.无向图的邻接矩阵是一个。A.对称矩阵B.零矩阵C.上三角矩阵D.对角矩阵（）4.一个带权的无向连通图的最小生成树。A．有一棵或多棵B．只有一棵C．一定有多棵D．可能不存在AA（）5．如果无向图G必须进行二次广度优先搜索才能访问其所有顶点，则下列说法中不正确的是。A．G不是完全图B．G不是连通图C．G中一定有回路D．G有2个连通分量C()6.从V1出发，对题10图按广度
2、优先搜索遍历，则可能得到的一种顶点序列为。A.V1,V2,V3,V5,V4,V6B.V1,V2,V3,V5,V6,V4C.V1,V5,V2,V3,V6,V4D.V1,V3,V6,V4,V5,V2B（）7.设图的邻接表如下图所示，则该图的边的数目是。A.4B.5C.10D.20B（）8.下列说法中不正确的是A.无向图的极大连通子图称为连通分量B.连通图的广度优先搜索中一般要采用队列来暂存刚访问过的顶点C.连通图的深度优先搜索中一般要采用栈来暂存刚访问过的顶点D.有向图的遍历不可采用广度优先搜索算法D二、填空题1.若图的邻接矩阵是一个对称矩阵，
3、则该图一定是一个。2.设有稠密(边较多)图G,则G采用存储结构较省空间。设有稀疏(边较少)图G，则G采用存储结构较省空间。3.一个有向图G中若有弧、和，则在图G的拓扑序列中，顶点Vi，Vj和Vk的相对位置为。无向图邻接矩阵邻接表Vi，Vj，Vk4.用Dijkstra算法求某一顶点到其余各顶点间的最短路径是按路径长度的次序来得到最短路径的。递增三、应用题1.画出以下无向图的邻接矩阵，并写出每个顶点的度。V1V2V4V5V3解:A=0101010011000111110001100TD(V1)=2,TD
4、(V2)=3,TD(V3)=2,TD(V4)=3,TD(V4)=2。2.画出以下有向图的邻接矩阵，并写出每个顶点的入度、出度。V1V2V4V5V3解:A=0111000000000000110001100ID(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出发的深度优先查找遍历和广度优先查找遍历的所有结果。V1V2V4V5V3解：(1)深度优先查找遍历和广度优先查找遍历均有以下顶点访问序列：
5、①1→2→3→4→5②1→2→4→3→5③1→3→2→4→5④1→3→4→2→5⑤1→4→2→3→5⑥1→4→3→2→5(2)深度优先查找遍历还有以下顶点访问序列：①1→3→5→2→4②1→3→5→4→24.求下图的连通分量。V6V7V3V4V5V1V2解：有以下2个连通分量V6V7V3V4V5V1V25.求下列连通图的最小生成树。1245323223115解：最小生成树为：1245322116.写出下图的拓扑排序序列。124563解：拓扑排序的序列为： （3，1，4，5，2，6）7.采用Dijkstra算法求图中从顶点a到其他各顶点间的最
6、短路径及路径长度。abcdefg15649284101253解：最短路径的终点的集合为：S=（a,c,f,e,d,g,b）始点终点最短路径路径长度ac(a,c)2f(a,c,f)6e(a,c,e)10d(a,c,f,d)11g(a,c,f,d,g)14b(a,b)15
