离散数学练习题库.doc

离散数学一、选择题1.给出下列语句： （1）5能被2整除. （2）2是素数当且仅当三角形有三条边. （3） x+50. （4）4是2的倍数或是3的倍数. （5）明天我去看电影.其中 （1）（2）（4）（5） 是命题； （2）（4） 是复合命题。 2.给出以下命题： （1）1+2=3. （3）.其中真值是T的命题是 (2)(4) 。3.给出下列语句： （1）5能被2整除. （2）雪是黑色的当且仅当太阳从西方升起. （3） x+50. （4）小李在宿舍里.其中 （1）（2）（4） 是命题； （2） 是复合命题。4.给出以下命题： （1）1+2=3. （3）. (4)其中真值是F的命题是 （1）（3） 。5. 设C(x): x是国家级运动员，G(x): x是健壮的，则命题“没有一个国家级运动员不是健壮的”可符号化为 ( D )。 6.设集合A=1,2,3, 4,5, 6,7,8，则下式为真的是( C )。(A) 1A (B) 1,2, 3A(C) 4,5A (D) A7. 设A1,2,B=a,b,c,C=c,d, 则A(BC)= ( A )。 (A) , (B) , (C) , (D) ,8. 如第5题图所示各图，其中存在哈密顿回路的图是 ( C )。A、h B、h h C、h h D、h h h h h h h h h h h h h h 9.下列式子中正确的有（B ）。10.某个集合的元数为10，可以构成（D ）个子集。 A、10 B、20 C、 D、11.下列命题正确的有（A ）。 A、 B、 C、 D、12. 设上的关系，则R的性质为 （ B ）。 （A）自反的 （B）对称的 （C）传递的、对称的 （D）反自反的、传递的13.已知集合Aa,b,c上的二元关系R的关系矩阵MR，那么R( D )。(A) , (B) , (C) , (D) , 14.设Va,b,c,d,与V能构成强连通图的边集E( A )。(A) , (B) ,(C) , (D) ,二、填空题 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，则AB= ，BA= ，所以笛卡尔积不满足交换律。 6若A=，则 ； ； ； 。;7若A=，则 ； ； ； 。8将下列各式翻译成自然语言，并在实数范围判断它们的真伪： （1） （1） ； （2） 。（1）对任意的x,存在y,使得x+y=5,是真命题,（2）存着对任意的，都有是假命题；9. 设上关系，则自反闭包 ；对称闭包 ；传递闭包 。 , ,10. 弱连通图G是欧拉图的充要条件是 G的每节点的入度等于其出度 。11.设Xa,b,c，R是X上的二元关系，其关系矩阵为 ah hc bh MR，那么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）证明：设 同理可证：所以2.证明： 所以原式成立。3证明：对任意集合A，B，C有 =四、计算题1设全集E(a,b,c,d,e,f), A=a,d，B=a,b,e，C=b,d，求下列集合：(1) ； (2). (1) ； (2). . 故 2化简集合表达式：(ABC)(AB)(B(BC)A) (ABC)(AB)(B(BC)A)(AB)(BA） =(AB)(BA) =A(BB)=A=A 3. 设集合上的关系 （1）（2分）写出它的关系矩阵A；（2）（4分）求出它的自反闭包；（3）（4分）求出它的对称闭包；（1） （2） （3） 4.设集合上的关系 （1）（2分）写出它的关系矩阵A；（2）（4分）求出它的自反闭包；（3）（4分）求出它的对称闭包；（1） （2） （3） 5.设无向图G=（P，L），P=v1，v2v6，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。 3410799712685 v1 v2 6. 图G如第6题图试求图G的最小生成树，并计算该生成树的权。 v5 v613 v8 v7 v4 v3 第6题图3477685 图G的最小生成树， 如第6题答案图. 首先选对边(v1,v2)得2分，再每选对一条边得1分. 该生成树的权=40. v1 v2 v5 v6 v8 v7 v4 v3 第6题答案图 1 9 2 8 7 4 3 第7题图5 6107. 已知带权图G