13.N个顶点的连通图的生成树含有 条边。【中山大学1998、9(1分)】 14.构造n个结点的强连通图,至少有条弧。【北京轻工业学院2000一、4(2分)】 15.有N个顶点的有向图,至少需要量条弧 才能保证是连通的。【西南交通大学2000一、3】 16.右图中的强连通分量的个数为()个 【北京邮电大学2001二、5(2分)】 17.N个顶点的连通图用邻接矩阵表示时,该矩阵 至少有 个非零元素。【中科院计算所1998一、6(1分)】【中国科技大学1998 6(15/6分)】 18.在图G的邻接表表示中,每个顶点邻接表中所含的结点数,对于无向图来说等于该顶点 的 对于有向图来说等于该顶点的 【燕山大学2001二、5(3分)】 19.在有向图的邻接矩阵表示中,计算第I个顶点入度的方法是。【青岛大学2002 三、7(2分)】 20.对于一个具有n个顶点e条边的无向图的邻接表的表示,则表头向量大小为,邻 接表的边结点个数为 【青岛大学2002三、8(2分)】 21.遍历图的过程实质上是 , breath- first search遍历图的时间复杂度 depth- first search遍历图的时间复杂度 两者不同之处在于 ,反映在数据 结构上的差别是 【厦门大学1999、3】 22.已知一无向图G=(V,E),其中V={a,b,c,d,e}E={(a,b),(a,d),(a,c),(d,c),(b,e)} 现用某一种图遍历方法从顶点a开始遍历图,得到的序列为 abcd,则采用的是遍历 方法 【南京理工大学1996二、2(2分)】 23.一无向图G(V,E),其中V(G)={1,2,3,4,5,6,7},E(G)={(1,2),(1,3),(2,4), (2,5),(3,6),(3,7),(6,7)(5,1)},对该图从顶点3开始进行遍历,去掉遍历中未走过 的边,得一生成树G(V,E'),V(G’)=V(G),E(G’)={(1,3),(3,6),(7,3),(1,2), (1,5),(2,4)},则采用的遍历方法是 【南京理工大学1997三、6(1分)】 24.为了实现图的广度优先搜索,除了一个标志数组标志已访问的图的结点外,还需 存放被访问的结点以实现遍历。【南京理工大学1999二、9(2分)】 25.按下图所示,画出它的广度优先生成树 和深度优先生成树 【西安电子科技大学1998三、6(5分)】③ 26.构造连通网最小生成树的两个典型算法是。【北京科技大学1998一、5】 27.求图的最小生成树有两种算法,算法适合于求稀疏图的最小生成树 【南京理工大学2001二、6(2分)】13．N 个顶点的连通图的生成树含有______条边。【中山大学 1998 一、9 （1 分）】 14．构造 n 个结点的强连通图，至少有______条弧。【北京轻工业学院 2000 一、4（2 分）】 15．有 N 个顶点的有向图，至少需要量______条弧 才能保证是连通的。【西南交通大学 2000 一、3】 16．右图中的强连通分量的个数为（ ）个。 【北京邮电大学 2001 二、5 （2 分）】 17．N 个顶点的连通图用邻接矩阵表示时,该矩阵 至少有_______个非零元素。【中科院计算所 1998 一、6（1 分）】【中国科技大学 1998 一、 6（15/6 分）】 18．在图 G 的邻接表表示中，每个顶点邻接表中所含的结点数，对于无向图来说等于该顶点 的______；对于有向图来说等于该顶点的______。 【燕山大学 2001 二、5 （3 分）】 19. 在有向图的邻接矩阵表示中，计算第 I 个顶点入度的方法是______。【青岛大学 2002 三、7 （2 分）】 20. 对于一个具有 n 个顶点 e 条边的无向图的邻接表的表示，则表头向量大小为______，邻 接表的边结点个数为______。【青岛大学 2002 三、8 （2 分）】 21. 遍历图的过程实质上是______，breath-first search 遍历图的时间复杂度______； depth-first search 遍历图的时间复杂度______，两者不同之处在于______，反映在数据 结构上的差别是______。 【厦门大学 1999 一、3】 22. 已知一无向图 G=（V，E），其中 V={a,b,c,d,e } E={(a,b),(a,d),(a,c),(d,c),(b,e)} 现用某一种图遍历方法从顶点 a 开始遍历图，得到的序列为 abecd，则采用的是______遍历 方法。 【南京理工大学 1996 二、2 （2 分）】 23. 一无向图 G（V，E），其中 V（G）={1,2,3,4,5,6,7}，E（G）={（1,2）,(1,3），（2,4）， （2,5），（3,6），（3,7），（6,7）（5,1）},对该图从顶点 3 开始进行遍历，去掉遍历中未走过 的边，得一生成树 G’(V，E’）,V（G’）=V（G），E（G’）={（1,3），（3,6），（7,3），（1,2）， （1,5），（2,4）}，则采用的遍历方法是______。 【南京理工大学 1997 三、6 （1 分）】 24. 为了实现图的广度优先搜索，除了一个标志数组标志已访问的图的结点外，还需______ 存放被访问的结点以实现遍历。【南京理工大学 1999 二、9 （2 分）】 25. 按下图所示，画出它的广度优先生成树______和深度优先生成树______。 【西安电子科技大学 1998 三、6 （5 分）】 26．构造连通网最小生成树的两个典型算法是______。【北京科技大学 1998 一、5】 27．求图的最小生成树有两种算法，______算法适合于求稀疏图的最小生成树。 【南京理工大学 2001 二、6（2 分）】