离散数学练习题库

1离散数学一、选择题1.给出下列语句：（1）5能被2整除.（2）2是素数当且仅当三角形有三条边.（3）x+50.（4）4是2的倍数或是3的倍数.（5）明天我去看电影.其中（1）（2）（4）（5）是命题；（2）（4）是复合命题。2.给出以下命题：（1）1+2=3743321)2(.743.（3）743321)4(.743521.其中真值是T的命题是(2)(4)。3.给出下列语句：（1）5能被2整除.（2）雪是黑色的当且仅当太阳从西方升起.（3）x+50.（4）小李在宿舍里.其中（1）（2）（4）是命题；（2）是复合命题。4.给出以下命题：（1）1+2=3743321)2(.743.（3）743321.(4)743321其中真值是F的命题是（1）（3）。5.设C(x):x是国家级运动员，G(x):x是健壮的，则命题“没有一个国家级运动员不是健壮的”可符号化为(D)。))()(()A(xGxCx))()(()B(xGxCx))()(()C(xGxCx))()(()D(xGxCx6.设集合A={{1,2,3},{4,5},{6,7,8}}，则下式为真的是(C)。(A)1A(B){1,2,3}A(C){{4,5}}A(D)A7.设A＝{1,2},B={a,b,c},C={c,d},则A×(BC)=(A)。(A){1,c,2,c}(B){c,1,2,c}(C){c,1c,2,}(D){1,c,c,2}8.如第5题图所示各图，其中存在哈密顿回路的图是(C)。9.下列式子中正确的有（B）。10.某个集合的元数为10，可以构成（D）个子集。A、10B、20C、D、11.下列命题正确的有（A）。A、B、C、D、12.设10,,2,1A上的关系AxAxyxyxR,,10,，则R的性质为（B）。（A）自反的（B）对称的（C）传递的、对称的（D）反自反的、传递的A、B、C、D、213.已知集合A＝{a,b,c}上的二元关系R的关系矩阵MR＝001011010，那么R＝(D)。(A){a,b,b,a,b,b,a,c}(B){a,b,b,a,b,b,c,b}(C){a,b,a,a,b,b,c,a}(D){a,b,b,a,b,b,c,a}14.设V＝{a,b,c,d},与V能构成强连通图的边集E＝(A)。(A){a,b,a,c,d,a,b,d,c,d}(B){a,d,b,a,b,c,b,d,d,c}(C){a,c,b,a,b,c,d,a,d,c}(D){a,d,b,a,b,d,c,d,d,c}二、填空题1．集合有两种表示方法，分别为列举法和描述法。2.“使有意义的所有的集合。”可表示为：。“大于3而小于或等于7的整数组成的集合”表示为。3．写出A={a,b,c,d}的全部子集，。4．设，则A-B=，B-A=，～A=，～B=。5．设A、B是两个集合，其中A={1，2}，B={a,b,c}，则A×B=，B×A=，所以笛卡尔积不满足交换律。6．若A=}0{xZxx，2xZxxB，则BA；BA；BA；BA。1,01,0ZBAABABAZBA，，，;7．若A=}3{xNxx，2xNxxB，则BA；BA；BA；BA。2102NBABABANBA，，，，8．将下列各式翻译成自然语言，并在实数范围判断它们的真伪：（1）)5()2()5(yxxyyxyx（1）；（2）。（1）对任意的x,存在y,使得x+y=5,是真命题,（2）存着y对任意的x，都有5yx是假命题；9.设4321，，，A上关系3,1,3,342,21，，，R，则3自反闭包Rr；对称闭包Rs；传递闭包Rt。Rr3,1,4,2,2,1,4,4,3,3,2,2,1,1,Rs1,3,3,1,3,3,2,4,4,2,1,2,2,1,3,3,4,2,4,1,3,1,2,1Rt10.弱连通图G是欧拉图的充要条件是G的每节点的入度等于其出度。11.设X＝{a,b,c}，R是X上的二元关系，其关系矩阵为MR＝001001101，那么R的关系图为12.各点之间都有边相连的图称为；只有点，没有边的图称为；只有一个点的零图称为。完全图；零图；平凡图13.设G是完全二叉树，G有15个点，其中8个叶子结点，则G有条边；G中度数为2的顶点数是。14；714.在有向图的邻接矩阵中，第i行元素之和与第j列元素之和分别为。结点vi的出度与结点vj的入度15.连通无向图G中存在欧拉轨迹的充要条件是G的度数为奇数的节点个数为0或为2。16.对右图二叉树的结点先根遍历的次序是，中根遍历的次序是，后根遍历的次序是。ABCDEF；CBDAEF；CDBFEA三、证明题1.设A、B、C为三个任意集合，证明题：1）证明：设同理可证：所以acb42.证明：所以原式成立。3．证明：对任意集合A，B，C有CABACBACBACBA~~=CBA~=CABA~=CABA四、计算题1．设全集E＝(a,b,c,d,e,f),A={a,d}，B={a,b,e}，C={b,d}，求下列集合：(1)CBA~)(；(2))()(APAA.(1)},,,{},,,{}{~)(fecafecaaCBA；(2))()()(AAAAAA.}},{},{},{,{)(dadaAP.故)()(APAA＝}},{},{},{,{dada2．化简集合表达式：((ABC)(AB))－((B(B－C))－A)((ABC)(AB))－((B(B－C))－A)＝(AB)－(B－A）=(AB)(～BA)=A(B～B)=A=A3.设集合AcbaA,,,上的关系accbbaR,,,,,（1）（2分）写出它的关系矩阵A；（2）（4分）求出它的自反闭包)(Rr；（3）（4分）求出它的对称闭包)(Rs；（1）001100010A（2）,,,,,,,,,,,cccbbbacbaaaRr（3）caacbccbabbaRs,,,,,,,,,,,4.设集合AdcbaA,,,,上的关系dccbabbaR,,,,,,,（1）（2分）写出它的关系矩阵A；（2）（4分）求出它的自反闭包)(Rr；（3）（4分）求出它的对称闭包)(Rs；5（1）0000100001010010A（2）dddccccbbbabbaaaRr,,,,,,,,,,,,,,,（3）cddcbccbabbaRs,,,,,,,,,,,5.设无向图G=（P，L），P={v1，v2…v6}，L={（v1，v2），（v2，v3），（v1，v4），（v2，v5），（v2，v4），（v3，v5），（v4，v5），（v1，v3）}。（1）画出G的图形；（2）求出G中各顶点的度及奇数度顶点的个数。G中各点的度如下：deg（v1）=3，deg（v2）=4，deg（v3）=3，deg（v4）=3，deg（v5）=1，deg（v6）=0。奇数度顶点的个数为4。v1v2v5v6v8v7v4v3第6题图v1v2v5v6v8v7v4v31334107997126856.图G如第6题图试求图G的最小生成树，并计算该生成树的权。图G的最小生成树，如第6题答案图.首先选对边(v1,v2)得2分，再每选对一条边得1分.该生成树的权=40.34776856第6题答案图7.已知带权图G，如第7题图所示．试求图G的最小生成树，并计算该生成树的权。做法如下：①选边1；②选边2；③选边3；④选边5；⑤选边7最小生成树为{1,2,3,5,7}．如第7题答案图中粗线所示．权数为18．1928743第7题图56101928743第7题答案图5610