第七章图
一、判断题
（）1. 在每个AOE网络中只有一条关键路径。
（）2. 图的深度优先搜索是一种典型的回溯搜索的例子，可以通过递归算法求解。（）3．用邻接矩阵表示图时，矩阵元素的个数与边的条数有关。
（）4．图的深度优先搜索序列和广度优先搜索序列不是唯一的。
（）5. 对AOV网进行拓扑排序时，如果存在从Vi到Vj的路径，则在拓朴序列中，结点Vi一定排在结点Vj的前面。
二、单项选择题
1. 在一个有向图的邻接矩阵表示中，删除一条边需要的时间复杂度为 ( )。
A) O(1) B) O(i) C) O(j) D) O(i+j)
2．一个有N个顶点的无向图最多有（）条边。
A) N B）N*(N−1) C）N*(N−1)/2 D）2*N
3．已知一个有向图的邻接矩阵表示，要删除所有从第i个结点发出的边，应该：（）A）将邻接矩阵的第i行删除B）将邻接矩阵的第i行元素全部置为0
C）将邻接矩阵的第i列删除D）将邻接矩阵的第i列元素全部置为0
4．下面是三个关于有向图运算的叙述：
（1）求有向图结点的拓扑序列，其结果必定是唯一的
（2）求两个指向结点间的最短路径，其结果必定是唯一的
（3）求AOE网的关键路径，其结果必定是唯一的
其中哪个（些）是正确的？
A) 只有（1）B) （1）和（2）C) 都正确D) 都不正确
5．已知一个无向图的邻接矩阵A[n][n]，要增加一条边( i, k )，应该：
A）将A[i][k]置为1 B）将A[i][i]和A[k][k]同时置为1
C）将A[k][i]置为1 D）将A[i][k]和A[k][i]同时置为1
三、填空题（在横线处填写合适内容）
1. 在使用Kruskal算法构造连通网络的最小生成树时，只有当一条候选边的两个端点不在同一个________ 上，才会被加入到生成树中。
2．已知有向图的邻接矩阵，要计算i号结点的入度，计算方法是：将累加。
3．已知有向图的邻接矩阵，要计算i号结点的出度，计算方法是：将累加。
四、综合题
1.用邻接矩阵表示图时，若图中有1000个顶点，1000条边，则形成的邻接矩阵有多少矩阵元素？有多少非零元素？是否稀疏矩阵？
2.用邻接矩阵表示图时，矩阵元素的个数与顶点个数是否相关？与边的条数是否相关？
3.有n个顶点的无向连通图至少有多少条边？有n个顶点的有向强连通图至少有多少条边？试举例说明。
4.对于有n个顶点的无向图，采用邻接矩阵表示，如何判断以下问题：图中有多少条边？任意两个顶点i和j之间是否有边相连？任意一个顶点的度是多少？
5.用邻接表表示图时，顶点个数设为n，边的条数设为e，在邻接表上执行有关图的遍历操作时，时间代价是O(n*e)？还是O(n+e)？或者是O(max(n,e))？
6.设有一有向图为G=(V，E)。其中，V={v0, v1, v2, v3}，E={, , , , }。请画出该有向图。
7.已知如图所示的有向图，请给出该图的：
（1）每个顶点的入度、出度；
（2）邻接矩阵；
（3）邻接表；
（4）逆邻接表；
（5）强连通分量。
8.已知如图所示的无向图，请给出该图的：（1）深度优先遍历该图所得顶点序列和边的序列；（2）广度优先遍历该图所得顶点序列和边的序列。
9.已知如图9所示的有向网，试利用Dijkstra算法求顶点1到其余顶点的最短路径，并给出算法执行过程中各步的状态。
图9 题9用图
10.下图是带权的有向图G的邻接表表示法。从结点V1出发，深度遍历图G所得结点序列为（A ），广度遍历图G所得结点序列为（B ）；G的一个拓扑序列是（ C ）；从结点V1到结点V8的最短路径为（D ）；从结点V1到结点V8的关键路径为（E ）。
其中A、B、C的选择有：
①V1,V2,V3,V4,V5,V6,V7,V8
②V1,V2,V4,V6,V5,V3,V7,V8
③V1,V2,V4,V6,V3,V5,V7,V8
④V1,V2,V4,V6,V7,V3,V5,V8
⑤V1,V2,V3,V8,V4,V5,V6,V7
⑥V1,V2,V3,V8,V4,V5,V7,V6
⑦V1,V2,V3,V8,V5,V7,V4,V6
D、E的选择有：
①V1,V2,V4,V5,V3,V8
②V1,V6,V5,V3,V8
③V1,V6,V7,V8
④ V1,V2,V5,V7,V8
11. 图是一个连通图，请画出：以顶点①为根的深度优先生成树；
12. 无向图采用邻接表作为存储结构，试写出以下算法 （1）求一个顶点的度； （2）往图中插入一个顶点； （3）往图中插入一条边； （4）删去图中某顶点； （5）删去图中某条边。
13. 使用普里姆和Kruskal 算法构造出如图所示的图G 的一棵最小生成树。
题10图
题13图
14.试基于图的深度优先搜索策略写一算法，判别以邻接表方式存储的有向图中是否存在由顶点vi到顶点vj的路径（i≠j）。注意：算法中涉及的图的基本操作必须在此存储结构上实现。
15.同14题要求。试基于图的广度优先搜索策略写一算法。
