资源描述：
《北邮数据结构第六章答案详解 图(1)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第六章图1、填空题(1)n个顶点的无向图，最多能有(__________)条边。解析：完全图是边数最多的图，参考完全图的定义即可。答案：n*(n-1)/2(2)有n个顶点的连通无向图G至少有(________)条边。解析：生成树是连通图中边数最少的图，参考生成树的定义即可。答案：n-1(3)有n个顶点的强连通有向图G至少有(________)条弧。答案：n(4)G为无向图，如果从G的某个顶点出发，进行一次广度优先遍历，即可访问图的每个顶点，则该图一定是(_______)图。解析：若一次遍历能访问所有的结
2、点，说明各个结点之间都可达。答案：连通(5)若采用邻接矩阵结构存储具有n个顶点的图，则对该图进行广度优先遍历的算法时间复杂度为______。解析：广度优先遍历需要遍历n个结点，对于每一个结点需要遍历邻接矩阵的一行以找2出该结点的所有连接点，即循环n次，因此，总的时间复杂度是O(n)。2答案：O(n)(6)n个顶点的连通图的生成树有(______)条边。答案：n-1(7)图的深度优先遍历类似于树的(______)遍历；图的广度优先遍历类似于树的(______)遍历。答案：前序层序(8)对于含有n个顶点e条
3、边的连通图，得用Prim算法求最小生成树的时间复杂度为(______)。2答案：O(n)(9)已知无向图G的顶点数为n，边数为e，其邻接表表示的空间复杂度为(______)。答案：O(n+e)(10)一棵具有n个顶点的生成树有且仅有(______)条边。答案：n-12、单选题(1)在一个无向图中，所有顶点的度数之和等于所有边数的()倍A.1/2B.1C.2D.4解析：顶点的度指的是与该顶点相连的边数，每一条边和两个顶点相连，因此该条边被相邻的两个顶点各计算1次，因此图的总度数是边数的两倍。答案：C(2)
4、在一个具有n个顶点的有向图中，若所有顶点的出度数之和为S，则所有顶点的度数之和为()。A.SB.S-1C.S+1D.2S答案：A(3)具有n个顶点的有向图最多有()条边。A.nB.n(n—1)C.n(n+1)D.n2答案：B(4)含n个顶点的连通图中任意一条简单路径，其长度不可能超过()A.1B.n/2C.n-1D.n解析：若超过n-1，则路径中必存在重复的顶点答案：C(5)若一个图中包含有k个连通分量，若按照深度优先搜索的方法访问所有顶点，则必须调用()次深度优先搜索遍历的算法。A.kB.1C.k-1
5、D.k+1解析：一次深度优先搜索可以访问一个连通分量中的所有结点，因此k个连通分量需要调用k次深度优先遍历算法。答案：A(6)若一个图的边集为{<1,2>,<1,4>,<2,5>,<3,1>,<3,5>,<4,3>},则从顶点1开始对该图进行深度优先遍历，得到的顶点序列可能为()。A.1,2,5,4,3B.1,2,3,4,5C.1,2,5,3,4D.1,4,3,2,5。解析：根据图的边集信息可得如图6-5所示的有向图，因此从1点开始遍历的顺序可以为1、2、5、4、3。14253图6-5构造有向图答案：A
6、(7)若一个图的边集为{(A,B),(A,C),(B,D),(C,F),(D,E),(D,F)}，则从顶点A开始对该图进行广度优先遍历，得到的顶点序列可能是()。A.A,B,C,D,E,FB.A,B,C,F,D,EC.A,B,D,C,E,FD.A,B,C,D,F,E解析：根据图的边集信息可得如图6-6所示的无向图，从A点开始广度遍历则为A、B、C、D、E、F。BDAECF图6-6构造无向图答案：A(8)存储无向图的邻接矩阵是()，存储有向图的邻接矩阵是()。A.对称的B.非对称的答案：AB(9)采用邻接
7、表存储的图的广度优先遍历算法类似于二叉树的()。A.先序遍历B.中序遍历C.后序遍历D.按层遍历。答案：D(10)设有一个无向图G=(V,E)和G'=(V',E')如果G'为G的生成树，则下面不正确的说法是()A.G'为G的子图B.G'为G的连通分量C.G'为G的极小连通子图且V'=VD.G'为G的一个无环子图解析：连通分量的定义是极大连通子图，即该子图包含所有的顶点和与这些顶点相连的所有的边。生成树的定义是极小连通子图，是子图的一种，并且本书所有的图均是无环图，因此A、C、D是正确的。答案：B3、画出
8、图6-7所示的无向图G的邻接表（顶点按照ASCII排列），并根据所得邻接表给出从A点开始的深度优先和广度优先搜索遍历该图所的顶点序列。BCDAGEHF图6-7无向图G答案：邻接表如下图所示：0A171B02672C1363D2464E3565F4676G1234577H0156深度优先：ABCDEFGH广度优先：ABHCGFDE4、分别使用普里姆算法和克鲁斯卡尔算法构造出如图6-8所示图G的一棵最小生成树1651552433642566图6
