电大离散数学往考题分类小抄

1、专业好文档一、单项选择题（每小题3分，本题共15分）1设a=a, b，b=1, 2，r1，r2，r3是a到b的二元关系，且r1=, ，r2=, , ，r3=, ，则（ b ）不是从a到b的函数 ar1和r2 br2 cr3 dr1和r32设a=1, 2, 3, 4, 5, 6, 7, 8，r是a上的整除关系，b=2, 4, 6，则集合b的最大元、最小元、上界、下界依次为 ( b ) a8、2、8、2 b无、2、无、2 c6、2、6、2 d8、1、6、13若集合a的元素个数为10，则其幂集的元素个数为（ a ） a1024 b10 c100 d14设完全图k有n个结点(n2)，m条边，当（ c

2、）时，k中存在欧拉回路am为奇数 bn为偶数 cn为奇数 dm为偶数5已知图g的邻接矩阵为 ，则g有（ d ） a5点，8边 b6点，7边 c6点，8边 d5点，7边1若集合a a，a，1，2，则下列表述正确的是( c ) aa，aa b2acaa da 2设图g，vv，则下列结论成立的是 ( c ) adeg(v)=2e b deg(v)=e c d3命题公式（pq）r的析取范式是 ( d ) a（pq）r b（pq）r c（pq）r d（pq）r4如图一所示，以下说法正确的是 ( a )ae是割点 ba, e是点割集cb, e是点割集 dd是点割集5下列等价公式成立的为( b )apqpq

3、 bp(qp) p(pq) cq(pq) q(pq) dp(pq) q1若集合a=1，2，b=1，2，1，2，则下列表述正确的是( a ) aab，且ab bba，且abcab，且ab dab，且ab 2设有向图（a）、（b）、（c）与（d）如图一所示，则下列结论成立的是 ( d ) 图一 a（a）是强连通的 b（b）是强连通的c（c）是强连通的 d（d）是强连通的3设图g的邻接矩阵为则g的边数为( b )a6 b5 c4 d34无向简单图g是棵树，当且仅当( a )ag连通且边数比结点数少1 bg连通且结点数比边数少1cg的边数比结点数少1 dg中没有回路5下列公式 ( c )为重言式apq

