离散数学试题带答案
一、选择题
1、G 是一棵根树，则（ ）。
A 、G 一定是连通的
B 、G 一定是强连通的
C 、G 只有一个顶点的出度为0
D 、G 只有一个顶点的入度为1
2、下面哪个语句不是命题（ ）。
A 、中国将成功举办2008年奥运会
B 、一亿年前地球发生了大灾难
C 、我说的不是真话
D 、哈密顿图是连通的
3、设R 是实数集合，在上定义二元运算*：a ，b ∈R ，a*b=a+b-ab ，则下面的论断中正确的
是（ ）。
A 、0是*的零元
B 、1是*的幺元
C 、0是*的幺元
D 、*没有等幂元
4、下面说法中正确的是（ ）。
A 、所有可数集合都是等势的
B 、任何集合都有与其等势的真子集
C 、有些无限集合没有可数子集
D 、有理数集合是不可数集合
5、无向完全图K 3的不同构的生成子图有（ ）个。
A. 6
B.5
C. 4
D. 3
6、下面哪一种图不一定是无向树?
A 、无回路的连通图
B 、有n 个顶点n-1条边的连通图
C 、每对顶点间都有通路的图
D 、连通但删去一条边则不连通的图
7、设集合A ＝{{1,2,3},{4,5},{6,7,8}}，则下列各式为真的是( )。
A.1∈A
B.{{4,5}}⊂A
C. {1,2,3}⊆A
D.∅∈A
8、在有界格中，若一个元素有补元，则补元( )。
A 、必惟一
B 、不惟一
C 、不一定惟一
D 、可能惟一
9、设集合A={1,2,3,…,10}，下面定义的哪种运算关于集合A 是不封闭的？（ ）
A 、 x*y=max{x,y}
B 、 x*y=min{x,y}
C 、 x*y=GCD(x,y)，即x,y 的最大公约数
D 、 x*y=LCM(x,y)，即x,y 的最小公倍数
10、集合X 中的关系R ，其矩阵是⎥⎥⎥⎦
⎤⎢⎢⎢⎣⎡=111011101M ，则关于R 的论述中正确的是（ ）
。
A 、R 是对称的
B 、R 是反对称的
C 、R 是反自反的
D 、R 中有7个元素
11. 下列各组数中，哪个可以构成无向图的度数列（ ）。
A.1，1，1，2，2
B.2，2，2，2，3
C.1，2，2，4，6
D.2，3，3，3
12. *是定义在Z 上的二元运算，y x xy y x Z y x -+=*∈∀,,，则*的幺元和零元分别是
（ ）。
A.不存在，0
B.0，1
C.1，不存在
D.不存在，不存在
13. 设N N N f ,:→为自然数，且 ⎪⎩⎪⎨⎧=为偶数若为奇数若x x
x x f 2
1)(
则})0({)0(f f 和分别是（ ）。 A.0，0 B.0，{0}
C.{0}，{0}
D.{0}，0
14. 下列命题公式中是矛盾式的有（ ）。
A.p p p ⌝→⌝→)(
B.p p q ∧→⌝)(
C.)()(p q q p ⌝→→→⌝
D.r q p →∨)(
15. 下列各Hasse 图中，是格的有（ ）。
A. B.
C. D.
16． 下列命题公式中是永假式的有（ ）。
A.p p p ⌝→⌝→)(
B.p p q ∧→⌝)(
C.)()(p q q p →⌝→→⌝
D.r q p →∨)(
17. 设命题公式⌝(P ∧(Q →⌝P))，记作G ，则使G 的真值指派为0的P ，Q 的取值是( )。
A.(0,0)
B.(0,1)
C.(1,0)
D. (1,1)
18. 与命题公式P →（Q →R ）等值的公式是( )。
A.(P ∨Q)→R
B.(P ∧Q)→R
C.(P →Q)→R
D. P →(Q ∨R)
19. 命题公式(P ∧Q)→P 是( )。
A.永真式
B.永假式
C.可满足式
D.合取范式
20. 设命题公式)(),(P Q P H Q P G ⌝→→⇔→⌝⇔，则G 与H 的关系是( ) 。
A.H Q →
B.G H →
C.G H ⇒
D.H G ⇒
21．谓词公式)())()((x Q y yR x P x →∃∨∀中量词∀x 的辖域是( )。
A ))()((y yR x P x ∃∨∀ B. P(x) C.)()(y yR x P ∃∨ D.)(x Q
22．设个体域为整数集，下列公式中其值为1的是( )。
A.)0(=+∃∀y x y x
B.)0(=+∀∃y x x y
C.)0(=+∀∀y x y x
D.)0(=+∃⌝∃y x y x
23．设L(x)：x 是演员，J(x)：x 是老师，A(x,y)：x 佩服y. 那么命题“所有演员都佩服
某些老师”符号化为( )。
A.),()(y x A x xL →∀
B.)),()(()((y x A y J y x L x ∧∃→∀
C.)),()()((y x A y J x L y x ∧∧∃∀
D.)),()()((y x A y J x L y x →∧∃∀
24．在谓词演算中，P(a)是)(x xP ∀的有效结论，根据是 ( )。
规则
B.UG 规则
C.ES 规则
D.EG 规则
25. 在图G ＝中，结点总度数与边数的关系是( )。
A.deg(v i )=2∣E ∣
B. deg(v i )=∣E ∣
C.∑∈=V v E v 2)deg(
D. ∑∈=V
v E v )deg(
26. 设G 是有n 个结点的无向完全图，则图G 的边数为( )；设D 是有n 个结点的有向完
全图，则图D 的边数为( )。
A. n(n －1)
B. n(n+1)
C. n(n －1)/2
D. n(n+1)/2
27. 仅有一个孤立结点的图称为( )。
A.零图
B.平凡图
C.补图
D.子图
28. 设G ＝为无向简单图，∣V ∣=n ，∆(G)为G 的最大度，则有（ ）。
A. ∆(G)B.∆(G)≤n
C. ∆(G)>n
D. ∆(G)≥n
