2022年离散数学期末考试复习题.docx

《2022年离散数学期末考试复习题.docx》由会员分享，可在线阅读，更多相关《2022年离散数学期末考试复习题.docx（62页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选学习资料 - - - - - - - - - 、判定题（共 5 道小题,共 50.0 分）1. 假如,就或A. 正确B. 错误学问点 : 集合同学答案 : B; 得分 : 10 试题分值 : 10.0 提示 : 2. 设为集合上的等价关系 , 就A. 正确B. 错误学问点 : 关系同学答案 : B; 得分 : 10 试题分值 : 10.0 提示 : 3. 设为集合上的等价关系 , 就也是集合上的等价关系A. 正确B. 错误学问点 : 关系同学答案 : A; 得分 : 10 试题分值 : 10.0 提示 : 4. 设A. 正确B. 错误学问点 : 关系同学答案 : A; 名师归纳总结 - -

2、 - - - - -第 1 页,共 40 页精选学习资料 - - - - - - - - - 得分 : 10 试题分值 : 10.0 提示 : 5. 错误 设集合正确,就A.错误B.关系学问点 : 同学答案 : A; 得分 : 0 试题分值 : 10.0 提示 : 二、单项挑选题（共 5 道小题,共 50.0 分）1. 设 A,B,C是集合,就（）成立 . A. 假如B. 假如C. 假如D. 假如学问点 : 集合同学答案 : B; 得分 : 10 试题分值 : 10.0 提示 : 2. 设,就以下各式中错误选项A.B.C.名师归纳总结 - - - - - - -第 2 页,共 40 页精选学习

3、资料 - - - - - - - - - D.学问点 : 集合同学答案 : B; 得分 : 10 试题分值 : 10.0 提示 : 3. 错误 以下各式中不正确选项A.B.C.D.学问点 : 集合同学答案 : B; 得分 : 0 试题分值 : 10.0 提示 : 4. 设 为实数集合,以下集合中哪一个不是空集A.B.C.D.学问点 : 集合同学答案 : A; 得分 : 10 试题分值 : 10.0 提示 : 名师归纳总结 - - - - - - -第 3 页,共 40 页精选学习资料 - - - - - - - - - 5. 设,就的恒等关系为A.B.C.D.学问点 : 关系同学答案 : A;

4、 得分 : 10 试题分值 : 10.0 提示 : 一、判定题（共 5 道小题,共 50.0 分）1. 设是代数系统的元素,假如是该代数系统的单位元）,就A. 正确B. 错误学问点 : 代数系统的基本概念同学答案 : A; 得分 : 10 试题分值 : 10.0 提示 : 2. 集合 A上的任一运算对 A是封闭的A. 正确B. 错误学问点 : 代数系统的基本概念同学答案 : A; 得分 : 10 试题分值 : 10.0 提示 : 名师归纳总结 - - - - - - -第 4 页,共 40 页精选学习资料 - - - - - - - - - 3. 设是群假如对于任意,有,就是阿贝尔群A.正确错

5、误B.群、环和域学问点 : 同学答案 : A; 得分 : 10 试题分值 : 10.0 提示 : 4. 设是布尔代数,就对任意,有A. 正确B. 错误学问点 : 格和布尔代数同学答案 : A; 得分 : 10 试题分值 : 10.0 提示 : 5. 设集合,就是格A. 正确B. 错误学问点 : 格和布尔代数同学答案 : A; 得分 : 10 试题分值 : 10.0 提示 : 二、单项挑选题（共 5 道小题,共 50.0 分）1. 以下哪个集关于减法运算是封闭的A.（自然数集）B.C.D.名师归纳总结 - - - - - - -第 5 页,共 40 页精选学习资料 - - - - - - - -

6、 - 学问点 : 代数系统的基本概念同学答案 : B; 得分 : 10 试题分值 : 10.0 提示 : 2.以下定义的实数集 R上的运算 * 中可结合的是A.B.C.D.学问点 : 代数系统的基本概念同学答案 : c 得分 : 0 试题分值 : 10.0 提示 : 3. 在整数集 上,以下哪种运算是可结合的A.B.C.D.学问点 : 代数系统的基本概念同学答案 : B; 得分 : 10 试题分值 : 10.0 提示 : 4.名师归纳总结 循环群1,0 的全部生成元为第 6 页,共 40 页A.B.-1 ,2- - - - - - -精选学习资料 - - - - - - - - - C. 1,