4、pq b(q(pq) (q(pq) c(p(qp)(p(pq) d(p(pq) q1若集合a=a，b，b= a，b， a，b ，则（ a ） aab，且ab bab，但ab cab，但ab dab，且ab2集合a=1, 2, 3, 4, 5, 6, 7, 8上的关系r=|x+y=10且x, ya，则r的性质为（ b ） a自反的 b对称的 c传递且对称的 d反自反且传递的3如果r1和r2是a上的自反关系，则r1r2，r1r2，r1-r2中自反关系有（ b ）个 a0 b2 c1 d34如图一所示，以下说法正确的是 ( d ) a(a, e)是割边 b(a, e)是边割集c(a, e) ,(b,

5、 c)是边割集 d(d, e)是边割集 图一5设a（x）：x是人，b（x）：x是学生，则命题“不是所有人都是学生”可符号化为（ c ）a(x)(a(x)b(x) b(x)(a(x)b(x) c(x)(a(x) b(x) d(x)(a(x)b(x)1若g是一个汉密尔顿图，则g一定是( d ) a平面图 b对偶图c欧拉图 d连通图2集合a=1, 2, 3, 4上的关系r=|x=y且x, ya，则r的性质为（ c ） a不是自反的 b不是对称的 c传递的 d反自反3设集合a=1，2，3，4，5，偏序关系是a上的整除关系，则偏序集上的元素5是集合a的（ b ） a最大元 b极大元 c最小元 d极小元4

6、图g如图一所示，以下说法正确的是 ( c ) a(a, d)是割边 b(a, d)是边割集c(a, d) ,(b, d)是边割集 d(b, d)是边割集 图一5设a（x）：x是人，b（x）：x是工人，则命题“有人是工人”可符号化为（ a ）a(x)(a(x)b(x) b(x)(a(x)b(x) c(x)(a(x) b(x) d(x)(a(x)b(x)1若集合a a，a，则下列表述正确的是( a ) aaa baaca，aa da2命题公式（pq）的合取范式是 ( c ) a（pq） b（pq）（pq） c（pq） d（pq）3无向树t有8个结点，则t的边数为( b )a6 b7 c8 d9 4

7、图g如图一所示，以下说法正确的是 ( b )aa是割点 bb, c是点割集cb, d是点割集 dc是点割集 图一5下列公式成立的为( d )apq pq bpq pq cqp p dp(pq)q1“小于5的非负整数集合”采用描述法表示为_a_ axxn, x5 bxxr, x5 cxxz, x5 dxxq, 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_闭包 a自反 b对称 c传递 d以上答案都不对 3设函数f：rr，f(a)=2a+1；

8、g：rr，g(a)=a2，则_c_有反函数 afg bgf cf dg 4已知图g的邻接矩阵为，则图g有_d_ a5点，8边 b6点，7边 c6点，8边 d5点7边 5无向完全图k4是_a_ a汉密尔顿图 b欧拉图 c非平面图 d树 6在5个结点的完全二叉树中，若有4条边，则有_b_片树叶 a2 b3 c4 d5 7无向树t有7片树叶，3个3度结点，其余的都是4度结点，则t有_c_个4度结点 a3 b2 c1 d0 8与命题公式p（qr）等值的公式是_a_ a(pq)r b(pq)r c(pq)r dp(qr) 9谓词公式中量词x的辖域是_b_ a b cp(x) d 10谓词公式的类型是_c

9、_ a蕴涵式 b永假式 c永真式 d非永真的可满足式1设a=1,2,3,4，b=1,3，c=-1,0,1,2，则_a_ a b c d 2若集合a的元素个数为10，则其幂集的元素个数为_b_ a1000 b1024 c1 d10 3设集合a=1,2，b=a,b，c=，则_c_ a, b1,1,2,2, c, d1,2,a,b, 4设a=1, 2, 3, 4, 5, 6, 7, 8，r是a上的整除关系，b=2, 4, 6，则集合b的最大元、最小元、上界、下界依次为_d_ a8、1、6、1 b 8、2、8、2 c6、2、6、2 d无、2、无、2 5有5个结点的无向完全图k5的边数为_a_ a10

10、b20 c5 d25 6设完全图k有n个结点(n2)，m条边，当_b_时，k中存在欧拉回路 an为偶数 bn为奇数 cm为偶数 dm为奇数 7一棵无向树t有5片树叶，3个2度分支点，其余的分支点都是3度顶点，则t有_c_个顶点 a3 b8 c11 d13 8命题公式（pq）r的析取范式是_b_ a（pq）r b （pq）r c（pq）r d（pq）r 9下列等价公式成立的是_b_ apqpq b p(qp) p(pq) cp(pq) q dq(pq) q(pq) 10谓词公式的类型是_c_ a蕴涵式 b永假式 c永真式 d非永真的可满足式二、填空题（每小题3分，本题共15分）6命题公式的真值是

11、 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的树叶数为 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

12、=10，则r的自反闭包为, 9结点数v与边数e满足 e=v-1 关系的无向连通图就是树6设集合aa，b，那么集合a的幂集是,a,b,a,b 7如果r1和r2是a上的自反关系，则r1r2，r1r2，r1-r2中自反关系有 2 个 8设图g是有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

13、设g是连通平面图，v, e, r分别表示g的结点数，边数和面数，则v，e和r满足的关系式v-e+r=2 8设g是有6个结点，8条边的连通图，则从g中删去 3 条边，可以确定图g的一棵生成树9无向图g存在欧拉回路，当且仅当g连通且所有结点的度数全为偶数10设个体域d1,2，则谓词公式消去量词后的等值式为a(1)a(2)6命题公式的真值是 t （或1） 7若图g=中具有一条汉密尔顿回路，则对于结点集v的每个非空子集s，在g中删除s中的所有结点得到的连通分支数为w，则s中结点数|s|与w满足的关系式为 w|s| 8给定一个序列集合000，001，01，10，0，若去掉其中的元素 0 ，则该序列集合构

14、成前缀码9已知一棵无向树t中有8个结点，4度，3度，2度的分支点各一个，t的树叶数为 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若集合a=1，3，5，7，b=2，4，6，8，则ab=空集（或） 7设集

15、合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的有序对集合为，7如果r是非空集合a上的等价关系，a a，ba，则可推知r中至少包含，等元素8设g是有4个结点，8条边的无向连通图，则从g中删去 5 条边，可以确

16、定图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,b 13设集合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=2 15无向连通图g是欧拉图的充分必要条件是结点度数均为偶数 1

17、6设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_ 19命题公式的合取范式为析取范式为 20设个体域为整数集，公式真值为_1_11设集合a=1,2,3,4，b=3,4,5,6，则： _3,4_，_1,2,3,4,5,6_ 12设集合a有n个元素，那么a的幂集合p(a)的元素个数为 13设集合a=a,b,c,d，b=x,y,z，r=,则关系矩阵mr 14设集合a=a,b,c,d

18、,e，a上的二元关系r=,，s=,，则rs=, 15无向图g存在欧拉回路，当且仅当g连通且_所有结点的度数全为偶数 16设连通平面图g的结点数为5，边数为6，则面数为 3 17设正则二叉树有n个分支点，且内部通路长度总和为i，外部通路长度总和为e，则有e=_ i+2n 18设p，q的真值为0，r，s的真值为1，则命题公式的真值为_1_ 19已知命题公式为g(pq)r，则命题公式g的析取范式是(pq)r 20谓词命题公式(x)(p(x)q(x)r(x，y)中的约束变元为_x_三、逻辑公式翻译（每小题4分，本题共12分）11将语句“如果所有人今天都去参加活动，则明天的会议取消”翻译成命题公式设p：

19、所有人今天都去参加活动，q：明天的会议取消， （1分） p q （4分）12将语句“今天没有人来” 翻译成命题公式设 p：今天有人来， （1分） p （4分）13将语句“有人去上课” 翻译成谓词公式设p(x)：x是人，q(x)：x去上课， （1分）($x)(p(x) q(x) （4分）11将语句“如果你去了，那么他就不去”翻译成命题公式设p：你去，q：他去， （1分）pq （4分）12将语句“小王去旅游，小李也去旅游”翻译成命题公式设p：小王去旅游，q：小李去旅游， （1分）pq （4分）13将语句“所有人都去工作”翻译成谓词公式设p(x)：x是人，q(x)：x去工作， （1分）(x)(p(x

20、)q(x) （4分）11将语句“他不去学校”翻译成命题公式设p：他去学校， （1分） p （4分）12将语句“他去旅游，仅当他有时间”翻译成命题公式设 p：他去旅游，q：他有时间， （1分）p q （4分）13将语句“所有的人都学习努力”翻译成命题公式设p(x)：x是人，q(x)：x学习努力， （1分）（x）(p(x)q(x) （3分）11将语句“尽管他接受了这个任务，但他没有完成好”翻译成命题公式设p：他接受了这个任务，q：他完成好了这个任务， （2分） p q （6分）12将语句“今天没有下雨”翻译成命题公式设p：今天下雨， （2分） p （6分）11将语句“他是学生”翻译成命题公式设p：

21、他是学生， （2分） 则命题公式为： p （6分）12将语句“如果明天不下雨，我们就去郊游”翻译成命题公式设p：明天下雨，q：我们就去郊游， （2分） 则命题公式为： p q （6分）11将语句“今天考试，明天放假”翻译成命题公式设p：今天考试，q：明天放假 （2分） 则命题公式为：pq （6分） 12将语句“我去旅游，仅当我有时间”翻译成命题公式 设p：我去旅游，q：我有时间， （2分）则命题公式为：pq （6分） 将语句“如果明天不下雨，我们就去春游”翻译成命题公式 将语句“有人去上课” 翻译成谓词公式设命题p表示“明天下雨”，命题q表示“我们就去春游”. 则原语句可以表示成命题公式 pq

22、. （5分） 设p(x)：x是人，q(x)：x去上课 则原语句可以表示成谓词公式 ($x)(p(x) q(x) 四、判断说明题（每小题7分，本题共14分）14p（pq）p为永真式正确 （3分）p（pq）p是由p（pq）与p组成的析取式，如果p的值为真，则p（pq）p为真， （5分）如果p的值为假，则p与pq为真，即p（pq）为真，也即p（pq）p为真，所以p（pq）p是永真式 （7分）15若偏序集的哈斯图如图一所示，则集合a的最大元为a，最小元不存在 正确 （3分）对于集合a的任意元素x，均有r（或xra），所以a是集合a中的最大元（5分）14如果r1和r2是a上的自反关系，则r1r2是自反的

23、正确 （3分）r1和r2是自反的，x a， r1， r2， 则 r1r2， 所以r1r2是自反的 （7分）v1v2v3v5v4dbacefghn图二15如图二所示的图g存在一条欧拉回路 正确 （3分）因为图g为连通的，且其中每个顶点的度数为偶数 （7分）14设n、r分别为自然数集与实数集，f：nr，f (x)=x+6，则f是单射正确 （3分）设x1，x2为自然数且x1x2，则有f(x1)= x1+6 x2+6= f(x2)，故f为单射 （7分）15设g是一个有6个结点14条边的连通图，则g为平面图错误 （3分）不满足“设g是一个有v个结点e条边的连通简单平面图，若v3，则e3v-6” 13下面

24、的推理是否正确，试予以说明 (1) （x）f（x）g（x） 前提引入 (2) f（y）g（y） us（1）错误 （3分）（2）应为f（y）g（x），换名时，约束变元与自由变元不能混淆 （7分）14若偏序集的哈斯图如图二所示，则集合a的最大元为a，最小元不存在 错误 （3分）集合a的最大元不存在，a是极大元 （7分）13下面的推理是否正确，试予以说明 (1) （x）f（x）g（x） 前提引入 (2) f（y）g（y） us（1）错误 （3分）（2）应为f（y）g（x），换名时，约束变元与自由变元不能混淆 （7分）14如图二所示的图g存在一条欧拉回路错误 （3分）因为图g为中包含度数为奇数的结点

25、（7分）13如果图g是无向图，且其结点度数均为偶数，则图g是欧拉图错误 （3分）当图g不连通时图g不为欧拉图 （7分）14若偏序集的哈斯图如图二所示，则集合a的最大元为a，最小元是f 图二错误 （3分）集合a的最大元与最小元不存在，a是极大元，f是极小元， 五计算题（每小题12分，本题共36分）16设集合a=1，2，3，4，r=|x, ya；|x-y|=1或x-y=0，试（1）写出r的有序对表示； （2）画出r的关系图；（3）说明r满足自反性，不满足传递性（1）r=, （3分）1234（2）关系图为 （6分）（3）因为,均属于r，即a的每个元素构成的有序对均在r中，故r在a上是自反的。 （9分

26、）因有与属于r，但不属于r，所以r在a上不是传递的。 17求pqr的析取范式，合取范式、主析取范式，主合取范式p（rq）p(rq) pqr （析取、合取、主合取范式） （9分） (pqr)(pqr) (pqr) (pqr) (pqr) (pqr) (pqr) （主析取范式） （12分）18设图g=，v= v1，v2，v3，v4，v5，e= (v1, v2)，(v1, v3)，(v2, v3)，(v2, v4)，(v3, v4)，(v3, v5)，(v4, v5) ，试 画出g的图形表示； 写出其邻接矩阵；(3) 求出每个结点的度数；v1v2v3v4v5ooooo(4) 画出图g的补图的图形（1

27、）关系图 （3分）（2）邻接矩阵 （6分）（3）deg(v1)=2deg(v2)=3v1v2v3v4v5ooooodeg(v3)=4deg(v4)=3deg(v5)=2 （9分） （4）补图16设谓词公式，试（1）写出量词的辖域； （2）指出该公式的自由变元和约束变元（1）$x量词的辖域为， （2分）z量词的辖域为, （4分） y量词的辖域为 （6分）（2）自由变元为与中的y，以及中的z约束变元为x与中的z，以及中的y （12分）17设a=1,2,1,2，b=1,2,1,2，试计算（1）（a-b）； （2）（ab）； （3）ab（1）a-b =1,2 （4分）（2）ab =1,2 （8分）（3

28、）ab=，, 18设g=，v= v1，v2，v3，v4，v5，e= (v1,v3)，(v2,v3)，(v2,v4)，(v3,v4)，(v3,v5)，(v4,v5) ，试（1）给出g的图形表示； （2）写出其邻接矩阵；（3）求出每个结点的度数； （4）画出其补图的图形1）g的图形表示为： （3分）（2）邻接矩阵： （6分）（3）v1，v2，v3，v4，v5结点的度数依次为1，2，4，3，2 （9分）（4）补图如下：16试求出（pq）r的析取范式，合取范式，主合取范式（pq）r(pq)r (pq)r（析取范式） （3分） (pr) (qr)（合取范式） （6分） (pr)(qq) (qr)(pp) (prq)(prq) (qrp)(qrp) (pqr)(pqr) (pqr) （主合取范式） （12分）17设a=a, b, 1, 2，b= a, b, 1, 1，试计算（1）（a-b） （2）（ab） （3）（ab）-（ab）（1）（a-b）=a, b, 2 （4分）（2）（ab）=a, b, 1,