2011-2012离散数学A卷试题

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.中根遍历下图中结点的次序为 .

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={ }.

v2v1

v4

v3

三、计算证明题（共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分）

5

4 7 3

ev2

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

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

本文来源：https://www.bwwdw.com/article/0ei1.html