《电大1009【离散数学】(本)分栏精编版即打印即用》由会员分享，可在线阅读，更多相关《电大1009【离散数学】(本)分栏精编版即打印即用（9页珍藏版）》请在金锄头文库上搜索。
1、一、单项选择题（每小题3分，本题共15分）1若集合A=1，2，B=1，2，1，2，则下列表述正确的是( a )AAB，且AB 2设有向图（a）、（b）、（c）与（d）如图一所示，则下列结论成立的是 ( d )D（d）是强连通的3设图G的邻接矩阵为则G的边数为( b ) B54无向简单图G是棵树，当且仅当( a )AG连通且边数比结点数少1 5下列公式 ( c )为重言式 C(P(QP)(P(PQ)1若集合A=a，b，B= a，b， a，b ，则（a）AAB，且AB 2集合A=1, 2, 3, 4, 5, 6, 7, 8上的关系R=|x+y=10且x, yA，则R的性质为（ b ） B对称的3如
2、果R1和R2是A上的自反关系，则R1R2，R1R2，R1-R2中自反关系有（ b ）个 B2 4如图一所示，以下说法正确的是 ( d ) D(d, e)是边割集5设A（x）：x是人，B（x）：x是学生，则命题“不是所有人都是学生”可符号化为（ c ）C(x)(A(x) B(x) 1设A=a, b，B=1, 2，R1，R2，R3是A到B的二元关系，且R1=, ，R2=, , ，R3=, ，则（ b ）不是从A到B的函数 BR2 2设A=1, 2, 3, 4, 5, 6, 7, 8，R是A上的整除关系，B=2, 4, 6，则集合B的最大元、最小元、上界、下界依次为 (b )B无、2、无、23若集合
3、A的元素个数为10，则其幂集的元素个数为（ a ）A1024 4设完全图K有n个结点(n2)，m条边，当（ c ）时，K中存在欧拉回路 Cn为奇数 5已知图G的邻接矩阵为 ，则G有（ d ） D5点，7边1若集合A a，a，1，2，则下列表述正确的是( c )CaA 2设图G，vV，则下列结论成立的是 ( c ) C 3命题公式（PQ）R的析取范式是 ( d ) D（PQ）R4如图一所示，以下说法正确的是 ( a )Ae是割点 5下列等价公式成立的为( b ) BP(QP) P(PQ)1若G是一个汉密尔顿图，则G一定是( d ) D连通图2集合A=1, 2, 3, 4上的关系R=|x=y且x,
4、 yA，则R的性质为（ c ）C传递的 3设集合A=1，2，3，4，5，偏序关系是A上的整除关系，则偏序集上的元素5是集合A的（ b ） B极大元 4图G如图一所示，以下说法正确的是 ( c ) C(a, d) ,(b, d)是边割集5设A（x）：x是人，B（x）：x是工人，则命题“有人是工人”可符号化为（ a ） A(x)(A(x)B(x) 1若集合A a，a，则下列表述正确的是( a ) AaA 2命题公式（PQ）的合取范式是 ( c ) C（PQ） 3无向树T有8个结点，则T的边数为( b ) B74图G如图一所示，以下说法正确的是 ( b ) Bb, c是点割集5下列公式成立的为( d
5、 ) DP(PQ)Q1“小于5的非负整数集合”采用描述法表示为（a）AxxN, x5 2设R1，R2是集合A=a,b,c,d上的两个关系，其中R1=(a,a),(b,b),(b,c), (d,d)，R2=(a,a),(b,b),(b,c),(c,b),(d,d)，则R2是R1的_b_闭包 B对称 3设函数f：RR，f(a)=2a+1；g：RR，g(a)=a2，则_c_有反函数 Cf 5无向完全图K4是_a_ A汉密尔顿图 6在5个结点的完全二叉树中，若有4条边，则有(b)片树叶 B3 7无向树T有7片树叶，3个3度结点，其余的都是4度结点，则T有_c_个4度结点 C1 8与命题公式P（QR）等
6、值的公式是_a_ A(PQ)R 9谓词公式中量词x的辖域是_b_ B 10谓词公式的类型是_c_ C永真式 1设A=1,2,3,4，B=1,3，C=-1,0,1,2，则_a_A 2若集合A的元素个数为10，则其幂集的元素个数为_b_ B10243设集合A=1,2，B=a,b，C=，则_c_ C, 4设A=1, 2, 3, 4, 5, 6, 7, 8，R是A上的整除关系，B=2, 4, 6，则集合B的最大元、最小元、上界、下界依次为(d) D无、2、无、25有5个结点的无向完全图K5的边数为_a_ A10 6设完全图K有n个结点(n2)，m条边，当_b_时，K中存在欧拉回路 Bn为奇数 7一棵无
7、向树T有5片树叶，3个2度分支点，其余的分支点都是3度顶点，则T有_c_个顶点 C11 8命题公式（PQ）R的析取范式是(_b_) B （PQ）R9下列等价公式成立的是_b_ B P(QP) P(PQ)二、填空题（每小题3分，本题共15分）6命题公式的真值是 T （或1） 7若图G=中具有一条汉密尔顿回路，则对于结点集V的每个非空子集S，在G中删除S中的所有结点得到的连通分支数为W，则S中结点数|S|与W满足的关系式为 W|S| 8给定一个序列集合000，001，01，10，0，若去掉其中的元素 _0 ，则该序列集合构成前缀码9已知一棵无向树T中有8个结点，4度，3度，2度的分支点各一个，T的
8、树叶数为 5 10(x)(P(x)Q(x)R(x，y)中的自由变元为R(x，y )中的y6若集合A的元素个数为10，则其幂集的元素个数为1024 7设A=a，b，c，B=1，2，作f：AB，则不同的函数个数为 8 8若A=1,2，R=|xA, yA, x+y=10，则R的自反闭包为, 9结点数v与边数e满足 e=v-1 关系的无向连通图就是树10设个体域Da, b, c，则谓词公式(x)A(x)消去量词后的等值式为A (a) A (b)A（c）6设集合Aa，b，那么集合A的幂集是,a,b,a,b 7如果R1和R2是A上的自反关系，则R1R2，R1R2，R1-R2中自反关系有 2 个 8设图G是
9、有6个结点的连通图，结点的总度数为18，则可从G中删去 4 条边后使之变成树9设连通平面图G的结点数为5，边数为6，则面数为 3 10设个体域Da, b，则谓词公式(x)A(x)（$x）B（x）消去量词后的等值式为(A (a)A (b)(B（a）B（b）) 6设集合A=0, 1, 2, 3，B=2, 3, 4, 5，R是A到B的二元关系，则R的有序对集合为，7设G是连通平面图，v, e, r分别表示G的结点数，边数和面数，则v，e和r满足的关系式v-e+r=2 8设G是有6个结点，8条边的连通图，则从G中删去 3 条边，可以确定图G的一棵生成树9无向图G存在欧拉回路，当且仅当G连通且所有结点的
10、度数全为偶数10设个体域D1,2，则谓词公式消去量词后的等值式为A(1)A(2)6若集合A=1，3，5，7，B=2，4，6，8，则AB=空集（或） 7设集合A=1，2，3上的函数分别为：f=,，g=,，则复合函数gf =, , ,8设G是一个图，结点集合为V，边集合为E，则G的结点度数之和为2|E|（或“边数的两倍”） 9无向连通图G的结点数为v，边数为e，则G当v与e满足 e=v-1 关系时是树 10设个体域D1, 2, 3， P(x)为“x小于2”，则谓词公式(x)P(x) 的真值为假（或F，或0） 6设集合A=2, 3, 4，B=1, 2, 3, 4，R是A到B的二元关系， 则R的有序对
11、集合为，7如果R是非空集合A上的等价关系，a A，bA，则可推知R中至少包含，等元素8设G是有4个结点，8条边的无向连通图，则从G中删去 5 条边，可以确定图G的一棵生成树9设G是具有n个结点m条边k个面的连通平面图，则m等于n+k-210设个体域D1, 2，A(x)为“x大于1”，则谓词公式的真值为真（或T，或1）11设集合A=1,2,3，用列举法写出A上的恒等关系IA，全关系EA： IA = _ IA =,； EA =,12设集合Aa，b，那么集合A的幂集是,a,b,a,b13设集合A=1,2,3，B=a,b，从A到B的两个二元关系R=,，S=,，则R-S=_ R-S=14设G是连通平面图，v, e, r分别表示G的结点数，边数和面数，则v，e和r满足的关系式v-e+r=215无向连通图G是欧拉图的充分必要条件是结点度数均为偶数16设G是有6个结点，8条边的连通图，则从G中删去 3 条边，可以确定图G的一棵生成树17设G是完全二叉树，G有15个结点，其中有8个是树叶，则G有_14_条边，G的总度数是_28_，G的分支点数是_7_18设P，Q的真值为1，R，S的真值为0，则命题公式的真值为_0_
