离散数学试卷A答案

1、 第1学期离散数学试卷 A（试卷共6页，答题时间120分钟）题号一二三四总分统分人复核人得分得分阅卷人一、选择题（每小题 2分，共 20 分。请将答案填在下面的表格内）题号12345 678 910答案1、从集合分类的角度看,命题公式可分为(   )  A.永真式、矛盾式          B. 永真式、可满足式、矛盾式 C. 可满足式、矛盾式        D. 永真式、可满足式 2、

2、设B不含有x，等值于 (   )A.   B. C.   D.3、设S,T,M是集合，下列结论正确的是（     ）A如果ST=SM，则T=M B如果S-T=，则S=TC D4、设R是集合A上的偏序关系，则R不一定是(   )A.自反的     B. 对称的   C. 反对称的      D. 传递的5 设R为实数集，定义R上4个二元运算

3、，不满足结合律的是（ ）。A. f1(x,y)= x+y B. f2(x,y)=x-y C. f3(x,y)=xy  D. f4(x,y)=maxx,y 6、设<L,>是一个格，则它不满足(   )A.交换律     B. 结合律   C. 吸收律      D. 消去律7、设A=1,2,则群的单位元和零元是(   )A. 与A      B.&

4、#160;  A 与  C. 1与    D. 1与A 8、下列编码是前缀码的是(    ).A.1,11,101  B.1,001,0011 C. 1,01,001,000  D.0,00,0009、下图中既是欧拉图又是哈密顿图的是（     ） A B C D 10、下图所示的二叉树中序遍历的结果是（     ）Aabcde Bedcba Cbdeca Dbadce得分阅卷

5、人二、填空题（每题3分，共24分）1、含3个命题变项的命题公式的主合取范式为,则它的主析取范式为 。()2、，模4加群， 则3是 阶元，33= ，3的逆元是 。 3、设V=<Z,+>,其中“+”是普通加法。，令1(x)=x, 2(x)=-x,3(x)=x+5, 4(x)=2x，其中有 个自同构.4、设是集合A=1，2，3，4,5,6上的一个置换，则把它表示成不相交的轮换的积是 。4、已知n阶无向简单图G有m条边，则G的补图有 条边。5、一个有向图是强连通的充分必要条件是 。7、已知n阶无向图G中有m条边，各顶点的度数均为3。又已知2n-3=m，则m= .8、在下图中从A点开始，用普

6、里姆算法构造最小生成树，加入生成树的第三条边是 （ ）。得分阅卷人三、计算题（每题9分，共 36分）1、已知命题公式，(1) 构造真值表。 (2) 求主析取范式(要求通过等值演算推出)。2、R1=<1,2>,<1,3>,<2,3>, R2=<2,2>,<2,3>,<3,4>,求： (1) （） () 求 、设<A,R>为一个偏序集，其中，A=1，2，3，4，6，9，12，24,R是A上的整除关系。（1）画R出的哈斯图； （2）求A的极大元和极小元； （3）求B=4,6的上确界和下确界。、画一棵带权为1，1，1，

7、3，3，5，8的最优二叉树T，并计算它的权W（T）。得分阅卷人四、证明题（共 20分）1、（7分）前提： 结论: 2、（7分）A=(0,0),(0,1),(1,0),(1,3),(2,2),(2,3),(3,1),R=<(a,b),(c,d)>| (a,b),(c,d)A且a+b=c+d .(1)证明：R是A上的等价关系 (2)给出R确定的对A的划分(分类).3、（6分）设是群, ,证明S是G的子群.离散数学试卷 A参考答案一、选择题（每小题 2分，共 20 分。请将答案填在下面的表格内）题号12345 678 910答案cadbbdbcaa 得分阅卷人二、填空题（每题3分，共24

8、分）1、 2、4,2,13、2 4、（123）（45）。4、 5、存在经过每个顶点的回路 7、 9 . 8、 d,c 或 c，d 三、计算题（每题9分，共 36分）1、(1)构造真值表(4分)p,q 0 0 0 1 1 0 1,101111011 1011(2) 主析取范式(5分): 2、(每小题3分) (1)= <1,2>,<1,3>() =<2,1>,<3,1>,<3,2> (1) 求=<1,2>,<1,3>,<1,4>,<2,4> 、 (每小题3分)(1)（4分）（2）（3分）A的极大元9,24; 极小元1;（3）（2分）B=4,6的上确界12 下确界2。、画图(7分) W（T）=55(2分) 四、证明题（共 20分）1、（7分）证明：附加前提证明法.1分 r . 3分 . 5分 . 7分2、证明：（1）（5分）自反性。对于 自反性成立对称