1、注：考试期间试卷不允许拆开 本试卷共 页 第 0 页第 1 学期离散数学试卷 A（试卷共 6 页，答题时间 120 分钟）题号 一 二 三 四 总分 统分人 复核人得分一、选择题（每小题 2 分，共 20 分。请将答案填在下面的表格内）1、从集合分类的角度看,命题公式可分为( )A.永真式、矛盾式 B. 永真式、可满足式、矛盾式 C. 可满足式、矛盾式 D. 永真式、可满足式 2、设 B 不含有 x， 等值于 ( )(BAA. B. C. D.)(xBxA)( )(BxA3、设 S,T,M 是集合，下列结论正确的是（ ）A如果 ST=SM，则 T=M B如果 S-T=，则 S=TC D)(TS
2、4、设 R 是集合 A 上的偏序关系，则 R 不一定是( )A.自反的 B. 对称的 C. 反对称的 D. 传递的5 设 R 为实数集，定义 R 上 4 个二元运算，不满足结合律的是（ ） 。A. f1(x,y)= x+y B. f2(x,y)=x-y C. f3(x,y)=xy D. f4(x,y)=maxx,y 得分 阅卷人题号 1 2 3 4 5 6 7 8 9 10答案注：考试期间试卷不允许拆开 本试卷共 6 页 第 1 页6、设是一个格，则它不满足( ),A.交换律 B. 结合律 C. 吸收律 D. 消去律7、设 A=1,2,则群 的单位元和零元是( ),APA. 与 A B. A
3、与 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 9K10K3,2K3,K10、下图所示的二叉树中序遍历的结果是（ ） abcdeAabcde Bedcba Cbdeca Dbadce二、填空题（每题 3 分，共 24 分）1、含 3 个命题变项的命题公式的主合取范式为 ,76430MM则它的主析取范式为 。( )的 形 势表 示 成 m2、 ， 模 4 加群， 则 3 是 阶元，3 3= ，3 的逆元是 。 4Z3、设 V
4、=,其中“ +”是普通加法。 ，令 1(x)=x, 2(x)=-x, 3(x)Zx=x+5, 4(x)=2x，其中有 个自同构.4、设 是集合 A=1，2，3，4,5,6上的一个置换，则645132把它表示成不相交的轮换的积是 。得分 阅卷人注：考试期间试卷不允许拆开 本试卷共 6 页 第 2 页4、已知 n 阶无向简单图 G 有 m 条边，则 G 的补图有 条边。5、一个有向图是强连通的充分必要条件是 。7、已知 n 阶无向图 G 中有 m 条边，各顶点的度数均为 3。又已知 2n-3=m，则 m= .8、在下图中从 A 点开始，用普里姆算法构造最小生成树，加入生成树的第三条边是 （ ） 。
5、 BCDE1245678三、计算题（每题 9 分，共 36 分）1、已知命题公式 ，)()(pqp(1) 构造真值表。 (2) 求主析取范式(要求通过等值演算推出)。2、R 1=, R2=,求：(1) （） () 求 21 12R、设为一个偏序集，其中，A=1，2，3，4，6，9，12，24,R 是 A 上的整除关系。（1）画 R 出的哈斯图； （2）求 A 的极大元和极小元； （3）求 B=4,6的上确界和下确界。、画一棵带权为 1，1，1，3，3，5，8 的最优二叉树 T，并计算它的权 W（T） 。得分 阅卷人注：考试期间试卷不允许拆开 本试卷共 6 页 第 3 页四、证明题（共 20 分
6、）1、 （7 分）前提： rpqsp,)(结论: sr2、 （7 分）A=(0,0),(0,1),(1,0),(1,3),(2,2),(2,3),(3,1),R=| (a,b),(c,d) A 且 a+b=c+d .(1)证明：R 是 A 上的等价关系(2)给出 R 确定的对 A 的划分(分类).3、 （6 分）设 是群, ,G,|xyGyxS且 对 于证明 S 是 G 的子群.离散数学试卷 A参考答案一、选择题（每小题 2 分，共 20 分。请将答案填在下面的表格内）二、填空题（每题 3 分，共 24 分）1、 2、4,2,152m3、2 4、 （123） （45） 。4、 5、存在经过每个
7、顶点的回路 n)(7、 9 . 8、 d,c 或 c，d 得分 阅卷人题号 1 2 3 4 5 6 7 8 9 10答案 c a d b b d b c a a得分 阅卷人注：考试期间试卷不允许拆开 本试卷共 6 页 第 4 页三、计算题（每题 9 分，共 36 分）1、(1)构造真值表(4 分)p,q (qp)(pq)()(pqp0 00 11 01,1011110111011(2) 主析取范式(5 分): )()()()()()( pqpqpqp )3,20(320m2、(每小题 3 分)(1) = , () =, 21R1R(1) 求 =, 1、 (每小题 3 分)(1)（4 分） 12
8、3469（2） （3 分）A 的极大元 9,24; 极小元 1;（3） （2 分）B=4,6的上确界 12 下确界 2。注：考试期间试卷不允许拆开 本试卷共 6 页 第 5 页、画图(7 分) W（T）=55(2 分) 3158264四、证明题（共 20 分）1、 （7 分）证明：附加前提证明法.1 分 r p . 3 分 )(sq . 5 分 . 7 分s2、证明：（1） （5 分）自反性。对于 自反性成立),(,),( baRbaAba对称性。对于 dcdcdc )(如 果对称性成立,),(Rdc所 以注：考试期间试卷不允许拆开 本试卷共 6 页 第 6 页传递性。 ),(,),(,),(),( yxRdcbaAyxdcba如 果bayx从 而所 以 传递性成立（2）A/R=(0,0),(0,1),(1,0),(1,3),(2,2),(3,1),(2,3) （2 分）3、证明：（每步各 2 分）（1）S 不空： 是群，设 是 的单位元，那么,Ge,G，所以 S 不空。yey,都 有（2） 2121 , yxyxSx 都 有那 么 对 于)()()()()( 1212121yxy那 么所以, ,21x（3） 11, yxxyxSyS都 有那 么 对 于xy1即所以, S 是 G 的子群.