7、2 D. 1,-1学问点 : 群、环和域同学答案 : D 得分 : 0 试题分值 : 10.0 提示 : 5.设代数系统A,.,就下面结论成立的是 . A.假如A,.是群,就A,.是阿贝尔群B.假如A,.是阿贝尔群,就A,.是循环群是循环群,就是阿贝尔群C.假如A,.A,.是阿贝尔群,就必不是循环群D.假如A,.A,.学问点 : 群、环和域同学答案 : C 得分 : 0 试题分值 : 10.0 提示 : 一、判定题（共 5 道小题,共 50.0 分）1. 强连通有向图肯定是单向连通的A. 正确B. 错误学问点 : 无向图和有向图同学答案 : A; 得分 : 10 试题分值 : 10.0 提示

8、: 2. 有生成树的无向图是连通的名师归纳总结 A.正确第 7 页,共 40 页- - - - - - -精选学习资料 - - - - - - - - - B. 错误学问点 : 树同学答案 : A; 得分 : 10 试题分值 : 10.0 提示 : 3. 设 P,Q都是命题公式,就A. 正确B. 错误学问点 : 命题规律同学答案 : A; 得分 : 10 试题分值 : 10.0 提示 : 4. 设都是命题公式,就也是命题公式A. 正确B. 错误学问点 : 命题规律同学答案 : B; 得分 : 10 试题分值 : 10.0 提示 : 5. “ 假如 872,就三角形有四条边” 是命题A. 正确B

9、. 错误学问点 : 命题规律同学答案 : A; 得分 : 10 试题分值 : 10.0 提示 : 6.二、单项挑选题（共5 道小题,共 50.0 分）第 8 页,共 40 页名师归纳总结 - - - - - - -精选学习资料 - - - - - - - - - 1.设 G1= V1, E1 , G2= V2, E2 都是无向图,就 #V1=#V2且#E1=#E2 是 G1与 G2同构的A. 充分必要条件B. 充分而非必要条件C. 必要而非充分条件D. 既非充分又非必要条件学问点 : 无向图和有向图同学答案 : C 得分 : 0 试题分值 : 10.0 提示 : 2.有向图,其中是,A.,就有

10、向图强连通图单向连通图B.弱连通图C.不连通图D.无向图和有向图学问点 : 同学答案 : C 得分 : 0 试题分值 : 10.0 提示 : 3.是无向图的关联矩阵,是中的孤立点,就名师归纳总结 A.对应的一行元素全为0第 9 页,共 40 页对应的一行元素全为B.1对应的一列元素全为C.0- - - - - - -精选学习资料 - - - - - - - - - D.对应的一列元素全为1图的矩阵表示学问点 : 同学答案 : A; 得分 : 10 试题分值 : 10.0 提示 : 4.由前提QS得到的有效结论为A.B.C.PD.学问点 : 命题规律同学答案 : C 得分 : 0 试题分值 :

11、10.0 提示 : 5. 设个体域,公式在上消去量词后应为A.B.C.D.学问点 : 一阶规律同学答案 : B; 得分 : 10 试题分值 : 10.0 提示 : 离散数学期末复习题第一章集合论名师归纳总结 - - - - - - -第 10 页,共 40 页精选学习资料 - - - - - - - - - 一、判定题（1）空集是任何集合的真子集（错）是2A到A的关（2）是空集（错）（3）aa ,a（对）（4）设集合A,12,12,就1 ,22A. 对）（5）假如aAB,就aA或aB（错）解aAB就aABAB,即aA且aB,所以aA且aB（6）假如 ABB,就AB.（对）（7）设集合Aa 1,

12、a2,a3,Bb 1,b 2,b 3,就ABa1,b 1,a2,b2,a 3,b 3（错）（8）设集合A01,就,0,1,0 ,0,0 ,1系（对）解2A,0 ,1 ,A ,2AA,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时,ab 对

