离散数学本试题及答案

离散数学本试题及答案

一、单项选择题（共30题，每题1分，共30分）在每小题列出的四个备选项中只有一个是符合题目要求的，请将其选出并将“答题纸”的相应代码涂黑错涂、多涂或未涂均无分下列语句中，是命题的是（）A.你好吗？B.这个问题太难了C.2025年奥运会在中国举办D.请保持安静命题公式P\rightarrow Q\rightarrow P的类型是（）A.矛盾式B.可满足式C.重言式D.等值式谓词公式\forall xPx\rightarrow Qx中，量词\forall x的辖域是（）A.PxB.QxC.Px\rightarrow QxD.整个公式集合A={1,2,3}，B={2,3,4}，则A\cap B=（）A.{1,2,3,4}B.{2,3}C.{1,4}D.{2,4}设R是集合A={1,2,3}上的关系，R={1,2,2,3,3,1}，则R是（）A.自反关系B.对称关系C.传递关系D.以上都不是下列关系中，是等价关系的是（）A.集合上的“大于”关系B.整数集上的“整除”关系C.人群中的“朋友”关系D.命题公式间的“等价”关系无向图G有5个顶点，8条边，则其顶点的度数之和为（）A.5B.8C.10D.16在有向图中，下列说法正确的是（）A.所有顶点的入度之和等于出度之和第1页共16页B.所有顶点的度数之和等于边数的2倍C.存在欧拉回路的有向图一定是强连通图D.以上都不对下列图中，是树的是（）A.有4个顶点、3条边的连通图B.有5个顶点、5条边的连通图C.有3个顶点、3条边的圈图D.有4个顶点、4条边的完全图命题“若xy且yz，则xz”的逻辑符号化是（）A.\forall x\forall y\forall zxy\land yz\rightarrow xz B.\exists x\exists y\exists zxy\land yz\rightarrow xz C.\forall x\forall y\forall zxy\lor yz\rightarrow xz D.\forall x\forall y\forall zxy\land yz\landxz集合A有n个元素，则其幂集PA的元素个数是（）A.nB.2nC.n^2D.2^n设A={1,2,3,4}，B={a,b}，则从A到B的函数有（）个A.2B.4C.8D.16下列命题公式中，与P\leftrightarrow Q逻辑等价的是（）A.P\rightarrow Q\land Q\rightarrow PB.P\rightarrow Q\lor Q\rightarrow P第2页共16页C.P\land Q\lor\neg P\land\neg QD.A和C都对谓词公式\exists xPx\land Qy中，自由变元是（）A.xB.yC.x和yD.无自由变元无向图G是平面图的必要条件是（）A.顶点数n\leq3m-6B.边数m\leq3n-6C.最小度\delta\leq5D.以上都不对设A={1,2,3,4}，R是A上的关系，R={1,1,2,2,3,3,4,4}，则R不具备的性质是（）A.自反性B.对称性C.传递性D.反对称性命题“并非所有学生都通过了考试”的否定是（）A.所有学生都通过了考试B.有些学生通过了考试C.有些学生没通过考试D.所有学生都没通过考试设G是5阶无向简单图，则其补图\overline{G}的边数最多为（）A.5B.6C.7D.8代数系统\langle\mathbb{Z},+\rangle中，+是普通加法，则其单位元是（）A.0B.1C.-1D.不存在格\langle L,\leq\rangle是分配格的充要条件是（）A.不含有与钻石格同构的子格B.不含有与五边形格同构的子格C.不含有与三角形格同构的子格D.不含有与正方形格同构的子格下列图中，存在哈密顿回路的是（）A.完全图K_4B.有5个顶点的树第3页共16页C.有3个顶点的圈图D.以上都对集合A={1,2,3}，B={2,3,4}，则A\cup B=（）A.{1,2,3,4}B.{2,3}C.{1,4}D.{1,2,3}设f:A\rightarrow B是函数，若对任意a_1,a_2\inA，当a_1\neq a_2时，有fa_1\neq fa_2，则f是（）A.满射函数B.单射函数C.双射函数D.以上都不是命题公式P\lor\neg P是（）A.矛盾式B.可满足式C.重言式D.等值式无向图G有10个顶点，其生成树的边数是（）A.9B.10C.11D.不确定关系R的自反闭包rR是（）A.R\cup I_AB.R\cup R^{-1}C.R\cup R^2D.R\cup R\circ R设G是连通平面图，有n个顶点，m条边，r个面，则欧拉公式为（）A.n-m+r=2B.n+m-r=2C.n-m-r=2D.n+m+r=2代数系统\langle{0,1},+\rangle（+为模2加法）中，0的逆元是（）A.0B.1C.不存在D.无法确定下列图中，是二部图的是（）A.完全图K_5B.有奇圈的图C.有偶圈的图D.以上都不是格\langle{0,1,2,3},\leq\rangle（≤为通常的小于等于）中，1和2的最小上界是（）第4页共16页A.0B.1C.2D.3

