《离散数学卷（1）-参考答案》山东大学测试答案
离散数学试卷 （参考答案）选择题
1、设，下列选项正确的是：（3）
（1） （2） （3） （4）
2、对任意集合，下述论断正确的是：（1）
（1）若，则 （2）若，则
（3）若，则 （4）若，则
3、假设上的关系如下，具有传递性的关系是：（4）
（1）
（2）
（3）
（4）
4、非空集合上的空关系不具备下列哪个性质：（1）
（1）自反性 （2）反自反性 （3） 对称性 （4）传递性
5、假设，，令：，则不同的函数个数为：（2）
（1）2+3个 （2）个 （3）个 （4）个
6、假设，，下列哪个关系是到的函数：（3）
（1）
（2）
（3）
（4）
7、一个无向简单图有条边，个顶点，则图中顶点的总度数为：（3）
（1） （2） （3） （4）
8、一个图是欧拉图是指：（1）
（1）图中包含一条回路经过图中每条边一次且仅一次；
（2）图中包含一条路经过图中每条边一次且仅一次；
（3）图中包含一条回路经过图中每个顶点一次且仅一次；
（4）图中包含一条路经过图中每个顶点一次且仅一次。
9、下面哪一种图不一定是树：（3）
（1）无回路的连通图 （2）有个顶点条边的连通图
（3）每一对顶点之间都有通路 （4）连通但删去一条边则不连通的图.
10、完全叉树中有片叶，个分支点，则有它们之间的关系表达式是：（2）
（1） （2） （3）（4）
二、填空题
1、假设，，
（1）{1，2，3，5}；（2）{1，3，5，7，11，13，17，19}；（3）{7，11，13，19}；（4）(；
2、假设上的关系，则：（1）{<1,1>,<1,2>,<2,2>,<3,3>,<4,4>}；（2）{<1,2>,<2,1>}；（3）{<1,2>}；3、设无向图有12条边，有3个3度的顶点，其余顶点度数均小于3，则中至少有 11 个顶点。4、一棵树有2个2度顶点，1个3度顶点，3个4度顶点，则有9片叶。
5、假设：我有时间，：我去图书馆。
（1）命题“如果我有时间，我就去图书馆”符号化为 ；
三、假设、是任意两个集合，证明：。
证明：对
则 或者
由幂集定义可知：或者
所以
因此
故
四、假设是自然数集合，定义上的二元关系
。
证明：是一个等价关系，并求出关系所确定的等价类。
证明：（1）对，则是偶数，所以是自反的；
对，假设，则是偶数，而也是偶数
所以，故是对称的；
对，假设，
则有，是偶数；
若是偶数，由于是偶数，所以也是偶数，则是偶数
若是奇数，由于是偶数，所以是奇数，
又因为是偶数，所以是奇数，因此是偶数
所以 是传递的。
综上 是等价关系。
（2）当是偶数时，
当是奇数时，
五、对下列集合在整除关系下构成的偏序集，画出Hasse图，并写出最大元，最小元，极大元，极小元。
（1）
（2）
（3）
解：（1）没有最大元和最小元；极大元是24,36。
（2）最大元和极大元是45，最小元和极小元是1。
（3）最大元和极大元时16，最小元和极小元是2。
六、令V = {a, b, c, d, e}, E = {aa, ab, ab, ba, cd, ca, dd, de}，
A = {<a, a>, <a, b>, <b, a>, <c, d >}
做出图G = <V, E> 和D = <V , A> 的图示。
解：
www.ap5u.com
页:
[1]