离散数学模拟试题

1、离散数学模拟试题1一单项选择题（每小题2分，共48分）。1设R是集合A=1，2，3，4上的二元关系，R=1，4，4，11，3，3，1，2，4，4，2，下面（ ）命题为真。是对称的 是自反的 不是传递的（A）仅 （B）仅 （C）仅和 （D）全真2设N为自然数集合，+、分别为普通的加法、减法和乘法。N，*在下面四种情况下不构成代数系统的为（ ）。（A）x*y=x+y2xy (B)x*y=x+y (C)x*y=xy (D)x*y=x+y3.设图G的顶点为五边形P的顶点，其边为P的边加上另一条连接P的两个不相邻顶点的边。下列命题中，（ ）命题是真命题。 G中存在欧拉回路 G中存在哈密尔顿回路（A）均不

2、是 （B）只有 （C）只有 （D）和4设T为n（n3）阶无向树，T有（ ）条割边。（A）n条 （B）n-2条 （C）n-1条 （D）没有5设A=1，2，3，4，5，6，R是集合A上的整除关系，下面命题中，（ ）是假的。（A）4，5，6全是A的极大元 （B）A没有最大元 （C）6是A的上界（D）1是A的最大下界6设A=1，2，3，4，5，则A有（ ）个子集。（A）16 （B）32 （C）64 （D）1287设连通图G有8个顶点和12条边，则任意一棵G的生成树的总边数为（ ）。（A）12 （B）9 （C）8 （D）78设无向图G=V，E，其中V=，E=下列命题为真的是（ ）。（A）G是哈密尔顿图（

3、B）G是欧拉图 （C）G是二分图 （D）G是平面图9设R+为正实数集合，R+，*在下面四种运算下不构成代数系统的是（ ）。（A）*代表普通加法（B）*代表普通乘法（C）*代表普通除法（D）*代表普通减法10对于一个只有4个不同元素的集合A来说，A上的不同的二元关系的总数为（ ）。（A）42 （B）24 （C） （D）取决于元素是否为数值11设无向树T由3个3度顶点，2个2度顶点。其余顶点都是树叶，则T有（ ）片树叶。（A）3 （B）4 （C）5 （D）612下面集合之间的包含和属于关系中，（ ）为真。 （A）和 （B）和 （C）和 （D）、和13设，。若是满射，则下面命题为真的是（ ）。（A）

4、是满射 （B）是单射 （C）是双射 （D）是满射14设，其中为矩阵乘法， ，则下面命题为真的是（ ）。 V是一个半群 T， 是V的子独异点 T， 是V的子半群（A）只有 （B）只有 （C）和 （D）全为真15设R是非空集合A上的等价关系，为x关于R的等价类，则下面命题为真的是（ ）。 存在，并且 对任意的，若，则 （A）只有 （B）和 （C）只有 （D）和16设R，S是非空集合A上的等价关系，则下面是A上的等价关系的是（ ）。（A）（AA）R （B）SR （C）SR （D）SR17设集合E=0，1，2，3，则下面集合与E相等的是（ ）。（A） （B）（C） （D）18对100名技术人员的调查结

5、果表明，有32人学过日语，20人学过法语，45人学过英语。又其中有15人既学过日语又学过英语，7人既学过日语又学过法语，10人既学过法语又学过英语，30人没学过这3门语言中的任何一种。则下面说法中正确的是（ ）。（A）3种语言都学过的人数为6。（B）只学过日语的人数为32。（C）至少学习以上3种语言中的2种语言的人数为22。（D）只学习日语和法语的人数为7。19设G是一个连通的无基本回路的图，G中包含：3个3度顶点，2个2度顶点，r个1度顶点，且G中不再包含其它顶点，则G的顶点个数为（ ）。（A）6 （B）9 （C）15r （D）5+5 r20设G是4阶群，则其子群的阶不能是下面的（ ）。（A

6、）1 （B）2 （C）3 （D）421设命题P，Q的真值为T，命题R，S的真值为F，则下列哪个命题的真值为F（ ）。（A）（P（QR）（PQ）（RS）（B）（PQ）R）（PQ）R）S）（C）（PR）（QS） （D）（PQ）（RS）22设P：天下雨，Q：我将去街上，R：我有时间，则下列命题中哪个符号化不正确（ ）。（A）PRQ：如果天不下雨和我有时间，那么我将去街上。（B）P：天不下雨。（C）PQ：天下雨，那么我不去街上。（D）PQ：天下雨，我也将去街上。23设N是正整数集合，对下列哪一个运算*，N，*不能构成半群（ ）。（A）a*b=max（a，b） （B）a*b=min（a，b）（C）a*b

7、=a （D）a*b=a/b，此处“/”是数的除法运算。24设I，Q，R，C分别是整数集合、有理数集合、实数集合、复数集合，+，是普通的数的加法和乘法运算，则下列代数系统不能构成域的是（ ）。（A）I，+， （B）Q，+， （C）R，+， （D）C，+，二简答题（每小题7分，共42分）。1设有5个城市，任意两城市之间铁路造价如下（以百万元计算）：，试求出连接5个城市的且造价最低的铁路网。2试构造一棵带权为1，2，3，4，5，6，7，8，9，10的最优二叉树。3试求公式的主析取范式和主合取范式。4试用推理规则证明：。5设集合A=1，2，3，4，5，6，R是集合A上的二元关系，其中R=x，y且x整除

