离散数学选择题题库及答案

1、编号 题目 b,cab ；A B、 ；c,ab,b 、。 ；C、 D 答案题型分值 大 纲区分度 1 下列是真命题的有（ ）?a?a?, AB、 、 ；?,?。 、 D、 ；C 答：C 选择题2 1 2 2 ）不是重言式。下面命题公式（ P)?(P?QPQ?(?Q) ；A、 B、；)?Q(?(?P?Q)P?Q)?(?P)?(P?Q 。C、； D、答：C 选择题2 33 x(Px)：M(x)：x 命题“没有不犯错误的人”符号化为（ ）。设是人，犯错误。)x(M(x)(x)M(x?P?)?P(x(?x(? ； B、A)()(?xM(x?Px?)?M(?x(x)P(x( 、。；C、 DD答： 选择题

2、 2 3 4 N,ab? ，哪种运算不是可结合的，运算定义为任对自然数集合N。 ）（)min(ba,?abb?ab?a?2 ； B、A；)?aba(modb3,3?abab? 、C。、 D；B答： 选择题 2 3 5 任意具有多个等幂元的半群，它（ ）。 、不一定能构成群； B、不能构成群；A 、能构成交换群。 D、不能构成交换群；C A答：选择题2 4答：D 选2 3 6 23,E?V?7?,EG?V）。 为无向图，设G一定是（ ，则择 题 D、多重图。A、完全图； B、树； C、简单图；3 选 2 答：B 7 ?E?V,G 。，如下图所示，下面哪个边集不是其边割集（ 给定无向图）择 题?v

3、,v?,?v,v? A、；4143 ,vv?,v?,?v ；B、6454?,?v,v?v,v ；C、8447v,v?v,v?, 、。D3221选2 答：D 3 8 m)3(n? 。， 条边的连通简单图是平面图的必要条件（）有n个结点择 题6?3m?3n?m?6n A、； B、6?m3n?63n?m? 、。； D C、选答：2 1 3 A 92x?x是整数且x?16A ）。设，下面哪个命题为假（ 择 题A10,2,12,?3?4?A, ； 、 A ； B、A?Axx是整数且?4x? 、C、 ； D答：C 选2 1 3 10 B,?A?,? 设。 ）A，则B是（择 题?,? 。 C ；、； D、A

4、、； B 选B答： 2 5 11,fe,b （下图描述的偏序集中，子集的上界为 ）。择题 答：C 选2 3 12 1?)(f?ggf X上的双射函数，则为（ ）设。和都是择 题1?1?1?1?1?1ffgg?gf?(g?f) 、 ； CA、 B ；、。 ； D3答：B 选2 13 ）关于减法运算是封闭的。下面集合（择是质数xx2x?1x?I2xx?I 、； C、 ； D、。N A、； B 题答： D 4 选2 14 ?G,? ，（具有如下定义的代数系统 ）不构成群。择 题,94,5GG?1,10?1,3, A、；11乘 ，；，*是模11乘 B、*是模QG?Q?G 是普通加法（有理数集），* ；

5、 D、，C、*是普通乘法。（有理数集）答：B 选2 4 15nm?G,I3m,n2G? 为普通乘法。则代数系统 的幺元为（）设。*，择 题100?13?3e?22e?3?e2 ； C、 D、 BA、不存在 ；、。 答：C5 选 2 16 ）关于整除关系构成格。下面集合（择 21 B36 2412632A、，；、，86，；12 43， 题 。12，9，6，3、 D；30 ，15，6，5，3，2，1、C答：C 选2 3 17 ,b,c,d,e,fV?a ，设择 题e?,f,?,?ca?,?a,d?,?d,e?E?a,b?,b,c ，则有向图?,EG?V）。 是（ 、不连通的。、弱连通的 ； DA、

6、强连通的 ； B、单侧连通的 ； C选2 4答：A 18 ）。下面那一个图可一笔画出（ 择 题 答：C 选2 3 19 ）。在任何图中必定有偶数个（ 择 ；A、度数为偶数的结点 ； B、入度为奇数的结点 题 、出度为奇数的结点 。C、度数为奇数的结点 ； D答：C 选2 3 20 个命题变元的具有不同真值的命题公式的个数为（）。含有3择2332 题 2332 D、。 ；A、； B、 ； C、223 2 答：A选 21 ）。下列集合中哪个是最小联结词集（择?,?,?,?,? D ； C、； B 。 ；A 题 2选3 B答： 22 。）下面哪个命题公式是重言式（ 择P(P?RQ?QP(?)(?)?

7、Q ； 、 B； 、A 题(?P?Q)?(P?Q)?(P?Q)?P 、C、。 ； D 23 。在谓词演算中，下列各式哪个是正确的（ ）)yx,y?xA(),y)?y?xA(x,y?x?yA(x,y)?xyA(x ； B、A、； )?xA(xAx,y)?y?xA(x,y)(a)?yA?x?( 。 ；C、 D、答：A 选择题2 3 24 )PQP?(? 。是（ 命题公式） 、等价式。、可满足式； C、重言式； D矛盾式； B 答：C选择题2 325 ）。下列各式中哪个不成立（ )xQ(x)?xP()?Q(x)?xP(x?x?( A、 ；)xQx()?(x?Q(?x(Px)?(x)?xP B、；)x

8、?Q(?x(Px)?(x)?xP()?xxQ( ；C、Q?xP?Qx)?)?(x)(?xP 。D、A答： 选择题 2 326 )?Q(x)(?)(?xPx?yRy 谓词公式是（中的 x 。） A、约束变元；、自由变元； B 、既不是自由变元又不是约束变元。 DC、既是自由变元又是约束变元； C答：选择题2 327 N6在自然数集 上，下列（）运算是可结合的。N?ba, （对任意）B答： 选择题 2 3a?b?max(a,b)b?b?aa ； B、 A、 a?b?a?bb?5?b?aa。、 ； DC、28 ）。，Q上定义运算*为a*b = a + b ab ,则的幺元为（Q为有理数集N 。 Ca

9、； B、b；、1； D、0 A、答：D 选择题2 3 29 ）可以构成无向简单图的结点次数序列。给定下列序列，（ 1，2，2，3）； B；，2），1，2，2、（1 A、（1， 4，5。），）； D、（13，4，（C、0，1，3，33答：B 选择题 2 3 30 ）关系。 （ 是简单有向图，可达矩阵设GP(G)刻划下列 D、边与边。A、点与边； B、边与点； C、点与点；答：C 选择题2 4 31 度结点数为（度结点，则1 ）。个一颗树有两个2度结点，13度结点和3个4 。；A、5 B、7； C、9 D、8答：C 选择题 2 3 32 42设A=1，3，5，下面（）集合等于A 。225是整数且x

10、xx? ，A、12，345；、，6； Bx5xx是正整数且x?5x是正有理数且?x 、。；、C D C答：选择题2 1 333 6543，下列各式中（ ）是错的。87，2A=1设，A? ，、A、； B67；8A，? ，A 3。21 D；54C、，A、， 答：D选择题 2 1 3 34 六阶群的子群的阶数可以是（。） A3、 C；4，、 B；5，2，、12、 D；7，63 ，2。 D答：选择题2 5答：D 选2 3 35 B?AS ）是正确的。，下列各式中（ 设择? ranS = S D、domSdomSB ； B、domS A； C、ranS。A； 题答：B 3 选2 ； 36?,*?G）是群

11、，则对 *（ 。择 题 、满足结合律、交换律；A B、有单位元，可结合； C、有单位元、可交换； D、每元有逆元，有零元。答：D 选2 5 37 ）哈斯图所描述的偏序关系构成分配格。下面（ 择 题 答：D 选2 1； 3 38 ）中的运算符都是可交换的。下列（ 择?,?,?,?,?,?, A、； D； B、。、； C 、 题答：A 3 2选 39 。）等于（条边和个结点、是设Gnmr个面的连通平面图，则m 择 、 Dn+r+2 。；、；、；A、n+r-2 Bn-r+2 Cn-r-2 题答：2D 3 选 40 K 个结点的无向完全图n的边数为（）。n择n(n?1)n(n?1) 题n1nn(?(n

12、?)1) A、 ； D、。 、 B、； C22 答：C 选2 3 41 下列图中（）是根树。择?,d?a,b?,?c?,b,c,d,?a,a,?Ga ；、 A1?,d?,d?,?c,c,d,?a,b?,?bG?a,b ； B、2?a?d?,?c,d,?a,b?,?a,G?a,bc, 、 ；C3?d?,?d,?a,b?,?a,c?Ga,b,c,d, D、 。4题 42 ）命题的真值为：太阳从东方升起，下列（ ：24=8，S设P：22=5，Q：雪是黑的，R 真。)?S?SP?Q?R?QR(P?R)?(QSR?P? ； B、。、 D、 ； C、； AA 答：选择题2 3 43 ，命题“所有演员都钦佩

13、某些老师”符钦佩y：x是老师，A(x , y)x：设L(x)x是演员，J(x)： 号化为（ ）。)A?(L(x)?Ax,y)x(L(x)?y(J(y)?(x,yx?( ； B、 A、；),yx)(x)?J(y?A(Lx?x)?Lx?y(x)J(y?A(,y)?y( ； D、C、答：B 选择题2 3 44 nA?N2?,n?xx 集合对（ ）运算封闭。yx? 。 D C BA、加法；、减法；、乘法；、 C答：选择题2 3 45 ZZ上定义运算m是任意正整数，为整数集合，设Im是由模的同余类组成的同余类集合，在mm?Z,?modij?(?j)m?i最确切的性质是（，则代数系统 ）。 mm 、群。

14、D、独异点； C、半群； B、封闭的代数系统；A答：B 选择题 2 5 46 。连通非平凡的无向图G有一条欧拉回路当且仅当图G ( ) 、只有一个奇度结点； B、只有两个奇度结点； A 、没有奇度结点。、只有三个奇度结点；C D答：D 选择题2 3 47 m?Vn,E?,EG?V 是树。若（ ）则G是连通的且 设无向图6nm?3n?6?3m? 、 ； A、M=N+1 B、n=m+1 ； C、； D 。答：B 选择题2 3 48 BA? I使公式。B也为真，则解释I使公式A为真，且使公式为（ ）如果解释 A、真；I无关。、可满足； D、与解释 B、假； C答：A 选择题2 3 49 ?PbA?a

15、, 。设）AA = （ ，则）（ ；）、 AA ； B、P（A?b,?b,a?,?b,b,?Aa?,?A,?,a?,?a?,?,b,?,a?ab?, 、 C； ?A?b,a,A?,?,?b,b?,?b,?,?,?,?a,a?,?b,a?,?a,b?a。 D、答：C 选择题 2 1 3 50 A?m,B?n，则从A到B有（ ）个不同的双射函数。 设集合A，B是有穷集合，且nmn!m! 、。 ； A、； B、 D ； C答：D 选择题2 4 51 ?K,? ）。四元群，则元素是Kleina的逆元为（，设K = e , a , b , c b ； D、c。、 Ae ； Ba ； C答：B 选择题 2

16、 ； 3 52 ）。 一个割边集与任何生成树之间（ D、有一条公共边；、至少有一条公共边。 C BA、没有关系；、割边集诱导子图是生成树；答：D 选择题 2 3 53 ） 下列语句中不是命题的有（ C、B答：选择 2 ；1 3? 、 x+3=5、 9+5；12 ； BA 、 我要努力学习。CPU主频是1G吗？； DC、我用的计算机题 54 ）命题“我不能一边听课，一边看小说”的符号化为（QP?Q?P ； 、 ； B、A)?Q?Q?P(P 、 C、 ； D 。答：A、D 选择题2 3 55 下列表达式正确的有（ ）PP?Q?Q?Q?(P?)? ；A、 B、 ；T?)(P?Q?(P?Q)PP?)?

17、(P?Q 。； C、 D、答：AC 选择题2 3 56 )R?Q(P?)?(P? 的主析取范式为若公式m?m?mm ）则它的主合取范式为（ 111001110011M?m?mM?M?M?mm ； ； B、 A、 101001000011100110010111mm?m?m?MM?M?M C、 D、 。；101010110000001111011100答：B 选择题2 4 57 命题“尽管有人聪明，但未必一切人都聪明”的符号化 ）是人）是聪明的，（P(x)：xM(x)：x （)(xMx)?(xP?)(?xMx?()Px?( 、 A)(?xMxM(x(?x(P)?)?(?)xP(x 、B答：C 选

18、择题2 3 68?x(M(x)?P(x)?(?x(M(x)?P(x) 、 C?x(M(x)?P(x)?(?x(M(x)?P(x) D、 答：B 选择题2 3 58 ? 下列（ ）表达式成立。 ，B=(设A=(A) ?B?B?B?B? 、 A、 D；、 ； C ； B、。v到v长度为2的通路有（ ，则有向图D= ）条。 答：A、B、C 选择题2 1； 3 59 ）A-B=（ A是素数集合，B是奇数集合，则? 。 D、 B、 奇数集合； C、 2；素数集合；A、 答：B 选择题 2 1； 3 60 ?,?,B?, ）。集合的幂集为（ ,?,?, A、；B?,?,?,?,?,?,?,?,?,?,?,

19、 ；B、,?,?,?,B?,?,?,?,?,?,?,?, C、；?,?,?,?,?,B?,?,?,?，、 D答：B 选择题2 1 3 61 。 ）下列结果正确的是（?B)A?B(?B)AA?A(? B、；、A；?A)(A?B?B? ；C、； D、答：B 选择题2 1； 3 62 r)(wff?p?q? 的主析取范式中含极小项的个数为（。 ） 。 8 、 E；0、 D；5、 C； 3、 B；2、A 答：C 选择题2 4答：D 选2 3 63 AA?B 。） 下有在（ 择BA?B?A?B?A?或BA? 题 ；B、；CA、D答：B 2 3 选 64 ）。下列二元关系中是函数的有（ 择10?x?y?x

20、R?,y?|x?Ny?N A、； 题2x?R?x,y?|?R?y?R?xy ；B、2?y?Rx?y|xR?,y?x?R? 、C答：C 选2 3 65 xyyx*y?x?Q?x,y?， 有）上定义的二元运算Q*，则Q中满足（ 。在有理数集择 题 、所有元素都有逆元； B、只有唯一逆元； A1?x1?x?Qx?, ；、时有逆元 D、所有元素都无逆元。C选2 答：B 5 66 设S=0，）。*1，为普通乘法，则是（ 择 A、半群，但不是独异点；、只是独异点，但不是群； B 题 、群；C D、环，但不是群。选2 4D答： 67 择 题图 给出一个格L，则L是（ ）。 都不对。 A,B,C、 D、布尔格

21、； C、有补格； B、分配格；A 41 3 。0A、； B、1； C、2； D、 答：D 选2 5 69 择 题在Peterson图中，至少填加（ ）条边才能构成Euler图。 5 。； D、；A、1 B、2； C、4 答：A、D 选2 ; 3 70 （ ）集合在普通加法运算下是封闭的。下面各集合都是N的子集，择 与5互质；、Ax | x 的幂可以被16整除； Bx | x 题 。 DC、x | x是30的因子；、x | x是30的倍数答：B 选2 ; 4 71 ?G?,G?0,12,?G0,G?1,*?则积代数表示模加法，表示模3，设*2乘法，其中，2121择 题 ）。 的幺元是（ D、；、

22、 。 C BA、；、；答：C 选2 5 72 ） S , ，S=1,2,3,6设集合“”为整除关系，则代数系统是（。择 、格，但不是布尔代数； B、域；A D、布尔代数； C、不是代数系统。 题73 k度结点，阶图G有m条边，每个结点度数不是k就是k+1，若G中有N个设nk 。则N=（ ）k 。 D、n(k+1)-2m n(k+1)； C、n(k+1)-m；、Ank； B、答：D 选择题2 ; 3 74 度结点。7片树叶，3个3度结点，其余全是4度结点，则该树有（ ）个4一棵树有 4 。、； B、2； C、3； DA、1答：A 选择题2 3 75 A?a?,b 。是环，的关于“+”的逆元是（

23、），ab (-b)a； D、ab 。(-a)A、(-a)(-b)； B、b； C、C答：B、 选择题2 ; 4 76 + ，Abel，+ 是群，如果还满足（ ）A ，A ，设 是一代数系统且 是域。 可分配；、A是独异点且对+? 可分配；，是独异点，无零因子且对+B、C、A- ，是Abel? AbelD、是且对+可分配。答：D 选择题2 ; 4 77 设A ，+ ， ）时，是一代数系统，、为普通加法和乘法运算，当A 是域。3xxba?|xxab5,均为有理数|?a?均为有理数bab5, A； B、 ；、a，x?I?0x|x?akb,ab?I?xx|且。 ； 、C D、?b 答：A选择题2 ;

24、4 78 ?A ,? ,? ）成立。 ，则（是一个格，由格诱导的代数系统为，则当A=”定义为：（ ）时，A, 设是偏序集，“ 是格。 1,2,3,4。，12； D、；A、1,2,3,4,6,12 B、1,2,3,4,6,8,12,14； C、1,2,3,答：A 选择题2 4 80 的父亲是y,y?|xy?P?xR?x,，集合，有上的关系，P是所人的PR设和S是?1的母亲x是yP?|x,y?S?x,y?RS表示关系 则（ ）。 ?x,y?|x,y?P?x是y的丈夫；A、 ?x,y?|x,y?P?x是y的孙子或孙女； B、?x,y?|x,y?P?x是y的祖父或祖母。C、 ； D、答：A 选择题2

25、3 81 在（）中，补元是唯一的。 、分配格；、有补格； C D、有补分配格。A、有界格； B答：D 选择题2 3 82 0?c?b?A , ,?,? ）。中，当且仅当（ 在布尔代数b?cb?cbc?cb? 、 D C；、。；A、 B；、C答： 选择题 2 4 83 ?,? ?,A? ,n A到A是从设f是布尔代数，） 的函数，则（ 。、C答：D 选择2 ; 5fA、f 、 能表示成析取范式，也能表示成合取范式；是布尔代数； Bf ，则一定能表示成析取范式，也能表示成合取范式；C、若A=0，1f 、若是布尔函数，它一定能表示成析（合）取范式。D题 84 ）。下列命题正确的有（ fg?fg,gg

26、,f?f 是满射，则 B是满射，则、若A、若都是满射；是满射；ff?g?fg,fg 是单射。、若C单射，则都是单射；D是单射，则、若答：A、D 选择题2 3 85 g设f，是函数，当（ ）时，f=g 。g且 f?)f?x?domf 都有 (x)?g(xdomg?domf A； B、；的表达式相同gf与rangefdomg?domf,rangef? 、C； D答：B 选择题2 3 86 ）能构成函数。（下列关系， 10xx,?N且x?|,f?xx?x ；A、2211212x?f?x,?|?xx?x,xR, 、B；211122,x的素数的个数x,x?Nx为小于|,xf?x? ；C、122121xx

27、f?,?R|x 、。 D答：C、D 选择题2 3 87 设R上的关系，则下列（A ）断言是正确的。是集合，SSS,R,RSS?RR 是对称的；B是自反的；、若对称的，则、A自反的，则S,S,RRS?R?SR 是反对称的。反对称的，则、若D是传递的；传递的，则、若C A答：选择题2 388 , 3 S? 1, 2SS? 上的等价关系，定义设?c?c,d?SS,a?d?b R?a,b?,?c,d? |?a,b?S?S,?的 生则由 R产S?S上一个划分共有（ ）个分块。 A4； B5； C6； D9 。 答：B 选择题2 3 89 。“没有不犯错误的人”的逻辑符号化为（ ） x犯错误。 P（x）：x设H（）：x是人，)P(x?H(x)?P(x)?(x(H(x)?x?( 、A、； B)x?)?P(x)x(H(x)?P(x?(?x(H( 、C。； D、答：B、D 选择题2 3 90 下列各符号串，不是合式公式的有（ ）。)?(P?Q)?R(PQ)?(R?S ； B、A、S)?Q?R)?(?P?Q?R(?P 、。； D、C答：C、B 选择题 2 3 91 下列语句是命题的有（）。 BA、2是素数；、x+5 6；。、地球外的星球上也有人；D、这朵花多好看呀！C CA答：、选择题 2 1 3 92 ）。下列问题成立的有（BCCA?BACB?C?B?AA ；，则，则A、若 B；、若B?