数据结构第章复习资料.doc

第 1 页
一、单选题
C01、在一个图中，所有顶点的度数之和等于图的边数的 倍。
A)1/2 B)1 C)2 D)4
B02、在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的 倍。
A)1/2 B)1 C)2 D)4
B03、有8个结点的无向图最多有 条边。
A)14 B)28 C)56 D)112
C04、有8个结点的无向连通图最少有 条边。
A)5 B)6 C)7 D)8
C05、有8个结点的有向完全图有 条边。
A)14 B)28 C)56 D)112
B06、用邻接表表示图进行广度优先遍历时，通常是采用 来实现算法的。
A)栈 B)队列 C)树 D)图
A07、用邻接表表示图进行深度优先遍历时，通常是采用 来实现算法的。
A)栈 B)队列 C)树 D)图
A08、一个含n个顶点和e条弧的有向图以邻接矩阵表示法为存储结构，则计算该有向图中某个顶点出度的时间复杂度为 。
A)O(n) B)O(e) C)O() D)O(n2)
C09、已知图的邻接矩阵，根据算法思想，则从顶点0出发按深度优先遍历的结点序列是 。
A)0 2 4 3 1 5 6 B)0 1 3 6 5 4 2 C)0 1 3 4 2 5 6 D)0 3 6 1 5 4 2
B10、已知图的邻接矩阵同上题，根据算法，则从顶点0出发，按广度优先遍历的结点序列是 。
A)0 2 4 3 6 5 1 B)0 1 2 3 4 6 5 C)0 4 2 3 1 5 6 D)0 1 3 4 2 5 6
D11、已知图的邻接表如下所示，根据算法，则从顶点0出发按深度优先遍历的结点序列是 。
A)0 1 3 2 B)0 2 3 1 C)0 3 2 1 D)0 1 2 3
A12、已知图的邻接表如下所示，根据算法，则从顶点0出发按广度优先遍历的结点序列是 。
A)0 3 2 1 B)0 1 2 3 C)0 1 3 2 D)0 3 1 2
A13、图的深度优先遍历类似于二叉树的 。
A)先序遍历 B)中序遍历 C)后序遍历 D)层次遍历
D14、图的广度优先遍历类似于二叉树的 。
A)先序遍历 B)中序遍历 C)后序遍历 D)层次遍历
B15、任何一个无向连通图的最小生成树 。
A)只有一棵 B)一棵或多棵 C)一定有多棵 D)可能不存在
A16、对于一个具有n个结点和e条边的无向图，若采用邻接表表示，则顶点表的大小为 ，所有边链表中边结点的总数为 。
A)n、2e B)n、e C)n、 D)2n、2e
C17、判断有向图是否存在回路，可以利用算法。
A)关键路径 B)最短路径的 C)拓扑排序 D)广度优先遍历
A18、若用邻接矩阵表示一个有向图，则其