数据结构图测验.doc

图练习：
1．图中有关路径的定义是（ ）。
A．由顶点和相邻顶点序偶构成的边所形成的序列
B．由不同顶点所形成的序列
C．由不同边所形成的序列 D．上述定义都不是
2．设无向图的顶点个数为n，则该图最多有（ ）条边。
A．n-1 B．n(n-1)/2 C． n(n+1)/2 D．0 E．n2
3．一个n个顶点的连通无向图，其边的个数至少为（ ）。
A．n-1 B．n C．n+1 D．nlogn；
4．要连通具有n个顶点的有向图，至少需要（ ）条边。
A．n-l B．n C．n+l D．2n
5．n个结点的完全有向图含有边的数目（　　　）。
A．n*n Ｂ．n（n＋１） C．n／2 D．n*（n－l）
6．一个有n个结点的图，最少有（ ）个连通分量，最多有（ ）个连通分量。
A．0 B．1 C．n-1 D．n
7．在一个无向图中，所有顶点的度数之和等于所有边数（ ）倍，在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（ ）倍。
A．1/2 B．2 C．1 D．4
8. 下列说法不正确的是（ ）。
A．图的遍历是从给定的源点出发每一个顶点仅被访问一次 C．图的深度遍历不适用于有向图
B．遍历的基本算法有两种：深度遍历和广度遍历 D．图的深度遍历是一个递归过程
9．无向图G=(V,E),其中：V={a,b,c,d,e,f},E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)}，对该图进行深度优先遍历，得到的顶点序列正确的是（ ）。
A．a,b,e,c,d,f B．a,c,f,e,b,d C．a,e,b,c,f,d D．a,e,d,f,c,b
10. 关键路径是事件结点网络中（ ）。
A．从源点到汇点的最长路径 B．从源点到汇点的最短路径
C．最长回路 D．最短回路

1.A
2.B
3.A
4.B
5.D
6.1B
6.2D
7.1B
7.2C
8C
9D
10A

二、判断题
1.树中的结点和图中的顶点就是指数据结构中的数据元素。（ ）
2．在n个结点的无向图中，若边数大于n-1,则该图必是连通图。（ ）
3．对有n个顶点的无向图，其边数e与各顶点度数间满足下列等式e=。（ ）
4. 有e条边的无向图，在邻接表中有e个结点。（ ）
5. 有向图中顶点V的度等于其邻接矩阵中第V行中的1的个数。（ ）
6．强连通图的各顶点间均可达。（ ）
7．邻接多重表是无向图和有向图的链式存储结构。（ ）
8. 十字链表是无向图的一种存储结构。（ ）
9．用邻接矩阵法存储一个图所需的存储单元数目与图的边数有关。（ ）
10．有n个顶点的无向图, 采用邻接矩阵表示, 图中的边数等于邻接矩阵中非零元素之和的一半。（ ）
11. 有向图的邻接矩阵是对称的。（ ）
12．无向图的邻接矩阵一定是对称矩阵，有向图的邻接矩阵一定是非对称矩阵。（ ）
13. 邻接矩阵适用于有向图和无向图的存储，但不能存储带权的有向图和无向图，而只能使用邻接表存储形式来存储它。（ ）
14. 用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小与图中结点个数有关，而与图的边数无关。（ ）
15. 广度遍历生成树描述了从起点到各顶点的最短路径。（ ）
16．任何无向图都存在生成树。（ ）
17. 不同的求最小生成树的方法最后得到的生成树是相同的.（ ）
18．带权无向图的最小生成树必是唯一的。（ ）
19. 最小代价生成树是唯一的。（ ）
20．一个网（带权图）都有唯一的最小生成树。（ ）
21．连通图上各边权值均不相同，则该图的最小生成树是唯一的。（ ）
22．带权的连通无向图的最小（代价）生成树（支撑树）是唯一的。（ ）
23．带权的连通无向图的最小代价生成树是唯一的。（ ）
24. 最小生成树问题是构造连通网的最小代价生成树。（ ）

1.√
2. ×
3.×
4.×
5.×
6.√
7×
8×
9.×
10. √
11×
12. ×
13. ×
14. √
15.×
16.×
17.×
18.×
19.×
20.×
21.√
22. ×
23×
24√

