离散数学试题库

模拟试题(一)

一、 单项选择题

在下列每小题的四个备选答案中选出一个正确的答案，并将其字母标号填入题目的括号内。

1．给定命题公式如下：(?p?q)?(?q?p) 成真赋值的个数为（ ）。

A．1 Ｂ．2 Ｃ．3 Ｄ．4

2. 设个体域D={a,b}，公式?xP?x???xS?x?在A中消去量词后应为（ ） A．P?x??S?x? B．P?a??P?b???S(a)?S(b)? C．P?a??S?b? D．P?a??P?b??S(a)?S(b) 3．若R和S是集合A上的两个关系，则下述结论正确的是（ ）。 A．若R和S是自反的，则R?S也是自反的 B．若R和S是对称的，则R?S也是对称的

C．若R和S是反对称的，则R?S也是反对成的 D．若R和S是传递的，则R?S也是传递的

4．设全集U={1,2,3,...,20},A,B,C是其子集，其A?{x|x?4}，

。 B?{x|x2?6x?7?0},C?{x|x2?100}则~A?~B?~C?（ ）

A．{16,17,18,19,20} B．{1,2,3,4,5} C．{10,11,12,13,14,15} D．{1,2,3,4,5,6,7} 5．下面偏序集构成有界格的是（ ）。

A． Ｂ． Ｃ．<{2,3,4,6,12},|> Ｄ． 6．全体自然数所组成的集合的最小元为（ ）。

A．负数 Ｂ．最小的正数 Ｃ．0 Ｄ．1 7．对任何a?A，形成的A上的等价关系R的等价类[a]R为（ ）。

A．空集 Ｂ．非空集 Ｃ．空集也可以为非空集 Ｄ．{x}x?A} 8．设S=Q?Q，其中Q为有理数集合，定义S上的二元运算“*”，?,?S，有?a,b?*?x,y???ax,by?b?，则是（ ）。

A．可交换的 Ｂ．可结合的

Ｃ．既是可交换的，又是可结合的 Ｄ．不是可交换的，也不是可结合的

?1?09. 设有向图D=的邻接矩阵为A(D)???0??0200011010?0??，则D中v1到v3长度为4的通路有（ ）1??0?条。

A．4 Ｂ．6 Ｃ．8 Ｄ．9 10.下面那种描述的图不一定是树（ ）。

A．无回路的连通图 Ｂ．有n个顶点的n-1条边

Ｃ．每对顶点都有通路的图 Ｄ．连通但删去一条边则不连通的图 11. 一颗二叉树后序遍历的结果是bdeca，中序遍历的结果是badce，则 根结点的右子树有（ ）结点。

A．1 B．2 C．3 D．4 12.设函数f：N→N（N 为自然数集），f(n)=n+1，下面四个命题为真的是 ( )

A. f是单射 B. f是满射 C. f是双射的 D.f非单射非满射 13.设S={0,1},则S满足（ ）。

A. 在普通乘法下封闭，在普通加法下不封闭 B. 在普通加法和乘法下都封闭

C．在普通加法下封闭，在普通乘法下不封闭 D．在普通加法和乘法下都不封闭

1

14. 下图中（ ）是欧拉图。

A B C D

15. 设集合A={a，b，c，d，e}， 偏序关系R的哈斯图如左图所示， 则元素的关系不正确的是（ ）。

A．c?d B．a?e C．a?b D．d?e

ecabdg二、 填空题

f16.设无向图G有12条边，有6个3度顶点，其余顶点度数均小于3，则G种至少有 顶点。 17. 在彼得森图中至少添加 条边才能构成欧拉图。

18.由Huffman算法，带权1,3,4,5,6的最优二叉树的权W(T)= 。

19.设V=为代数系统，其中A={0,1,2,3,4}。?a,b?A,a*b=(ab)mod5。关于运算“*”的幺元是 。

20．设Z为整数集，?a,b?Z，有a?b=a+b-1，则a的逆元= 。

