2011-2012学年第一学期 《离散数学》期末考试试卷A

题目 分数 一 二 三 四 五 六 七

一、选择题（共6题，每题3分，共18分）

1.设P：天下大雨,Q：他在室内运动,命题“除非天下大雨，否则他不在室内运动”可符合化为（ ） A.?P∧Q B.?P→Q C.?P→?Q D.P→?Q

2.谓词公式?x(P(x)∨?yR(y))→Q(x)中变元x是（ ） A.自由变元 B.约束变元

C.既不是自由变元也不是约束变元 D.既是自由变元也是约束变元 3.下列命题中不正确的是（ ） A.x∈{x}-{{x}} B.{x}?{x}-{{x}} C.A={x}∪x,则x∈A且x?A D.A-B=??A=B

4.设集合A?{?,{a}}，则下面（ ）是A的幂集： A {?,{a},{{a}}} B {?,{?},{a},{?,{a}}} C {{?},{a},{?,{a}}} D {?,{?},{a}}}

5.设集合A={1，2，3}，下列关系R中不是等价关系的是（ ） A.R={<1,1>,<2,2>,<3,3>}

B.R={<1,1>,<2,2>,<3,3>,<3,2>,<2,3>} C.R={<1,1>,<2,2>,<3,3>,<1,2>}

D.R={<1,1>,<2,2>,<3,3>,<1,2>,<2,1>,<1,3>,<3,1>,<2,3>,<3,2>} 6.关于下列四个无向图的命题，正确的是（ ）

(a) (b)

(c)

(d)

A （a）是欧拉图，（b）是哈密顿图 B （a）是欧拉图，（c）是哈密顿图 C （b）是欧拉图，（d）是哈密顿图 D （c）是欧拉图，（d）是哈密顿图 二、填空题（共8题，每题3分,共24分）

1.已知A?3,P(B)?64,P(A?B)?256，则B? ， A?B? ，P(A?B)? .

2. 命题公式A?p?(q?r),B?(p??q)?r，它们关系是 A B （填写“?,?,?”）. 3 .判别命题公式的类型：?(p?q)?q是 公式.

4.中根遍历下图中结点的次序为 .

A B D E F G I K C H J 5.设f∶R→ R,f(x)=x+3,g∶R→R,g(x)=2x+1,则复合函数(f?g)(x)?_________,

(g?f)(x)?______。

6.一棵树有2个2度结点，1个3度结点，3个4度结点，其他为树叶结点，则它 有 个结点， 条边， 片树叶.

7.设有连通平面图有12个结点，22条边，则有 个面. 8.设有二部图如右图，则其互补结点子集分别为 V1={ }, V2={ }.

v2v1v8v7v4 v5v6v3三、计算证明题（共4小题，前3题每题6分，第4小题7分，共25分） 1、设A,B为任意集合，证明：(A-B)-C = A-(B∪C). 2、用等值演算算法证明等值式 (p∧q)∨(p∧?q)?p

?1，2?，求公式： 3、设P?x,y?为x整除y，Q?x?为x?2，个体域为??x???y??P?x,y??Q?x??的真值。

1,2,4,8,12,24,?上的整除关系4、设A??R?a1,a2a1,a2?A,a1整除a2??，R是否为A上

的偏序关系？若是，则：（1）画出R的哈斯图；（3分）（2）求它的最小元，最大元。（4分）

四 有向图G如右图所示。

（1）求G的邻接矩阵A； （2分） （2）G中v1到v4长度为4的通路路有几条？ （3分） （3）G中v1到自身长度为3的回路有几条？ （3分） （4）G是否强连通图？ （2分） 五、求下图的最小生成树及权。（6分）

e1 v1 e4 ee2 6 e5

v4 e7 v3

e3 v2

B 2 A 3 6 F 7

E 9 D 4 4 C 5 8 10

六、求叶的权重分别为3,5,6,7,8,10的最优二元树，并求其权重。（7分） 七、符号化下面的命题，并证明其推理是正确的。（10分）

每个运动员都是强壮的，每一个既强壮又聪明的人都将在事业中获得成功。张三是运动员，并且是聪明的。因此张三一定能在事业中获得成功。（个体域是人的集合）