《离散数学》期末练习题考试卷和答案

1《离散数学》练习题一一、单项选择题1．设集合3,2,1,0E，则下面集合与E相等的是。A．03xRxB．92xRxC．0652xxRxD．30xNx2．设6,5,4,3,2,1A，R是集合A上的整除关系，下列叙述中错误的是。A．4，5，6全是A的极大元B．A没有最大元C．6是A的上界D．1是A的最大下界3.设4,3,2,1X，dcbaY,,,，则下列关系中为从X到Y的映射是。A．cba,3,,2,,1B．bcba,4,,3,,2,,1C．baa,3,,2,,1D．cbbba,3,,4,,2,,1,,14.设G是4阶群，则其子群的阶不能是下面的。A.1B.2C.3D.45．设5,4,3,2,1S，则下列集合中等于S的是。A．4,3,2,1B．25,2xxx是有理数C．5,xxx是正整数D．5,xxx是有理数6．下面有关集合之间的包含和属于关系的说法，正确的是。Ⅰ．Ⅱ．,,Ⅲ．bababa,,,,Ⅳ．cbababa,,,,,A．Ⅰ和ⅡB．Ⅰ和ⅢC．Ⅰ和ⅣD．Ⅱ、Ⅲ和Ⅳ7.设A为n个元素的集合，则A上有个二元关系。A．n2B．nn2C．2nD．n8.数的加法在下列集合中上是封闭的。A．1,0B．11，C．Zbaba,D．是奇数xx9.下列图形中为欧拉图的是。10．设,L是格，Lcba,,，且abac,，则cbacaba。2A.=B.C.D.没关系11．设BA，则有。A．BB．BC．BAD．AB12.QP。A．QPPB．PQQPC．PQQPD．PQQP13.对于一个只有4个不同元素的集合A来说，A上的不同的二元关系的总数为。A．4B．16C．162D．4214.下列代数系统*,G中，不构成群。A．01,1G，*是模11乘法B．9,5,4,3,1G，*是模11乘法C．G为有理数集，*是普通加法D．G为有理数集，*是普通乘法15.设G为有n个顶点的简单图，则有。A．nGB．nGC．nGD．nG16．设5,4,3,2,1S，则下列集合中等于S的是（）。A．4,3,2,1B．25,2xxx是有理数C．5,xxx是正整数D．5,xxx是有理数17．设8,7,6,5,4,3,2,1A，下列选项正确的是（）。A．A1B．A3,2,1C．A5,4D．A18．设A为n个元素的集合，则A上有（）个二元关系。A．n2B．nn2C．2nD．n19．数的加法在下列集合中（）上是封闭的。A．1,0B．11，C．Zbaba,D．是奇数xx20．下列图形中为欧拉图的是（）。321．设5,4,3,2,1S，则下列集合中等于S的是（）。A．4,3,2,1B．25,2xxx是有理数C．5,xxx是正整数D．5,xxx是有理数22．设8,7,6,5,4,3,2,1A，下列选项正确的是（）。A．A1B．A3,2,1C．A5,4D．A23．设A为n个元素的集合，则A上有（）个二元关系。A．n2B．nn2C．2nD．n24．数的加法在下列集合中（）上是封闭的。A．1,0B．11，C．Zbaba,D．是奇数xx25．下列图形中为欧拉图的是（）。26．下列命题中，是错误的。A.xxxB.xxxC.若xxA，则Ax且AxD.若BA，则BA27．幂集)))(((PPP是。A．,,B．,,,4C．,,,,D．,,28.下列命题公式中为重言式。Ⅰ．rqppⅡ．rpqprqpⅢ．rprpqpⅣ．rqqpA.ⅢB.Ⅰ和ⅢC.Ⅰ和ⅡD.Ⅰ、Ⅱ、Ⅲ和Ⅳ29．任意一个具有多个等幂元的半群(若元素a满足aaa*，则称a为等幂元)，该半群。A．不能构成群B．不一定能构成群C．必能构成群D．能构成交换群30．设I是整数集合，下列集合中关于数的加法和乘法构成整环。A．Inn2B．Inn12C．Innn,0D．I31．设集合3,2,1A，5,4,3,2B，16,8,4,2C，4,3,2,1D，又规定偏序关系“|”是集合上的“整除”关系，则下列偏序集中能构成格。A．,AB．,BC．,CD．二、填空题1．设A为非空集合，且nA，则A上不同的二元关系的个数为，A上不同的映射的个数为。2．设P、Q为两个命题，当且仅当时，QP的真值为1。3.在运算表中的空白处填入适当符号，使*,,,cba成为群。*abcaababccc4.当n为数时，3nKn必为欧拉图。5.某校有足球队员38人，篮球队员15人，排球队员20人，三队队员总数为58人，且其中只有3人同5时参加3种球队，那么仅仅参加两种球队的队员人数是。6.命题公式QP的主析取范式为。7.一棵无向树有两个2度顶点，一个3度顶点，三个4度顶点，则它的树叶数为。8．设P：我生病，Q：我去学校，命题“如果我生病，那么我不去学校”符号化为。9．P,Q为两个命题，当且仅当时，QP的值为0。10.设DCBA,,,是四个非空集合，则DCBA的充分必要条件是。11.在有理数集合Q上定义二元运算*：abbaba*，则*,Q的幺元是。12.设,L是分配格，若对任意的Lcba,,，都有cabacaba,，则。13.某班有学生50人，有26人在第一次考试中得优，有21人在第二次考试中得优，有17人两次考试都没有得优，那么两次考试都得优的学生人数是。14.将布尔表达式cbbcca化简得。15.设P：我有钱，Q：我去看电影，命题“当且仅当我有钱时，我才去看电影”符号化为。16.设*,,ba是群，且baa*，则bb*。17．命题公式rqqpp是永（）式。18．QP的主析取范式中，含有（）个极小项。19.设集合gfedcbaA,,,,,,，A上有一个划分gfedcba,,,,,,，那么所对应的等价关系R应有（）个序偶。20.在有理数集合Q上定义二元运算*：abbaba*，则*,Q的幺元是（）。21.一个（）称为布尔代数。22．命题公式rqqpp是永（）式。23．QP的主析取范式中，含有（）个极小项。24.设集合gfedcbaA,,,,,,，A上有一个划分gfedcba,,,,,,，那么所对应的等价关系R应有（）个序偶。25.在有理数集合Q上定义二元运算*：abbaba*，则*,Q的幺元是（）。26.一个（）称为布尔代数。27．QPQP的主析取范式是。(写出一般6表示形式即可)28．设集合,,,dcbaA，R是A上的二元关系，且cadccbabbaR,,,,,,,,,，则R的传递闭包Rt。29．设集合12,8,6,4,3,2A，R是A上的整除关系，则R的关系矩阵RM，哈斯图为。30.一个连通平面图有9个顶点，它们的度数分别为：2，2，2，3，3，3，4，4，5，则该图共有个面。31.集合cbaA,,上可以定义的二元运算的个数是。三、解答题1.求带权值为1,3,5,5,8,12,14,19的最优二叉树。(只要最终结果，不要求中间过程)(8分)2．求的最小生成树。(只要最终结果，不要求中间过程。)(8分)3.设G是平面图，有n个顶点，m条边，f个面，k个连通分支，证明：1kfmn(10分)74.化简下列布尔表达式。(1)cbcbaba(2)cbacba(8分)5.证明在格,,L中，是格L中的偏序关系，Lcba,,，若cba，则有cabacbba。(8分)6.设cbaA,,，AP是A的幂集，是集合的对称差运算，已知,AP是群，在群,AP中，求：(1)关于运算的幺元；(2)AP中每个元素的逆元；(3)求元素x，使得bxa。(9分)7.设*,,,,dcba是半群，其运算表如下(8分)证明：*,,,,dcba是循环群。*abcdaabcdbbcdaccdabddabc88.设R是集合A上的二元关系，若R是自反的和传递的，则RRR。(8分)9.设DS,75是格，其中75S是75的的所有正因数的集合，D是75S上的整除关系，求75S中每个元素的余元素。(8分)10.证明等价式：QRPQRQP。(6分)11.用推理规则证明：SRSRBABAPPDCDC,,,。12．设R是非空集合A上的二元关系，令1RRIA，证明：具有自反性，对称性。13.设*,G是独异点，并且对于G中的每一个元素x，都有exx*，其中e是幺元，证明：*,G是一个阿贝尔群。914.证明：循环群aG是交换群。15.设,,L是一个格，Lba,，且ba，令bxaLxS其中是格L中的偏序关系，证明：,,S是,,L的子格。16.证明在格,,L中，是格L中的偏序关系，Lcba,,，若ab，ac，则有cabacba。17.给定树叶的权为1，4，9，16，25，36，49，64，81，100，试构造一棵最优二叉杩。18.证明：若无向图G是不连通的，则其补图G是连通的。1019．(10分)求带权1、2、3、4、5、6、7、8、9、10的最优二叉树。20.(10分)设集合cbaA,,，R是A上的二元关系，bccabaaaR,,,,,,,，试求：(1)AP；(2)R的关系图与关系矩阵RM；(3)Rr、Rs、Rt。21．证明等价式：CQPACQPACAQP。22.证明：树是一个偶图。1123.设*,G是群，对任意的Ga，令xaaxGxH**，证明：H是G的子群。24.设R为实数集，RRRRf:，对任意的RRyx,，定义：yxyxyxf,,证明：f是双射。25.设,*,B是含幺环,且*满足等幂律,在B上定义运算+,·,ˉ如下:bababa*,baba*,1aa证明:1,0,,,,B是一个布尔代数，其中0和1分别是关于运算和*的幺元。26．用推理规则证明：CBEDAEDCBA,,(10分)27．设R是非空集合A上自反的二元关系，证明：1R也是自反的。(10分)28．设G是整数加群，在G上定义：2*baba，证明：*,G是交换群。(20分)1229．设,,L是一个格，Lba,，且ba，令bxaLxS其中是格L中的偏序关系，证明：,,S是,,L的子格。(15分)30．给定树叶的权为1，4，9，16，25，36，49，64，81，100，试构造一棵最优二叉杩。(10分)31．假设一家化工厂要将多种化学产品利用铁路从精炼厂运到炼油厂，但是根据EPA(美国环保署)的规定，这些化学产品不能全部都装在同一节车厢里运输，因为如果它们混和起来，就会产生剧烈反应，从而引发事故，为了使费用最低，厂长希望使用尽可能少的车厢，问最少使用多少车厢？其中