离散数学单项选择题习题(有答案)集.doc

单项选择题
第一章第二章
1. 下列表达式正确的有( )
A. B. C. D.
2. 下列推理步骤错在( )
① P
② US①
③ P
④ ES③
⑤ T②④I
⑥ EG⑤
A.② B.④ C.⑤ D.⑥
3. 设P：2×2=5，Q：雪是黑的，R：2×4=8，S：太阳从东方升起，下列( )命题的真值为真。
A. B. C. D.
4. 下列公式中哪些是永真式？( )
A.(┐PQ)→(Q→R) B.P→(Q→Q) C.(PQ)→P D.P→(PQ)
5. 下列等价关系正确的是( )
A. B.
C. D.
6. 下列推导错在( )
① P
② US①
③ ES②
④ UG③
A.② B. ④ C. ③ D.无
7. 若公式的主析取范式为则它的主合取范式为( )
A. B. ；
C. D. 。
8. 在下述公式中不是重言式为( )
A． B．
C． D．
9. 下列各式中哪个不成立( )
A. B.
C. D.
10. 命题“尽管有人聪明，但未必一切人都聪明”的符号化（P(x)：x是聪明的，M(x)：x是人）( )
A. B.
C. D.
11. 下述命题公式中，是重言式的为( )
A. B.
C. D.
12. 谓词公式中的x是( )
A.自由变元 B.约束变元
C.既是自由变元又是约束变元 D.既不是自由变元又不是约束变元
13. 命题“有的人喜欢所有的花”的逻辑符号化为( )
设D：全总个体域，F（x）：x是花，M(x) ：x是人，H(x,y)：x喜欢y
A. B.
C. D.
14. 下列等价式成立的有( )
A. B. C. D.
15. 给定公式，当D={a,b}时，解释( )使该公式真值为0。
A.P(a)=0、P(b)=0 B.P(a)=0、P(b)=1 C.P(a)=1、P(b)=1
16. 设是人，犯错误,命题“没有不犯错误的人”符号化为( )
A. B. C. D.
17. 下列语句是命题的有( )
A.明年中秋节的晚上是晴天 B. C.当且仅当x和y都大于0 D.我正在说谎
18. 下列公式是重言式的有( )
A. B. C. D.
19. 下列集合中哪个是最小联结词集( )
A. B.{,D} C. {",D} D.
20. 设L(x)：x是演员，J(x)：x是老师，A(x , y)：x钦佩y，命题“所有演员都钦佩某些老师”符号化为( )
A. B.
C. D.
21. 下列各命题中真值为真的命题有( )
A.2+2=4当且仅当3是奇数 B.2+2=4当且仅当3不是奇数
C.2+2≠4当且仅当3是奇数 D.2+2=4仅当3不是奇数
22. 命题逻辑演绎的CP规则为( )
A.在推演过程中可随便使用前提
B.在推演过程中可随便使用前面演绎出的某些公式的逻辑结果
C.如果要演绎出的公式为形式，那么将B作为前提，演绎出C
D.设是含公式A的命题公式，，则可用B替换中的A
第三章
23. 设A={1，2，3，4}，P（A）（A的幂集）上规定二元系则P（A）/ R=( )
A．A B．P(A) C．{[]R，[{1}]R，[{1，2}]R，[{1，2，3}]R，[{1，2，3，4}]R }
D．{[]R，[2]R，[2，3]R，[2，3，4]R，[A]R }
24. 集合A={1,2,…,10}上的关系R={<x,y>|x+y=10,x,yA}，则R 的性质为( )
A.自反的　　B.对称的　　 C.传递的，对称的 D.传递的
25. 集合A={1，2，3，4}上的偏序关系为，则它的Hass图为( C )

26. 设R，S是集合A上的关系，则下列说法正确的是( )
A．若R，S 是自反的， 则是自反的 B．若R，S 是反自反的， 则是反自反的
C．若R，S 是对称的， 则是对称的 D．若R，S 是传递的， 则是传递的
27. Ａ，Ｂ，Ｃ是三个集合，则下列哪几个推理正确 ( )
A.AB，BC则AC B.AB，BC则 A∈B C.A∈B，B∈C则 A∈C
28. 设A={，{1}，{1，3}，{1，2，3}}则A上包含关系“”的哈斯图为( C )

29. 设f，g是函数，当( C )时，f=g
A. B.
C. D.
30. 设，则B－A是( )
A. B. C. D.
31. 集合A={1，2，3，4}上的偏序关系图如下左，则它的哈斯图为( C )

32. 设，定义上的等价关系,,则由R产生的上一个划分共有( B )个分块。
A．4 B．5 C．6 D．9
33. 下列是真命题的有( )
A． B． C． D．
34. 设，下列各式中( B )是正确的
domSB B.domSA C.ranSA D.domS ranS = S
35. 设，S上关系R的关系图如下 ，则R具有( D )性质

A．自反性、对称性、传递性 B．反自反性、反对称性 C．反自反性、反对称性、传递性 D．自反性
36. 设,,,
下列相等的集合是( D )
A.A的B B.B和C C.C和D D.A和D
37. 设，则P（A）×A = ( C)
A.A B.P（A）
C.
D.
38. A是素数集合，B是奇数集合，则A-B=( D )
A.素数集合 B.奇数集合 C. D.{2}
39. 设R和S是P上的关系，P是所有人的集合，，则表示关系 ( A )
A. B.
C. D.
40. 在自然数集N上，（对任意）下列( B)运算是可结合的
A. B. C. D.
41. Q为有理数集N，Q上定义运算*为a*b = a + b – ab ，则<Q，*>的幺元为( 0 )
A.a B.b C.1 D.0
42. 公式换名( A )
A. B.；
C. D.。
43. 下面蕴涵关系不成立的是( C )
A. B.
C. D.
44. N是自然数集，定义（即x除以3的余数）,则f是(D)
A.满射不是单射 B.单射不是满射 C.双射 D.不是单射也不是满射
45. 集合A={2，3，6，12，24，36}上偏序关系R的Hass图为
则集合B={2，3，6，12}的上确界( )
B={2，3，6，12}的下界( )
C={6，12，24，36}的下确界( )
D={6，12，24，36}的上界( )
A. 12,无,6,36 B. 12,2,6,36 C. 12,2,12,36 D.12,无,6,无
46. 下列哪个偏序集构成有界格( )
A.（N，）　B.（Z，） C.（{2，3，4，6，12}，|（整除关系）） D.(P（A），)
47. 六阶群的子群的阶数可以是( D)
A.1，2，5 B.2，4 C.3，6，7 D.2，3
48. 对右图，则分别为( C )
A.2、2、1 B.1、1、2 C.1、1、1 D.1、2、2
49. 一棵树有7片树叶，3个3度结点，其余全是4度结点，则该树有( A )个4度结点
A.1 B.2 C.3 D.4
50. 具有6 个顶点，12条边的连通简单平面图中，每个面都是由( C )条边围成
A.2　　B.4　　C.3　　D.5
51. 设G是有n个结点m条边的连通平面图，且有k个面，则k等于( A)
A.m-n+2 B.n-m-2 C.n+m-2 D.m+n+2
52. 下列哪个公式为永真式？( C )
A.Q=>Q→P B.Q=>P→Q C.P=>P→Q D.P(PQ)=>P
53. “人总是要死的”谓词公式表示为( )（论域为全总个体域）M(x)：x是人；Mortal(x)：x是要死的
A. B. C. D.
54. 设，则有( A )
A.{{1,2}} B.{1,2 } C.{1} D.{2}
55. 判断下列命题哪个正确？( B )
A.若A∪B＝A∪C，则B＝C B.{a,b}={b,a}
C.P(A∩B)P(A)∩P(B)（P(S)表示S的幂集） D.若A为非空集，则AA∪A成立
56. 下列结果正确的是( )
A. B. C. D.
57. 集合对( )运算封闭
A. 乘法 B.减法 C. 加法 D.
58. 设I为整数集合，m是任意正整数，是由模m的同余类组成的同余类集合，在上定义运算，则代数系统最确切的性质是( )
A.封闭的代数系统 B.半群 C.独异点 D.群
59. 设是偏序格，其中N是自然数集合，“≤”是普通的数间“小于等于”关系，则 有( )
A.a B.b C.min(a，b) D. max(a，b)
60. 一棵无向树T有4度、3度、2度的分枝点各1个，其余顶点均为树叶，则T中有( )片树叶
A.3 B.4 C.5 D.6
61. 有向图D=<V , E> ，则长度为2的通路有( )条
A.0 B.1 C.2 D.3
62. 设，，则有向图
是( )
A.强连通的 B.单侧连通的 C.弱连通的 D.不连通的
63. 设无向图G有18条边且每个顶点的度数都是3，则图G有( )个顶点
A.10 B.4 C.8 D.12

64. 下列命题正确的是( C )
A. B.
C. D.
65. 设A={a,{a}}，下列命题错误的是( B )
A.{a}P(A) B.{a}P(A) C.{{a}}P(A) D.{{a}}P(A)
66. 设A={} ，B=Р(Р(A)) 下列( )表达式不成立
A. B. C. D.
67. 设R，S是集合A上的关系，则下列( )断言是正确的
A.自反的，则是自反的 B.若对称的，则是对称的
C.若传递的，则是传递的 D.若反对称的，则是反对称的
68. 设P={x|(x+1)4且xR},Q={x|5x+16且xR},则下列命题哪个正确( )
A.QP　　B.QP　C.PQ　 D.P=Q
代数系统
69. ，其中，为集合对称差运算，则方程的解为( )
A. B. C. D.
70. 在有理数集Q上定义的二元运算*，有， 则Q中满足( )
A. 时有逆元 B.只有唯一逆元 C. 所有元素都有逆元 D.所有元素都无逆元
71. 设S={0，1}，*为普通乘法，则< S ， * >是( )
A.半群，但不是独异点 B.只是独异点，但不是群 C.群 D.环，但不是群
72. 设A={1，2，…，10 }，则下面定义的运算*关于A封闭的有( )
A.x*y=max(x ，y) B.x*y=质数p的个数使得
C.x*y=gcd(x ， y) (gcd (x ，y)表示x和y的最大公约数)
D.x*y=lcm(x ，y) （lcm(x ，y) 表示x和y的最小公倍数）
73. 设[{a ， b ， c}，*]为代数系统，*运算如下：
*
a
b
c
a
a
b
c
b
b
a
c
c
c
c
c
则零元为( C)
A.a B.b C.c D.没有
74. 设，，其中表示模3加法，*表示模2乘法，在集合上定义如下运算：有称为的积代数，则的积代数幺元是( B )
A.<0，0> B.<0，1> C.<1，0> D.<1，1>
75. 设R是实数集合，“”为普通乘法，则代数系统<R ，×> 不是( A )
A．群 B．独异点 C．半群

76. 设<A， >是一个格，由格诱导的代数系统为，则( )成立
A. B.
C. D.
77. 设，*为普通乘法，则<S，*>是( )
A.代数系统 B.半群 C.群 D.都不是
78. 设，*为普通乘法，则<S，*>是( )
A.代数系统 B.半群 C.群 D.都不是
79. 在自然数集N上，下列哪种运算是可结合的？( )
A.a*b=a-b　　B.a*b=max{a，b}　C.a*b=a+2b　D.a*b=|a-b|
80. 设是一个有界格，如果它也是有补格，只要满足( )
A. 每个元素都至少有一个补元 B. 每个元素都有多个补元 C.每个元素都无补元 D. 每个元素都有一个补元
81. 具有如下定义的代数系统，( )不构成群
A.，*是模11乘 B.，*是模11乘
C.（有理数集），*是普通加法 D.（有理数集），*是普通乘法
82. 在( )中，补元是唯一的
A.有界格 B.有补格 C.分配格 D.有补分配格
83. 在布尔代数中，当且仅当( )
A. B. C. D.
84. 设<A， >是偏序集，“”定义为：，则当A=( )时，<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}
85. 设是布尔代数，f是从An到A的函数，则( )
A.f是布尔代数 B.f能表示成析取范式，也能表示成合取范式
C.若A={0，1}，则f一定能表示成析取范式，也能表示成合取范式
D.若f是布尔函数，它一定能表示成析（合）取范式
图论
86. 连通非平凡的无向图G有一条欧拉回路当且仅当图G ( )
A.只有一个奇度结点 B.只有两个奇度结点 C.只有三个奇度结点 D.没有奇度结点
87. 设为无向图，，则G一定是( )
A.完全图 B.树 C.简单图 D.多重图
88. 若一棵完全二元（叉）树有2n-1个顶点，则它( )片树叶
A.n　　B.2n C.n-1 D.2
89. 图 给出一个格L，则L是( )
A.分配格 B.有补格 C.布尔格 D.A，B，C都不对
90. 在Peterson图 中，至少填加( )条边才能构成Euler图
A.1 B.2 C.4 D.5
91. 在有n个顶点的连通图中，其边数( )
A.最多有n-1条　　B.至少有n-1 条 C.最多有n条 　 D.至少有n 条
92. 图 中 从v1到v3长度为2的通路有( )条

