《数据结构单元8练习参考答案.doc》由会员分享,可在线阅读,更多相关《数据结构单元8练习参考答案.doc(12页珍藏版)》请在金锄头文库上搜索。
1、单元练习8一判断题(下列各题,正确的请在前面的括号内打;错误的打 )()(1)图可以没有边,但不能没有顶点。()(2)在无向图中,(V1,V2)与(V2,V1)是两条不同的边。()(3)邻接表只能用于有向图的存储。()(4)一个图的邻接矩阵表示是唯一的。()(5)用邻接矩阵法存储一个图时,所占用的存储空间大小与图中顶点个数无关,而只与图的边数有关。()(6)有向图不能进行广度优先遍历。()(7)若一个无向图的以顶点V1为起点进行深度优先遍历,所得的遍历序列唯一,则可以唯一确定该图。()(8)存储无向图的邻接矩阵是对称的,因此只要存储邻接矩阵的上三角(或下三角)部分就可以了。()(9)用邻接表法
2、存储图时,占用的存储空间大小只与图中的边数有关,而与结点的个数无关。()(10)若一个无向图中任一顶点出发,进行一次深度优先遍历,就可以访问图中所有的顶点,则该图一定是连通的。二填空题(1) 图常用的存储方式有邻接矩阵和 邻接表 等。(2) 图的遍历有: 深度优先搜 和广度优先搜等方法。(3) 有n条边的无向图邻接矩阵中,1的个数是 _2n_。(4) 有向图的边也称为 _ 弧_ 。(5) 图的邻接矩阵表示法是表示 _顶点_之间相邻关系的矩阵。(6) 有向图G用邻接矩阵存储,其第i行的所有元素之和等于顶点i的 _出度_。(7) n个顶点e条边的图若采用邻接矩阵存储,则空间复杂度为: O(n2)
3、。(8) n个顶点e条边的图若采用邻接表存储,则空间复杂度为: O(n+e) 。(9) 设有一稀疏图G,则G采用 _邻接表_存储比较节省空间。(10) 设有一稠密图G,则G采用 _邻接矩阵_存储比较节省空间。(11) 图的逆邻接表存储结构只适用于 _有向_图。(12) n个顶点的完全无向图有 n(n-1)/2_ 条边。(13) 有向图的邻接表表示适于求顶点的 出度 。(14) 有向图的邻接矩阵表示中,第i列上非0元素的个数为顶点Vi的 入度 。(15) 对于具有n个顶点的图,其生成树有且仅有 n-1 条边。(16) 对n个顶点,e条弧的有向图,其邻接表表示中,需要 n+e 个结点。(17) 从
4、图中某一顶点出发,访遍图中其余顶点,且使每一顶点仅被访问一次,称这一过程为图的 遍历 。(18) 无向图的邻接矩阵一定是 对称 矩阵。(19) 一个连通网的最小生成树是该图所有生成树中 权 最小的生成树。(20) 若要求一个稠密图G的最小生成树,最好用 Prim 算法来求解。三选择题(1)在一个图中,所有顶点的度数之和等于图的边数的( C )倍。 A1/2 B. 1 C. 2 D. 4(2)在一个有向图中,所有顶点的入度之和等于所有顶点的出度之和的( B )倍。 A1/2 B. 1 C. 2 D. 4(3)对于一个具有n个顶点的有向图的边数最多有( B )。 An Bn(n-1) Cn(n-1
5、)/2 D2n(4)在一个具有n个顶点的无向图中,要连通全部顶点至少需要( C )条边。 An Bn+1 C n-1 Dn/2(5)有8个结点的有向完全图有( C )条边。 A14 B. 28 C. 56 D. 112(6)深度优先遍历类似于二叉树的( A )。 A先序遍历 B中序遍历 C后序遍历 D层次遍历(7)广度优先遍历类似于二叉树的( D )。 A先序遍历 B中序遍历 C后序遍历 D层次遍历(8)任何一个无向连通图的最小生成树( A )。 A只有一棵 B一棵或多棵 C一定有多棵 D可能不存在(9)无向图顶点v的度是关联于该顶点( B )的数目。 A顶点 B边 C序号 D下标(10)有n
6、个顶点的无向图的邻接矩阵是用( B )数组存储。 A一维Bn行n列 C任意行n列 Dn行任意列(11)对于一个具有n个顶点和e条边的无向图,采用邻接表表示,则表头向量大小为( C )。 An-1Bn+1 Cn Dn+e(12)在图的表示法中,表示形式唯一的是( A )。 A邻接矩阵表示法 B邻接表表示法 C逆邻接表表示法 D邻接表和逆邻接表表示法(13)在一个具有n个顶点e条边的图中,所有顶点的度数之和等于( C )。 An Be C 2n D2e(14)下列图中,度为3的结点是( B )。12354 AV1 B. V2 C. V3 D. V412354(15)下列图是( A )。 A连通图
7、B. 强连通图 C. 生成树 D. 无环图(16)如下图所示,从顶点a出发,按深度优先进行遍历,则可能得到的一种顶点序列为( D )。abcfdeA a,b,e,c,d,fB a,c,f,e,b,dC. a,e,b,c,f,dD. a,e,d,f,c,b(17)如下图所示,从顶点a出发,按广度优先进行遍历,则可能得到的一种顶点序列为( A )。abcfdeA. a,b,e,c,d,fB. a,b,e,c,f,dC. a,e,b,c,f,dD. a,e,d,f,c,b(18)最小生成树的构造可使用( A )算法。 Aprim算法 B卡尔算法 C哈夫曼算法 D迪杰斯特拉算法(19)下面关于图的存储
8、结构的叙述中正确的是( A )。A 用邻接矩阵存储图,占用空间大小只与图中顶点数有关,而与边数无关B 用邻接矩阵存储图,占用空间大小只与图中边数有关,而与顶点数无关 C 用邻接表存储图,占用空间大小只与图中顶点数有关,而与边数无关 D 用邻接表存储图,占用空间大小只与图中边数有关,而与顶点数无关(20)连通分量是( C )的极大连通子图。 A树 B图 C无向图D有向图四应用题(30分)1有向图如下图所示,画出邻接矩阵和邻接表解:(1)邻接矩阵 1 2 3 4 5(2)邻接表1235243541542 已知一个无向图有6个结点,9条边,这9条边依次为(0,1),(0,2),(0,4),(0,5)
9、,(1,2),(2,3),(2,4),(3,4),(4,5)。试画出该无向图,并从顶点0出发,分别写出按深度优先搜索和按广度优先搜索进行遍历的结点序列。(5分)231D045解:从顶点0出发的深度优先搜索遍历的结点序列:0 1 2 3 4 5(答案不唯一)从顶点0出发的广度优先搜索遍历的结点序列:0 1 2 4 5 3(答案不唯一)3 已知一个无向图的顶点集为:a,b,c,d,e,其邻接矩阵如下,画出草图,写出顶点a出发按深度优先搜索进行遍历的结点序列。(5分)解:acbed(1) (2)深度优先搜索:a b d c e (答案不唯一) 广度优先搜索: a b e d c (答案不唯一) 4网G的邻接矩阵如下,试画出该图,并画出它的一棵最小生成树。2543125431解: 最小生成树: 8 11 10 8 3 4 13 7 3 4 75. 已知某图G的邻接矩阵如图,(1)画出相应的图; (2)要使此图为完全图需要增加几条边。解:134242D31(1)(2) 完全无向图应具有的边数为:n*(n-1)1/2=4*(4-1)/2=6,所以还要增加2条边(如右图)。6已知如图所示的有向图,请给出该图的:(1) 每个顶点的入/出度;(2) 邻接表;(3) 邻接矩阵。解:(1) (2)顶点123456入度321122出度022313(3)7如图,请完成以下操作:(2