中央电大离散数学(本科)考试试的题目

1、实用标准文案中央电大离散数学（本科）考试试题一、单项选择题（每小题3 分，本题共15 分）1若集合A=1， 2 ， B=1， 2， 1 ， 2 ，则下列表述正确的是( a)AAB，且A BBBA，且ABCAB，且ABDAB，且AB2设有向图（ a）、（ b）、（ c）与（ d）如图一所示，则下列结论成立的是( d )图一A（ a）是强连通的B（ b）是强连通的C（ c ）是强连通的D（ d）是强连通的3设图 G的邻接矩阵为0110010011100000100101010则 G的边数为 ( b )A 6B 5C 4D34无向简单图 G是棵树，当且仅当 ( a )A G连通且边数比结点数少 1B

2、G连通且结点数比边数少 1C G的边数比结点数少 1DG中没有回路5下列公式 (c)为重言式A PQP QB (Q(PQ)(Q (PQ)C (P(Q P)(P(PQ)D( P(PQ)Q1若集合 A= a，b ，B=a ，b， a ， b ，则（ a）A AB，且ABBAB，但ABC AB，但ABDAB，且ABA2集合 A=1, 2, 3,4,5, 6, 7,8 上的关系 R=< x，y>| x+y=10 且 x, yA ，则自反的B对称的C传递且对称的AD反自反且传递的3如果1 和2是上的自反关系，则12，12，1-2 中自反关系有（bRRRRRRRRA 0B 2C 1D34如图一

3、所示，以下说法正确的是( d)A (a, e ) 是割边B (a, e ) 是边割集C (a, e) ,(b, c) 是边割集D(,e) 是边割集dR的性质为（b）个图一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)DAB (x)(A(x) B(x)1设 =, ， =1,2， 1， 2， 3是到的二元关系，且1=< ，2>, < ，2> ， 2 =< ，1>,< ，A ab BR R RABR abR aa2

4、>, < ，1> ，3=< ， 1>, <， 2> ，则（ b）不是从到的函数bRabA1和2B 2C 3D1和3RRRRRR2设 =1, 2, 3, 4, 5, 6, 7, 8，R是A上的整除关系，=2, 4, 6，则集合B的最大元、最小AB元、上界、下界依次为 ( b)A 8、2、8、 2B无、 2、无、 2C 6、2、6、 2D8、 1、 6、 13若集合A 10244设完全图A m为奇数5已知图A 的元素个数为 10，则其幂集的元素个数为（a）KB10C100D 1有 n 个结点 ( n 2) ， m条边，当（ c）时， K 中存在欧拉回路nn

5、 为偶数Cn 为奇数DnBm为偶数G的邻接矩阵为精彩文档实用标准文案，则 G有（d）A5点，8 边B6点， 7边C6点，8边D5点，7边1若集合A a ， a ，1 ，2 ，则下列表述正确的是( c )A a ， aAB 2AC aA2设图 G<V, E>deg(v)2 EAdeg(v)=2EC v VD A，vV，则下列结论成立的是 ( cBdeg(v) deg(v)=D v V)EE3命题公式（ PQ） R 的析取范式是(d )A（PQ） RB（PQ） RC（ P Q） RD（PQ） R4如图一所示，以下说法正确的是( a )A e 是割点Ba, e是点割集C b, e是点割集

6、D d 是点割集5下列等价公式成立的为( b )APQPQBP(QP)P(PQ)CQ(PQ)Q(PQ)DP(PQ)Q1若 G是一个汉密尔顿图，则G一定是 ( d )A平面图B对偶图C欧拉图D连通图2集合 A=1, 2, 3, 4上的关系R=<x， y>|x=y 且 x, yA，则 R 的性质为（c）A不是自反的B不是对称的C传递的D反自反3设集合 A=1，2， 3， 4， 5 ，偏序关系 是 A 上的整除关系，则偏序集 <A， >上的元素 5 是集合 A 的（ b ）A最大元B极大元C最小元D极小元4图 G如图一所示，以下说法正确的是( c )A (a, d)是割边B

7、(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 )A aAB aAC a ， aADA2命题公式（ P Q）的合取范式是( c)A（ P Q）B（ PQ）（ P Q）C（PQ）D（PQ）3无向树T 有 8 个结点，则T 的边数为 ( b )A6B7C8D94图 G如图一所示，以下说法正确的是( b )A a

8、 是割点Bb, c是点割集C b, d是点割集D c 是点割集图一5下列公式成立的为( d )APQPQBPQPQ精彩文档实用标准文案CQPPD P(PQ) Q1“小于 5 的非负整数集合”采用描述法表示为_a_A xxN, x<5 BxxR, x<5 C xxZ, x<5 DxxQ, x<5 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)

9、=2a+1； g： RR， g(a)=a2 ，则 _c_有反函数A fgB gfC fD g4 已知图 G的邻接矩阵为 01011，则图 G有 _d_10001000111010111110A5点，8边B6点，7边C6点，8边D5点7边5无向完全图 K4 是_a_A汉密尔顿图B欧拉图C非平面图D树6在 5 个结点的完全二叉树中，若有4 条边，则有 _b_片树叶A 2B 3C 4D 57无向树 T 有 7 片树叶， 3 个 3 度结点，其余的都是4 度结点，则 T 有 _c_个 4 度结点A 3B 2C 1D 08 与命题公式 P （Q R）等值的公式是 _a_A (PQ)RB(PQ)RC (P

10、Q)RD P(QR)9谓词公式x( P(x)yR( y)Q( x)中量词 x 的辖域是 _b_Ax( P(x)yR( y)B P( x)yR( y )C P(x)D( Q( x)10谓词公式xP( x)x Q( x)xQ( x) 的类型是 _c_A蕴涵式B永假式C永真式D非永真的可满足式1设 A=1,2,3,4，B=1,3，C=-1,0,1,2，则 _a_A BAB BCC BAD BC2 若集合 A 的元素个数为 10，则其幂集的元素个数为 _b_A 1000B1024C 1D10，则(A B)C _c_3设集合 A=1,2 ，B=a,b，C=A <1,a,>,<1,b,&

11、gt;,<2,a,>,<2,b,>B <1,<a,>>,<1,<b,>>,<2,<a,>>,<2,<b,>>C <<1,a>,>,<<1,b>,>,<<2,a>,>,<<2,b>,>D 1,2,a,b,4设 A=1, 2, 3, 4, 5, 6, 7, 8，R 是 A 上的整除关系， B=2, 4, 6，则集合 B 的最大元、最小元、上界、下界依次为 _d_A 8、1、6、 1B

12、8 、2、8、2C 6、2、6、 2D无、 2、无、 25有 5 个结点的无向完全图K5 的边数为 _a_A 10B 20C 5D 256 设完全图 K n 有 n 个结点 (n 2) ， m条边，当 _b_时， K n 中存在欧拉回路A n 为偶数Bn 为奇数C m为偶数Dm为奇数7一棵无向树 T 有 5片树叶， 3 个 2 度分支点，其余的分支点都是3 度顶点，则 T 有_c_ 个顶点A 3B 8C 11D 138 命题公式（ P Q） R的析取范式是 _b_A（ P Q） RB （PQ） RC（ P Q） RD（ P Q） R9下列等价公式成立的是_b_AP QPQBP (QP)P(PQ

13、)C P(P Q)QD Q(P Q)Q(P Q)10谓词公式xP( x)(x Q( x)xQ( x) 的类型是 _c_A蕴涵式B永假式C永真式D非永真的可满足式二、填空题（每小题3 分，本题共 15分）精彩文档6命题公式 P(QP) 的真值是实用标准文案T（或 1）VS7若图,中具有一条汉密尔顿回路，则对于结点集的每个非空子集，在中删除中的所G=<V E>中结点数 |S|W |S|SG有结点得到的连通分支数为，则与满足的关系式为WSW8给定一个序列集合 000 ，001，01，10，0 ，若去掉其中的元素0，则该序列集合构成前缀码T 中有 8 个结点，4 度，3 度，2 度的分支点

14、各一个， T 的树叶数为9已知一棵无向树510 (x)( () () (，) 中的自由变元为(，) 中的yP xQ xR x yR x y6若集合 A 的元素个数为10，则其幂集的元素个数为10247设 A= a，b，c ，B=1 ， 2 ，作 f ：AB，则不同的函数个数为88若 =1,2， =<,>|,+=10 ，则R的自反闭包为 <1,1>,<2,2>AR xy x A y A x y9结点数v与边数e满足-1关系的无向连通图就是树e=vAb6设集合 ， ，那么集合的幂集是 ,Aaba ba7如果1 和2 是A上的自反关系，则1 2， 12， 1 -

15、2 中自反关系有2个RRRRRRR R8设图 G是有 6个结点的连通图，结点的总度数为18，则可从 G中删去4条边后使之变成树9设连通平面图 G的结点数为5，边数为6，则面数为310设个体域 D a,b ，则谓词公式 (x) A( x) （ x）B（ x）消去量词后的等值式为( A ( a) A ( b)( B（a） B（b）) 6设集合=0, 1, 2, 3， =2, 3, 4, 5，R是A到B的二元关系，ABRx, yxA且 yB且 x, yAB则 R 的有序对集合为 <2, 2> ， <2, 3> ， <3, 2> ， <3, 3> 7设G

16、是连通平面图， , ,分别表示G的结点数，边数和面数，则， 和rve rv e8设 < ,>是有 6 个结点， 8 条边的连通图，则从G中删去3G VE棵生成树9无向图G存在欧拉回路，当且仅当连通且所有结点的度数全为偶数G10设个体域 D1,2，则谓词公式xA( x) 消去量词后的等值式为A(1)6命题公式 P(QP) 的真值是T（或 1）V7若图,中具有一条汉密尔顿回路，则对于结点集的每个非空子集G=<V E>S中结点数 |S|W|S|有结点得到的连通分支数为，则与满足的关系式为WW08给定一个序列集合 000 ，001，01，10，0 ，若去掉其中的元素满足的关系式

17、v- e+r =2条边，可以确定图G的一A(2)S，在 G中删除 S 中的所，则该序列集合构成前缀码9已知一棵无向树 T 中有 8 个结点，4 度，3 度，2 度的分支点各一个， T 的树叶数为510 (x)( () () (，)中的自由变元为(，) 中的yP xQ xR x yR x y6若集合 A 的元素个数为10，则其幂集的元素个数为10247设 A= a，b，c ，B=1 ， 2 ，作 f ：AB，则不同的函数个数为88若 =1,2 ， =<,>|,+y=10 ，则R的自反闭包为 <1,1>,<2,2>AR xy x A y A x9结点数v与边数e

18、满足-1关系的无向连通图就是树e=v10设个体域 D a,b,c ，则谓词公式 (x) A( x) 消去量词后的等值式为A ( a) A ( b) A（ c）6若集合1 ， 3，5， 7 ， =2 ，4， 6， 8 ，则 =空集（或 ）A=BAB7设集合 A=1 ， 2， 3 上的函数分别为： f =<1,2>,<2,1>,<3,3>,，g=<1,3>,<2,2>,<3,2>,，则复合函数 g f =<1, 2>, <2, 3>, <3, 2>,8设G是一个图，结点集合为，边集合为，则G

19、的结点度数之和为2| | （或“边数的两倍” ）VEE9无向连通图 G的结点数为 v，边数为e，则 G当 v 与 e 满足e=v-1关系时是树10设个体域 1,2,3 ，P(x) 为“x小于 2”，则谓词公式 () ()的真值为假（或 F，或 0） Dx P x6设集合 A=2, 3, 4，B=1, 2, 3, 4，R 是 A 到 B的二元关系，Rx, yxA且yB且xy则 R 的有序对集合为 <2, 2> ， <2, 3> ， <2, 4> ， <3, 3> ， <3, 4> ， <4, 4>7如果 R是非空集合 A 上

20、的等价关系， aA，bA，则可推知R 中至少包含 <a, a > ， < b ,b > 等元素8设 < ,>是有 4 个结点， 8 条边的无向连通图，则从G中删去5条边，可以确定图G V EG的一棵生成树9设 G是具有 n 个结点 m条边 k 个面的连通平面图，则m等于 n+k 210设个体域DA xx大于 1”，则谓词公式( x) A(x)的真值为真（或T，或 1）1, 2，()为“11设集合 =1,2,3，用列举法写出A上的恒等关系IA，全关系A：AEIA=_ I A= <1, 1>, <2, 2>, <3, 3> ；

21、A= <1, 1>, <1, 2>, <1, 3>, <2, 1>, <2, 2>, <2, 3>, <3, 1>, <3, 2>, <3, 3>EaAabab12设集合 ， ，那么集合的幂集是 ,Ab13设集合 A=1,2,3，B=a, b ，从 A 到 B 的两个二元关系 R=<1,a>,<2,b>,<3,a> ， S=<1,a>,<2,a>,<3,a>，则 -=_R-S=<2,b> R S14 设

22、G是连通平面图， v, e, r 分别表示 G的结点数，边数和面数，则 v，e 和 r 满足的关系式 v - e+r =2 15 无向连通图 G是欧拉图的充分必要条件是结点度数均为偶数16 设 < , >是有 6 个结点， 8 条边的连通图，则从G中删去3条边，可以确定图G的一G V E棵生成树17 设 G是完全二叉树， G有 15 个结点，其中有 8 个是树叶，则 G有 _14_条边， G的总度数是_28_， G的分支点数是 _7_精彩文档实用标准文案18设 P，Q的真值为1，R，S的真值为0，则命题公式 (P Q)RSQ 的真值为 _0_19命题公式 P(QR) 的合取范式为

23、P0)(QR) 析取范式为 (PQ)( PR)20设个体域为整数集，公式xy( xy真值为 _1_11设集合=1,2,3,4， =3,4,5,6， 则 ：AABBB_3,4_， A_1,2,3,4,5,6_12设集合A有n个元素，那么A的幂集合() 的元素个数为bcdyzP Axazyczy13设集合=,， =,， =<,>,<,>,<,>,<,>,<,>A aB xRabd101则关系矩阵R 01014M=,d,e ，A=<,b>,<c,d>,<,b> ， =<d,b>,设集合上的二元

24、关系< ,>,<,>A0a0 b1c,>,<,RabSeca， 则· =<ae>,<cbbe>bR S15无向图 G0存在1欧拉0回路，当且仅当G连通且 _所有结点的度数全为偶数16设连通平面图G的结点数为5，边数为6，则面数为317设正则二叉树有n个分支点，且内部通路长度总和为I，外部通路长度总和为，则有 =_I+2nP QRSR)(QS)EE18的真值为的真值为1，则命题公式( P的真值为 _1_设 ，0， ，PR19已知命题公式为 ()，则命题公式的析取范式是 ()GP QRGQ20 谓词命题公式 ( x)( P( x

25、) Q( x) R( x， y) 中的约束变元为 _x_三、逻辑公式翻译 （每小题4 分，本题共12 分）11将语句“如果所有人今天都去参加活动，则明天的会议取消”翻译成命题公式设 P：所有人今天都去参加活动，Q：明天的会议取消，（1 分）PQ（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将语句“小

26、王去旅游，小李也去旅游”翻译成命题公式设 P：小王去旅游， Q：小李去旅游，（1分）P Q（4 分）13将语句“所有人都去工作 ”翻译成谓词公式设 P(x) ： x 是人， Q(x) ：x 去工作，（1 分）(x)(P(x)Q(x) （4 分）11将语句“他不去学校 ”翻译成命题公式设 P：他去学校，（1 分）P （4 分）12将语句“他去旅游，仅当他有时间 ”翻译成命题公式设 P ：他去旅游， Q：他有时间，（1 分）PQ（4 分）13将语句“所有的人都学习努力”翻译成命题公式设 P(x) ： x 是人， Q(x) ：x 学习努力，（1 分）（ x） (P(x)Q(x) （3 分）11将语句

27、“尽管他接受了这个任务，但他没有完成好”翻译成命题公式设 P：他接受了这个任务，Q：他完成好了这个任务，（2 分）PQ（6 分）12将语句“今天没有下雨 ”翻译成命题公式设 P：今天下雨，（2 分）P （6 分）11将语句“他是学生 ”翻译成命题公式设 P：他是学生，（2 分）则命题公式为： P （6 分）12将语句“如果明天不下雨，我们就去郊游”翻译成命题公式设 P：明天下雨， Q：我们就去郊游，（2 分）则命题公式为：PQ（6 分）11将语句“今天考试，明天放假”翻译成命题公式设 P：今天考试， Q：明天放假（2 分）则命题公式为： PQ（6分）12 将语句“我去旅游，仅当我有时间”翻译成

28、命题公式设 P：我去旅游， Q：我有时间，（2 分）则命题公式为： PQ（6 分） 将语句“如果明天不下雨，我们就去春游”翻译成命题公式 将语句“有人去上课 ” 翻译成谓词公式设命题 P 表示“明天下雨” ，命题 Q表示“我们就去春游” .则原语句可以表示成命题公式PQ.（5 分）设 P(x) ：x 是人， Q(x) ： x 去上课则原语句可以表示成谓词公式( x)(P(x)Q(x) 精彩文档实用标准文案四、判断说明题 （每小题 7 分，本题共14 分）14 P（ P Q） P 为永真式正确（3 分）P（ P Q） P 是由 P（ P Q）与 P 组成的析取式，如果 P 的值为真，则 P（ P

29、 Q） P 为真，（5 分）如果 P 的值为假，则 P 与 P Q为真，即 P（ P Q）为真，也即 P（ P Q） P 为真，所以 P（ P Q） P 是永真式（7 分）15若偏序集 <A， R>的哈斯图如图一所示，则集合A 的最大元为 a，最小元不存在正确（3 分）对于集合 A 的任意元素 x ，均有 <x, a>R（或 xRa），所以 a 是集合 A 中的最大元 （5 分）14如果 R1 和 R2 是 A 上的自反关系，则 R1 R2 是自反的（3 分）正确R1和 R2 是自反的， xA， <x, x>R1，<x, x>R2，则<x,

30、 x>R1 R2，所以 R1 R2 是自反的（7 分）15如图二所示的图 G存在一条欧拉回路 ev5dv4gv1fhncav2bv3正确图二（3 分）因为图 G 为连通的，且其中每个顶点的度数为偶数（7 分）14设 N、 R 分别为自然数集与实数集，f ：N R， f (x)=x+6，则 f 是单射正确（3 分）设 x1，x2为自然数且 x1x2，则有 f(x1)= x1+6x2+6= f(x2)，故 f 为单射（7 分）15设 G 是一个有 6 个结点 14 条边的连通图，则G为平面图（3分）错误不满足“设 G 是一个有 v 个结点 e 条边的连通简单平面图，若v 3，则 e3v-6

31、”13下面的推理是否正确，试予以说明(1)（ x） F（x） G（x）前提引入(2) F（ y） G（ y）US（ 1）（3 分）错误（2）应为 F（ y ） G（ x ），换名时，约束变元与自由变元不能混淆（7 分）14若偏序集 <A， R>的哈斯图如图二所示，则集合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 为中包含度数为奇数的结点（7 分）13如果图 G 是无向图，且其结点度数均为偶数，则图G是欧拉图错误（3 分）当图 G不连通时图 G不为欧拉图（7 分）14若偏序集 <A， R>的哈斯图如图二所示，则集合A 的最大元为 a，最小元是 f 图二错误（3 分）集合 A 的最大元与最小元不存在，a 是极大元， f 是极小元，五计算题 （每小题 12 分，