2015-2016广东海洋大学离散数学真题(满分必备)

课程号：

题 号 各题分数 实得分数 《离散数学》课程试题

1920015-0 一 20 二 10 三 15 √□ 考试

□ 考查

四 35 五 20 □ A卷

√□ B卷

总分 100 √□ 闭卷

□ 开卷

阅卷教师 注：第一、第二和第三大题的答案直接写在试卷上指定空格内。只有计算题和证明题的答案写在答题纸上。 一、 填空题（每空1分，共20分）

1、命题是具有 真值的 。 2、A{,{}}，则P(A) ；

3、E{1,2,,9}，A{1,2,3,4,5},B{4,5,6,7}，则,AB ； 而

,BA 。

4、设p：这门课让人喜欢；q：这本书有趣；r：这本书习题很难；则下列语句： 1）若这本书有趣，习题也不很难，则这门课就不会让人喜欢。 2）这本书没趣，习题也不很难，并且这门课不让人喜欢。 3）这门课让人喜欢当且仅当这本书有趣且这本书习题不很难。

符号化为1） ；2） ；3） 。 5、ppp 。

6、A{,{a},{b},{a,b}}上的包含关系为，则子集C{{a},{b}}的极大元为 ，最大元为 ，上界为 ；

7、若非空集合上的关系是 、 和 的，则称为等价关系； 8、G(n,m)无向图，则G有生成树当且仅当 ，要确定G的一棵生成树，必删去G的 条边；

第 1 页 共 4 页

9、实数集R上定义如下二元运算：

1）aba2b；2）ababab；3）abb；4）abab其中可结合的有 ，可交换的有 ，既不可结合也不交换的有 ； 10、无向图中所有顶点度数之和等于边数的 倍。

二、单项选择题（每题1分，共10分）

1、下列语句中，真命题是 ； A、我正在说谎； B、这句话是错的； C、若1+2=3则雪是黑的； D、若1+2=5则1=2； 2、下列哪个公式是永真式 ；

A、(pq)(qp)； B、pqp； C、(pq)(pq)； D、(pq) 3、对任意集合A,B,C，下列结论正确的是 ； A、ABBCAC； B、ABBCAC； C、ABBCAC； D、ABBCAC；

4、A{1,2,3}上关系R{1,1,1,2,1,3,3,3}，则R具有 ； A、传递性和反对称性； B、传递性和对称性； C、自反性和对称性； D、反自反性和对称性；

5、下列代数系统， 是独异点（R为实数集，I为整数集，I为正整数集）； A、(R,),aba2b2； B、(R,),ab3a3b3； C、(I,max),max为求两数中较大数； D、(I,gcd),gcd为求最大公约数； 6、任何一个有限群在同构意义下可看作是 ； A、循环群； B、置换群； C、变换群； D、Abel群； 7、具有6个顶点的非同构无向树的数目为 ； A、4； B、5； C、6； D、8；

8、若A3,B2,f:AB，则不同的映射个数为 ； A、23个； B、23个；

第 2 页 共 4 页

C、23个； D、32个；

9、R{1,2,1,3,2,4,4,3}则domR ； A、{1,2,3,4}； B、{1,2,3}； C、{2,3,4}； D、{1,2,4}

10、无向图GV,E是哈密顿图，V1VV1，均有p(GV1) V1； A、； B、； C、； D、。

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

1、语句“爱美之心人皆有之”可以用命题逻辑中的简单命题来描述（ ） 2、所谓的“推理是有效的”是指该推理的前提和结论都是正确的（ ） 3、由于引入了论域的概念，在一阶逻辑中，不存在永真或永假的公式（ ） 4、在一阶逻辑（谓词逻辑）中，量词也存在分配律，全称量词对合取存在分配律，存在量词对析取存在分配律（ ） 5、空集是一切集合的子集（ ） 6、 ABAB（ ）

7、R为二元关系， A是集合，R在A上的限制RA还是一个关系，并且是R的子关系（ ）

8、一个关系如果不是自反的，就一定是反自反的。（ ） 9、不存在一种关系，即是等价关系，同时也是偏序关系（ ） 10、Abel群肯定是独异点（ ） 11、平凡图是连通图（ ）

12、在有向图的可达矩阵中，对角线元素可能是0（ ） 13、完全图Kn(n≥1)都是哈密顿图（ ）

14、Kruskal算法构造最小生成树的过程中，按照权从大到小添加边，避免回路的出现即可（ ）

15、在后续课程《编译原理》中有重要应用的逆波兰式是指：运算符号在他的两个运算对象之后（ ）

第 3 页 共 4 页

三、计算题（10+10+5+10=35分）

1、求(pq)r的主析取范式和成真赋值；（此类型必考） 2、有向图D为

1）求邻接矩阵A；2）计算A3；3）D中v3到v4的长度为3的通路有几条？说明理由。（必考）

3、Z6,为群，其中Zn{0,1,2,3,4,5}，为模6加法；（必考） 1）求幺元（单位元）e；2）xZn求x1；3）计算42008；

4、一棵树有2个2度顶点，1个3度顶点，3个4度顶点，求其树叶数。

四、证明题（每题10分，共20分）

1、前提：x(F(x)H(x)),x(G(x)H(x))（必考类型） 结论：x(G(x)F(x)) 证明：

2、设N是自然数集，定义N上的二元关系R{x,yx,yNxy是偶数}，则R是等价关系。

第 4 页 共 4 页