三、填空题
1.判断一个无向图是一棵树的条件是______。
2．有向图G的强连通分量是指______。
3．一个连通图的______是一个极小连通子图。
4．具有10个顶点的无向图，边的总数最多为______。
5．若用n表示图中顶点数目，则有_______条边的无向图成为完全图。
6. 设无向图 G 有n 个顶点和e 条边，每个顶点Vi 的度为di（1<=i<=n〉，则e=______
7．G是一个非连通无向图，共有28条边，则该图至少有______个顶点。
8. 在有n个顶点的有向图中，若要使任意两点间可以互相到达，则至少需要______条弧。
9．在有n个顶点的有向图中，每个顶点的度最大可达______。
10．设G为具有N个顶点的无向连通图，则G中至少有______条边。
11．n个顶点的连通无向图，其边的条数至少为______。
12．如果含n个顶点的图形形成一个环，则它有______棵生成树。
13．N个顶点的连通图的生成树含有______条边。
14．构造n个结点的强连通图，至少有______条弧。
15．有N个顶点的有向图，至少需要量______条弧
才能保证是连通的。
16．右图中的强连通分量的个数为（ ）个。
17．N个顶点的连通图用邻接矩阵表示时,该矩阵
至少有_______个非零元素。
18．在图G的邻接表表示中，每个顶点邻接表中所含的结点数，对于无向图来说等于该顶点的______；对于有向图来说等于该顶点的______。
19. 在有向图的邻接矩阵表示中，计算第I个顶点入度的方法是______。
20. 对于一个具有n个顶点e条边的无向图的邻接表的表示，则表头向量大小为______，邻接表的边结点个数为______。
21. 已知一无向图G=（V，E），其中V={a,b,c,d,e } E={(a,b),(a,d),(a,c),(d,c),(b,e)}现用某一种图遍历方法从顶点a开始遍历图，得到的序列为abecd，则采用的是______遍历方法。

答案：
1.有n个顶点，n-1条边的无向连通图
2.有向图的极大强连通子图
3. 生成树
4. 45 5. n(n-1)/2 6 .
7. 9 8. n
9. 2(n-1) 10. N-1 11. n-1 12. n 13. N-1 14. n 15. N
16. 3 17. 2（N-1） 18. 度 出度 19. 第I列非零元素个数 20.n 2e
22. 深度优先 23.宽度优先遍历

四、 应用题
1．（1）．如果G1是一个具有n个顶点的连通无向图，那么G1最多有多少条边？G1最少有多少条边？
（2）．如果G2是一个具有n个顶点的强连通有向图，那么G2最多有多少条边？G2最少有多少条边？
（3）．如果G3是一个具有n个顶点的弱连通有向图，那么G3最多有多少条边？G3最少有多少条边？
2．n个顶点的无向连通图最少有多少条边？n个顶点的有向连通图最少有多少条边？
3． 首先将如下图所示的无向图给出其存储结构的邻接链表表示，然后写出对其分别进行深度，广度优先遍历的结果。
3

10

5

7

8

4

2

1

6

9

3

6

7

5

8

9

4

2

1

4．给出图G：
（1）．画出G的邻接表表示图；
（2）．根据你画出的邻接表，以顶点①为根，画出G的深度优先生成树和广度优先生成树。
5．对一个图进行遍历可以得到不同的遍历序列，那么导致得到的遍历序列不唯一的因素有哪些？
6．考虑下图：
(1)从顶点A出发，求它的深度优先生成树
(2)从顶点E出发，求它的广度优先生成树
（3）根据普利姆(Prim) 算法，求它的最小生成树 从A点开始
（4）根据kruskal 算法，求它的最小生成树

7．考虑下图：
(1)从顶点A出发，求它的深度优先生成树
(2)从顶点E出发，求它的广度优先生成树
（3）根据普利姆(Prim) 算法，求它的最小生成树 从1点开始
（4）根据kruskal 算法，求它的最小生成树

答案：
1．（1）G1最多n(n-1)/2条边，最少n-1条边
(2) G2最多n(n-1)条边，最少n条边
(3) G3最多n(n-1)条边，最少n-1条边 (注：弱连通有向图指把有向图看作无向图时，仍是连通的)
2．n-1，n
3．深度优先遍历序列：125967384
宽度优先遍历序列：123456789
注：（1）邻接表不唯一，这里顶点的邻接点按升序排列
（2）在邻接表确定后，深度优先和宽度优先遍历序列唯一
（3）这里的遍历，均从顶点1开始
4.略
5.遍历不唯一的因素有：开始遍历的顶点不同；存储结构不同；在邻接表情况下邻接点的顺序不同。
6．设该图用邻接表存储结构存储，顶点的邻接点按顶点编号升序排列
(1)ABGFDEC (2)EACFBDG
7.略
7 / 7