广东海洋大学离散数学历年考题 - 答案
班级： 姓名密 ： 学 号 ：封 试 题 共线 4页 加白纸3张 GDOU-B-11-302
广东海洋大学2021――2021学年第二学期 《离散数学》课程试题
√□ A卷 √□ 闭卷 课程号：
1920015-0 √□ 考试□ 考查 □ B卷 □ 开卷
题 号 一 二 三 四 五 总分 阅卷教师 各题分数 20 10 15 35 20 100 实得分数 注：第一、第二和第三大题的答案直接写在试卷上指定空格内。只有计算题和证明题的答案写在答题纸上。
一、填空题（每空1分，共20分）
1、数理逻辑中公式的三种类型是 、 和 。
2、设p：我说谎；q：太阳从西边出来；则?p?q表示 ； (p?q)?p? 。
3、A?{1,2,3,4,5},B?{4,5,6,7}，则?= ； 而B?A? 。
4、若?x?2,4???5,2x?y?则x? ，y? 。 5、A?{1,2}，则EA? ，IA? 。 6、若非空集合上的关系是 、 和 的，则称为偏序关系。 7、?Z4,??中
e? ，2?5? 。 8、G?(n,m)，则G的生成树中有
条边， 个顶点。 9、除顶点外， 的图称为平面图，平面图中的欧拉公式为 。
二、单项选择题（每题1分，共10分） 1、下列语句中，真命题是 ； 第 1 页 共 7 页
A、2是有理数； B、全体起立！；
C、2是素数?三角形有三条边； D、4是2的倍数或是3的倍数吗？
2、p：张三可做此事；q：李四可做此事；“张三可做此事或李四不可做此事”符号化为 ；
A、p??q； B、p??q； C、?(p?q)； D、?(p?q)
3、R?{?1,2?,?3,4?,?2,2?},S?{?4,2?,?2,5?,?3,1?}，则R?S? ； A、{?1,2?}； B、{?4,5?}；
C、{?4,2?,?3,2?}； D、{?1,5?,?3,2?,?2,5?}； 4、
A?{1,2,?,10}上的关系R?{?x,y?x?y?10?x,y?A}，则R的性质为 ； A、自反； B、对称；
C、传递、对称； D、反自反，传递；
5、对任意非空集合A，?P(A),??的幺元（单位元）是 ； A、A； B、?； C、{A}； D、{?}； 6、下列矩阵，能够作为无向图关联矩阵的是 ；
111??111??100?A、? B、 C、、 111??
D????????000111110011???????? ?111??111???001?111?????????
7、Able群必须满足 ； A、存在幺元； B、每个元素均有逆元； C、结合律和交换律； D、以上全是；
8、图G有6个顶点，各顶点度数分别为1，4，4，3，5，5则G边数为 ； A、11； B、12； C、22； D、23； 9、n?1个顶点的图G是强连通图当且仅当 ； A、G中至少有一条通路； B、G中有通过每个顶点至少一次的通路； 第 2 页 共 7 页
C、G中至少有一条回路； D、G中有通过每个顶点至少一次的回路； 10、无向图G??V,E?是欧拉图，当且仅当G中（ ）；
A、每个顶点的度数相同； B、每个顶点的入度等于出度； C、每个顶点的度数均为奇数； D、每个顶点的度数均为偶数。 三、判断题（每题1分，共15分）
1、语句“豆沙包是由面粉和红小豆做成的”是命题逻辑中的复合命题（ ） 2、任何命题公式都存在唯一与之等值的主析取范式，相应的主合取范式则不唯一（ ） 3、所谓的“自然推理系统”是指，从任意给定的前提出发，应用系统中的推理规则进行推理演算，最后得到的命题公式是推理的结论，这个结论肯定是有效的结论。（ ）
4、在一阶逻辑（谓词逻辑）中，同一个公式在不同的解释下，其真假值可能不同（ ） 5、在一阶逻辑公式中，换名规则是对量词辖域中的自由变元而言的（ ） 6、数字60的欧拉函数值是16（ ）
7、笛卡尔积运算对于并和交运算满足分配律（ ）
8、一个关系只能是对称的或者反对称的；不能即是对称的，又是反对称的（ ） 9、在等价关系中，商集和划分是等值的，即：商集就是一个划分，不同的商集对应不同的划分（ ）
10、如果一个代数系统存在零元，则一定存在单位元（ ） 11、n阶竞赛图可能是有向简单图，也可能是有向复杂图（ ） 12、在有向图的关联矩阵中，每一列的元素之和必为零（ ） 13、n(n≥2)阶有向完全图都是欧拉图（ ） 14、Huffman算法所构造的最优二叉树是唯一的（ ）
15、在构造最小生成树的过程中，Kruskal算法是通过按照大小顺序添加边的形式实现的，根据其思想，也可以通过添加点的形式，实现构造最小生成树算法（ ） 四、计算题（10+10+5+10=35分） 1、求(p?q)?r的主合取范式；
2、已知无向图G=如下所示，求该图的全部点割集、割点、边割集、割边（桥）， 第 3 页 共 7 页
并分别求出其连通度和边连通度。
3、Z为整数集，?x,y?Z定义x?y?x?y?xy，求?Z,??的幺元（单位元）和逆元。 4、设表达式为((a?(b?c))?d?e)?(f?g) 1）求表达式树；（6分）
2）前序遍历该表达式树；（2分） 3）后序遍历该表达式树；（2分） 五、证明题（每题10分，共20分） 1、前提：(p?q)?r,?r?s,?s,p 结论：?q
广东海洋大学离散数学历年考题 - 答案
