广东海洋大学离散数学历年考题 - 答案

班级： 姓名密 ： 学 号 ：封 试 题 共线 4页 加白纸3张

GDOU-B-11-302

广东海洋大学2008——2009学年第二学期

《离散数学》课程试题

√□ 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

2、设?G,??为群,?a,b?G，有(a?b)2?a2?b2 证明 a?b?b?a

GDOU-B-11-302

广东海洋大学2008——2009学年第二学期

课程号：

《离散数学》评分细则

1920015-0

一、 填空题（每空1分，共20分）

1、永真式、永假式和可满足式； 2、若我不说谎则太阳从西边出来；1； 3、{1,2,3,6,7} ，{1,2,3,6,7}； 4、3，-2；

√ □考试 □ 考查 √ □A卷

□ B卷 √ □闭卷

□ 开卷

第 4 页 共 7 页

5、EA?{?1,1?,?2,2?,?1,2?,?2,1?},IA?{?1,1?,?2,2?}； 6、自反，反对称，传递； 7、0，2； 8、n?1，n；

9、无边相交，n?m?r?2。

二、单项选择题（每题1分，共10分） 1～5、C/ABDBB； 6～10：ADADD。 三、判断题：（每题1分，共15分） 对的有：3、4、6、7、9、12、13、15 错的有：1、2、5、8、10、11、14 四、计算题（10+10+5+10=35分）

1、(p?q)?r?(p?r)?(?q?r)?(?p?q??r) 4分

(p?r)?M0?M2 2分 (?q?r)?M2?M6 2分 ?(p?q)?r?M0?M2?M5?M6 2分

2、点割集：｛v2,v4｝, ｛v3｝, ｛v5｝ （2分）

割点：v3 和v5 (2分) 边割集：｛e5｝、｛e6｝、｛e2 ,e3｝、｛e1 ,e2｝、｛e3 ,e4｝、｛e1 ,e4｝、｛e1 ,e3｝｛e2 ,e4｝ （2分） 割边（桥）：e5 、e6 （2分） 连通度：1； （1分） 边连通度：1 （1分） 3、解：设幺元为e，?x?Z，有x?e?e?x?x，则x?e?xe?x?e?0 2分 由x?x?1?x?1?x?e，得x?x?1?xx?1?0，

x?1?x x?1第 5 页 共 7 页

故 2分

?x只能为0和2，且0?1?0,2?1?2 1分 4、

1）表达式树：

6分

2）前序遍历：????a?bcde?fg 2分 3）后序遍历：abc??d?e?fg?? 2分

五、证明题（每题10分，共20分） 1、 证明：

①q 否定前提引入 1分 ②?r?s 前提引入 1分 ③?s 前提引入 1分 ④?r ②③析取三段论 1分 ⑤(p?q)?r 前提引入 1分 ⑥?(p?q) ④⑤拒取式 1分 ⑦?p??q ⑥置换 1分

?? ? e f ? ? a bd g ? c 第 6 页 共 7 页

⑧p 前提引入 1分 ⑨?q ⑦⑧析取三段论 1分 ⑩0 ⑧⑨合取 1分 2、证： 由(a?b)2?a2?b2 2分 得：a?b?a?b?a?a?b?b 3分 根据群中的消去律得b?a?a?b 3即a?b?b?a 2第 7 页 共 7 页分 分

本文来源：https://www.bwwdw.com/article/iina.html