离散数学模拟试题1

离散数学模拟试题1一．单项选择题（每小题2分，共48分）。1．设R是集合A={1，2，3，4}上的二元关系，R={〈1，4〉，〈4，1〉〈1，3〉，〈3，1〉，〈2，4〉，〈4，2〉}，下面（）命题为真。Ⅰ．RR是对称的Ⅱ．RR是自反的Ⅲ．RR不是传递的（A）仅Ⅰ（B）仅Ⅱ（C）仅Ⅰ和Ⅱ（D）全真2．设N为自然数集合，+、－、×分别为普通的加法、减法和乘法。〈N，*〉在下面四种情况下不构成代数系统的为（）。（A）x*y=x+y－2×x×y(B)x*y=x+y(C)x*y=x×y(D)x*y=│x│+│y│3.设图G的顶点为五边形P的顶点，其边为P的边加上另一条连接P的两个不相邻顶点的边。下列命题中，（）命题是真命题。Ⅰ．G中存在欧拉回路Ⅱ．G中存在哈密尔顿回路（A）均不是（B）只有Ⅰ（C）只有Ⅱ（D）Ⅰ和Ⅱ4．设T为n（n≥3）阶无向树，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={54321,,,,vvvvv}，E={),(),,(),,(),,(),,(4332214441vvvvvvvvvv}下列命题为真的是（）。（A）G是哈密尔顿图（B）G是欧拉图（C）G是二分图（D）G是平面图9．设R+为正实数集合，〈R+，*〉在下面四种运算下不构成代数系统的是（）。（A）*代表普通加法（B）*代表普通乘法（C）*代表普通除法（D）*代表普通减法10．对于一个只有4个不同元素的集合A来说，A上的不同的二元关系的总数为（）。（A）42（B）24（C）162（D）取决于元素是否为数值11．设无向树T由3个3度顶点，2个2度顶点。其余顶点都是树叶，则T有（）片树叶。（A）3（B）4（C）5（D）612．下面集合之间的包含和属于关系中，（）为真。ⅠⅡ,,Ⅲbababa,,,,Ⅳcbababa,,,,,（A）Ⅰ和Ⅱ（B）Ⅰ和Ⅲ（C）Ⅰ和Ⅳ（D）Ⅱ、Ⅲ和Ⅳ13．设CBf:，BAg:。若gf是满射，则下面命题为真的是（）。（A）f是满射（B）f是单射（C）f是双射（D）g是满射14．设,SV，其中•为矩阵乘法，RbabaS,00，RaaT000则下面命题为真的是（）。ⅠV是一个半群Ⅱ〈T，•〉是V的子独异点Ⅲ〈T，•〉是V的子半群（A）只有Ⅰ（B）只有Ⅱ（C）Ⅰ和Ⅱ（D）全为真15．设R是非空集合A上的等价关系，Ax，Rx为x关于R的等价类，则下面命题为真的是（）。Ⅰ存在Ax，并且RxⅡ对任意的Ayx,，若Ryx,，则RRyxⅢAAxxR（A）只有Ⅰ（B）Ⅰ和Ⅲ（C）只有Ⅱ（D）Ⅱ和Ⅲ16．设R，S是非空集合A上的等价关系，则下面是A上的等价关系的是（）。（A）（A×A）－R（B）S∪R（C）S－R（D）S∩R17．设集合E={0，1，2，3}，则下面集合与E相等的是（）。（A）03xRx（B）92xRx（C）0652xxRx（D）30xNx18．对100名技术人员的调查结果表明，有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）15－r（D）5+5r20．设G是4阶群，则其子群的阶不能是下面的（）。（A）1（B）2（C）3（D）421．设命题P，Q的真值为T，命题R，S的真值为F，则下列哪个命题的真值为F（）。（A）（P∧（Q∧R））∨┒（（P∨Q）∧（R∨S））（B）（┑（P∧Q）∨┐R）∨（（（┐P∧Q）∨┐R）∧S）（C）（PR）∧（┐Q∧S）（D）（PQ）∨（RS）22．设P：天下雨，Q：我将去街上，R：我有时间，则下列命题中哪个符号化不正确（）。（A）P∧R→Q：如果天不下雨和我有时间，那么我将去街上。（B）┓P：天不下雨。（C）P→┓Q：天下雨，那么我不去街上。（D）P∧Q：天下雨，我也将去街上。23．设N是正整数集合，对下列哪一个运算*，〈N，*〉不能构成半群（）。（A）a*b=max（a，b）（B）a*b=min（a，b）（C）a*b=a（D）a*b=a/b，此处“/”是数的除法运算。24．设I，Q，R，C分别是整数集合、有理数集合、实数集合、复数集合，+，·是普通的数的加法和乘法运算，则下列代数系统不能构成域的是（）。（A）〈I，+，·〉（B）〈Q，+，·〉（C）〈R，+，·〉（D）〈C，+，·〉二．简答题（每小题7分，共42分）。1．设有5个城市521,,,vvv，任意两城市之间铁路造价如下（以百万元计算）：4,21vvw，10,51vvw，7,31vvw，16,41vvw，13,32vvw，8,42vvw，17,52vvw，3,43vvw，10,53vvw，12,54vvw，试求出连接5个城市的且造价最低的铁路网。2．试构造一棵带权为1，2，3，4，5，6，7，8，9，10的最优二叉树。3．试求公式qpqp的主析取范式和主合取范式。4．试用推理规则证明：NMGHJGHNMJ,,。5．设集合A={1，2，3，4，5，6}，R是集合A上的二元关系，其中R={〈x，y〉∣Ayx,且x整除y}，试求R的关系矩阵RM，关系图以及R的三个关系闭包，即r（R），s（R），t（R）。6．设DSn,是格，其中nS是n的所有正因数的集合，D是nS上的整除关系，当n=75时，试求每个元素的余元素。三．证明题（10分）：设〈G，*〉是一个独异点，并且对于G中的每一个元素x，都有x*x=e，其中e是幺元，证明〈G，*〉是一个阿贝尔群。参考答案模拟试题1答案一.单项选择题（每小题2分，共48分）。1.C2.A3.C4.C5.C6.B7.D8.D9.D10.C11.C12.B13.A14.D15.D16.D17.D18.C19.C20.C21.C22.A23.D24.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)每一个元素都无余元(D)每一个元素仅有一个余元4．设X={1,2,3,4}，Y={a,b,c,d}，则下列关系中为函数的是（）。(A){1,a，1,b，2,c}(B){1,a，2,d，3,c，4,b}(C){1,a，2,a，3,b}(D){1,a，1,b，2,b，4,b}5．下列语句中为命题的是（）。(A)今天是阴天。(B)你身体好吗？(C)我真快乐。(D)请不要走。6．设N为自然数集合，+、－、×分别为普通的加法、减法和乘法。〈N，*〉在下面四种情况下不构成代数系统的为（）。（A）x*y=x+y－2×x×y(B)x*y=x+y(C)x*y=x×y(D)x*y=│x│+│y│7．设集合，上的两个二元运算分别为模n加法运算和模n法运算，则代数系统为（）。（A）域（B）格（C）环，但不一定是域（D）布尔代数8．设P：天下雨，Q：我将去街上，R：我有时间，则下列命题中哪个符号化不正确（）。（A）P∧R→Q：如果天不下雨和我有时间，那么我将去街上。(B）┓P：天不下雨。(C）P→┓Q：天下雨，那么我不去街上。(D）P∧Q：天下雨，我也将去街上。9．设P,Q的真值是0，R,S的真值是1，下列公式中真值为1的是（）。(A)R→P(B)Q∧S(C)PS(D)Q∨R10．重言式的否定为（）。（A）重言式（B）矛盾式（C）可满足式（D）蕴涵式11．命题公式P®(Q®P)为（）。（A）重言式（B）可满足式（C）矛盾式（D）等价式12．下面集合中,（）关于数的减法是封闭的。(A)N={全体自然数}(B){2x|x∈Z}(C){2x+1|x∈Z}(D){x|x是质数}二.填空题。(每空3分，共42分)1.设A,≤是偏序集，如果A中任意两个元素都有（）和（），则称A,≤是格。2.设L,≤是格，如果L中存在（）和（），则称L是有界格。3.已知群的阶是12，则的子群的阶只可能是（）。4.不含（）和（）的图称为简单图。5.任何简单图中结点的度数之和等于边数的（）倍。6．集合常用的表示法有（）和（）。7．设A是非空有限集合，则中的幺元是（），零元是（），中的幺元是（），零元是（）。三.计算及证明题。(第1题---第3题每题6分，第4题、第5题每题8分，共34分)1.证明在格中，若，则有。2.设是格，其中是的所有正因数的集合，是上的整除关系，当=45时，求每个元素的余元素。3.证明等价式：。4.设是一个群，其中，是模6加法，求(1)的所有子群；(2)每个子群的右陪集；(3)的所有生成元；(4)中每个元素的阶。5.某市有七个新建单位要求煤气公司为其铺设煤气管道，经施工单位测量，这七个单位之间可通管道的路线长度如表所示(其中的“-”表示其间无直达路线)。铺设费用为25元∕米，试协助施工单位设计一个施工路线图，使得费用最少，并求出最小费用值。参考答案一.单项选择题。(每题2分，共24分)1.C2.D3.A4.B5.A6.A7.C8.A9.D10.B11.A12.B二.填空题。(每空3分，共42分)1.最小上界，最大下界2.最大元，最小元3.1，2，3，4，6，124.平行边，环5.26.描述法，列举法7.，，，三.计算及证明题。(第1题---第3题每题6分，第4题、第5题每题8分，共34分)1.证明在格中，若，则有。证明：因为，则，，所以。2.设是格，其中是的所有正因数的集合，是上的整除关系，当=45时，求每个元素的余元素。解：1与45互为余元素，5与9互为余元素，3与15不存在余元素。3.证明等价式：。证明：所以。4.设是一个群，其中，是模6加法，求(1)的所有子群；(2)每个子群的右陪集；(3)的所有生成元；(4)中每个元素的阶。解：(1)，其所有互不相同的右陪集为：，其所有互不相同的右陪集为：，其所有互不相同的右陪集为：，其所有互不相同的右陪集为：(3)1,5(4)0的阶是1；1的阶是6；2的阶是3；4的阶是3；5的阶是6。5.某市有七个新建单位要求煤气公司为其铺设煤气管道，经施工单位测量，这七个单位之间可通管道的路线长度如表所示(其中的“-”表示其间无直达路线)。铺设费用为25元∕米，试协助施工单位设计一个施工路线图，使得费用最少，并求出最小费用值。