13、（15）设1,2为集合A 上的等价关系 , 就 错 二、单项挑选题（1）设 R为实数集合,以下集合中哪一个不是空集B90,且xRR,B（ A ）第 11 页,共 40 页A. x|x210 ,且xR Bx|x2C. x|xx,1且xR D. x|x2,1且xA（ C ）（2）设A,B为集合,如AB,就肯定有 D. A. B B B C. A D. （ C ）（3）以下各式中不正确选项A. B C. 名师归纳总结 - - - - - - -精选学习资料 - - - - - - - - - （4）设 A a , a ,就以下各式中错误选项（ B ）A A A AA. a 2 Ba 2 C. a 2

14、 D. a 2（5）设 A ,1 2,B a , b , c,C c , d,就 A B C 为（ B ）A. c 1, , 2 , c B,1 c , 2 , cC. ,1 c , c , 2 D. c 1, , c , 2（6）设 A 0 , b,B ,1 b , 3,就 A B 的恒等关系为（A ）A. 0 , 0 , 1,1 , b , b , 3 3, B0 , 0 , 1,1 , 3 3,C. 0 0, , b , b , 3 3, D. 1,0 , ,1 b , b , 3 , 3 0,（7）设 A a , b , c 上的二元关系如下,就具有传递性的为（ D ）A. 1 a ,

15、 c , c , a , a , b , b , aB2 a , c , c , aC. 3 a , b , c , c , b , a , b , cD. 4 a, a（8）设 为集合 A上的等价关系,对任意 a A,其等价类 a 为（ B ）A. 空集； B非空集； C. 是否为空集不能确定； D. x | x A . （9）映射的复合运算满意（ B ）A. 交换律 B结合律 C. 幂等律 D. 安排律（10）设 A,B 是集合,就以下说法中（C ）是正确的 . AA 到 B 的关系都是 A 到 B 的映射BA 到 B 的映射都是可逆的CA 到 B 的双射都是可逆的DAB时必不存在A 到

16、B 的双射又是的关系共有（ B ）.（11）设 A 是集合,就（B ）成立 . A# 2A2#ABX2AXAC2ADA2A（12）设 A 是有限集（#An）,就 A 上既是A0 个B1 个C2 个D n 个名师归纳总结 - - - - - - -第 12 页,共 40 页精选学习资料 - - - - - - - - - 三、填空题1. 设A,12,12 ,就2A_. ,A 填2A,1 ,2 ,1 ,2 ,12 ,1,12 ,2,12 ,A 2. 设A,就A 2 = . 填2A,3. 设集合A,B中元素的个数分别为# A5,# B7,且#AB9,就集合AB中元素的个数#AB .3 .40 4.

17、设集合Ax|1x100,x 是4 的倍数,xZ,Bx|1x100 ,x是5 的倍数,xZ,就AB中元素的个数为5. 设Aa,b , 是2A上的包含于关系, 就有= . ,a,b ,A,a ,a ,a,A,b ,b,b ,A,A ,A0 ,2,4的 关 系26. 设1,2为集合A 上的二元关系 , 就12,20B .217. 集合 A上的二元关系为传递的充分必要条件是8. 设 集 合A0 ,1 ,2上的关系10 ,2及 集 合A到 集 合a,b|a,bAB且a,bAB, 就12_ . 填00,0,2,2,0,2 ,2四、解答题1. 设Aa,b,c,d,A上的关系a,c ,d,d,ca ,a,b,

18、b,c,c,d,d,a,b,b ,（1）写出的关系矩阵；（2）验证是 A上的等价关系；（3）求出 A 的各元素的等价类；解 （1）的关系矩阵为1100M110000110011（2）从的关系矩阵可知：是自反的和对称的；又由于所以110011001100M第 13 页,共 40 页MM110011001100001100110011001100110011或满意是传递的；名师归纳总结 由于是自反的、对称的和传递的,所以是 A上的等价关系；- - - - - - -精选学习资料 - - - - - - - - - （3） a b a , b , c d c , d 2. 设集合 A 1 , 2 ,

19、 3 6, 8, , 12 , 24 , 36 ,是 A 上的整除关系,（1）写出 的关系矩阵 M；（2）画出偏序集 A , 的哈斯图；（3）求出 A 的子集 B 2 3, , 6 的最小上界和最大下界；1 1 1 1 1 1 1 10 1 0 1 1 1 1 10 0 1 1 0 1 1 10 0 0 1 0 1 1 1解：（1）M0 0 0 0 1 0 1 00 0 0 0 0 1 1 10 0 0 0 0 0 1 00 0 0 0 0 0 0 1（2）（3）lubB=6, glbB=1五、证明题1. 设 1, 2 为集合 A上的等价关系 , 试证 1 2 也是集合 A 上的等价关系；证明