A． 0 B． 3 C． 2 D． 1
93. 下面那一个图可一笔画出( A )

94. 一个割边集与任何生成树之间( )
A.没有关系 B.割边集诱导子图是生成树 C.有一条公共边 D.至少有一条公共边
95. 在任何图中必定有偶数个( )
A.度数为偶数的结点 B.入度为奇数的结点 C.度数为奇数的结点 D.出度为奇数的结点
96. 一棵树有2个2度顶点，1 个3度顶点，3个4度顶点，则其1度顶点为( )
A.5　　B.7 C.8 D.9

97. 下列偏序集( C )能构成格

98. 连通图G是一棵树当且仅当G中( )
A.有些边是割边　　B.每条边都是割边 C.所有边都不是割边 D.图中存在一条欧拉路径
99. 有n个结点，条边的连通简单图是平面图的必要条件( )
A. B. C. D.
100. 设无向图G有18条边且每个顶点的度数都是3，则图G有( )个顶点
A.10 B.4 C.8 D.12
101. 在有n个顶点的连通图中，其边数( )
A.最多有n-1条　　B.至少有n-1条 C.最多有n条　 D.至少有n条
102. 给定无向图，如下图所示，下面哪个边集不是其边割集( )
A. B.
C. D.
103. 如右图 相对于完全图K5的补图为( A )

