13. 如图8.22所示 权值：165
623725191813121096745图8.22 Huffman树习 题 七 图
7.1 单项选择题
1. 在一个图中，所有顶点的度数之和等于所有边数的____倍。 A. 1/2 B. 1 C. 2 D. 4
2. 在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的____倍。 A. 1/2 B. 1 C. 2 D. 4 3. 一个有n个顶点的无向图最多有____条边。
A. n B. n(n-1) C. n(n-1)/2 D. 2n 4. 具有4个顶点的无向完全图有____条边。 A. 6 B. 12 C. 16 D. 20
5. 具有6个顶点的无向图至少应有____条边才能确保是一个连通图。 A. 5 B. 6 C. 7 D. 8
6. 在一个具有n个顶点的无向图中，要连通全部顶点至少需要____条边。 A. n B. n+1 C. n-1 D. n/2
7. 对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是____。 A. n B. (n-1)2 C. n-1 D. n2
8. 对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表头向量的大小为_①___；所有邻接表中的接点总数是_②___。 ① A. n B. n+1 C. n-1 D. n+e ② A. e/2 B. e C.2e D. n+e
9. 已知一个图如图9.5所示，若从顶点a出发按深度搜索法进行遍历，则可能得到的一种顶点序列为__①__；按宽度搜索法进行遍历，则可能得到的一种顶点序列为__②__。
17
① A. a,b,e,c,d,f B. e,c,f,e,b,d C. a,e,b,c,f,d D. a,e,d,f,c,b ② A. a,b,c,e,d,f B. a,b,c,e,f,d C. a,e,b,c,f,d D. a,c,f,d,e,b
abced图 9.5 一个无向图f10. 已知一有向图的邻接表存储结构如图9.6所示。
1 3 2 ^ 2 ^
3 4 5
4 ^ 5 2 4
图9.6 一个有向图的邻接表存储结构
⑴ 根据有向图的深度优先遍历算法，从顶点v1出发，所得到的顶点序列是____。 A. v1,v2,v3,v5,v4 B. v1,v2,v3,v4,v5 C. v1,v3,v4,v5,v2 D. v1,v4,v3,v5,v2
⑵ 根据有向图的宽度优先遍历算法，从顶点v1出发，所得到的顶点序列是____。 A. v1,v2,v3,v4,v5 B. v1,v3,v2,v4,v5 C. v1,v2,v3,v5,v4 D. v1,v4,v3,v5,v2
11. 采用邻接表存储的图的深度优先遍历算法类似于二叉树的____。 A. 先序遍历 B. 中序遍历 C. 后序遍历 D. 按层遍历 12. 采用邻接表存储的图的宽度优先遍历算法类似于二叉树的____。 A. 先序遍历 B. 中序遍历 C. 后序遍历 D. 按层遍历
13. 判定一个有向图是否存在回路除了可以利用拓扑排序方法外，还可以利用____。 A. 求关键路径的方法 B. 求最短路径的Dijkstra方法 C. 宽度优先遍历算法 D. 深度优先遍历算法
18
7.2 填空题（将正确的答案填在相应饿空中） 1. n个顶点的连通图至少____条边。 2. 在无权图G的邻接矩阵A中，若(vi,vj)或＜vi,vj＞属于图G的边集合，则对应元素A[i][j]等于____，否则等于____。
3. 在无向图G的邻接矩阵A中，若A[i][j]等于1，则A[j][i ]等于____。
4. 已知图G的邻接表如图9.7所示，其从顶点v1出发的深度有限搜索序列为____，其从顶点v1出发的宽度优先搜索序列为____。
V1 V2 V5 V4 ^
v2 v3 V5 ^
v3 V6 ^
v4 ^
v5 V4 V6 V3 ^
v6 ^
图9.7 图G的邻接表
5. 已知一个有向图的邻接矩阵表示，计算第i个结点的入度的方法是____。 6.已知一个图的邻接矩阵表示，删除所有从第i个结点出发的边的方法是____。 7.3
1．已知如图所示的有向图，请给出该图的:
1 5 （1）每个顶点的入/出度；
（2）邻接距阵； （3）邻接表； （4）逆邻接表； 6（5）强连通分量。 2 3
19
4
2．请用克鲁斯卡尔普里姆两种算法分别构造最小生成树：
（1）
a b d f 16 11 15 15 c 15 13 16 14 12 e 21
（2） 12 1 6 6 1315 2 16
4 7 5 2 20 9 10 12 4 3 5
3. 试列出下图中全部的拓扑排序序列。
53 1 2
4 5
4. 请用图示说明从顶点a到其余各顶点之间的最短路径。
b d 6
a f
e c
20
相关推荐：
loading