发布时间 : 星期二 文章数据结构试题集(含答案)更新完毕开始阅读7176e5f6961ea76e58fafab069dc5022aaea46cc
C. v1,v3,v4,v5,v2 D. v1,v4,v3,v5,v2
22、关键路径是事件结点网络中（ A ）。
A. 从源点到汇点的最长路径 B. 从源点到汇点的最短路径 C. 最长的回路 D. 最短的回路
23、以下说法正确的是（ B ）。
A. 连通分量是无向图中的极小连通子图 B. 强连通分量是有向图中的极大强连通子图
C. 在一个有向图的拓扑序列中若顶点 a在顶点 b之前，则图中必有一条弧
24、假设有向图含 n个顶点及 e条弧，则表示该图的邻接表中包含的弧结点个数为 （ B ）。
A. n
B. e
C. 2e
D. n*e
0 1 1 0 1 0
25、设图的邻接矩阵为 0 0 1 ，则该图为（
A ）。
A. 有向图 B. 无向图 C. 强连通图 D. 完全图 26、为便于判别有向图中是否存在回路，可借助于（ D ）。
A. 广度优先搜索算法 B. 最小生成树算法
C. 最短路径算法 D. 拓扑排序算法
27、任何一个无向连通图的最小生成树（
B ）种。
A. 只有一棵 B. 有一棵或多棵 C. 一定有多棵 D. 可能不存在
28、已知一有向图的邻接表存储结构如图所示，根据有向图的广度优先遍历算法，从 顶点 v1出发，所得到的顶点序列是（ B ）。
1 2
3
2
^
^
4
5
3 4 5
^
^
2
4
^
A. v1,v2,v3,v4,v5 B. v1,v3,v2,v4,v5 C. v1,v2,v3,v5,v4 D. v1,v4,v3,v5,v2
29、对于一个有向图，若一个顶点的入度为 k1, 、出度为 k2，则对应邻接表中该顶点单链表中的结点数为（ B ）。
A. k1 B. k2 C. k1+k2 D. k1-k2
30、一个具有 8个顶点的有向图中，所有顶点的入度之和与所有顶点的出度之和的差
33
等于（ C ）。
A.16 B.4 C.0 D.2
31、无向图中一个顶点的度是指图中（ B ）。
A. 通过该顶点的简单路径数 B. 与该顶点相邻接的顶点数 C. 与该顶点连通的顶点数 D. 通过该顶点的回路数
二、填空题
1、n个顶点的连通图至少有 边。 答案： n-1 条
2、一个连通图的生成树是一个 ，它包含图中所有顶点，但只有 足以构成一棵树的 n-1 条边。 答案：极小连通子图 3、一个图的 表示法是惟一的。 答案：邻接矩阵
4、遍历图的基本方法有深度优先搜索和广度优先搜索，其中 是一个递归过 程。
答案：深度优先搜索
5、在无向图 G的邻接矩阵 A中，若 A[i][j] 等于 1，则 A[j][i] 等于 。 答案： 1
6、判定一个有向图是否存在回路，可以利用 。 答案：拓扑排序
7、已 知 一 个 图 的 邻 接 矩 阵 表 示 ， 计 算 第 i 个 结 点 的 入 度 的 方 法 是 。
答案：第 i 列上非无穷元素的个数之和 8、n个顶点的无向图最多有 边。 答案： n*(n-1)/2
9、已 知 一 个 图 的 邻 接 矩 阵 表 示 ， 删 除 所 有 从 第 i 个 结点 出发 的 边 的 方法
是 。
答案：将邻接矩阵的第 i 行元素全部置为 0.
10、若以邻接矩阵表示有向图，则邻接矩阵上第 的 。 答案：出度 三、判断题
i 行中非零元素的个数即为顶点 vi
1、图的连通分量是无向图的极小连通子图。 错 2、一个图的广度优先搜索树是惟一的。 错
3、图的深度优先搜索序列和广度优先搜索序列不是惟一的。 对
4、邻接表只能用于存储有向图，而邻接矩阵则可存储有向图和无向图。 错 5、存储图的邻接矩阵中，邻接矩阵的大小不但与图的顶点个数有关，而且与图的边数也有关。 错
34
6、AOV网是一个带权的有向图。 错
7、从源点到终点的最短路径是唯一的。 错
8、邻接表只能用于存储有向图，而邻接矩阵则可存储有向图和无向图。 dui
9、图的生成树是惟一的。 错
四、程序分析题
1、写出下面算法的功能。
typedef struct{
int vexnum,arcnum; char vexs[N]; int arcs[N][N];
}graph;
void funtion(int i,graph *g){
int j;
printf(\ visited[i]=TRUE;
for(j=0;j
if((g->arcs[i][j]==1)&&(!visited[j]))
function(j,g); } 答案：实现图的深度优先遍历算法
五、综合题
1、已知图 G的邻接矩阵如下所示：
（ 1）求从顶点 1 出发的广度优先搜索序列；
（ 2）根据 prim 算法，求图 G从顶点 1 出发的最小生成树，要求表示出其每一步生成过程。（用图或者表的方式均可） 。
6
1 5
6 5
3 1 5
5
6 4
5
5 2
3
6
6
4
2
6
答案： (1) 广度优先遍历序列： 1; 2, 3, 4; 5; 6
(2) 最小生成树（ prim 算法）
35
1
1
1
1
1
1
1
1
1
2
5
2 1
2
5
3
3
3
4
3
4 2
3 3
5
4 2
4
6 4 6 4 6 4 6
2、设一个无向图的邻接矩阵如下图所示： （ 1）画出该图；
（ 2）画出从顶点 0 出发的深度优先生成树；
0 1 1 1 0 1 0 1 0 0 1 1 0 1 1 1 0 1 0 1 0 0 1 1 0 0 0 0 1 1
0 0 0 1 1 0
答案： (1)
图形态
1
(2)
0
深度优先搜索树
1
0
3 2 3 2
5 4 5 4
3、写出下图中全部可能的拓扑排序序列。
1
2
3
4
5 6
答案： 1，5，2，3，6，4 1 ，5，6，2，3，4 5 ，1，2，3，6，4
5 ，1，6，2，3，4 5 ，6，1，2，3，4
4、AOE网G如下所示，求关键路径。（要求标明每个顶点的最早发生时间和最迟发生时
间，并画出关键路径）
3
v0
v1
3
2
v3
v4
2
2
v5
2
v2
4
3
答案： (1) 最早发生时间和最迟发生时间： (2) 关键路径：
36