20、：由于 1, 2 是自反的,所以对任意 a A , a , a 1 , a , a 2 , 因而 a , a 1 2,即1 2 是自反的；如 a ,b 1 2, 就 a , b 1 , a , b 2 , 由 于 1, 2 是 对 称 的 , 所 以b , a 1 , b , a 2 , 从而 b ,a 1 2,即 1 2 是对称的；如 a , b , b , c 1 2,就 a , b , b , c 1 , a , b , b , c 2 , 由于 1, 2 是传递的,所以 a , c 1 , a , c 2 , 从而 a , c 1 2,即 1 2 是传递的；由于 1 2 是自反的、对称

21、的和传递的,所以 1 2 是等价关系；其次章 代数系统一、判定题（1）集合 A 上的任一运算对A 是封闭的b,就是可结合的（对）第 14 页,共 40 页（2）代数系统的零元是可逆元. （错）（3）设 A 是集合,:AAA,ab（对）名师归纳总结 - - - - - - -精选学习资料 - - - - - - - - - （ 4 ） 设a,b是 代 数 系 统A ,的 元 素 , 如 果abbae e是 该 代 数 系 统 的 单 位 元 ）, 就a1b. 对 , 有（错）（5）设a ,b是群G,的元素,就ab 1a1b1.（ 6 ） 设G,是 群 如 果 对 于 任 意a,bGab 2a2b

22、2, 就G,是 阿 贝 尔群（对）（7）设L,是格,就运算满意幂等律.（对）（对）（8）设集合Aa ,b ,就,a,b ,A ,是格（9）设B,是布尔代数,就B,是格（对）二、单项挑选题（1）在整数集 Z 上,以下哪种运算是可结合的（ B ）第 15 页,共 40 页C ）A. abab Babmaxa ,b C. aba2 D. ab|ab|（2）以下定义的实数集R 上的运算* 中可结合的是 . （A abaabA不是封闭的Baba2abCabbDabab其中, +, , 分别为实数的加法、乘法和取肯定值运算. （3）设集合A,12 ,3 ,4,10,下面定义的哪种运算关于集合A. xyma

23、xx ,y （ D ）Bxyminx ,y （ B ）C. xyGCDx,y ,即x,y的最大公约数D. xyLCMx,y ,即x,y的最小公倍数（4）以下哪个集关于减法运算是封闭的A. N（自然数集） ； B2x|xZ整数集；Q ,的单位元C. 2x1|xZ； D. x|x 是质数. （5）设 Q 是有理数集,在Q 定义运算为ababab,就为（ D ）A. a ； B b ； C. 1； D. 0 （C ）（6）设代数系统A,就下面结论成立的是. A假如A,是群,就A,是阿贝尔群名师归纳总结 - - - - - - -精选学习资料 - - - - - - - - - B假如A,是阿贝尔群,

24、就A,是循环群,-1 （ D ）C假如A,是循环群,就A,是阿贝尔群D假如A,是阿贝尔群,就A,必不是循环群（7）循环群Z的全部生成元为,2 D. 1A. 1 ,0 B-1 ,2 C. 1三、填空题1. 设 A为非空有限集,代数系统2A,中,2 对运算 A的单位元为,零元为 .填,A填2. 代数系统Z,中（其中 Z 为整数集合, +为一般加法） ,对任意的xI,其x1x3. 在整数集合 Z 上定义运算为aba2b,就Z,的单位元为 . 解 设单位元为 e ,ae 2aa ,2 2e a a,所以e 22 a,所以单位元为e2又a2 a22a4. 在整数集合 Z 上定义运算为ababab,就Z,

