文档介绍：第七章图
一、选择题
( )。【北方交通大学 2001 一、24 (2分)】
,则该图最多有( )条边。
-1 (n-1)/2 C. n(n+1)/2
【清华大学 1998 一、5 (2分)】【西安电子科技大 1998 一、6 (2分)】
【北京航空航天大学 1999 一、7 (2分)】
,其边的个数至少为( )。【浙江大学 1999 四、4 (4分)】
-1 +1 ;
,至少需要( )条边。【北京航空航天大学 2000 一、6(2分)】
-l +l
( )。【中山大学 1998 二、9 (2分)】
*n (n+1) *(n-l)
,最少有( )个连通分量,最多有( )个连通分量。
-1
【北京邮电大学 2000 二、5 (20/8分)】
,所有顶点的度数之和等于所有边数( )倍,在一个有向图中,所有顶点的入度之和等于所有顶点出度之和的( )倍。【哈尔滨工业大学 2001 二、3 (2分)】
(A+B)*((A+B)/A),至少需要顶点的数目为( )。【中山大学1999一、14】
,并在DFS算法退栈返回时打印相应的顶点,则输出的顶点序列是( )。
【中科院软件所 1998】
( ),适于表示稀疏有向图的是( )。
【北京工业大学 2001 一、3 (2分)】
?( )【北方交通大学 2001 一、11 (2分)】
12. 从邻接阵矩可以看出,该图共有(①)个顶点;如果是有向图该图共有(②) 条弧;如果是无向图,则共有(③)条边。【中科院软件所 1999 六、2(3分)】
①.
②.
③.
,顶点Vi的度是( )。【南京理工大学1998一、4(2分)】
A. B. C. D.+
,判定任意两个顶点Vi和Vj之间是否有长度为m 的路径相连,则只要检查( )的第i行第j列的元素是否为零即可。【武汉大学 2000 二、7】
-1
15. 下列说法不正确的是( )。【青岛大学 2002 二、9 (2分)】
:深度遍历和广度遍历
=(V,E),其中:V={a,b,c,d,e,f},E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)},对该图进行深度优先遍历,得到的顶点序列正确的是( )。【南京理工大学 2001 一、14 ()】
,b,e,c,d,f ,c,f,e,b,d ,e,b,c,f,d ,e,d,f,c,b
17. 设图如右所示,在下面的5个序列中,符合深度优先遍历的序列有多少?( )
【南京理工大学 2000 一、20 ()】
a e b d f c a c f d e b a e d f c b a e f d c b a e f d b c
第17题图第18题图
。从顶点1出发,对它进行深度优先遍历得到的序列是( ①),而进行广度优先遍历得到的顶点序列是( ②)。【中科院软件所 1999 六、2-(1)(2分)】
①.
②.