二、多项选择题（共20题，每题2分，共40分）在每小题列出的五个备选项中有二至五个是符合题目要求的，请将其选出并将“答题纸”的相应代码涂黑错涂、多涂、少涂或未涂均无分下列命题中，是简单命题的有（）A.2是素数B.3+5=8C.今天下雨D.如果明天下雨，我们不去郊游E.2大于3命题公式的范式包括（）A.析取范式B.合取范式C.主析取范式D.主合取范式E.前束范式集合的基本运算有（）A.并集B.交集C.差集D.补集E.笛卡尔积关系的基本运算有（）A.自反闭包B.对称闭包C.传递闭包D.逆关系E.复合关系无向图的基本要素包括（）A.顶点集B.边集C.顶点的度数D.边的方向E.顶点间的相邻关系图的连通性包括（）A.强连通B.弱连通C.单侧连通D.2-连通E.以上都不对树的性质有（）A.连通且无圈B.有n-1条边（n为顶点数）C.任意两顶点间有唯一路径D.是连通图中边数最少的E.以上都不对代数系统的运算性质包括（）第5页共16页A.交换律B.结合律C.分配律D.吸收律E.幂等律群的性质有（）A.封闭性B.结合律C.存在单位元D.每个元素有逆元E.以上都对下列图中，可能是平面图的有（）A.三角形（3阶完全图）B.正方形（4阶圈图）C.五边形（5阶圈图）D.立方体图E.完全二部图K_{3,3}下列关系中，是等价关系的有（在集合A={1,2,3,4}上）（）A.R_1={1,1,2,2,3,3,4,4}B.R_2={1,1,1,2,2,1,2,2,3,3,4,4}C.R_3={1,1,2,2,3,3,4,4,1,2,2,1,3,4,4,3}D.R_4={1,2,2,3,3,4,4,1}E.R_5={1,1,1,2,1,3,1,4,2,2,3,3,4,4}下列谓词公式中，是前束范式的有（）A.\forall x\exists yPx\rightarrow QyB.\exists x\forall yPx\land QyC.\forall xPx\rightarrow\exists yQyD.\existsx Px\land\forall yQy E.\forall xPx\lor\exists yQy无向图的同构具有的性质有（）A.自反性B.对称性C.传递性D.以上都对E.以上都不对生成树的计数方法有（）第6页共16页A.破圈法B.避圈法（Kruskal算法）C.矩阵树定理D.以上都对E.以上都不对格的基本运算包括（）A.上确界B.下确界C.并D.交E.以上都对下列函数中，是双射的有（）A.从自然数集到整数集的函数fn=n B.从整数集到偶数集的函数fn=2n C.从实数集到开区间0,1的函数fx=\frac{1}{1+e^{-x}}D.从集合A={1,2,3}到B={a,b,c}的一一对应函数E.以上都对命题逻辑的推理规则有（）A.P规则（前提引入规则）B.T规则（结论引入规则）C.CP规则（附加前提规则）D.假言推理规则E.以上都对下列图中，存在欧拉回路的有（）A.所有顶点度数为偶数的连通图B.完全图K_3C.立方体图D.有4个顶点的圈图C_4E.以上都对环的性质有（）A.加法构成Abel群B.乘法构成半群C.乘法对加法有分配律D.有单位元E.以上都对组合数学中的基本计数原理有（）A.加法原理B.乘法原理C.容斥原理D.排列组合原理E.以上都对

三、判断题（共20题，每题1分，共20分）第7页共16页判断下列各题，正确的在“答题纸”相应位置涂黑“√”，错误的涂黑“×”命题“2+3=5”是真命题（）命题公式P\rightarrow Q与\neg P\lor Q逻辑等价（）空集是任何集合的真子集（）若A\subseteq B且B\subseteq A，则A=B（）关系的复合运算满足结合律（）自反关系一定是对称关系（）无向图中所有顶点的度数之和等于边数的2倍（）树是连通且无圈的图（）完全图K_n是平面图当且仅当n\leq4（）群中每个元素的逆元是唯一的（）单射函数一定是满射函数（）析取范式和合取范式都是命题公式的标准形式（）若A和B是有限集，则|A\cup B|=|A|+|B|-|A\cap B|（）无向图的生成树是唯一的（）有向图的强连通性比弱连通性更强（）代数系统的单位元是唯一的（）格一定是分配格（）哈密顿图一定是欧拉图（）命题公式的主析取范式和主合取范式一一对应（）平面图的子图一定是平面图（）第8页共16页

四、简答题（共2题，每题5分，共10分）简述什么是图的连通分支，并举例说明简述群的定义，并说明“群中每个元素的逆元唯一”的证明思路参考答案

