第七章 图
一、选择题www.tyutbbs.com( m2 T, u# v* l3 z% U
1.图中有关路径的定义是( )。【北方交通大学 2001 一、24 (2分)】; g; A: W8 V. Z# A1 a
A.由顶点和相邻顶点序偶构成的边所形成的序列 B.由不同顶点所形成的序列
; C4 V( M2 t. ]+ k( Q太原理工大学论坛[龙城水秀] C.由不同边所形成的序列 D.上述定义都不是
" J; I( ~: i+ V2 n3 p清泽论坛-太原理工大学网络家园 2.设无向图的顶点个数为n，则该图最多有( )条边。清泽论坛-太原理工大学网络家园' d( j& j+ U% n8 l8 ^3 B
A.n-1 B.n(n-1)/2 C. n(n+1)/2 D.0 E.n2www.tyutbbs.com$ M# k/ g$ N3 L& q3 H' v! M* n( C1 [
【清华大学 1998 一、5 (2分)】【西安电子科技大 1998 一、6 (2分)】太原理工大学|太原理工大学论坛|太原理工大学BBS" R4 T$ v0 @: O- T. ~" \4 {
【北京航空航天大学 1999 一、7 (2分)】www.tyutbbs.com& t. x/ G: t! D q/ d& g/ j
3.一个n个顶点的连通无向图，其边的个数至少为( )。【浙江大学 1999 四、4 (4分)】
- b+ [5 r+ Q" K/ x太原理工大学|太原理工大学论坛|太原理工大学BBS A.n-1 B.n C.n+1 D.nlogn;太原理工大学论坛[龙城水秀]9 w2 |6 |% |. `2 l T% K
4.要连通具有n个顶点的有向图，至少需要( )条边。【北京航空航天大学 2000 一、6(2分)】
, O* g8 }1 s* R5 M5 H4 k太原理工大学,太原理工大学论坛 A.n-l B.n C.n+l D.2n清泽论坛-太原理工大学网络家园 t" _/ Z: S' W# d& `- V6 b
5.n个结点的完全有向图含有边的数目( )。【中山大学 1998 二、9 (2分)】太原理工大学,太原理工大学论坛0 E6 ~5 m7 D# D# k0 K
A.n*n B.n(n+1) C.n/2 D.n*(n-l)
/ q+ j% e2 |4 }/ V- M太原理工大学|太原理工大学论坛|太原理工大学BBS 6.一个有n个结点的图，最少有( )个连通分量，最多有( )个连通分量。
* F- @5 e7 ^& \9 p& ^ a" `清泽论坛-太原理工大学网络家园 A.0 B.1 C.n-1 D.n太原理工大学,太原理工大学论坛/ s7 K* a5 y1 P
【北京邮电大学 2000 二、5 (20/8分)】www.tyutbbs.com9 y5 K9 R/ P6 b. h# D" d' ?
7.在一个无向图中，所有顶点的度数之和等于所有边数( )倍，在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的( )倍。【哈尔滨工业大学 2001 二、3 (2分)】
; a W: g8 T, e/ q. Y清泽论坛-太原理工大学网络家园 A.1/2 B.2 C.1 D.4
}( l) m8 q; z, A+ j) I太原理工大学,太原理工大学论坛 8.用有向无环图描述表达式(A+B)*((A+B)/A)，至少需要顶点的数目为( )。【中山大学1999一、14】
. g1 v* T7 Z$ w K2 lwww.tyutbbs.com A.5 B.6 C.8 D.9
# v2 i6 N2 `4 s. s太原理工大学论坛[龙城水秀] 9.用DFS遍历一个无环有向图，并在DFS算法退栈返回时打印相应的顶点，则输出的顶点序列是( )。www.tyutbbs.com9 o; ^* e/ D& `' h* X/ b9 E
A.逆拓扑有序 B.拓扑有序 C.无序的 【中科院软件所 1998】
5 X# G! m% E& H+ G$ K6 @www.tyutbbs.com 10.下面结构中最适于表示稀疏无向图的是( )，适于表示稀疏有向图的是( )。太原理工大学|太原理工大学论坛|太原理工大学BBS. s1 r) ?& U( m
A.邻接矩阵 B.逆邻接表 C.邻接多重表 D.十字链表 E.邻接表
7 v% H7 {) w3 f) X1 d( b( r太原理工大学论坛[龙城水秀] 【北京工业大学 2001 一、3 (2分)】
