北邮数据结构第六章答案详解 图（一）.pdfVIP

第六章 图 1、填空题 (1) n 个顶点的无向图，最多能有(__________)条边。 解析：完全图是边数最多的图，参考完全图的定义即可。 答案：n*(n-1)/2 (2) 有n 个顶点的连通无向图G 至少有(________)条边。 解析：生成树是连通图中边数最少的图，参考生成树的定义即可。 答案：n-1 (3) 有n 个顶点的强连通有向图G 至少有(________)条弧。 答案：n (4) G 为无向图，如果从G 的某个顶点出发，进行一次广度优先遍历，即可访问图的每 个顶点，则该图一定是(_______)图。 解析：若一次遍历能访问所有的结点，说明各个结点之间都可达。 答案：连通 (5) 若采用邻接矩阵结构存储具有n 个顶点的图，则对该图进行广度优先遍历的算法时 间复杂度为______ 。 解析：广度优先遍历需要遍历n 个结点，对于每一个结点需要遍历邻接矩阵的一行以找 2 出该结点的所有连接点，即循环n 次，因此，总的时间复杂度是O(n ) 。 2 答案：O(n ) (6) n 个顶点的连通图的生成树有(______)条边。 答案：n-1 (7) 图的深度优先遍历类似于树的(______)遍历；图的广度优先遍历类似于树的(______) 遍历。 答案：前序 层序 (8) 对于含有n 个顶点e 条边的连通图，得用Prim 算法求最小生成树的时间复杂度为 (______) 。 2 答案：O(n ) (9) 已知无向图G 的顶点数为n ，边数为e，其邻接表表示的空间复杂度为(______) 。 答案：O(n+e) (10) 一棵具有n 个顶点的生成树有且仅有(______)条边。 答案：n-1 2、 单选题 (1) 在一个无向图中，所有顶点的度数之和等于所有边数的( )倍 A.1/2 B.1 C.2 D.4 解析：顶点的度指的是与该顶点相连的边数，每一条边和两个顶点相连，因此该条边被 相邻的两个顶点各计算1 次，因此图的总度数是边数的两倍。 答案：C (2) 在一个具有n 个顶点的有向图中，若所有顶点的出度数之和为S，则所有顶点的度 数之和为( ) 。 A.S B.S-1 C.S+1 D.2S 答案：A (3) 具有n 个顶点的有向图最多有( )条边。 A.n B.n(n—1) C.n(n+1) D.n2 答案：B (4) 含n 个顶点的连通图中任意一条简单路径，其长度不可能超过( ) A. 1 B. n/2 C.n-1 D.n 解析：若超过n-1，则路径中必存在重复的顶点 答案：C (5) 若一个图中包含有k 个连通分量，若按照深度优先有哪些信誉好的足球投注网站的方法访问所有顶点，则必 须调用( )次深度优先有哪些信誉好的足球投注网站遍历的算法。 A.k B.1 C.k-1 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,3 B.1,2,3,4,5 C.1,2,5,3,4 D.1,4,3,2,5 。 解析：根据图的边集信息可得如图6-5 所示的有向图，因此从1 点开始遍历的顺序可以 为1、2 、5、4、3