数据结构第六章图练习题及详细解析(精华版).doc

(完好word版)数据构造第六章图练习题及答案详尽分析(精髓版) (完好word版)数据构造第六章图练习题及答案详尽分析(精髓版) PAGE / NUMPAGES (完好word版)数据构造第六章图练习题及答案详尽分析(精髓版) 图 填空题 ⑴ 设无向图 G 中极点数为 n ，则图 G 起码有（ ）条边，至多有（ ）条边；若 G 为有向图， 则起码有（ ） 条边，至多有（ ）条边。 【解答】 0， n(n-1)/2 ， 0， n(n-1) 【剖析】图的极点会合是有穷非空的，而边集能够是空集；边数达到最多的图称为完好图，在完好图中， 随意两个极点之间都存在边。 ⑵ 任何连通图的连通重量只有一个，即是（ ）。 【解答】其自己 ⑶ 图的储存构造主要有两种，分别是（ ）和（ ）。 【解答】毗邻矩阵，毗邻表 【剖析】这是最常用的两种储存构造，别的，还有十字链表、毗邻多重表、边集数组等。 ⑷ 已知无向图 G 的极点数为 n，边数为 【解答】Ｏ (n+e) 【剖析】在无向图的毗邻表中，极点表有 为Ｏ (n+2e)= Ｏ (n+e) 。 ⑸ 已知一个有向图的毗邻矩阵表示，计算第  e，其 毗邻表表示的空间复杂度为（ n 个结点，边表有 2e 个结点，共有 j 个极点的 入度的方法是（ ）。  ）。 n+2e  个结点，其空间复杂度 【解答】求第  j 列的所有元素之和 ⑹ 有向图 G 用毗邻矩阵  A[n][n] 储存，其第  i 行的所有元素之和等于极点  i 的（ ）。 【解答】出度 ⑺ 图的深度优先遍历近似于树的（ ）遍历，它所用到的数据构造是（ ）；图的广度优先遍历近似于树的 （ ）遍历，它所用到的数据构造是（ ）。 【解答】前序，栈，层序，行列 ⑻ 对于含有 n 个极点 e 条边的连通图，利用 Prim 算法求最小生成树的时间复杂度为（ ），利用 Kruskal 算法求最小生成树的时间复杂度为（ ）。 【解答】Ｏ (n2) ，Ｏ (elog2e) 【剖析】 Prim 算法采纳毗邻矩阵做储存构造，合适于求浓密图的最小生成树； Kruskal 算法采纳边集数组 做储存构造，合适于求稀少图的最小生成树。 ⑼ 假如一个有向图不存在（ ），则该图的所有极点能够摆列成一个拓扑序列。 【解答】回路 ⑽ 在一个有向图中，若存在弧、、，则在其拓扑序列中，极点 vi, vj, vk 的相对序次为（ ）。 【解答】 vi, vj, vk 【剖析】对由极点 vi, vj, vk 构成的图进行拓扑排序。 选择题 ⑴ 在一个无向图中，所有极点的度数之和等于所有边数的（ ）倍。 A1/2B1C2D4 【解答】 C 【剖析】设无向图中含有 n 个极点 e 条边，则 。 ⑵ n 个极点的 强连通图 起码有（ ）条边，其形状是（ ）。 A n B n+1 C n- 1 D n × (n-1) E无回路 F有回路 G环状 H树状 【解答】 A，G ⑶ 含 n 个极点的连通图中的随意一条简单路径，其长度不行能超出（ ）。 A 1 B n/2 C n-1 D n 【解答】 C 【剖析】若超出 n-1 ，则路径中必存在重复的极点。 ⑷ 对于一个拥有 n 个极点的无向图，若采纳毗邻矩阵储存，则该矩阵的大小是（ ）。 A n B (n-1)2 C n-1 D n2 【解答】 D ⑸ 图的生成树（ ）， n 个极点的生成树有（ ）条边。 A 独一 B 不独一 C 独一性不可以确立 D n E n +1 F n-1 【解答】 C， F ⑹ 设无向图 G=(V, E) 和 G =(V, E ) ，假如 G 是 G 的生成树，则下边的说法中错误的选项是（ ）。 AG 为 G的子图 BG 为 G的连通重量 C G 为 G 的极小连通子图且 V = V D G 是 G 的一个无环子图 【解答】 B 【剖析】连通重量是无向图的极大连通子图， 此中极大的含义是将依赖于连通重量中极点的所有边都加上， 所以，连通重量中可能存在回路。 ⑺ G 是一个非连通无向图，共有 28 条边，则该图起码有（ ）个极点。 A6B7C8D9 【解答】 D 【剖析】 n 个极点的无向图中，边数 e≤ n(n-1)/2 ，将 e=28 代入，有 n≥ 8，现已知无向图非连通，则 n=9 。 ⑻ 最小生成树指的是（ ） 。 由连通网所获得的边数最少的生成树 由连通网所获得的极点数相对较少的生成树 连通网中所有生成树中权值之和为最小的生成树 连通网的极小连通子图 【解答】 C ⑼ 判断一个有向图能否存在回路除了能够利用拓扑排序方法外，还能够用（ ）。 A 求重点路径的方法 B 求最短路径的方法 C 广度优先遍历算法 D 深度优先遍历算法 【解答】 D 【剖