1-1无向连通图所有顶点的度之和为偶数。T
1-2无向连通图边数一定大于顶点个数减1。F
1-3用邻接表法存储图，占用的存储空间数只与图中结点个数有关，而与边数无关。 F
1-4用邻接矩阵法存储图，占用的存储空间数只与图中结点个数有关，而与边数无关。T
1-5在一个有向图中，所有顶点的入度与出度之和等于所有边之和的2倍。 T
1-6在任一有向图中，所有顶点的入度之和等于所有顶点的出度之和。 T
1-7如果无向图G必须进行两次广度优先搜索才能访问其所有顶点，则G一定有2个连通分量。 T
1-8Prim 算法是维护一个森林，每一步把两棵树合并成一棵。 F
1-9Kruskal 算法是维护一个森林，每一步把两棵树合并成一棵。 T
1-10Kruskal 算法是通过每步添加一条边及其相连的顶点到一棵树，从而逐步生成最小生成树。 F
1-11Prim 算法是通过每步添加一条边及其相连的顶点到一棵树，从而逐步生成最小生成树。 T
1-12无向连通图至少有一个顶点的度为1。F
1-13用一维数组G[]存储有4个顶点的无向图如下：
G[] = { 0, 1, 0, 1, 1, 0, 0, 0, 1, 0 }
则顶点2和顶点0之间是有边的。 T
2-1下面关于图的存储的叙述中，哪一个是正确的？ A
A.用相邻矩阵法存储图，占用的存储空间数只与图中结点个数有关，而与边数无关
B.用相邻矩阵法存储图，占用的存储空间数只与图中边数有关，而与结点个数无关
C.用邻接表法存储图，占用的存储空间数只与图中结点个数有关，而与边数无关
D.用邻接表法存储图，占用的存储空间数只与图中边数有关，而与结点个数无关
2-2关于图的邻接矩阵，下列哪个结论是正确的？ B
A.有向图的邻接矩阵总是不对称的
B.有向图的邻接矩阵可以是对称的，也可以是不对称的
C.无向图的邻接矩阵总是不对称的
D.无向图的邻接矩阵可以是不对称的，也可以是对称的
2-3设N个顶点E条边的图用邻接表存储，则求每个顶点入度的时间复杂度为： C
A.O(N)
B.O(N2)
C.O(N+E)
D.O(N×E)
2-4在任一有向图中，所有顶点的入度之和与所有顶点的出度之和的关系是： A
A.相等
B.大于等于
C.小于等于
D.不确定
2-5下面给出的有向图中，有_C_个强连通分量。
A.1 ({0,1,2,3,4})
B.1 ({1,2,3,4})
C.2 ({1,2,3,4}, {0})
D.5 ({0}, {1}, {2}, {3}, {4})
2-6给定一个有向图的邻接表如下图，则该图有_B_个强连通分量。
A.4 {{0, 1, 5}, {2}, {3}, {4}}
B.3 {{2}, {4}, {0, 1, 3, 5}}
C.1 {0, 1, 2, 3, 4, 5}
D.1 {0, 5, 1, 3}
2-7对于一个具有N个顶点的无向图，要连通所有顶点至少需要多少条边？A
A.N−1
B.N
C.N+1
D.N/2
2-8一个有N个顶点的强连通图至少有多少条边？ B
A.N−1
B.N
C.N+1
D.N(N−1)
2-9对于有向图，其邻接矩阵表示比邻接表表示更易于：A
A.求一个顶点的入度
B.求一个顶点的出边邻接点
C.进行图的深度优先遍历
D.进行图的广度优先遍历
2-10在用邻接表表示有N个结点E条边的图时，深度优先遍历算法的时间复杂度为： B
A.O(N)
B.O(N+E)
C.O(N2)
D.O(N2×E)
2-11给定一有向图的邻接表如下。从顶点V1出发按深度优先搜索法进行遍历，则得到的一种顶点序列为：B
A.V1,V2,V3,V5,V4
B.V1,V3,V4,V5,V2
C.V1,V4,V3,V5,V2
D.V1,V2,V4,V5,V3
2-12已知一个图的邻接矩阵如下，则从顶点V1出发按深度优先搜索法进行遍历，可能得到的一种顶点序列为： B
A.V1,V2,V3,V4,V5,V6
B.V1,V2,V4,V5,V6,V3
C.V1,V3,V5,V2,V4,V6
D.V1,V3,V5,V6,V4,V2
2-13如果从无向图的任一顶点出发进行一次深度优先搜索可访问所有顶点，则该图一定是：A
A.连通图
B.完全图
C.有回路的图
D.一棵树
2-14给定一有向图的邻接表如下。从顶点V1出发按广度优先搜索法进行遍历，则得到的一种顶点序列为： C
A.V1,V2,V3,V4,V5
B.V1,V2,V3,V5,V4
C.V1,V3,V2,V4,V5
D.V1,V4,V3,V5,V2
2-15已知一个图的邻接矩阵如下，则从顶点V1出发按广度优先搜索法进行遍历，可能得到的一种顶点序列为：A
A.V1,V2,V3,V5,V4,V6
B.V1,V2,V4,V5,V6,V3
C.V1,V3,V5,V2,V4,V6
D.V1,V3,V5,V6,V4,V2
2-16图的广度优先遍历类似于二叉树的：D
A.先序遍历
B.中序遍历
C.后序遍历
D.层次遍历
2-17我们用一个有向图来表示航空公司所有航班的航线。下列哪种算法最适合解决找给定两城市间最经济的飞行路线问题？ A
A.Dijkstra算法
B.Kruskal算法
C.深度优先搜索
D.拓扑排序算法
2-18数据结构中Dijkstra算法用来解决哪个问题？ B
A.关键路径
B.最短路径
C.拓扑排序
D.字符串匹配
2-19使用迪杰斯特拉（Dijkstra）算法求下图中从顶点1到其他各顶点的最短路径，依次得到的各最短路径的目标顶点是：B
A.5, 2, 3, 4, 6
B.5, 2, 3, 6, 4
C.5, 2, 4, 3, 6
D.5, 2, 6, 3, 4
2-20任何一个带权无向连通图的最小生成树——C
A.是唯一的
B.是不唯一的
C.有可能不唯一
D.有可能不存在
2-21给定有权无向图的邻接矩阵如下，其最小生成树的总权重是：D
A.10
B.11
C.12
D.14
2-22对下图进行拓扑排序，可以得到不同的拓扑序列的个数是：B
A.4
B.3
C.2
D.1
2-23使用迪杰斯特拉（Dijkstra）算法求下图中从顶点1到其他各顶点的最短路径，依次得到的各最短路径的目标顶点是：A
A.6, 7, 5, 3, 2, 4
B.6, 2, 5, 7, 3, 4
C.2, 3, 4, 5, 6, 7
D.2, 4, 3, 6, 5, 7
5-1下列代码的功能是对一个给定的图G执行拓扑排序，其中TopNum[]从1开始记录拓扑序。
void Topsort( Graph G )
{
Queue Q;
Vertex V, W;
NodePtr ptr;
int counter = 0;
Q = CreateEmptyQueue(NumVertex);
for ( V=0; V<G->NumV; V++ )
if ( Indegree[V] == 0 )
Enqueue(V, Q);
while ( !IsEmpty(Q) ){
V = Dequeue( Q );
TopNum[V] = **++counter**(2分);
for ( ptr=G->List[V]; ptr; ptr=ptr->Next) {
W = ptr->Vertex;
if ( **--Indegree[W]**(2分) == 0 )
Enqueue(W, Q);
}
}
if ( counter != NumVertex )
printf("ERROR: Graph has a cycle.\n");
DisposeQueue(Q);
}
5-2
/* 广度优先遍历邻接矩阵存储的图Graph */
typedef struct {
Vertex G[MAX][MAX];
int Nv;
}Graph;
typedef Graph* MGraph;
typedef struct {
Vertex *vertex;
int len;
int ptr;
int end;
}queue;
typedef queue* Queue;
/* IsEdge(Graph, V, W)检查<V, W>是否图Graph中的一条边，即W是否V的邻接点。 */
bool IsEdge( MGraph Graph, Vertex V, Vertex W )
{
return Graph->G[V][W]<INFINITY ? true : false;
}
/* Visited[]为布尔类型全局数组，已经初始化为false */
void BFS ( MGraph Graph, Vertex S, void (*Visit)(Vertex) )
{
Queue Q;
Vertex V, W;
Q = CreateQueue( MaxSize );
Visit( S );
Visited[S] = true;
**AddQ(Q, S)** (2分);
while ( !IsEmpty(Q) ) {
**V = DeleteQ(Q)**(2分);
for( W=0; W<Graph->Nv; W++ )
if (**!Visited[W] && IsEdge(Graph, V, W)** (2分) ) {
Visit( W );
Visited[W] = true;
AddQ(Q, W);
}
} /* while结束*/
}