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

1、离散数学试卷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） （

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，

3、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）命题“如果我有时间，我就去图书馆”符号化为 ；三、假设、是任意两个集合，证明：。证明：对 则 或者 由幂集定义可知：或者 所以 因此 故 四、假设

4、是自然数集合，定义上的二元关系。证明：是一个等价关系，并求出关系所确定的等价类。证明：（1）对，则是偶数，所以是自反的； 对，假设，则是偶数，而也是偶数 所以，故是对称的； 对，假设， 则有，是偶数； 若是偶数，由于是偶数，所以也是偶数，则是偶数 若是奇数，由于是偶数，所以是奇数，又因为是偶数，所以是奇数，因此是偶数所以 是传递的。综上 是等价关系。（2）当是偶数时， 当是奇数时，五、对下列集合在整除关系下构成的偏序集，画出Hasse图，并写出最大元，最小元，极大元，极小元。（1）（2）（3）解：（1）没有最大元和最小元；极大元是24,36。 （2）最大元和极大元是45，最小元和极小元是1。

5、（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> 的图示。解：离散数学模拟卷2参考答案一、选择题1、请指出下列选项中哪一个是错误的：（2）（1） （2） （3） （4）2、对任意集合，下述论断正确的是：（1）（1）若，则 （2）若，则（3）若，则 （4）若，则3、假设上的关系，那么，是：（

6、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）图中包含一条回路经过图中

7、每个顶点一次且仅一次；（4）图中包含一条路经过图中每个顶点一次且仅一次。9、一棵树有2个2度顶点，1个3度顶点，3个4度顶点，则其1度的顶点数为：（2）（1）5 （2）7 （3）8 （4）910、完全叉树中有片叶，个分支点，则有关系式是：（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>

8、,<3,2>；（3）<2,3>；4、假设，是到的函数，其中：（a）；（b），；（c），；则：（1）g 是满射；（2）g 是双射；5、设无向图有36条边，有6个3度的顶点，其余顶点度数均小于3，则中至少有33个顶点。6、假设：今天天气好，：我就去锻炼身体。（1）命题“如果今天天气好，我就去锻炼身体”符号化为 P®Q ；三、假设、是任意两个集合，证明：。证明：对，则且 所以 并且 由交集的定义，则 所以 因此 反之，假设 则 所以 并且 所以 且 由交集定义，则 故 综上 四、证明定义在实数集合上的关系是一个等价关系。证明：对，则是整数，所以是自反的； 对，并且设

9、，则是整数 而也是整数，所以，是对称的； 对，并且设， 则 ，是整数； 而 也是整数 所以 因此 是传递的 综上，是等价关系。五、对下列集合在整除关系下构成的偏序集，画出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度顶点 则度为奇数的顶

10、点只能为偶数个，所以5度顶点应该为4个，而6度顶点最多也为4个，所以与命题条件有9个顶点产生矛盾；因此G中至少有5个6度顶点或至少有6个5度顶点。离散数学模拟3参考答案一、选择题1、假设，下列选项错误的是：（2）（1） （2） （3） （4）2、对任意集合，下述论断正确的是：（1）（1）若，则 （2）若，则（3）若，则 （4）若，则3、假设上的关系如下，具有传递性的关系是：（4）（1）（2）（3）（4）4、假设和是集合上的任意关系，则下列命题为真的是：（1）（1）若和是自反的，则也是自反的；（2）若和是反自反的，则也是反自反的；（3）若和是对称的，则也是对称的；（4）若和是传递的，则也是传递的

11、。5、若是满射函数，则复合函数必是：（3）（1）双射函数 （2）单射函数 （3）满射函数 （4）不单射也不满射6、假设，令：，则不同的函数个数为：（2）（1）2+3个 （2）个 （3）个 4）个7、一个无向简单图有条边，个顶点，则图中顶点的总度数为：（3）（1） （2） （3） （4）8、一个图是半欧拉图是指：（2）（1）图中包含一条回路经过图中每条边一次且仅一次；（2）图中包含一条路经过图中每条边一次且仅一次；（3）图中包含一条回路经过图中每个顶点一次且仅一次；（4）图中包含一条路经过图中每个顶点一次且仅一次。9、下面哪一种图不一定是树：（3）（1）无回路的连通图 （2）有个顶点条边的连通图

12、（3）每一对顶点之间都有通路 （4）连通但删去一条边则不连通的图.10、完全叉树中有片叶，个分支点，则它们之间的关系表达式是：（2）（1） （2） （3） （4）二、填空题1、假设， （1）5，7；（2）5；2、假设上的关系，则：（1）；（2）；（3）；3、假设，是到的函数，其中：（a）；（b）；（c）。则：（1）_g_是满射；（2）_g_是双射；4、设无向图有24条边，有4个3度的顶点，其余顶点度数均小于3，则中至少有22个顶点。5、一棵树有2个2度顶点，1个3度顶点，3个4度顶点，则有 7 片叶。6、假设：我有时间，：我去体育馆。（1）命题“如果我有时间，我就去体育馆”符号化为 ；三、假设、是非空集合，并且。证明：。 证明：对任意的，有，所以 因为，所以 所以 ，因此 故 同理可证 综上 。四、假设R,S是集合A上的等价关系，证明RÇS也是集合A上的等价关系。证明：对任意的，因为R,S是集合A上的等价关系，所以是自反、对称、传递的。 故有 ，所以，是自反的； 对任意的，并且假设，有 所以 ，因此，是对称的； 对任意的，并且假设，有，并且所以有 因此，是传递的。综上是集合A上的等价关系。五、对下列集合在整除关系下构成的偏序集，画出Hasse图，并写出最大元，最小元，极大元，极小元。（1）