《离散数学卷（2）-参考答案》山东大学测试答案
离散数学模拟卷2参考答案一、选择题1、请指出下列选项中哪一个是错误的：（2）（1） （2） （3） （4）
2、对任意集合，下述论断正确的是：（1）
（1）若，则 （2）若，则
（3）若，则 （4）若，则
3、假设上的关系，那么，是：（4）
（1）反自反的 （2）反对称的 （3） 可传递的 （4）不可传递的4、非空集合上的空关系不具备下列哪个性质：（1）
（1）自反性 （2）反自反性 （3） 对称性 （4）传递性
5、若是满射函数，则复合函数必是：（3）
（1）双射函数 （2）单射函数 （3）满射函数 （4）不单射也不满射
6、假设，，下列哪个关系是到的函数：（3）
（1）
（2）
（3）
（4）
7、一个无向简单图有条边，个顶点，则图中顶点的总度数为：（3）
（1） （2） （3） （4）
8、一个图是哈密顿图是指：（3）
（1）图中包含一条回路经过图中每条边一次且仅一次；
（2）图中包含一条路经过图中每条边一次且仅一次；
（3）图中包含一条回路经过图中每个顶点一次且仅一次；
（4）图中包含一条路经过图中每个顶点一次且仅一次。9、一棵树有2个2度顶点，1个3度顶点，3个4度顶点，则其1度的顶点数为：（2）
（1）5 （2）7 （3）8 （4）9
10、完全叉树中有片叶，个分支点，则有关系式是：（2）
（1） （2） （3）（4）
二、填空题
1、假设，试求出：
的幂集{(,{{a,b}},{{c}},{{a,b},{c}}}；
2、假设，，
（1）{7,9,11,13,15,17,19}；（2）(；
3、假设上的关系，则：（1）{<1,1>,<2,2>,<2,3>,<3,3>,<4,4>}；（2）{<2,3>,<3,2>}；（3）{<2,3>}；
4、假设，是到的函数，其中：（a）；（b），，；（c），；则：（1）g 是满射；（2）g 是双射；5、设无向图有36条边，有6个3度的顶点，其余顶点度数均小于3，则中至少有33个顶点。6、假设：今天天气好，：我就去锻炼身体。
（1）命题“如果今天天气好，我就去锻炼身体”符号化为 P(Q ；三、假设、是任意两个集合，证明：。
证明：对，则且
所以 并且
由交集的定义，则
所以
因此
反之，假设
则
所以 并且
所以 且
由交集定义，则
故
综上
四、证明定义在实数集合上的关系是一个等价关系。
证明：对，则是整数，所以是自反的；
对，并且设，则是整数
而也是整数，所以，是对称的；
对，并且设，
则 ，，是整数；
而 也是整数
所以
因此 是传递的
综上，是等价关系。
五、对下列集合在整除关系下构成的偏序集，画出Hasse图，并写出最大元，最小元，极大元，极小元。
（1）
（2）
（3）
解：（1）无最大元，极大元为：24，36；无最小元，极小元为：2，3；
（2）最大元和极大元为：30；最小元和极小元为：1
（3）无最大元，极大元为：6，9；最小元和极小元为：1
六、设无向图G中有9个顶点，每个顶点的度数不是5就是6，试证明G中至少有5个6度顶点或至少有6个5度顶点。
解：假设图G中最多有4个6度顶点，并且最多有有5个5度顶点
则度为奇数的顶点只能为偶数个，所以5度顶点应该为4个，
而6度顶点最多也为4个，所以与命题条件有9个顶点产生矛盾；
因此G中至少有5个6度顶点或至少有6个5度顶点。www.ap5u.com
页:
[1]