2021-2021离散数学A卷试题

1、2021-2021离散数学a卷试题 2021-2021学年第一学期 离散数学期末考试试卷a 一、选择题（共6题，每题3分，共18分） 1.设p：天下大雨,q：他在室内运动,命题“除非天下大雨，否则他不在室内运动”可符合化为（ ） a. pq b. pq c. p q d.p q 2.谓词公式 x(p(x) yr(y)q(x)中变元x是（ ） a.自由变元 b.约束变元 c.既不是自由变元也不是约束变元 d.既是自由变元也是约束变元 3.下列命题中不正确的是（ ） a.xx-x b.x x-x c.a=xx,则xa且x a d.a-b= a=b 4.设集合a ,a，则下面（ ）是 a的幂集： a

2、 ,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

3、 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.设fr r,f(x)=x+3,grr,g(x)=2x+1,则复合函数(f g)(x) _, (g f)(x) _。 6. 一棵树有2个2度结点，1个3度结点，3个4度结点，其他为树叶结点，则它 有 个结点， 条边， 片树叶. 7.设有连通平面图有12个结点，22条边，则有 个面. 8.设有二部图如右图，则其互补结点子集分别为 v1= , v2= . v2v

4、1 v4 v3 三、计算证明题（共4小题，前3题每题6分，第4小题7分，共25分） 1、设a,b为任意集合，证明：(a-b)-c = a-(bc). 2、用等值演算算法证明等值式 (pq)(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分） 每个运动员都是强壮