《离散数学》测试题答案 下载本文

内容发布更新时间 : 2024/12/23 21:03:12星期一 下面是文章的全部内容请认真阅读。

测 试 题

——离散数学

一、选择题

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、无向完全图K3的不同构的生成子图有( )个。 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的最小公倍数

?101??10、集合X中的关系R,其矩阵是M??。 ?110? ,则关于R的论述中正确的是( )

??111??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上的二元运算,?x,y?Z,x?y?xy?x?y,则?的幺元和零元分别是( )。

A.不存在,0 B.0,1

C.1,不存在 D.不存在,不存在 13. 设f:N?N,N为自然数,且

?1?f(x)??x??2则f(0)和f({0})分别是( )。

若x为奇数若x为偶数

A.0,0 B.0,{0} C.{0},{0} D.{0},0

14. 下列命题公式中是矛盾式的有( )。

A.(p??p)??p B.?(q?p)?p C.(?p?q)?(q??p) D.(p?q)?r 15. 下列各Hasse图中,是格的有( )。

A. B.

C. D.

16. 下列命题公式中是永假式的有( )。

A.(p??p)??p B.?(q?p)?p C.(?p?q)?(?q?p) D.(p?q)?r

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. 设命题公式G??(P?Q),H?P?(Q??P),则G与H的关系是( ) 。 A.Q?H B.H?G C.H?G D.G?H

21.谓词公式?x(P(x)??yR(y))?Q(x)中量词?x的辖域是( )。 A ?x(P(x)??yR(y)) B. P(x) C.P(x)??yR(y) D.Q(x) 22.设个体域为整数集,下列公式中其值为1的是( )。

A.?x?y(x?y?0) B.?y?x(x?y?0) C.?x?y(x?y?0) D.??x?y(x?y?0)

23.设L(x):x是演员,J(x):x是老师,A(x,y):x佩服y. 那么命题“所有演员都佩服某些老师”符号化为( )。

A.?xL(x)?A(x,y) B.?x(L(x)??y(J(y)?A(x,y)) C.?x?y(L(x)?J(y)?A(x,y)) D.?x?y(L(x)?J(y)?A(x,y))

24.在谓词演算中,P(a)是?xP(x)的有效结论,根据是 ( )。 A.US规则 B.UG规则 C.ES规则 D.EG规则 25. 在图G=中,结点总度数与边数的关系是( )。

A.deg(vi)=2?E? B. deg(vi)=?E? C.

?deg(v)?2E D. ?deg(v)?E

v?Vv?V26. 设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. 仅有一个孤立结点的图称为( )。