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

一、选择题 1、有6个结点的有向完全图有（）条弧。 A、36 B、28 C、30 D、15 2、用邻接表表示图进行广度优先遍历时，通常采用（）来实现算法。 A、栈 B、队列 C、树 D、图 3、用邻接表表示图进行深度优先遍历时，通常采用（）来实现算法。 A、栈 B、队列 C、树 D、图 4、任何一个无向连通图的最小生成树（） A、只有一棵 B、一棵或多棵 C、一定有多棵 D、可能不存在 5、在一个图中，所有顶点的度数之和等于所有边数和的（）倍。 A、1/2 B、1 C、2 D、4 6、在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（）倍。 A、1/2 B、1 C、2 D、4 7、一个有n个顶点的无向图最多有（）条边。 A、n B、n(n-1) C、n(n-1)/2 D、2n 8、具有5个顶点的无向完全图有（）条边。 A、6 B、8 C、10 D、20 9、在一个具有n个顶点的无向图中，要连通全部顶点至少需要（）条边。 A、n B、n+1 C、n-1 D、n/2 10、对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是（） A、(n+1)*(n-1) B、(n-1)*(n-1) C、n D、n*n 11、对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表头向量的大小为（），所有邻接表中的结点总数是（） (1)A、n B、n+1 C、n-1 D、n+e (2)A、e/2 B、e C、2e D、n+e 12、采用邻接表存储的图的深度优先遍历算法类似于二叉树的（） 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条边的图，若用邻接矩阵存储，广度优先遍历算法的时间复杂度为（n2）。 9、图的BFS生成树的树高比DFS生成树的树高（小）。 10、若要求一个稀疏图G的最小生成树，最好用（克鲁斯卡尔）算法来求解。 11、若要求一个稠密图G的最小生成树，最好用（普里姆）算法来求解。 12、n个顶点的连通图至少（N-1）条边。 13、已知一个图的邻接矩阵表示，计算第i个结点的入度的方法是（求第I列的和）。 14、已知一个图的邻接矩阵表示，删除所有从第i个结点出发的边的方法是（将第I行和第I列的值全部更新为零）。 15、设有向图G有n个顶点e条边，进行拓扑排序的总的计算时间为（N+E）。