一、选择题
1.图中有关路径的定义是（）。
A.由顶点和相邻顶点序偶构成的边所形成的序列
B.由不同顶点所形成的序列
C.由不同边所形成的序列
D.上述定义都不是
2.设无向图的顶点个数为n，则该图最多有（）条边。
A.n-1
B.n（n-1）/2
C.n（n+1）/2
D.0
3.一个n个顶点的连通无向图，其边的个数至少为（）。
A.n-1
 B.n
C.n+1
 D.nlogn；
4.要连通具有n个顶点的有向图，至少需要（）条边。
.n-1
 B.n
C.n+1
 D.2n
5.n个结点的完全有向图含有边的数目（）。
 A.n＊n
B.n（n+1）
C.n/2
D.n（n-1）
6.一个有n个结点的图，最少有（）个连通分量，最多有（）个连通分量。
A.0
B.1
C.n-1
 D.n
7.下列关于图的叙述中，正确的是（）
1.回路是简单路径
Ⅱ.存储稀疏图，用邻接矩阵比邻接表更省空间
Ⅲ.若有向图中存在拓扑序列，则该图不存在回路
A.仅Ⅱ
B.仅I、Ⅱ
C.仅Ⅲ
D.仅、Ⅲ
8.用有向无环图描述表达式（A+B）＊（（+B）/A），至少需要顶点的数目为（）。
A.5
B.6
C.8
D.9
9.用DFS遍历一个无环有向图，并在DFS算法退栈返回时打印相应的顶点，则输出的顶点序列是（）
A.逆拓扑有序
B.拓扑有序
C.无序的
D.按值有序的
10.下面结构中最适于表示稀疏无向图的是（），适于表示稀疏有向图的是（）
A.邻接矩阵
B.逆邻接表
C.邻接多重表
D.十字链表
E.邻接表
二、应用题
1.证明:具有n个顶点和多于n-1条边的无向连通图G一定不是树。
2.证明:对有向图的顶点适当的编号，可使其邻接矩阵为下三角形且主对角线为全0的充要条件是该图为无环图。
3.请回答下列关于图（ Graph）的一些问题:
（1）有n个顶点的有向强连通图最多有多少条边？最少有多少条边？
（2）表示有1000个顶点、1000条边的有向图的邻接矩阵有多少个矩阵元素？是否稀疏矩阵？
（3）对于一个有向图，不用拓扑排序，如何判断图中是否存在环？
4.欲用四种颜色对地图上的国家涂色，有相邻边界的国家不能用同一种颜色（点相交不算相邻）。
（1）试用一种数据结构表示地图上各国相邻的关系，
（2）描述涂色过程的算法。（不要求证明）