离散数学选择题.pdf

《离散数学选择题.pdf》由会员分享，可在线阅读，更多相关《离散数学选择题.pdf（18页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、编号1下列是真命题的有（）A、aa；B、,；题目答：C答案题 分型 值大纲区难分度度22选 21择题C、,；D、。2下面命题公式（）不是重言式。A、Q (P Q)；B、(P Q)P；C、(P Q)(P Q)；D、(P Q)(P Q)。3x是人，P(x)：x犯错误。命题“没有不犯错误的人”符号化为（）。设M(x)：A、x(M(x)P(x)；B、(x(M(x)P(x)；C、(x(M(x)P(x)；D、(x(M(x)P(x)。4对自然数集合 N，哪种运算不是可结合的，运算定义为任a,b N（）。A、ab min(a,b)；B、ab a 2b；C、ab a b 3；D、ab a,b(mod3)。5任意

2、具有多个等幂元的半群，它（）。A、不能构成群；B、不一定能构成群；C、不能构成交换群；D、能构成交换群。答：A选 28.3择题44答：B选 28.1择题33答：D选 23.1择题33答：C选 22.1择题3316设G V,E 为无向图，V 7,。E 23，则 G 一定是（）答：DA、完全图；B、树；C、简单图；D、多重图。7给定无向图G V,E，如下图所示，下面哪个边集不是其边割集（）。A、v1,v4,v3,v4；B、v4,v5,v4,v6；C、v4,v7,v4,v8；D、v1,v2,v2,v3。8有 n 个结点(n 3)，m条边的连通简单图是平面图的必要条件（）。A、n 3m 6；B、n 3

3、m 6；C、m 3n 6；D、m 3n 6。9设A x x是整数且。x216，下面哪个命题为假（）A、0,1,2,4 A；B、3,2,1 A；C、A；D、x x是整数且 x 4 A10设A ,答：A答：D答：B选 27.1择题选 26.2择题3333选 26.4择题选 21择题3333B ,，则 BA 是（）。答：CA、；B、；C、,；D、。11下图描述的偏序集中，子集b,e,f的上界为（）。答：B选 21择题选 24.4择题33552A、b,c；B、a,b；C、b；D、a,b,c。12设f和g都是 X 上的双射函数，则(f g)1为（）。A、f1答：C1 g1；B、(g f)1；C、g1 f

4、1；D、g f。答：B选 25.2择题选 28.1择题选 28.3择题3313下面集合（）关于减法运算是封闭的。A、N；B、2x xI；C、2x1 xI；D、xx是质数。14具有如下定义的代数系统 G,，（）不构成群。A、G 1,10，*是模 11 乘；B、G 1,3,4,5,9，*是模 11 乘；C、G Q（有理数集），*是普通加法；D、G Q（有理数集），*是普通乘法。15mn设G 2 3m,n I，*为普通乘法。则代数系统 G,的幺元为（）。0011A、不存在；B、e 2 3；C、e 23；D、e 23。33答：D44答：B选 28.3择题选 28.3择题选 26.2择题4416下面集合

5、（）关于整除关系构成格。A、2，3，6，12，24，36；B、1，2，3，4，6，8，12；C、1，2，3，5，6，15，30；D、3，6，9，12。17设V a,b,c,d,e,f，答：C55答：C333E a,b ,b,c ,c,a ,a,d ,d,e ,f,e，则有向图。G V,E 是（）A、强连通的；B、单侧连通的；C、弱连通的；D、不连通的。18下面那一个图可一笔画出（）。答：A选 26.4择题4419在任何图中必定有偶数个（）。A、度数为偶数的结点；B、入度为奇数的结点；C、度数为奇数的结点；D、出度为奇数的结点。20含有 3 个命题变元的具有不同真值的命题公式的个数为（）。A、2

6、；B、3；C、23答：C选 26.2择题选 22.1择题选 23.2择题选 22.2择题33答：C33223；D、232。答：A21下列集合中哪个是最小联结词集（）。A、,；B、,；C、,；D、,。22下面哪个命题公式是重言式（）。A、(P Q)(Q R)；B、(P Q)P；C、(P Q)(P Q)；D、(P Q)P。23在谓词演算中，下列各式哪个是正确的（）。A、xyA(x,y)yxA(x,y)；B、xyA(x,y)yxA(x,y)；33答：B33答：A选 23.2择题334C、xyA(x,y)yxA(x,y)；D、A(a)xA(x)。24命题公式P (Q P)是（）。矛盾式；B、可满足式；

7、C、重言式；D、等价式。25下列各式中哪个不成立（）。A、x(P(x)Q(x)xP(x)xQ(x)；B、x(P(x)Q(x)xP(x)xQ(x)；C、x(P(x)Q(x)xP(x)xQ(x)；D、x(P(x)Q)xP(x)Q。26谓词公式x(P(x)yR(y)Q(x)中的 x 是（）。A、自由变元；B、约束变元；C、既是自由变元又是约束变元；D、既不是自由变元又不是约束变元。27 6在自然数集 N 上，下列（）运算是可结合的。（对任意a,b N）A、ab a b；B、ab max(a,b)；C、ab a 5b；D、ab ab。28 Q 为有理数集 N，Q 上定义运算*为 a*b=a+b ab,

8、则的幺元为（）。A、a；B、b；C、1；D、0。29给定下列序列，（）可以构成无向简单图的结点次数序列。A、（1，1，2，2，3）；B、（1，1，2，2，2）；答：C选 22.2择题选 23.2择题33答：A33答：C选 23.1择题选 28.1择题33答：B33答：D选 28.1择题选 26.1择33答：B335C、（0，1，3，3，3）；D、（1，3，4，4，5）。30设 G 是简单有向图，可达矩阵P(G)刻划下列（）关系。A、点与边；B、边与点；C、点与点；D、边与边。31一颗树有两个 2 度结点，1 个 3 度结点和 3 个 4 度结点，则 1 度结点数为（）。A、5；B、7；C、9；

9、D、8。32设 A=1，2，3，4，5，下面（）集合等于 A。A、1，2，3，4，5，6；B、x x是整数且x2 25；C、x x是正整数且x 5；D、x x是正有理数且x 5。33设 A=1，2，3，4，5，6，7，8，下列各式中（）是错的。A、A；B、6，7，8A；C、4，5A；D、1，2，3A。34六阶群的子群的阶数可以是（）。A、1，2，5；B、2，4；C、3，6，7；D、2，3。35设S A B，下列各式中（）是正确的。domSB；B、domSA；C、ranSA；D、domSranS=S。36答：D答：D答：C题选 26.2择题选 27.1择题选 21择题44答：C33答：C33选

10、21择题选 28.3择题选 25.1择题3355答：D33 G,*是群，则对*（）。A、满足结合律、交换律；B、有单位元，可结合；C、有单位元、可交换；D、每元有逆元，有零元。答：B选 28.3；8.133择题637下面（）哈斯图所描述的偏序关系构成分配格。答：D选 28.3择题5538下列（）中的运算符都是可交换的。A、,；B、,；C、,；D、,。39设 G 是 n 个结点、m 条边和 r 个面的连通平面图，则m 等于（）。A、n+r-2；B、n-r+2；C、n-r-2；D、n+r+2。40n 个结点的无向完全图Kn的边数为（）。A、n(n 1)；B、41下列图中（）是根树。A、G1a,b,

11、c,d,a,a,a,b,c,d；B、G2a,b,c,d,a,b,b,d,c,d；C、G3a,b,c,d,a,b,a,d,c,a；D、G4a,b,c,d,a,b,a,c,d,d。答：D选 21；2.1择题选 26.4择题选 26.1择题33答：A33答：D33n(n 1)n(n 1)；C、n(n 1)；D、。22答：C选 27.2择题3342设 P：22=5，Q：雪是黑的，R：24=8，S：太阳从东方升起，下列（）命题的真值为真。答：A选 22.1择337A、P Q R；B、R P S；C、S Q R；D、(P R)(Q S)。43设 L(x)：x 是演员，J(x)：x 是老师，A(x,y)：x

12、 钦佩 y，命题“所有演员都钦佩某些老师”符号化为（）。A、x(L(x)A(x,y)；B、x(L(x)y(J(y)A(x,y)；C、xy(L(x)J(y)A(x,y)；D、xy(L(x)J(y)A(x,y)44n集合A x x 2,nN对（）运算封闭。A、加法；B、减法；C、乘法；D、x y。45答：B设 I 为整数集合，m 是任意正整数，Zm是由模 m 的同余类组成的同余类集合，在Zm上定义运算答：C答：B题选 23.1择题33选 28.1择题选 28.3择题3355i j(i j)modm，则代数系统 Zm,m最确切的性质是（）。A、封闭的代数系统；B、半群；C、独异点；D、群。46连通非

13、平凡的无向图 G 有一条欧拉回路当且仅当图G()。A、只有一个奇度结点；B、只有两个奇度结点；C、只有三个奇度结点；D、没有奇度结点。47设无向图G V,E 是连通的且V n,E m若（）则 G 是树。A、M=N+1；B、n=m+1；C、m 3n 6；D、n 3m 6。48如果解释 I 使公式 A 为真，且使公式A B也为真，则解释 I 使公式 B 为（）。A、真；B、假；C、可满足；D、与解释 I 无关。49设A a,b，则P（A）A=（）。A、A；B、P（A）；答：D选 26.4择题选 26.4择题选 22.2择题选 21择题33答：B33答：A33答：C338C、,a,b,a,a,a,b

14、,b,a,b,b,A,a,A,b；D、a,b,a,a,b,a,a,b,b,b,a,A,b,A。选 25.2择题4450答：D设集合 A，B 是有穷集合，且A m,B n，则从A 到 B 有（）个不同的双射函数。A、n；B、m；C、n!；D、m!。51设 K=e,a,b,c，K,是 Klein 四元群，则元素 a 的逆元为（）。A、e；B、a；C、b；D、c。52一个割边集与任何生成树之间（）。答：DA、没有关系；B、割边集诱导子图是生成树；C、有一条公共边；D、至少有一条公共边。53下列语句中不是命题的有（）A、9+512；B、x+3=5；C、我用的计算机 CPU 主频是 1G 吗？；D、我要

15、努力学习。54命题“我不能一边听课，一边看小说”的符号化为（）A、P Q；B、P Q；C、Q P；D、(P Q)。55下列表达式正确的有（）A、(P Q)Q；B、P Q P；C、(P Q)(P Q)P；D、P (P Q)T。56若公式(P Q)(P R)的主析取范式为答：B答：A、C答：A、D答：B、C答：B选 28.1；8.333择题选 26.2择题选 21；2.1择题选 22.2择题333333选 22.4择题33选 22.3择题449m001 m011 m110 m111则它的主合取范式为（）A、m001 m011 m110 m111；B、M000 M010 M100 M101；C、M0

16、01 M011 M110 M111；D、m000 m010 m100 m101。57命题“尽管有人聪明，但未必一切人都聪明”的符号化（P(x)：x 是聪明的，M(x)：x 是人）（）A、x(M(x)P(x)(x(M(x)P(x)B、x(M(x)P(x)(x(M(x)P(x)C、x(M(x)P(x)(x(M(x)P(x)D、x(M(x)P(x)(x(M(x)P(x)58设 A=，B=(A)下列（）表达式成立。A、B；B、B；C、答：A、B、C选 21；2.1择题选 21；3.1择题选 21择题33答：C选 23.1择题33 B；D、B。答：B59 A 是素数集合，B 是奇数集合，则 A-B=（）

17、A、素数集合；B、奇数集合；C、；D、2。60集合B,的幂集为（）。A、,；B、,B；C、,B；33答：B3310D、,，,B61下列结果正确的是（）。A、(A B)A B；B、(A B)A ；C、(A B)B A；D、；62答：B选 21；3.1择题33wff(p q)r的主析取范式中含极小项的个数为（）。答：CA、2；B、3；C、5；D、0；E、8。63在（）下有A B A。A、A B；B、B A；C、A B；D、A 或B 64下列二元关系中是函数的有（）。A、R x,y|x N y N x y 10；B、R x,y|xR yR y x；C、R x,y|xR yR x y 22选 22.3

18、择题选 24.2择题选 25.2择题44答：D33答：B3365答：Cx,yQ有x*y x y xy，在有理数集 Q 上定义的二元运算*，则 Q 中满足（）。A、所有元素都有逆元；B、只有唯一逆元；C、xQ,x 1时有逆元x；D、所有元素都无逆元。66设 S=0，1，*为普通乘法，则是（）。A、半群，但不是独异点；B、只是独异点，但不是群；C、群；D、环，但不是群。答：B1选 28.1择题33选 28.3择题551167答：D选 28.3择题44图给出一个格 L，则 L 是（）。A、分配格；B、有补格；C、布尔格；D、A,B,C 都不对。68答：B选 26.2择题33有向图 D=69，则v1到

19、v4长度为 2 的通路有（）条。答：D选 26.4择题55A、0；B、1；C、2；D、3。在 Peterson 图中，至少填加（）条边才能构成 Euler 图。A、1；B、2；C、4；D、5。70下面各集合都是 N 的子集，（）集合在普通加法运算下是封闭的。A、x|x 的幂可以被 16 整除；B、x|x 与 5 互质；C、x|x 是 30 的因子；D、x|x 是 30 的倍数。71设G10,1,2,，G20,1,*，其中表示模 3 加法，*表示模 2 乘法，则积代数G1G2答：A、D选 28.1;8.2择题选 28.1;8.3择33答：B4412的幺元是（）。A、；B、；C、；D、。72设集合

20、 S=1,2,3,6，“”为整除关系，则代数系统是（）。A、域；B、格，但不是布尔代数；C、布尔代数；D、不是代数系统。73设 n 阶图 G 有 m 条边，每个结点度数不是k 就是 k+1，若 G 中有 Nk个 k 度结点，则 Nk=（）。A、nk；B、n(k+1)；C、n(k+1)-m；D、n(k+1)-2m。答：C题选 28.3择题选 26.1;6.4择题选 27.1择题选 28.1;8.3择题选 28.2;8.3择题55答：D3374一棵树有 7 片树叶，3 个 3 度结点，其余全是4 度结点，则该树有（）个4 度结点。答：AA、1；B、2；C、3；D、4。75设 是环，a,b A，ab

21、 的关于“+”的逆元是（）。A、(-a)(-b)；B、(-a)b；C、a(-b)；D、ab。76设 是一代数系统且是 Abel 群，如果还满足（）是域。A、是独异点且对+可分配；B、是独异点，无零因子且对+可分配；C、是 Abel 群且无零因子；D、是 Abel 且对+可分配。77设是一代数系统，+、为普通加法和乘法运算，当 A 为（）时，是域。A、x|x a b 5,a,b均为有理数；B、x|x a b35,a,b均为有理数；C、x|x 答：D答：B、C334444答：A选 28.2;8.3择题44a,a,b I,且a kb；D、x|x 0，x I。b答：B选 28.2择题5578设是一个格

22、，由格诱导的代数系统为 A,，则（）成立。A、A,满足 对的分配律；B、a,b A,a b a b b；13C、a,b,c A,若a b a c则b c；D、a,b A,有a(a b)b且 a(ab)b。79设是偏序集，“”定义为：a,b A,a b a|b，则当 A=（）时，是格。A、1,2,3,4,6,12；B、1,2,3,4,6,8,12,14；C、1,2,3,，12；D、1,2,3,4。80设 R 和 S 是 P 上的关系，P 是所有人的集合，R x,y|x,yP x是y的父亲，。S x,y|x,yP x是y的母亲则S1R表示关系（）A、x,y|x,yP x是y的丈夫；B、x,y|x,

23、yP x是y的孙子或孙女；C、；D、x,y|x,yP x是y的祖父或祖母。81在（）中，补元是唯一的。A、有界格；B、有补格；C、分配格；D、有补分配格。82在布尔代数 A,中，b c 0当且仅当（）。A、b c；B、c b；C、b c；D、c b。83设 A,是布尔代数，f 是从 An到 A 的函数，则（）。A、f 是布尔代数；B、f 能表示成析取范式，也能表示成合取范式；C、若 A=0，1，则 f 一定能表示成析取范式，也能表示成合取范式；D、若 f 是布尔函数，它一定能表示成析（合）取范式。答：A选 28.3择题选 25.2择题44答：A33答：D选 28.3择题选 28.3择题选 28

24、.2;8.3择题33答：C44答：C、D551484下列命题正确的有（）。A、若g,f是满射，则g f是满射；B、若g f是满射，则g,f都是满射；C、若g f是单射，则g,f都是单射；D、若g f单射，则f是单射。85设 f，g 是函数，当（）时，f=g。A、xdomf 都有 f(x)g(x)；B、domg domf 且 f g；C、f与g的表达式相同；D、domg domf,rangef rangef86下列关系，（）能构成函数。A、f x1,x2|x1,x2 N且x1 x210；B、f x1,x2|x1,x2R,x1 x2；C、f x1,x2|x1,x2 N,x2为小于x1的素数的个数；

25、D、f x,x|xR。87设 R，S 是集合 A 上的关系，则下列（）断言是正确的。A、R,S自反的，则R S是自反的；B、若R,S对称的，则R S是对称的；C、若R,S传递的，则R S是传递的；D、若R,S反对称的，则R S是反对称的。88设S 1,2,3，定义S S上的等价关系2答：A、D选 25.2择题33答：B选 25.2择题33答：C、D选 25.1择题33答：A选 24.3择题33答：BR a,b,c,d|a,b S S,c,d S S,a d b c则 由R 产生 的S S上一个划分共有（）个分块。A4；B5；C6；D9。选 24.1择题331589“没有不犯错误的人”的逻辑符号

26、化为（）。设 H（x）：x 是人，P（x）：x 犯错误。A、x(H(x)P(x)；B、(x(H(x)P(x)；C、(x(H(x)P(x)；D、x(H(x)P(x)。90下列各符号串，不是合式公式的有（）。A、(P Q)R；B、(P Q)(R S)；C、P Q R；D、(P Q)R)S。91下列语句是命题的有（）。A、2 是素数；B、x+5 6；C、地球外的星球上也有人；D、这朵花多好看呀！。92下列问题成立的有（）。A、若A C B C，则A B；B、若A C B C，则A B；C、若A B，则A B；D、若A B，则A B。93命题“有的人喜欢所有的花”的逻辑符号化为（）。设 D：全总个体域

27、，F（x）：x 是花，M(x)：x 是人，H(x,y)：x 喜欢 yA、x(M(x)y(F(y)H(x,y)；B、x(M(x)y(F(y)H(x,y)；C、x(M(x)y(F(y)H(x,y)；D、x(M(x)y(F(y)H(x,y)。94公式xy(P(x,y)Q(y,z)xP(x,y)换名（）。A、xu(P(x,u)Q(u,z)xP(x,y)；B、xy(P(x,u)Q(u,z)xP(x,u)；C、xy(P(x,y)Q(y,z)xP(x,u)；D、uy(P(u,y)Q(y,z)uP(u,y)。答：B、D选 23.2择题33答：B、C选 23.1择题33答：A、C选 21择题选 22.3择题选

28、23.2择题33答：C、D33答：B33答：A选 23.1择题331695给定公式xP(x)xP(x)，当 D=a,b时，解释（）使该公式真值为 0。A、P(a)=0、P(b)=0；B、P(a)=0、P(b)=1；C、P(a)=1、P(b)=0；D、P(a)=1、P(b)=196下面蕴涵关系成立的是（）。A、xP(x)xQ(x)x(P(x)Q(x)；B、xP(x)xQ(x)x(P(x)Q(x)；C、xP(x)xQ(x)x(P(x)Q(x)；D、xyA(x,y)yxA(x,y)。97设S 1,2,3，S 上关系 R 的关系图为答：B、C选 23.1择题选 23.2择题33答：B、D33答：D选 24.3择题33则 R 具有（）性质。A自反性、对称性、传递性；B反自反性、反对称性；C反自反性、反对称性、传递性；D自反性。98一棵无向树 T 有 8 个顶点，4 度、3 度、2 度的分枝点各 1 个，其余顶点均为树叶，则T 中有（）答：C片树叶。A、3；B、4；C、5；D、699下图中是哈密顿图的为（）。选 27.1择题选 26.4择33答：B、D3317题100下面是前缀编码的是（）答：AA.00,10,110,011C.111,000,110,11B.10,000,101,01D.010,110,01,101选 27.2择题2218