（新编）数据结构第七章图练习及答案.doc

一、选择题1、有 6 个结点的有向完全图有（）条弧A、36 B、28 C、30 D、152、用邻接表表示图进行广度优先遍历时，通常采用（）来实现算法A、栈 B、队列 C、树 D、图3、用邻接表表示图进行深度优先遍历时，通常采用（）来实现算法A、栈 B、队列 C、树 D、图4、任何一个无向连通图的最小生成树（）A、只有一棵 B、一棵或多棵 C、一定有多棵 D、可能不存在5、在一个图中，所有顶点的度数之和等于所有边数和的（）倍A、1/2 B、1 C、2 D、46、在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（）倍A、1/2 B、1 C、2 D、47、一个有 n 个顶点的无向图最多有（）条边A、n B、n(n-1) C、n(n-1)/2 D、2n8、具有 5 个顶点的无向完全图有（）条边A、6 B、8 C、10 D、209、在一个具有 n 个顶点的无向图中，要连通全部顶点至少需要（）条边A、n B、n+1 C、n-1 D、n/210、对于一个具有 n 个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是（）A、(n+1)*(n-1) B、(n-1)*(n-1) C、n D、n*n11、对于一个具有 n 个顶点和 e 条边的无向图，若采用邻接表表示，则表头向量的大小为（） ，所有邻接表中的结点总数是（）(1)A、n B、n+1 C、n-1 D、n+e(2)A、e/2 B、e C、2e D、n+e12、采用邻接表存储的图的深度优先遍历算法类似于二叉树的（）A、先序遍历 B、中序遍历 C、后序遍历 D、按层遍历13、采用邻接表存储的图的广度优先遍历算法类似于二叉树的（）A、先序遍历 B、中序遍历 C、后序遍历 D、按层遍历14、判定一个有向图是否存在回路，除了利用拓扑排序方法外，还可以利用（）A、求关键路径的方法 B、求最短路径的方法C、宽度优先遍历算法 D、深度优先遍历算法15、关键路径是 AOE 网中的（）A、从源点到汇点的最长路径 B、从源点到汇点的最短路径C、最短的回路 D、活动的最早开始时间与最迟发生时间相等二、填空题1、有向图 G 用邻接矩阵存储，则其第 i 行的所有元素之和等于顶点 i 的（出度） 。

2、设有一稀疏图 G，则 G 采用（邻接表）存储较省空间3、设有一稠密图 G，则 G 采用（邻接矩阵）存储较省空间4、图的邻接表存储结构只适用于（）图5、已知一个图的邻接矩阵表示，删除所有从第 i 个顶点出发的边的方法是（访问矩阵第 I行） 6、图的深度优先遍历序列（不是）唯一的7、n 个顶点 e 条边的图，若用邻接表存储，深度优先遍历算法的时间复杂度为（n+e） 8、n 个顶点 e 条边的图，若用邻接矩阵存储，广度优先遍历算法的时间复杂度为（n 2） 9、图的 BFS 生成树的树高比 DFS 生成树的树高（小） 10、若要求一个稀疏图 G 的最小生成树，最好用（ 克鲁斯卡尔）算法来求解11、若要求一个稠密图 G 的最小生成树，最好用（ 普里姆）算法来求解12、n 个顶点的连通图至少（N-1）条边 13、已知一个图的邻接矩阵表示，计算第 i 个结点的入度的方法是（求第 I 列的和） 14、已知一个图的邻接矩阵表示，删除所有从第 i 个结点出发的边的方法是（将第 I 行和第 I 列的值全部更新为零） 15、设有向图 G 有 n 个顶点 e 条边，进行拓扑排序的总的计算时间为（ N+E） 。