第七章 图
一,选择题
1.图中有关路径的定义是( ).【北方交通大学 2001 一,24 (2分)】
A.由顶点和相邻顶点序偶构成的边所形成的序列 B.由不同顶点所形成的序列
C.由不同边所形成的序列 D.上述定义都不是
2.设无向图的顶点个数为n,则该图最多有( )条边.
A.n-1 B.n(n-1)/2 C. n(n+1)/2 D.0 E.n2
【清华大学 1998 一,5 (2分)】【西安电子科技大 1998 一,6 (2分)】
【北京航空航天大学 1999 一,7 (2分)】
3.一个n个顶点的连通无向图,其边的个数至少为( ).【浙江大学 1999 四,4 (4分)】
A.n-1 B.n C.n+1 D.nlogn;
4.要连通具有n个顶点的有向图,至少需要( )条边.【北京航空航天大学 2000 一,6(2分)】
A.n-l B.n C.n+l D.2n
5.n个结点的完全有向图含有边的数目( ).【中山大学 1998 二,9 (2分)】
A.n*n B.n(n+1) C.n/2 D.n*(n-l)
6.一个有n个结点的图,最少有( )个连通分量,最多有( )个连通分量.
A.0 B.1 C.n-1 D.n
【北京邮电大学 2000 二,5 (20/8分)】
7.在一个无向图中,所有顶点的度数之和等于所有边数( )倍,在一个有向图中,所有顶点的入度之和等于所有顶点出度之和的( )倍.【哈尔滨工业大学 2001 二,3 (2分)】
A.1/2 B.2 C.1 D.4
8.用有向无环图描述表达式(A+B)*((A+B)/A),至少需要顶点的数目为( ).【中山大学1999一,14】
A.5 B.6 C.8 D.9
9.用DFS遍历一个无环有向图,并在DFS算法退栈返回时打印相应的顶点,则输出的顶点序列是( ).
A.逆拓扑有序 B.拓扑有序 C.无序的 【中科院软件所 1998】
10.下面结构中最适于表示稀疏无向图的是( ),适于表示稀疏有向图的是( ).
A.邻接矩阵 B.逆邻接表 C.邻接多重表 D.十字链表 E.邻接表
【北京工业大学 2001 一,3 (2分)】
11.下列哪一种图的邻接矩阵是对称矩阵 ( )【北方交通大学 2001 一,11 (2分)】
A.有向图 B.无向图 C.AOV网 D.AOE网
12. 从邻接阵矩可以看出,该图共有(①)个顶点;如果是有向图该图共有(②) 条弧;如果是无向图,则共有(③)条边.【中科院软件所 1999 六,2(3分)】
①.A.9 B.3 C.6 D.1 E.以上答案均不正确
②.A.5 B.4 C.3 D.2 E.以上答案均不正确
③.A.5 B.4 C.3 D.2 E.以上答案均不正确
13.当一个有N个顶点的图用邻接矩阵A表示时,顶点Vi的度是( ).【南京理工大学1998一,4(2分)】
A. B. C. D.+
14.用相邻矩阵A表示图,判定任意两个顶点Vi和Vj之间是否有长度为m 的路径相连,则只要检查( )的第i行第j列的元素是否为零即可.【武汉大学 2000 二,7】
A.mA B.A C.Am D.Am-1
15. 下列说法不正确的是( ).【青岛大学 2002 二,9 (2分)】
A.图的遍历是从给定的源点出发每一个顶点仅被访问一次 C.图的深度遍历不适用于有向图
B.遍历的基本算法有两种:深度遍历和广度遍历 D.图的深度遍历是一个递归过程
16.无向图G=(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 (1.5分)】

下一页