数据结构第七章图练习及答案

《数据结构第七章图练习及答案》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、一、选择题1、有6个结点的有向完全图有（）条弧。A、36B、28C、30D、152、用邻接表表示图进行广度优先遍历时，通常采用（）来实现算法。A、栈B、队列C、树D、图3、用邻接表表示图进行深度优先遍历时，通常采用（）来实现算法。A、栈B、队列C、树D、图4、任何一个无向连通图的最小生成树（）A、只有一棵B、一棵或多棵C、一定有多棵D、可能不存在5、在一个图中，所有顶点的度数之和等于所有边数和的（）倍。A、1/2B、1C、2D、46、在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（）倍。A、1/2B、1C、2D、47、一个有n个顶点的无向图最多有（）条边

2、。A、nB、n(n-1)C、n(n-1)/2D、2n8、具有5个顶点的无向完全图有（）条边。A、6B、8C、10D、209、在一个具有n个顶点的无向图中，要连通全部顶点至少需要（）条边。A、nB、n+1C、n-1D、n/210、对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是（）A、(n+1)*(n-1)B、(n-1)*(n-1)C、nD、n*n11、对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表头向量的大小为（），所有邻接表中的结点总数是（）(1)A、nB、n+1C、n-1D、n+e(2)A、e/2B、eC、2eD、n+e12、采用

3、邻接表存储的图的深度优先遍历算法类似于二叉树的（）A、先序遍历B、中序遍历C、后序遍历D、按层遍历13、采用邻接表存储的图的广度优先遍历算法类似于二叉树的（）A、先序遍历B、中序遍历C、后序遍历D、按层遍历14、判定一个有向图是否存在回路，除了利用拓扑排序方法外，还可以利用（）A、求关键路径的方法B、求最短路径的方法C、宽度优先遍历算法D、深度优先遍历算法15、关键路径是AOE网中的（）A、从源点到汇点的最长路径B、从源点到汇点的最短路径C、最短的回路D、活动的最早开始时间与最迟发生时间相等二、填空题1、有向图G用邻接矩阵存储，则其第i行的所有元素之和等于顶点i的（

4、出度）。2、设有一稀疏图G，则G采用（邻接表）存储较省空间。3、设有一稠密图G，则G采用（邻接矩阵）存储较省空间。4、图的邻接表存储结构只适用于（）图。5、已知一个图的邻接矩阵表示，删除所有从第i个顶点出发的边的方法是（访问矩阵第I行）。6、图的深度优先遍历序列（不是）唯一的。7、n个顶点e条边的图，若用邻接表存储，深度优先遍历算法的时间复杂度为（n+e）。8、n个顶点e条边的图，若用邻接矩阵存储，广度优先遍历算法的时间复杂度为（n2）。9、图的BFS生成树的树高比DFS生成树的树高（小）。10、若要求一个稀疏图G的最小生成树，最好用（克鲁斯卡尔）算法来求解。11、

5、若要求一个稠密图G的最小生成树，最好用（普里姆）算法来求解。12、n个顶点的连通图至少（N-1）条边。13、已知一个图的邻接矩阵表示，计算第i个结点的入度的方法是（求第I列的和）。14、已知一个图的邻接矩阵表示，删除所有从第i个结点出发的边的方法是（将第I行和第I列的值全部更新为零）。15、设有向图G有n个顶点e条边，进行拓扑排序的总的计算时间为（N+E）。