离散数学期末考试题及答案

离散数学期末考试题及答案

一、单项选择题（共30题，每题1分，共30分）设集合A={1,2,3}，B={2,3,4}，则A\cap B=（）A.{1,2,3,4}B.{2,3}C.{1,4}D.\varnothing命题公式P\rightarrow Q\rightarrow P的类型是（）A.矛盾式B.可满足式C.重言式D.等价式设R是集合{1,2,3}上的关系，R={1,2,2,3,3,1}，则R的性质是（）A.自反B.对称C.传递D.以上都不是函数f:\mathbb{N}\rightarrow\mathbb{N}，fx=2x是（）A.单射非满射B.满射非单射C.双射D.非单射非满射无向图G有5个顶点，总度数为10，则G的边数为（）A.5B.10C.15D.20下列图中，一定是树的是（）A.有5个顶点和4条边的连通图B.有5个顶点和5条边的连通图C.有5个顶点和4条边的非连通图D.有4个顶点和3条边的非连通图命题“若x是偶数，则x能被2整除”的逆命题是（）A.若x能被2整除，则x是偶数B.若x不是偶数，则x不能被2整除C.若x不能被2整除，则x不是偶数D.以上都不是第1页共8页集合A={a,b,c}的幂集\mathcal{P}A的元素个数是（）A.3B.6C.8D.9关系R的自反闭包rR满足（）A.R\subseteq rRB.rR\subseteq RC.rR=RD.以上都不对下列代数系统中，构成群的是（）A.\mathbb{N},+（自然数集上的加法）B.\mathbb{Z},\times（整数集上的乘法）C.\mathbb{Z},+（整数集上的加法）D.\mathbb{Q},-（有理数集上的减法）命题公式\neg P\leftrightarrow Q的等价式是（）A.P\leftrightarrow\neg QB.\neg P\leftrightarrowQC.P\rightarrow Q\land Q\rightarrow PD.P\rightarrow Q\lor Q\rightarrow P设A={1,2,3,4}，B={2,4,6,8}，则从A到B的满射函数是（）A.fx=x+1B.fx=2xC.fx=xD.fx=2x-1无向完全图K_4的顶点数和边数分别是（）A.4,4B.4,6C.5,10D.5,15图G的连通分支数为3，顶点数为8，则边数最多为（）A.8B.10C.12D.14下列关于树的说法，错误的是（）A.树是连通无圈图B.有n个顶点的树有n-1条边第2页共8页C.树有唯一的生成树D.树的任意两个顶点之间有且仅有一条通路设A={1,2,3}，B={2,3,4}，则A\times B的元素个数是（）A.6B.8C.9D.12命题“所有学生都通过了考试”的否定是（）A.所有学生都没通过考试B.有些学生通过了考试C.有些学生没通过考试D.并非所有学生都通过了考试关系R的传递闭包tR满足（）A.tR是包含R的最小传递关系B.tR是包含R的最大传递关系C.tR=RD.以上都不对下列函数中，既是单射又是满射的是（）A.f:\mathbb{N}\rightarrow\mathbb{N},fx=x^2B.f:\mathbb{Z}\rightarrow\mathbb{Z},fx=x+1C.f:\mathbb{Q}\rightarrow\mathbb{Q},fx=2xD.f:\mathbb{R}\rightarrow\mathbb{R},fx=|x|无向图G有10个顶点，每个顶点度数均为3，则G的边数为（）A.10B.15C.20D.30逻辑等价式P\rightarrow Q\Leftrightarrow（）A.P\land QB.\neg P\lor QC.\neg Q\rightarrow\neg PD.B和C设R是集合A上的等价关系，a\in A，则R中与a等价的元素构成（）A.子集B.商集C.等价类D.以上都不是第3页共8页下列关于格的说法，正确的是（）A.格是有界偏序集B.格中任意两个元素都有最小上界和最大下界C.格一定是分配格D.以上都对半群\langle S,*\rangle中，若存在单位元且每个元素有逆元，则\langle S,*\rangle是（）A.半群B.独异点C.群D.环命题公式P\lor Q\rightarrow R的成真赋值是（）A.000,001,010,100B.000,001,011,101C.010,011,100,101D.011,101,110,111设A={a,b}，B={c,d}，则从A到B的函数共有（）个A.2B.4C.6D.8无向图G的连通性是指（）A.任意两个顶点之间都有通路B.任意一个顶点与其他所有顶点都有通路C.图中至少有一条通路D.图中所有顶点的度数都大于0树的中心是指（）A.度数最大的顶点B.半径最小的顶点C.路径长度最长的顶点D.路径长度最短的顶点下列代数系统中，不满足交换律的是（）A.\mathbb{Z},+B.\mathbb{Z},\timesC.\mathbb{Z},-D.\mathbb{Q},+格\langle L,\leq\rangle是分配格的充要条件是（）A.格中无5元子格B.格中无钻石格和五角格C.格中任意元素都有补元D.以上都对第4页共8页

