数据结构-图的遍历（中）
2010-07-02 02:38阅读：
28.采用邻接表存储的图的广度优先遍历类似于二叉树的(
A
)。
A．按层次遍历
B. 中序遍历
C.
后序遍历
D. 先序遍历
29.一个图中包含k个连通分量，若按深度优先(DFS)搜索方法访问所有结点，则必须调用(
A
)次深度优先遍历算法。
A．k
B. 1
C. k-1
D. k+1
30.以下说法正确的是
( B
)。
(全国2991年自考题。)
A.连通分量是无向图中的极小连通子图
B.强连通分量是有向图中的极大强连通子图
C.在一个有向图的拓扑序列中若顶点a在顶点b之前，则图中必有一条弧<a,b>
D.对有向图G，如果以任一顶点出发进行一次深度优先或广度优先搜索能访问到每个顶点，则该图一定是完全图
31.下面关于图的存储的叙述中，哪一个是正确的。 （
A ）
A．用相邻矩阵法存储图，占用的存储空间数只与图中结点个数有关,而与边数无关
B．用相邻矩阵法存储图，占用的存储空间数只与图中边数有关,而与结点个数无关
C．用邻接表法存储图，占用的存储空间数只与图中结点个数有关，而与边数无关
D．用邻接表法存储图，占用的存储空间数只与图中边数有关，而与结点个数无关
32.对于如右下图所示的带权有向图，从顶点1到顶点5的最短路径（
D ）
A．1，4，5
B.1，2，3，5
C．1，4，3，5
D.1，2，4，3，5
33.设G1=(V1,E1)和G2=(V2,E2)为两个图，
V1ÍV2,E1ÍE2,则称（
A ）
A．G1是G2的子图
B.G2是G1的子图
C．G1是G2的连通分量
D.G2是G1的连通分量
34.带权有向图G用邻接矩阵A存储，则顶点i的入度等于A中（ D
）
A、第i行非∞的元素之和 B、第i列非∞的元素之和
C、第i行非∞且非0的元素个数
D、第i列非∞且非0的元素个数
35.假设一个有n个顶点和e条弧的有向图用邻接表表示，则删除与某个顶点vi相关的所有弧的时间复杂度是（
C ）
A． O(n) B．O(e)
C．O(n+e)
D．O(n*e)
填空题：
36.一个无向图有n个顶点和e条边，则所有顶点的度的和即(表示顶点i的度)=
2e
。
答：2e
(一条边被两个顶点使用)
37.一个连通图的
生成树
是一个极小连通子图。
(重大2000年研究生试题。)
38.设无向图G的顶点数为n，图G最少有
0
条边，最多有 n(n-1)/2
条边。若G为有向图，有n个顶点，则图G最少有
0 条边，最多有
n(n-1)
条边。具有n个顶点的无向完全图，边的总数为
n(n-1)/2
条；而具有n个顶点的有向完全图中，边的总数有
n(n-1)
条。
(注*：设每个结点都有n-1条弧线从自己出发分别射向其它各个结点的话，则n个结点共有n(n-1)
条有向弧线存在；但是，如此一来任两个结点之间都会有两条相向而指的弧线存在，这就是所谓的有向完全图。如果我们限定任意两个结点之间都有且仅有一条无向的连线存在，则整个图的连线总数就会比有向完全图的弧线总数刚好少一半，即共有n(n-1)条边，也就是n-1)
条边。此乃所谓(无向)完全图。)
39.在有n个顶点的有向图中，每个顶点的度最大可达
2(n-1)
。
(武大2000年研究生试题。)
40.在无向图G的邻接矩阵A中，若A[I][j]等于1，则A[j][I]等于
1
。
41.在一个图G的邻接表表示中，每个顶点的邻接表中所含的结点数，对于有向图而言等于该顶点的
出度
；而对于无向图而言等于该顶点的
度 。
42.对无向图，若它有n个顶点e条边，则其邻接表中需要
n+e
个结点。其中，
2e
个结点构成邻接表，
n
个结点构成顶点表。
43.已知一个有向图的邻接矩阵表示，计算第i个结点的入度的方法是
第i列的元素之和
。
44.已知一个有向图的邻接矩阵表示，删除所有从第i个结点出发的边的方法是
使 第i行元素值为0
。
45.遍历图的过程实质上是
通过边或弧找邻接点的过程
。Breadth-first
search遍历图的时间复杂度为
O（n+e）
，depth-first
search遍历图的时间复杂度为 O(n+e)
，两者不同之处在于 对顶点访问顺序不同
，反映在数据结构上的差别
深度优先搜索需用栈，广度优先搜索需用队列
。
(厦大1999年研究生试题。)
46.遍历图的基本方法有深度优先搜索和广度优先搜索，其中
深度优先搜索
是一个递归过程。
(全国2001年自考题)
简答题：
47.简述无向图和有向图有哪几种存储结构，并说明各种结构在图中的不同操作(图的遍历，有向图的拓扑排序等)中有什么样的优越性？
无向图的存储结构有：邻接矩阵的数组表示法、邻接表、邻接多重表。
有向图的存储结构有：邻接矩阵的数组表示法、邻接表、逆邻接表、十字链表。
.48已知一个无向图的邻接表如下图所示，要求：
(1).画出该无向图；
(2).根据邻接表，分别写出用DFS和BFS算法从顶点V0开始的遍历该图后所得到的遍历序列，并画出DFS生成树和BFS生成树。
（1）无向图（2）DFS：V0,V2,V3,V1,V4,V6,V5;BFS:V0,V2,V5,V6,V1,V3,V4
