离散数学形成性考核作业（三）
集合论与图论综合练习
本课程形成性考核作业共4次，内容由中央电大确定、统一布置。本次形考作业是第三次作业，大家要认真及时地完成图论部分的形考作业，字迹工整，抄写题目，解答题有解答过程。
一、单项选择题
1．若集合A＝{2，a，{ a }，4}，则下列表述正确的是( B )．
A．{a，{ a }}A B．{ a }A
C．{2}A D．∅A
2．设B = { {2}, 3, 4, 2}，那么下列命题中错误的是（ B ）．A．{2}∈B B．{2, {2}, 3, 4}B
C．{2}B D．{2, {2}}B
3．若集合A={a，b，{1，2 }}，B={1，2}，则（ B ）．
A．B A，且B A B．B A，但B A
C．B A，但B A D．B A，且B A
4．设集合A = {1, a }，则P(A) = ( C )．
A．{{1}, {a}} B．{∅,{1}, {a}}
C．{∅,{1}, {a}, {1, a }} D．{{1}, {a}, {1, a }}
5．设集合A= {1，2，3，4，5，6 }上的二元关系R ={a, b∈A, 且a +b = 8}，则R具有的性质为（ B ）．
A．自反的 B．对称的
C．对称和传递的 D．反自反和传递的
6．设集合A= {1，2，3，4，5 }，B= {1，2，3}，R从A到B的二元关系，R ={a∈A，b∈B且1
a}
=
-b
则R具有的性质为（）．
A．自反的 B．对称的 C．传递的 D．反自反的
[注意]：此题有误！自反性、反自反性、对称性、反对称性以及传递性指某一个集合上的二元关系的性质。
7．设集合A={1 , 2 , 3 , 4}上的二元关系
R = {<1 , 1>，<2 , 2>，<2 , 3>，<4 , 4>}，S = {<1 , 1>，<2 , 2>，<2 , 3>，<3 , 2>，<4 , 4>}，
则S是R的（ C ）闭包．
A．自反 B．传递 C．对称 D．以上都不对8．非空集合A上的二元关系R，满足( A )，则称R是等价关系．
A．自反性，对称性和传递性 B．反自反性，对称性和传递性C．反自反性，反对称性和传递性 D．自反性，反对称性和传递性
9．设集合A ={a , b }，则A 上的二元关系R={，}是A 上的( C )关系．
A ．是等价关系但不是偏序关系
B ．是偏序关系但不是等价关系
C ．既是等价关系又是偏序关系
D ．不是等价关系也不是偏序关系
10．设集合A = {1 , 2 , 3 , 4 , 5}上的偏序关系
的哈斯图如右图所示,若A 的子集B = {3 , 4 , 5}， 则元素3为B 的（ C ）．
A ．下界
B ．最大下界
C ．最小上界
D ．以上答案都不对 11．设函数f ：R →R ，f (a ) = 2a + 1；g ：R →R ，g (a ) = a 2
．则（ C ）有反函数．
A ．g f
B ．f g
C ．f
D ．g 12．设图G 的邻接矩阵为
⎥⎥⎥⎥⎥
⎥⎦
⎤⎢⎢⎢⎢⎢⎢⎣⎡0101010010000011100000100
则G 的边数为( D )．
A ．5
B ．6
C ．3
D ．4
13．下列数组中，能构成无向图的度数列的数组是( C ) ． A ．(1, 1, 2, 3) B ．(1, 2, 3, 4, 5) C ．(2, 2, 2, 2) D ．(1, 3, 3)
14．设图G ＝，则下列结论成立的是 ( C )． A ．deg(V )=2E B ．deg(V )=E
C ．E v V
v 2)deg(=∑∈ D ．E v V
v =∑∈)deg(
解；C 为握手定理。
15．有向完全图D ＝， 则图D 的边数是( D )．
A ．E (E －1)/2
B ．V (V －1)/2
C ．E (E －1)
D ．V (V －1) 解：有向完全图是任意两点间都有一对方向相反的边的
图，其边数应为D ，即)1(2-=V V P v
16．给定无向图G 如右图所示，下面给出的结点
集子集中，不是点割集的为（ A ） A ．{b , d } B ．{d }
C ．{a , c }
D ．{g , e }
17．设G 是连通平面图，有v 个结点，e 条边，r 个面，则r = ( A )．
A ．e －v ＋2
B ．v ＋e －2
C ．e －v －2
D ．e ＋v ＋2
2
4 1 3
5 a g
d
f
c e
18．无向图G 存在欧拉通路，当且仅当( D )．
A ．G 中所有结点的度数全为偶数
B ．G 中至多有两个奇数度结点
C ．G 连通且所有结点的度数全为偶数
D ．G 连通且至多有两个奇数度结点
19．设G 是有n 个结点，m 条边的连通图，必须删去G 的( A )条边，才能确定G 的一棵生成树．
A ．1m n -+
B ．m n -
C ．1m n ++
D ．1n m -+ 20．已知一棵无向树T 中有8个结点，4度，3度，2度的分支点各一个，T 的树叶数为 B ． A ．8 B ．5 C ．4 D ． 3
二、填空题
1．设集合A B =={,,},{,}12312，则A ⋃B = {1，2，3}=A ，
A ⋂
B = B ，A – B = {3} ，P (A )-P (B )= {{3},{1,3},{2,3},{1,2,3} } ．
2．设A , B 为任意集合，命题A B 的条件是 B A ⊆ ． 3．设集合A 有n 个元素，那么A 的幂集合P (A )的元素个数为 n 2 ． 4．设集合A = {1，2，3，4，5，6 }，A 上的二元关系A b a b a R ∈><=,,{且1=-b a }，则R 的集合表示式为
}5,6,6,5,4,5,5,4,3,4,4,3,2,3,3,2,1,2,2,1{〉〈〉〈〉〈〉〈〉〈〉〈〉〈〉〈〉〈〉〈 ．
5．设集合A = {1，2，3，4，5 }，B = {1，2，3}，R 从A 到B 的二元关系， R ={a ∈A ，b ∈B 且2≤a + b ≤4}
则R 的集合表示式为 }1,3,2,2,1,2,3,1,2,1,1,1{〉〈〉〈〉〈〉〈〉〈〉〈 ．
6．设集合A ={0,1,2},B ={0,2,4},R 是A 到B 的二元关系，
},,{B A y x B y A x y x R ⋂∈∈∈><=且且
则R 的关系矩阵M R ＝⎪⎪⎪
⎭
⎫ ⎝⎛011000011
．
7．设集合A ={1, 2, 3, 4 }，B ={6, 8, 12}， A 到B 的二元关系
R ＝},,2,{B y A x x y y x ∈∈=>< 那么R －1
＝
}4836{}8463{1〉〈〉〈=〉〈〉〈=-，，，，所以，，，
解：R R 8．设集合A ={a ,b ,c }，A 上的二元关系
R ={,}，S ={,,} 则(R
S )－1= ．