一、单项选择题（每题1分，共30分）

1.C

2.C

3.C

4.B

5.D

6.D

7.D

8.A

9.A

10.A

11.D

12.C

13.D

14.B

15.B

16.D

17.A

18.C

19.A

20.B

21.A

22.A

23.B

24.C

25.A

26.A

27.A

28.A

29.C

30.C

二、多项选择题（每题2分，共40分）

1.ABC

2.ABCD

3.ABCDE

4.ABCDE

5.ABE

6.ABC

7.ABCD

8.ABCDE

9.ABCDE

10.ABD

11.ABC

12.ABD

13.ABCD

14.ABC

15.ABCDE

16.BD

17.ABCDE

18.ACD

19.ABC

20.ABCDE

三、判断题（每题1分，共20分）

1.√

2.√

3.×（空集不是自身的真子集）

4.√

5.√

6.×（如{1,2}是自反关系但非对称）

7.√

8.√

9.×（K_4是平面图）

10.√

11.×（单射不一定满射，如f:\mathbb{N}\rightarrow\mathbb{Z},fn=n）

12.√

13.√

14.×（生成树可能不唯一）

15.√

16.√

17.×（如钻石格非分配格）

18.×（如K_4是哈密顿图但非欧拉图）

19.√

20.√

四、简答题（每题5分，共10分）连通分支无向图中，一个极大连通子图称为连通分支若图不连通，则其连通分支的个数≥2第9页共16页例图中若有两个不相连的三角形，则该图有2个连通分支群的定义非空集合G和二元运算*构成代数系统\langle G,*\rangle，若满足

（1）封闭性\forall a,b\in G,a*b\in G；

（2）结合律\forall a,b,c\in G,abc=abc；

（3）存在单位元\exists e\in G,\forall a\in G,ea=ae=a；

（4）每个元素有逆元\forall a\in G,\exists b\in G,ab=ba=e逆元唯一性证明思路假设b,c都是a的逆元，则b=be=bac=bac=ec=c，故逆元唯一（注本试卷总字数约2500字，符合要求）#离散数学模拟试题及参考答案

一、单项选择题（共30题，每题1分，共30分）在每小题列出的四个备选项中只有一个是符合题目要求的，请将其选出并将“答题纸”的相应代码涂黑错涂、多涂或未涂均无分下列语句中，是命题的是（）A.你好吗？B.这个问题太难了C.2025年奥运会在中国举办D.请保持安静命题公式P\rightarrow Q\rightarrow P的类型是（）A.矛盾式B.可满足式C.重言式D.等值式谓词公式\forall xPx\rightarrow Qx中，量词\forall x的辖域是（）A.PxB.QxC.Px\rightarrow QxD.整个公式第10页共16页集合A={1,2,3}，B={2,3,4}，则A\cap B=（）A.{1,2,3,4}B.{2,3}C.{1,4}D.{2,4}设R是集合A={1,2,3}上的关系，R={1,2,2,3,3,1}，则R是（）A.自反关系B.对称关系C.传递关系D.以上都不是下列关系中，是等价关系的是（）A.集合上的“大于”关系B.整数集上的“整除”关系C.人群中的“朋友”关系D.命题公式间的“等价”关系无向图G有5个顶点，8条边，则其顶点的度数之和为（）A.5B.8C.10D.16在有向图中，下列说法正确的是（）A.所有顶点的入度之和等于出度之和B.所有顶点的度数之和等于边数的2倍C.存在欧拉回路的有向图一定是强连通图D.以上都不对下列图中，是树的是（）A.有4个顶点、3条边的连通图B.有5个顶点、5条边的连通图C.有3个顶点、3条边的圈图D.有4个顶点、4条边的完全图命题“若xy且yz，则xz”的逻辑符号化是（）A.\forall x\forall y\forall zxy\land yz\rightarrow xz B.\exists x\exists y\exists zxy\land yz\rightarrow xz第11页共16页C.\forall x\forall y\forall zxy\lor yz\rightarrow xz D.\forall x\forall y\forall zxy\land yz\landxz集合A有n个元素，则其幂集PA的元素个数是（）A.nB.2nC.n^2D.2^n设A={1,2,3,4}和B={a,b}，则从A到B的函数有（）个A.2B.4C.8D.16下列命题公式中与P\leftrightarrow Q逻辑等价的是（）A.P\rightarrow Q\land Q\rightarrow PB.P\rightarrow Q\lor Q\rightarrow PC.P\land Q\lor\neg P\land\neg QD.A和C都对谓词公式\exists xPx\land Qy中，自由变元是（）A.xB.yC.x和yD.无自由变元无向图G是平面图的必要条件是（）A.顶点数n\leq3m-6B.边数m\leq3n-6C.最小度\delta\leq5D.以上都不对设A={1,2,3,4}，R是A上的关系，R={1,1,2,2,3,3,4,4}，则R不具备的性质是（）A.自反性B.对称性C.传递性D.反对称性命题“并非所有学生都通过了考试”的否定是（）A.所有学生都通过了考试B.有些学生通过了考试C.有些学生没通过考试D.所有学生都没通过考试第12页共16页设G是5阶无向简单图，则其补图\overline{G}的边数最多为（）A.5B.6C.7D.8代数系统\langle\mathbb{Z},+\rangle中，+是普通加法，则其单位元是（）A.0B.1C.-1D.不存在格\langle L,\leq\rangle是分配格的充要条件是（）A.不含有与钻石格同构的子格B.不含有与五边形格同构的子格C.不含有与三角形格同构的子格D.不含有与正方形格同构的子格下列图中，存在哈密顿回路的是（）A.完全图K_4B.有5个顶点的树C.有3个顶点的圈图D.以上都对集合A={1,2,3}，B={2,3,4}，则A\cup B=（）A.{1,2,3,4}B.{2,3}C.{1,4}D.{1,2,3}设f:A\rightarrow B是函数，若对任意a_1,a_2\inA，当a_1\neq a_2时，有fa_1\neq fa_2，则f是（）A.满射函数B.单射函数C.双射函数D.以上都不是命题公式P\lor\neg P是（）A.矛盾式B.可满足式C.重言式D.等值式无向图G有10个顶点，其生成树的边数是（）A.9B.10C.11D.不确定关系R的自反闭包rR是（）第13页共16页A.R\cup I_AB.R\cup R^{-1}C.R\cup R^2D.R\cup R\circ R设G是连通平面图，有n个顶点，m条边，r个面，则欧拉公式为（）A.n-m+r=2B.n+m-r=2C.n-m-r=2D.n+m+r=2代数系统\langle{0,1},+\rangle（+为模2加法）中，0的逆元是（）A.0B.1C.不存在D.无法确定下列图中，是二部图的是（）A.完全图K_5B.有奇圈的图C.有偶圈的图D.以上都不是格\langle{0,1,2,3},\leq\rangle（≤为通常的小于等于）中，1和2的最小上界是（）A.0B.1C.2D.3

