北邮离散数学期末复习题[1]1

1、学习资料收集于网络，仅供参考离散数学期末复习题第一章集合论一、判断题（1）空集是任何集合的真子集（错）（2）是空集（错）（3） a a, a（对）（4）设集合 A1,2,1,2 ,则 1,22 A .( 对）（5）如果 a AB ，则 aA 或 aB （错）解 aAB 则 aABAB ，即 aA 且 aB ，所以 aA 且 a B（6）如果 A BB,则 AB.（对）（7）设集合 A a1 , a2 , a3 ， B b1 ,b2 ,b3 ，则A B a1 ,b1,a2 , b2,a3 ,b3 （ 错）（8）设集合 A 0,1， 则,0 ,1 ,0, 0 ,0,1 是2A到 A的关系（对）解

2、2 A, 0, 1, A ，2 AA,0,1,0,0, 0,1 ,1, 0 , 1, 1,A,0,A,1（9）关系的复合运算满足交换律（错）（10）是集合 A上的关系具有传递性的充分必要条件 .（错）（11）设是集合 A上的传递关系 , 则 也是 A上的传递关系 .(对)（12）集合 A 上的对称关系必不是反对称的 .（错）（13）设1, 2 为集合 A 上的等价关系 , 则12 也是集合 A上的等价关系( 对 )（14）设是集合 A 上的等价关系 ,则当a, b时， a b(对 )（15）设1, 2 为集合A 上的等价关系 , 则(错 )二、单项选择题（1）设 R 为实数集合，下列集合中哪一

3、个不是空集（ A）A. x | x21 0,且 x RB x | x29 0,且 x RC. x | x x 1, 且 x RD.x | x21, 且 x R学习资料学习资料收集于网络，仅供参考（2）设 A, B 为集合，若 AB，则一定有（ C）A. BB BC.A BD.A B（3）下列各式中不正确的是（ C）A.BC.D.,（4）设 Aa, a，则下列各式中错误的是（ B）A. a2 AB a2 AC. a2 AD. a2 A（5）设 A1,2 ，Ba, b, c ， Cc, d ，则 A ( BC ) 为（ B）A.c,1,2,cB1,c,2, cC.1, c,c,2D.c,1,c,2

4、（6）设 A0, b ， B1, b, 3，则 AB 的恒等关系为（ A）A.0,0,1,1,b,b,3,3B 0,0,1,1,3,3C.0,0,b, b,3,3D.0,1,1,b, b,3,3,0（7）设 Aa, b, c 上的二元关系如下，则具有传递性的为（ D）A.BC.D.1234a, c,c, a,a, b,b, aa, c,c, aa,b,c, c,b, a,b,ca,a（8）设为集合A 上的等价关系，对任意a A ，其等价类 a为（ B）A. 空集；B非空集；C.是否为空集不能确定；D. x | xA .（9）映射的复合运算满足（ B）A. 交换律B结合律C.幂等律D.分配律（1

5、0）设 A， B 是集合，则下列说法中（C ）是正确的 .AA 到 B 的关系都是 A 到 B 的映射B A 到 B 的映射都是可逆的C A 到 B 的双射都是可逆的D AB时必不存在 A到 B的双射学习资料学习资料收集于网络，仅供参考（11）设 A 是集合，则（ B）成立 .A #2A2# AB X2AXAC2AD A2A（12）设 A 是有限集（ # An ），则 A 上既是 又是的关系共有（B ） .A0 个B1 个C2 个D n 个三、填空题1. 设A 1, 2, 1,2，则 2A_.填 2A,1, 2, 1,2, 1,2, 1,1,2, 2,1,2,A2.设 A , ，则 2A=.填

6、 2 A , , A3. 设集合A, B 中元素的个数分别为 # A 5，#B 7，且 #(AB)9 ，则集合 AB 中元素的个数 # ( AB).34.设集合 A x |1x100, x是 4的倍数， xZ ，B x |1x 100, x是 5的倍数， xZ ，则A B 中元素的个数为.405.设A a,b ,是2 A上的包含于关系，, 则有=., a , b, A, a, a, a, A , b, b, b,A, A,A6.1 ,A 上的二元关系 ,设2 为集合则 12.217.集合 A 上的二元关系为传递的充分必要条件是8.设集合 A0, 1, 2 上的关系10, 2,2, 0及集合 A

7、 到集合 B0,2,4的关系2a, b|a, bAB且 a, bAB,则 12_.填 0,0, 0,2,2,0 ,2,2 四、解答题1.设A a, b, c, d, A 上的关系a, a, b, b,c,c,d , d, a,b, b, a,c, d,d ,c（ 1）写出 的关系矩阵；（ 2）验证 是 A 上的等价关系；（ 3）求出 A 的各元素的等价类。学习资料学习资料收集于网络，仅供参考解 （ 1）的关系矩阵为11001100M00110011（ 2）从 的关系矩阵可知： 是自反的和对称的。又由于110011001100M110011001100M0110011001M0100110011

8、0011或满足所以是传递的。因为是自反的、对称的和传递的，所以是 A 上的等价关系。（3） ab a, b ， c d c, d2. 设集合 A 1,2,3,6,8,12,24,36 ， 是 A 上的整除关系，（ 1） 写出 的关系矩阵 M ；（ 2）画出偏序集A,的哈斯图；（3） 求出 A 的子集 B 2,3,6 的最小上界和最大下界。11111111010111110011011100010111解：（ 1） M00010100000001110000001000000001（2）学习资料学习资料收集于网络，仅供参考（ 3） lubB=6,glbB=1五、证明题1. 设1 ,2 为集合 A

9、 上的等价关系 ,试证12 也是集合 A 上的等价关系。证明：由于1 ,2 是自反的，所以对任意aA ,a, a1 ,a, a2, 因而a, a12 ，即12 是自反的。若a, b12 ，则a,b1,a,b2, 由于1 , 2是对称的， 所以b, a1 ,b, a2 ,从而 b, a12，即12 是对称的。若a,b,b, c12，则a, b , b, c1 ,a, b , b, c2,由于1,2是传递的，所以a, c1 ,a, c2 ,从而a, c12 ，即12 是传递的。由于12 是自反的、对称的和传递的，所以12 是等价关系。第二章 代数系统一、判断题（1）集合 A 上的任一运算对 A 是

10、封闭的（对）（2）代数系统的零元是可逆元 .（ 错）（3）设 A是集合，: AAA ， a bb ，则是可结合的（对）（4）设 a, b是代数系统A,的元素， 如果 abb ae(e是该代数系统的单位元） ，则a 1b.(对)（5）设,b 是群G,的元素,则() 1a1b1.（ 错）aa b（6）设G ,是群如果对于任意a,bG ，有( a b)2a 2 b2，则G , 是阿贝尔群（对）（7）设 L, ,是格 ,则运算满足幂等律 .（对）（8）设集合 A a, b ，则, a, b,A,是格（对）（9）设B, ,是布尔代数，则B,是格（对）学习资料学习资料收集于网络，仅供参考二、单项选择题（1

11、）在整数集 Z 上，下列哪种运算是可结合的（ B）A.aba bB a b max a, bC.a b a 2bD.a b | a b |（2）下列定义的实数集R 上的运算 *中可结合的是 .（C）A abaa bB aba2abC abbD abab其中， +，·， 分别为实数的加法、乘法和取绝对值运算.（3）设集合 A1, 2, 3, 4, , 10 ，下面定义的哪种运算关于集合A 不是封闭的（ D）A.xymax x, yBxymin x, yC.xyGCD x, y ，即 x, y 的最大公约数D.xyLCM x, y ，即 x, y 的最小公倍数（4）下列哪个集关于减法运算

12、是封闭的（ B）A.N （自然数集）；B 2x | xZ (整数集 ) ；C. 2 x1 | xZ ；D. x | x是质数 .（5）设 Q 是有理数集，在Q 定义运算为 a ba bab ，则 Q,的单位元为（ D）A. a ；B b ；C. 1；D.0（6）设代数系统A，·，则下面结论成立的是 .（C）A 如果A，·是群，则A，· 是阿贝尔群B如果A，·是阿贝尔群，则A，· 是循环群C如果A，·是循环群，则A，·是阿贝尔群D如果A，·是阿贝尔群，则A，· 必不是循环群（7）循环群 Z,的所有生成元为（

13、 D）A.1 ，0B-1 ，2C. 1， 2D. 1， -1三、填空题学习资料学习资料收集于网络，仅供参考1.设 A 为非空有限集，代数系统2 A ,中， 2A对运算的单位元为，零元为.填, A2.代数系统Z ,中（其中Z 为整数集合，+为普通加法） ，对任意的x I ，其x 1.填x3.在整数集合 Z 上定义运算为 aba2b ，则Z ,的单位元为.解 设单位元为 e ， aea 2ea ，所以 e2 ，e2又 a (2)a2( 2)a, (2)a(2)2aa ，所以单位元为4.在整数集合 Z 上定义运算为 ababab ，则Z,的单位元为.解设单位元为 e ， aea eaea ， (1a

14、)e0 ，所以 e05.设 G,是群，对任意 a,b,cG ，如果 abac, ，则.填 bc6.设 G,是群， e 为单位元，若 G 元素 a 满足 a 2a ，则 a.填 e四、解答题1.设 为实数集 R 上的二元运算，其定义为: R2R,aba b2ab ，对于任意 a, bR求运算的单位元和零元。解：设单位元为e ，则对任意 aR ，有 aeae2aea ，即 e(12a)0 ，由 a 的任意性知e0 ，又对任意 aR ， a0a 00a ； 0a0a0a所以单位元为 0设零元为，则对任意 aR，有 aa2a，即a(12 )0，由 a 的任意性知12( 1) a111 )11又对任意

15、aR ， aa， (aa a1222222所以零元为22.设为集合 I5 0,1,2,3,4 上的二元运算，其定义为: I 52I 5 ,ab( ab) mod 5 ，对于任意 a, bI 5（ 1） 写出运算 的运算表；（ 2） 说明运算 是否满足交换律、结合律，是否有单位元和零元、如果有请指出；（ 3） 写出所有可逆元的逆元解：（ 1 ）运算表为学习资料学习资料收集于网络，仅供参考01234000000101234202413303142404321（2）运算满足交换律、结合律，有单 位元， 单位元为1，有 零元， 零元为 0；（3）1的逆元为 1，2 的逆元为 3，3 的逆元 为 2，4

16、 的逆元 4，0 没有逆元五、证明题1. 设G,是一个群，试证G 是交换群当且仅当对任意的a, b G , 有a 2b2(ab)2 .证明：充分性若在群G ,中，对任意的a, bG , 有 a2b2(ab) 2 .则(aa)(b b)(ab)(ab)a ( a b) b a (b a) bG,a b b a从而是一个交换群。必要性若G,是一个交换群，对任意的a, bG , 有 a bba ，则a (a b) b a (b a) b(a a) (bb) (a b)(ab)即 a2 b 2( a b)2 .2. 证明代数系统Z ,是群，其中二元运算定义如下： Z 2Z ， xyx y3（这里， +

17、，分别是整数的加法与减法运算.）证明 （ 1）运算满足交换律对任意 x, y, zZ ，由( x y ) z( xy3) zxyz 6 ,x ( y z)x ( yz 3 ) x y z 6得 ( xy )zx( yz ), 即满足结合律；（2）有单位元3 是单位元；（3）任意元素有逆元对任意 xZ ， x 16x.所以 , Z ，是群 .学习资料学习资料收集于网络，仅供参考第三章 图论一、判断题（1） n 阶完全图的任意两个不同结点的距离都为1.（对）（2）图 G 的两个不同结点 vi ,v j 连接时一定邻接 .（错）（3）图 G 中连接结点 vi,v j的初级通路为 vi , v j之间

18、的短程 .（错）（4）在有向图中，结点vi 到结点 v j的有向短程即为v j 到 vi 的有向短程（错）（5）强连通有向图一定是单向连通的（对）（6）不论无向图或有向图，初级回路一定是简单回路（对）（7）设图 G是连通的，则任意指定G的各边方向后所得的有向图是弱连通的（对）（8）有生成树的无向图是连通的（对）（9）下图所示的图是欧拉图 .（错）（10）下图所示的图有哈密尔顿回路.（对）二、单项选择题（1）仅由孤立点组成的图称为（ A）A. 零图；B平凡图；C.完全图；D.多重图 .（2）仅由一个孤立点组成的图称为（ B）A. 零图；B平凡图；C.多重图；D.子图 .（3）在任何图 G 中必有

19、偶数个（ B）A. 度数为偶数的结点；B度数为奇数的结点；C. 入度为奇数的结点；D.出度为奇数的结点 .（4）设 G 为有 n 个结点的无向完全图，则G 的边数为（ C）A. n(n1)B n(n1)C.n(n1) 2D.(n 1) 2（5）在有n 个结点的连通图G 中，其边数（ B）A. 最多 n1 条；B至少 n1 条；学习资料学习资料收集于网络，仅供参考C. 最多 n 条；D.至少 n 条.（6）任何无向图G 中结点间的连通关系是（ B）A. 偏序关系；B等价关系；C. 既是偏序关系又是等价关系；D.既不是偏序关系也不是等价关系.（7）对于无向图，下列说法中正确的是.（B）A 不含平行

20、边及环的图称为完全图B任何两个不同结点都有边相连且无平行边及环的图称为完全图C具有经过每条边一次且仅一次回路的图称为哈密尔顿图D具有经过每个结点一次且仅一次回路的图称为欧拉图（8）设 D 是有向图，则D 强连通的充分必要条件为.( C)A 略去 D 中各边方向后所得到的无向图是连通的B D 是单向连通图，且改变它的各边方向后所得到的有向图也是单向连通图C D 的任意两个不同的结点都可以相互到达D D 是完全图（9）对于无向图G，以下结论中 不正确 的是 .（ A）A 如果 G 的两个不同结点是连接的，则这两个结点之间有初级回路B如果 G 的两个不同结点是连接的，则这两个结点之间至少有一条短程C

21、如果 G 是树，则任何两个不同结点之间有且仅有一条初级通路D如果 G 是欧拉图，则G 有欧拉回路三、填空题1.设树 T 中有 7 片树叶， 3 个 3 度结点，其余都是4 度结点，则 T 中有个 4度结点 .解 用握手定理和树的性质列出方程求解，设有x 个 4 度结点，79 4x2(73 x1) ， x 12.设 TV , E为树， T 中有 4 度，3 度，2 度分支点各1 个，问T 中有片树叶。解 与上题解法相同，设有x 片树叶， 4 3 2x2(3x 1) ， x 53.n 阶完全图的任意两个不同结点的距离都为 14.图 G 为 n 阶无向完全图，则 G 共有条边。 n(n1)/25.设

22、 G 为 (n, m) 图，则图中结点度数的总和为。 2m6.图 G 为欧拉图的充分必要条件是 _. G 为无奇度结点的连通图四、解答题1. 对下图所示的图 G，求（1） G 的邻接矩阵 A ；（ 2） G 的结点 v1 ,v3 之间长度为 3 的通路；（ 3） G 的连接矩阵 C ；（ 4） G 的关联矩阵 M 。学习资料学习资料收集于网络，仅供参考v1v2v3v4v5v101110解 （1）v210101A=1 .v31101v410100v501100（2） 因为31212713221A2= 2241 1,A3=,1212121112所以，结点 v1, v3 之间长度为3 的通路共有7

23、条，它们是v1v3v1v3 ,v1v2 v5 v3 ,v1v2v1v3 ,v1v4v1v3 ,v1 v3 v5 v3 ,v1v3v2v3, v1v3 v4 v3 .（3）由于图G 是连通的，所以v1v2v3v4v5v111111v211111C= v311111 .v411111v511111（4）e1e2e3e4e5e6e7v11011000v21100001M = v3 0 110110 .v40001100v500000112. 在下面的有向图D 中，回答下列问题学习资料学习资料收集于网络，仅供参考（ 1）写出图 D 的邻接矩阵 A ；（ 2）写出结点 v1 到结点 v3 的长度为 3

24、的所有有向通路；（ 3）写出结点 v5 到自身的长度为 3 的所有有向回路；0000110100解：（1）A00110000010101001010101010011101121（2） A200111A30112101010101011010101121所以结点 v1 到结点 v3 的长度为3 的所有有向通路只有一条:v1v5 v2 v3（3）结点 v5 到自身的长度为3 的所有有向回路只有一条： v5v2v1v53. 在下面的无向图 G 中，回答下列问题aedbc（ 1）写出 a, d 之间的所有初级通路；（ 2）写出 a, d 之间的所有短程，并求d (a, d ) ；（ 3）判断无向图G

25、 是否为欧拉图并说明理由。解（ 1） a, d 之间的所有初级通路共有7 条，分别为aed ， aecd ， aebcd ， abed ， abcd ， abecd ， abced（2） a, d 之间的长度最短的通路只有1 条，即 aed ，因而它是a, d 之间唯一的短程，d( a, d)2（3）由于无向图G 中有两个奇度顶点deg(b)3, deg(c)3 ，所以无向图 G 没有欧学习资料学习资料收集于网络，仅供参考拉回路，因而不是欧拉图。第四章 数理逻辑一、判断题（1）“如果 8 7 2，则三角形有四条边”是命题（对）（2）设 P, Q 都是命题公式，则PQ 也是命题公式（错）（3）命题公式 P,