山东大学网络教育《离散数学(1-3)》

离散数学试卷1（参考答案）

一、 选择题

1、设A?{{1,2,3},{4,5},{6,7,8}}，下列选项正确的是：（3）

（1）1?A （2）{1,2,3}?A （3）{{4,5}}?A （4）??A 2、对任意集合A,B,C，下述论断正确的是：（1）

（1）若A?B,B?C，则A?C （2）若A?B,B?C，则A?C （3）若A?B,B?C，则A?C （4）若A?B,B?C，则A?C 3、假设A?{a,b,c}上的关系如下，具有传递性的关系是：（4） （1）{?a,c??c,a??a,a??a,b??b,a?} （2）{?a,c??c,a??a,a?} （3）{?a,c??c,a?} （4）{?a,c?}

4、非空集合A上的空关系R不具备下列哪个性质：（1）

（1）自反性 （2）反自反性 （3） 对称性 （4）传递性 5、假设A?{a,b,c}，B?{1,2}，令：f:A?B，则不同的函数个数为：（2） （1）2+3个 （2）2个 （3）2?3个 （4）3个 6、假设A?{a,b,c}，B?{1,2}，下列哪个关系是A到B的函数：（3） （1）f?{?a,1??a,2??b,1??b,2??c,1??c,2?} （2）f?{?a,a??a,b??b,a??b,b??c,a??c,c?} （3）f?{?a,1??b,2??c,1?} （4）f?{?1,a??2,b??1,c?}

7、一个无向简单图G有m条边，n个顶点，则图中顶点的总度数为：（3） （1）m （2）n （3）2m （4）2n 8、一个图是欧拉图是指：（1）

2232（1）图中包含一条回路经过图中每条边一次且仅一次； （2）图中包含一条路经过图中每条边一次且仅一次； （3）图中包含一条回路经过图中每个顶点一次且仅一次； （4）图中包含一条路经过图中每个顶点一次且仅一次。 9、下面哪一种图不一定是树：（3）

（1）无回路的连通图 （2）有n个顶点n?1条边的连通图 （3）每一对顶点之间都有通路 （4）连通但删去一条边则不连通的图. 10、完全m叉树中有l片叶，i个分支点，则有它们之间的关系表达式是：（2） （1）i?l?1 （2）(m?1)i?1?l （3）(m?1)i?l （4）(m?1)l?i?1

二、填空题

1、假设A?{x|x2?30,x?整数}，B?{x|x是素数，x?20}，C?{1,3,5}

（1）(A?B)?C?{1，2，3，5}；

（2）(B?A)?C?{1，3，5，7，11，13，17，19}；

（3）(C?A)?(B?A)?{7，11，13，19}；

（4）(B?C)?A??；

2、假设A?{1,2,3,4}上的关系R?{?1,2?}，则：

（1）r(R)?{<1,1>,<1,2>,<2,2>,<3,3>,<4,4>}；

（2）s(R)?{<1,2>,<2,1>}；

（3）t(R)?{<1,2>}；

3、设无向图G有12条边，有3个3度的顶点，其余顶点度数均小于3，则G中至少有 11 个顶点。

4、一棵树有2个2度顶点，1个3度顶点，3个4度顶点，则有9片叶。 5、假设P：我有时间，Q：我去图书馆。

（1）命题“如果我有时间，我就去图书馆”符号化为 P?Q；

三、假设A、B是任意两个集合，证明：?(A)??(B)??(A?B)。

证明：对?X?p(A)?p(B) 则 X?p(A)或者X?p(B) 由幂集定义可知：X?A或者X?B 所以 X?A?B 因此 ?X?p(A?B) 故 ?(A)??(B)??(A?B)

四、假设N是自然数集合，定义N?{0}上的二元关系R

R?{?x,y?|x,y?N?{0},x?y是偶数}。

证明：R是一个等价关系，并求出关系R所确定的等价类。 证明：（1）对?x?N?{0}，则x?x是偶数，所以R是自反的；

对?x,y?N?{0}，假设?x,y??R，则x?y是偶数，而y?x也是偶数 所以?y,x??R，故R是对称的；

对?x,y,z?N?{0}，假设?x,y??R，?y,z??R 则有x?y，y?z是偶数；

若x是偶数，由于y?z是偶数，所以z也是偶数，则x?z是偶数 若x是奇数，由于x?y是偶数，所以y是奇数，

又因为y?z是偶数，所以z是奇数，因此x?z是偶数 所以 R是传递的。 综上 R是等价关系。

（2）当x是偶数时，[x]R?{y|y?N?{0}并且y是偶数} 当x是奇数时，[x]R?{y|y?N?{0}并且y是奇数}

五、对下列集合在整除关系下构成的偏序集，画出Hasse图，并写出最大元，最小元，极大元，极小元。

（1）A1?{2,3,6,12,24,36} （2）A2?{1,3,5,9,15,45} （3）A3?{2,4,8,16}

解：（1）没有最大元和最小元；极大元是24,36。 （2）最大元和极大元是45，最小元和极小元是1。 （3）最大元和极大元时16，最小元和极小元是2。

24 36 45 16 15 4 3 2 （1） 3 5 2 1 （2） （3） 8 12 6 9

六、令V = {a, b, c, d, e}, E = {aa, ab, ab, ba, cd, ca, dd, de}，

A = {, , , }

做出图G = 和D = 的图示。

解：

a b a c d e ? e d ? ? b c （1） （2）

离散数学模拟卷2参考答案

一、选择题

1、请指出下列选项中哪一个是错误的：（2）

（1）??? （2）??? （3）??{?} （4）??{?} 2、对任意集合A,B,C，下述论断正确的是：（1）

（1）若A?B,B?C，则A?C （2）若A?B,B?C，则A?C （3）若A?B,B?C，则A?C （4）若A?B,B?C，则A?C

3、假设A?{a,b,c}上的关系R?{?a,a??a,b??a,c??c,a?}，那么，R是：（4） （1）反自反的 （2）反对称的 （3） 可传递的 （4）不可传递的

4、非空集合A上的空关系R不具备下列哪个性质：（1）

（1）自反性 （2）反自反性 （3） 对称性 （4）传递性 5、若f:A?B,g:B?C是满射函数，则复合函数g?f必是：（3）

（1）双射函数 （2）单射函数 （3）满射函数 （4）不单射也不满射 6、假设A?{a,b,c}，B?{1,2}，下列哪个关系是A到B的函数：（3） （1）f?{?a,1??a,2??b,1??b,2??c,1??c,2?} （2）f?{?a,a??a,b??b,a??b,b??c,a??c,c?} （3）f?{?a,1??b,2??c,1?} （4）f?{?1,a??2,b??1,c?}

7、一个无向简单图G有m条边，n个顶点，则图中顶点的总度数为：（3） （1）m （2）n （3）2m （4）2n 8、一个图是哈密顿图是指：（3）

（1）图中包含一条回路经过图中每条边一次且仅一次； （2）图中包含一条路经过图中每条边一次且仅一次； （3）图中包含一条回路经过图中每个顶点一次且仅一次； （4）图中包含一条路经过图中每个顶点一次且仅一次。

22

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