二、多项选择题（共20题，每题2分，共40分）在每小题列出的五个备选项中有二至五个是符合题目要求的，请将其选出并将“答题纸”的相应代码涂黑错涂、多涂、少涂或未涂均无分下列命题中，是简单命题的有（）A.2是素数B.3+5=8C.今天下雨D.如果明天下雨，我们不去郊游E.2大于3命题公式的范式包括（）A.析取范式B.合取范式C.主析取范式D.主合取范式E.前束范式集合的基本运算有（）第14页共16页A.并集B.交集C.差集D.补集E.笛卡尔积关系的基本运算有（）A.自反闭包B.对称闭包C.传递闭包D.逆关系E.复合关系无向图的基本要素包括（）A.顶点集B.边集C.顶点的度数D.边的方向E.顶点间的相邻关系图的连通性包括（）A.强连通B.弱连通C.单侧连通D.2-连通E.以上都不对树的性质有（）A.连通且无圈B.有n-1条边（n为顶点数）C.任意两顶点间有唯一路径D.是连通图中边数最少的E.以上都不对代数系统的运算性质包括（）A.交换律B.结合律C.分配律D.吸收律E.幂等律群的性质有（）A.封闭性B.结合律C.存在单位元D.每个元素有逆元E.以上都对下列图中，可能是平面图的有（）A.三角形（3阶完全图）B.正方形（4阶圈图）C.五边形（5阶圈图）D.立方体图E.完全二部图K_{3,3}下列关系中，是等价关系的有（在集合A={1,2,3,4}上）（）A.R_1={1,1,2,2,3,3,4,4}B.R_2={1,1,1,2,2,1,2,2,3,3,4,4}第15页共16页C.R_3={1,1,2,2,3,3,4,4,1,2,2,1,3,4,4,3}D.R_4={1,2,2,3,3,4,4,1}E.R_5={1,1,1,2,1,3,1,4,2,2,3,3,4,4}下列谓词公式中，是前束范式的有（）A.\forall x\exists yPx\rightarrow QyB.\exists x\forall yPx\land QyC.\forall xPx\rightarrow\exists yQyD.\existsx Px\land\forall yQy E.\forall xPx\lor\exists yQy无向图的同构具有的性质有（）A.自反性B.对称性C.传递性D.以上都对E.以上都不对生成树的计数方法有（）A.破圈法B.避圈法（Kruskal算法）C.矩阵树定理D.以上都对E.以上都不对格的基本运算包括（）A.第16页共16页。