8、y，试求R的关系矩阵，关系图以及R的三个关系闭包，即r（R），s（R），t（R）。6设是格，其中是的所有正因数的集合，是上的整除关系，当=75时，试求每个元素的余元素。三证明题（10分）：设G，*是一个独异点，并且对于G中的每一个元素x，都有x*x=e，其中e是幺元，证明G，*是一个阿贝尔群。参考答案模拟试题1答案一. 单项选择题（每小题2分，共48分）。1. C 2. A 3. C 4. C 5. C6. B 7. D 8. D 9. D 10. C11. C 12. B 13. A 14. D 15. D16. D 17. D 18. C 19. C 20. C21. C 22. A 23

9、. D 24. A二简答题（每小题7分，共42分）。1. 2. 3. 4. 5. 关系矩阵：关系图：6. 1与75互为余元素，3与25互为余元素，5与15不存在余元素。三证明题（10分）证明：由可知，中的每一个元素都以自身为逆元，所以是群。对任意的，有所以运算*是可交换的，因此，是一个阿贝尔群。离散数学模 拟 试 题2一. 单项选择题。(每题2分，共24分)1. 一个格的哈斯图如下，下述子集中为子格的是（ ）。2. 如下的哈斯图所示偏序集为格的是（ ）。3. 设A是有界格，若它也是有余格，只要（ ）。 (A) 每一个元素都有一个余元 (B) 每一个元素至少有两个余元(C) 每一个元素都无余元

10、(D) 每一个元素仅有一个余元4设X=1, 2, 3, 4，Y=a, b, c, d，则下列关系中为函数的是（ ）。(A) ， (B) ，(C) ， (D) ，5下列语句中为命题的是（ ）。(A) 今天是阴天。 (B) 你身体好吗？(C) 我真快乐。 (D) 请不要走。 6设N为自然数集合，+、分别为普通的加法、减法和乘法。N，*在下面四种情况下不构成代数系统的为（ ）。（A）x*y=x+y2xy (B)x*y=x+y (C)x*y=xy (D)x*y=x+y7设集合，上的两个二元运算分别为模n加法运算和模n法运算，则代数系统为（ ）。（A）域 （B）格 （C）环，但不一定是域 （D）布尔代数

11、8设P：天下雨，Q：我将去街上，R：我有时间，则下列命题中哪个符号化不正确（ ）。（A）PRQ：如果天不下雨和我有时间，那么我将去街上。(B）P：天不下雨。(C）PQ：天下雨，那么我不去街上。(D）PQ：天下雨，我也将去街上。9设P, Q的真值是0，R, S的真值是1，下列公式中真值为1的是（ ）。(A) RP( B) QS (C) PS (D) QR10 重言式的否定为（ ）。（A）重言式 （B）矛盾式 （C）可满足式 （D）蕴涵式11命题公式P (QP)为（ ）。（A）重言式 （B）可满足式 （C）矛盾式 （D）等价式12下面集合中,（ ）关于数的减法是封闭的。(A) N = 全体自然数

12、(B) 2x | xZ(C) 2x+1 | xZ(D) x | x是质数二. 填空题。(每空3分，共42分)1. 设是偏序集，如果A中任意两个元素都有（ ）和（ ），则称是格。2. 设是格，如果L中存在（ ）和（ ），则称L是有界格。3. 已知群的阶是12，则的子群的阶只可能是（ ）。4. 不含（ ）和（ ）的图称为简单图。5. 任何简单图中结点的度数之和等于边数的（ ）倍。6集合常用的表示法有（ ）和（ ）。7设A是非空有限集合，则中的幺元是（ ），零元是（ ），中的幺元是（ ），零元是（ ）。三. 计算及证明题。(第1题-第3题每题6分，第4题、第5题每题8分，共34分)1. 证明在格中，

13、若，则有。2. 设是格，其中是的所有正因数的集合，是上的整除关系，当=45时，求每个元素的余元素。3. 证明等价式：。4. 设是一个群，其中，是模6加法，求(1) 的所有子群；(2) 每个子群的右陪集；(3) 的所有生成元；(4) 中每个元素的阶。5. 某市有七个新建单位要求煤气公司为其铺设煤气管道， 经施工单位测量， 这七个单位之间可通管道的路线长度如表所示 (其中的“-”表示其间无直达路线)。 铺设费用为25元米，试协助施工单位设计一个施工路线图，使得费用最少，并求出最小费用值。参考答案一. 单项选择题。(每题2分，共24分)1. C 2. D 3. A 4. B 5. A6. A7. C

14、8. A 9. D10. B11. A12. B二. 填空题。(每空3分，共42分)1. 最小上界，最大下界2. 最大元，最小元3. 1，2，3，4，6，12 4. 平行边，环5. 2 6. 描述法，列举法7. ，三. 计算及证明题。(第1题-第3题每题6分，第4题、第5题每题8分，共34分)1. 证明在格中，若，则有。证明：因为，则，所以。2. 设是格，其中是的所有正因数的集合，是上的整除关系，当=45时，求每个元素的余元素。解：1与45互为余元素，5与9互为余元素，3与15不存在余元素。3. 证明等价式：。证明： 所以。4. 设是一个群，其中，是模6加法，求(1) 的所有子群；(2) 每个子群的右陪集；(3) 的所有生成元；(4) 中每个元素的阶。解