25、的单位元为 . 解设单位元为e,aeaeaea,1ae0,所以e05. 设G,是群,对任意a,b,cG,假如abac,就.填bc6. 设G,是群, e为单位元,如G 元素 a 满意a2a,就 a .填 e四、解答题1.设 为实数集 R 上的二元运算,其定义为2: R R , a b a b 2 ab,对于任意 a, b R求运算 的单位元和零元；解：设单位元为 e ,就对任意 a R,有 a e a e 2 ae a,即 e 1 2 a 0,由 a 的任意性知 e 0,又对任意 a R,a 0 a 0 0 a；0 a 0 a 0 a所以单位元为 0 设零元为,就对任意 a R,有 a a 2

26、a,即 a 1 2 0,由 a 的任意性知 12又对任意 a R,a 1 a 1a 1, 1 a 1a a 12 2 2 2 2 2所以零元为 122. 设 为集合 5I 0 ,1, 2 3, , 4 上的二元运算,其定义为2: I 5 I 5 , a b ab mod 5,对于任意 a , b I 5（1）写出运算 的运算表；（2）说明运算 是否满意交换律、结合律,是否有单位元和零元、假如有请指出；（3） 写出全部可逆元的逆元解：（ 1）运算表为名师归纳总结 - - - - - - -第 16 页,共 40 页精选学习资料 - - - - - - - - - 0 1 2 3 4 0；0 0

27、0 0 0 0 1 0 1 2 3 4 2 0 2 4 1 3 3 0 3 1 4 2 4 0 4 3 2 1 （ 2）运 算满意交换律、结合律,有单 位元, 单位元为1,有 零元, 零元为（ 3） 1 的逆 元为1, 2 的逆元为3, 3 的逆元 为 2, 4 的逆元4, 0 没 有逆元五、证明题1. 设G,是一个群,试证b2G是交换群当且仅当对任意的a,bG , 有a2ab2 . 证明：充分性如在群G,中,对任意的a,bG , 有a2b2ab2 . ,就就aabbababaaab baba b从而G,是一个交换群；abbabb必要性如G,是一个交换群,对任意的a,bG , 有aaabbab

28、abaabbabab即a2b2ab 2. 2. 证明代数系统Z,是群,其中二元运算定义如下：Z2Z,xyxy3（这里, +,分别是整数的加法与减法运算.）证明 （ 1）运算满意交换律对任意x,y,zZ,由y3zxyz6,xyzxxyzxyz3xyz6得xyzxyz,即满意结合律；（2）有单位元3 是单位元；（3）任意元素有逆元对任意 xZ,x16x. 所以,Z,是群 . 图论第三章一、判定题（1）n 阶完全图的任意两个不同结点的距离都为1. （对）第 17 页,共 40 页名师归纳总结 - - - - - - -精选学习资料 - - - - - - - - - （2）图 G 的两个不同结点 v

29、 , iv j 连接时肯定邻接 . （错）（3）图 G 中连接结点 v i , v j 的初级通路为 v i , v j 之间的短程 .（错）（4）在有向图中,结点 iv 到结点 jv 的有向短程即为 v 到 j iv 的有向短程（错）（5）强连通有向图肯定是单向连通的（对）（6）不论无向图或有向图,初级回路肯定是简洁回路（对）（7）设图 G是连通的,就任意指定 G的各边方向后所得的有向图是弱连通的（对）（8）有生成树的无向图是连通的（对）（9）下图所示的图是欧拉图 . （错）（10）下图所示的图有哈密尔顿回路 . （对）二、单项挑选题（1）仅由孤立点组成的图称为1 . （ A ）A. 零图；

30、 B平凡图； C. 完全图； D. 多重图 . （ B ）（2）仅由一个孤立点组成的图称为A. 零图； B平凡图； C.多重图； D. 子图 . （ B ）（3）在任何图 G 中必有偶数个（ C ）A. 度数为偶数的结点； B度数为奇数的结点；C. 入度为奇数的结点； D. 出度为奇数的结点. （4）设 G 为有 n 个结点的无向完全图,就G 的边数为2A. nn1 Bnn1 C. nn1 2 D. n（ B ）（5）在有 n 个结点的连通图G 中,其边数A. 最多n1条； B至少n1条；（ B ）C. 最多 n 条； D. 至少 n 条. （6）任何无向图 G 中结点间的连通关系是A. 偏序关系； B等价关系；（B ）C. 既是偏序关系又是等价关系； D. 既不是偏序关系也不是等价关系（7）对于无向图,以下说法中正