21．集合{a,b,c,d}上关系R的关系图如左所示，则R的传递 闭包（用集合表示）为 。

22.设R是由方程x+3y=12定义的正整数集N上的关系，即{?x,y?|x,y?N?x?3y?12}，则

R?{2,3,4,6}? ，{3}在R下的象是 。

23.若集合A的基数|A|=10，则其幂集|P(A)|= 。

三、计算题

24．判断正整数集合Z+和下面的二元运算是否构成代数系统。如果是，则说明这个运算是否满足交换律、结合律和幂等律，并求出单位元和零元。 (1)a*b=min(a,b) (2)a?b=(a/b)+(b/a)

25.用主析取范式判断?p?q??r与q??p?r?是否等值。 26.

设，为上关系，关系矩阵为

，

。 (3) 求

，

，

，

。

(1) 画出关系图。 (2) 求(4) 指出

具有的性质。(5)

是偏序关系吗？能否画出哈斯图？

2

27．求下图的最小生成树，写出过程，并计算权。

四、证明题

28．在命题逻辑中构造下面推理的证明。

前提：p?s，q?r，?r，p?q 结论：s

29．设无向图G是由k（k≥2）棵树组成的森林，已知G中有n个结点，m条边，证明m=n-k。

30．证明对于任意集合A,B,C，有(A-B)-C=(A-C)-(B-C)

五、应用题

31．75名儿童到公园游乐场，他们在那儿可以骑旋转木马，坐滑行铁道，乘宇宙飞船，已知其中20人这三种东西都乘过，其中55人至少乘过其中的两种。若每样乘坐一次的而费用是0.50元，公园游乐场总共收入70元，试确定有多少儿童没有乘过其中任何一种。

32．有四个村庄的地下各有一个防空洞甲、乙、丙、丁，相邻两个防空洞之间有地道相通，且每个防空洞各有一条地道与地面相通，如下图所示（图中表示地道）。问能否从某一个防空洞开始，每个地道走一次且仅走一次后回到该防空洞。（要求有一定的分析过程）

模拟试题(二)

三、单项选择题

在下列每小题的四个备选答案中选出一个正确的答案，并将其字母标号填入题目的括号内。

1．下列是两个命题变元p，q的小项是（ ）

A．p??p?q B．?p?q C．?p?q D．?p?p?q

2．令p：今天下雪了，q：路滑，则命题“虽然今天下雪了，但是路不滑”可符号化为（ ） A．p??q B．p??q C．p?q D．p??q 3．下列语句中是命题的只有（ ）

A．1+1=10 B．x+y=10 C．sinx+siny<0 D．x mod 3=2 4．下列等值式不正确的是（ ）

A．?(?x)A(x)?(?x)?A(x) B．(?x)(B→A(x))?B→(?x)A(x)

3

C．(?x)(A(x)?B(x))?(?x)A(x)?(?x)B(x)

D．( ?x)( ?y)(A(x)→B(y))?( ?x)A(x)→( ?y)B(y)

5．谓词公式?xP(x,y)??t(Q(t,z)→?x?yR(x,y,t))中量词?t的辖域是（ ） A．?t(Q(t,z)→?x?yR(x,y,t)) B．Q(t,z)→?x?yR(x,y,t) C．?x?yR(x,y,t) D．Q(t,z)

6．设R为实数集，函数f：R→R，f(x)=2x，则f是（ ）

A．满射函数 B．入射函数 C．双射函数 D．非入射非满射

7．设A={a,b,c,d}，A上的等价关系R={,,,}∪IA，则对应于R的A的划分是（ ）

A．{{a},{b,c},{d}} B．{{a,b},{c},{d}} C．{{a},{b},{c},{d}} D．{{a,b},{c,d}}

8．设A={?}，B=P(P(A))，以下正确的式子是（ ）

A．{?,{?}}∈B B．{{?,?}}∈B C …… 此处隐藏：3625字，全部文档内容请下载后查看。喜欢就下载吧 ……