数据结构答案
第 6 章 图
2005-07-14
第 6 章 图
课后习题讲解
1. 填空题
⑴ 设无向图G中顶点数为n,则图G至少有( )条边,至多有( )条边;若G为有向图,则至少有( )条边,至多有( )条边。 【解答】0,n(n-1)/2,0,n(n-1)
【分析】图的顶点集合是有穷非空的,而边集可以是空集;边数达到最多的图称为完全图,在完全图中,任意两个顶点之间都存在边。
⑵ 任何连通图的连通分量只有一个,即是( )。 【解答】其自身
…… 此处隐藏0字 ……
⑶ 图的存储结构主要有两种,分别是( )和( )。 【解答】邻接矩阵,邻接表
【分析】这是最常用的两种存储结构,此外,还有十字链表、邻接多重表、边集数组等。 ⑷ 已知无向图G的顶点数为n,边数为e,其邻接表表示的空间复杂度为( )。 【解答】O(n+e)
【分析】在无向图的邻接表中,顶点表有n个结点,边表有2e个结点,共有n+2e个结点,其空间复杂度为O(n+2e)=O(n+e)。
⑸ 已知一个有向图的邻接矩阵表示,计算第j个顶点的入度的方法是( )。 【解答】求第j列的所有元素之和
⑹ 有向图G用邻接矩阵A[n][n]存储,其第i行的所有元素之和等于顶点i的( )。 【解答】出度
⑺ 图的深度优先遍历类似于树的( )遍历,它所用到的数据结构是( );图的广度优先遍历类似于树的( )遍历,它所用到的数据结构是( )。 【解答】前序,栈,层序,队列
⑻ 对于含有n个顶点e条边的连通图,利用Prim算法求最小生成树的时间复杂度为( ),利用Kruskal算法求最小生成树的时间复杂度为( )。 【解答】O(n2),O(elog2e)
【分析】Prim算法采用邻接矩阵做存储结构,适合于求稠密图的最小生成树;Kruskal算法采用边集数组做存储结构,适合于求稀疏图的最小生成树。