104. 下列哪一种图不一定是树( )
A.无回路的简单连通图　　 B.每对顶点间都有通路的图
C.有n个顶点n-1条边的连通图 D.连通但删去任何一条边便不连通的图
105. 下面偏序集( B )能构成格

106. 6阶有限群的任何子群一定不是( )
A.2阶　　 B.3 阶 C.4 阶 D.6 阶
107. 在如下的有向图中，从V1到V4长度为3 的道路有( )条

A．1 B．2 C．3 D．4
108. n个结点的无向完全图的边数为( )
A. B. C. D.
109. 设G是一个哈密尔顿图，则G一定是( )
A.欧拉图 B.树 C.平面图 D.连通图
110. 在如下各图中( B)是欧拉图

111. 下列图中( )是根树
A. B.
C. D.
112. 下面给出的集合中，哪一个是前缀码？( )
A.{0，10，110，101111} B.{1，11，101，001，0011} C.{b，c，aa，ab，aba} D.{01，001，000，1}
113. 左图[0]相对于完全图的补图为( A )

114. 下列图中是欧拉图的有( A )

115. 设n阶图G有m条边，每个结点度数不是k就是k+1，若G中有Nk个k度结点，则Nk=( )
A.n×k B.n×(k+1) C.n×(k+1)-m D.n×(k+1)-2m
116. 设G是简单有向图，可达矩阵P(G)刻画下列 ( C )关系
A.点与边 B.边与点 C.点与点 D.边与边
117. 设G是一棵树，n,m分别表示顶点数和边数，则( )
A.n=m B. n=m+1 C. m=n+1 D.不能确定 .

13