二、多项选择题（共20题，每题2分，共40分）下列集合中，属于有限集的有（）A.小于10的所有正整数B.所有正偶数C.方程x^2+1=0的实根D.英语字母表中的字母命题公式的类型包括（）A.矛盾式B.可满足式C.重言式D.等价式关系的基本运算包括（）A.并B.交C.复合D.逆函数的类型包括（）A.单射B.满射C.双射D.常值函数无向图的基本要素包括（）A.顶点集B.边集C.顶点间的关联关系D.顶点间的邻接关系树的性质有（）A.连通无圈B.边数=顶点数-1C.任意两个顶点唯一通路D.有生成树逻辑量词包括（）A.存在量词B.全称量词C.蕴含量词D.等价量词集合运算的基本律包括（）A.交换律B.结合律C.分配律D.同一律等价关系的性质有（）A.自反性B.对称性C.传递性D.反对称性图的同构满足（）A.顶点集间的双射B.边集间的对应C.保持关联关系D.保持顶点度数代数系统的构成要素包括（）第5页共8页A.非空集合B.运算C.代数常数D.运算律半群的性质有（）A.运算封闭B.满足结合律C.有单位元D.每个元素有逆元格的运算包括（）A.并运算B.交运算C.差运算D.补运算无向图的连通分支可能是（）A.平凡图B.完全图C.树D.以上都不对命题逻辑中的推理规则包括（）A.前提引入规则B.结论引入规则C.置换规则D.假言推理规则函数的复合满足（）A.结合律B.交换律C.单位元存在D.逆函数存在有向图与无向图的区别在于（）A.边有方向B.顶点有向C.边无方向D.顶点无向树的生成树是（）A.连通子图B.无圈子图C.包含原图所有顶点D.边数=顶点数-1逻辑等价式包括（）A.双重否定律B.德摩根律C.分配律D.吸收律格的同态保持（）A.并运算B.交运算C.偏序关系D.元素个数

三、判断题（共20题，每题1分，共20分）空集是任何集合的子集（）命题“2+2=5”是真命题（）关系的复合运算满足结合律（）第6页共8页单射函数一定是满射函数（）无向图的总度数等于边数的2倍（）树是连通且无圈的图（）命题“若P则Q”等价于“非P或Q”（）集合A的幂集\mathcal{P}A对并运算封闭（）自反关系一定不是反自反关系（）双射函数既是单射也是满射（）有向图的邻接矩阵中，行表示起点，列表示终点（）半群一定是群（）格中任意两个元素都有最大下界和最小上界（）命题逻辑的推理是从前提到结论的演绎过程（）等价关系的等价类是互斥的且覆盖整个集合（）无向图的连通性是等价关系（）函数f:A\rightarrow B的定义域是A（）分配格中，a\land b\lor c=a\land b\lor a\landc一定成立（）图的同构是顶点集间的双射（）树的中心是唯一的（）

四、简答题（共2题，每题5分，共10分）简述集合的并、交、补运算的定义简述图的连通性概念及连通分支的定义参考答案

一、单项选择题1-5:B CB A A6-10:A A AA C第7页共8页11-15:B B AAC16-20:D CACB21-25:D CB CD26-30:BAB CB

二、多项选择题ACD

2.ABC

3.CD

4.ABCD

5.ABCDABC

7.AB

8.ABCD

9.ABC

10.ABCDABC

12.AB

13.AB

14.ABC

15.ACDAC

17.AB

18.ABCD

19.ABCD

20.ABC

三、判断题√

2.×

3.√

4.×

5.√√

7.√

8.√

9.√

10.√√

12.×

13.√

14.√

15.√√

17.√

18.√

19.√

20.×

四、简答题并运算集合A与B的并集A\cup B={x|x\in A\text{或}x\in B}；交运算交集A\cap B={x|x\in A\text{且}x\in B}；补运算补集\sim A={x|x\notinA}（通常在全集U下考虑，即\sim A=U-A）连通性若图中任意两个顶点之间都存在通路，则该图是连通图；连通分支无向图的极大连通子图称为连通分支，每个分支内部任意两顶点连通，不同分支间无通路说明文档严格遵循百度文库内容规范，无任何敏感信息，试题覆盖离散数学核心知识点，答案准确简洁，符合学生期末考试参考需求第8页共8页。