《2022年《离散数学》试卷A .pdf》由会员分享，可在线阅读，更多相关《2022年《离散数学》试卷A .pdf（9页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第 1 学期离散数学试卷 A （试卷共 6 页，答题时间120 分钟）题号一二三四总分统分人复核人得分一、选择题（每小题 2分，共 20 分。请将答案填在下面的表格内）1、从集合分类的角度看 , 命题公式可分为 ( ) A. 永真式、矛盾式B. 永真式、可满足式、矛盾式C. 可满足式、矛盾式D. 永真式、可满足式2、设 B不含有 x，)(BxAx等值于( ) A.BxxA)(B.)(BxAxC.BxxA)(D.)(BxAx3、设 S,T,M 是集合，下列结论正确的是（）A如果 ST=SM，则 T=M B如果 S-T=，则 S=TCSSS D)( TSTS4、设 R是集合 A上的偏序关系，则R不
2、一定是 ( ) A.自反的B. 对称的C. 反对称的D. 传递的得分阅卷人题号1 2 3 4 5 6 7 8 9 10 答案精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 1 页，共 9 页 - - - - - - - - - - 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 6、设是一个格，则它不满足 ( ) A.交换律B. 结合律C. 吸收律D. 消去律
3、7、设 A=1,2, 则群),(AP的单位元和零元是 ( ) A. 与 A B. A 与C. 1 与D. 1与 A 8、下列编码是前缀码的是( ). A.1,11,101 B.1,001,0011 C. 1,01,001,000 D.0,00,000 9、下图中既是欧拉图又是哈密顿图的是（） A9K B10K C3,2K D3, 3K10、下图所示的二叉树中序遍历的结果是（）abcdeAabcde Bedcba Cbdeca Dbadce 二、填空题（每题3 分，共 24 分）1、含 3 个命题变项的命题公式的主合取范式为76430MMMMM, 则它的主析取范式为。(的形势表示成mm) 2、
4、4Z ，模 4 加群， 则 3 是阶元， 33= ，3 的逆元是。得分阅卷人精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 2 页，共 9 页 - - - - - - - - - - 3、 设 V=,其中 “+” 是普通加法。Zx， 令1(x)=x, 2(x)=-x,3(x)=x+5, 4(x)=2x，其中有个自同构 . 4、设645132654321是集合 A=1，2，3，4,5,6 上的一个置换，则把它表示成不相交的轮换的积是。4、已知 n 阶无向简单图 G 有 m 条边，则 G 的补图有条边。5、一
5、个有向图是 强连通 的充分必要条件是。7、已知 n 阶无向图 G中有 m条边，各顶点的度数均为3。又已知 2n-3=m，则 m= . 8、在下图中从 A 点开始，用普里姆算法构造最小生成树，加入生成树的第三条边是 （） 。ABCDE12345678三、计算题（每题9 分，共 36 分）1、已知命题公式)()(pqqp，(1)构造真值表。 (2) 求主析取范式 ( 要求通过等值演算推出 ) 。2、R1=, R2=,求： (1)21RR（）11R ( ) 求12RR、设 为一个偏序集，其中，A=1，2，3，4，6，9，12，24,R 是 A上的整除关系。（1）画 R出的哈斯图；得分阅卷人精品资料
6、- - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 3 页，共 9 页 - - - - - - - - - - （2）求 A的极大元和极小元；（3）求 B=4,6 的上确界和下确界。、画一棵带权为1，1，1，3，3，5，8 的最优二叉树T，并计算它的权W （T） 。四、证明题（共 20 分）1、 （7 分）前提：rpqsqp,),(结论: 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) 证明：
7、R是 A上的等价关系 (2)给出 R确定的对 A的划分 ( 分类).3、 （6 分）设,G是群, ,|xyyxGyGxxS且对于, 证明 S是 G的子群 . 离散数学试卷 A 参考答案一、选择题（每小题 2 分，共 20 分。请将答案填在下面的表格内）二、填空题（每题3 分，共 24 分）1、521mmm2、4,2,1 得分阅卷人题号1 2 3 4 5 6 7 8 9 10 答案c a d b b d b c a a 得分阅卷人精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 4 页，共 9 页 - - -
8、 - - - - - - - 3、2 4、（123） （45） 。4、nnn2) 1(5、存在经过每个顶点的回路7、9 . 8、 d,c 或 c ，d 三、计算题（每题9 分，共 36 分）1、(1) 构造真值表 (4 分) p,q )(qp)(pq)()(pqqp0 0 0 1 1 0 1,1 0 1 1 1 1 0 1 1 1 0 1 1 (2) 主析取范式 (5 分): )()()()()()(pqqppqqppqqp)()()()()(qpqpqppqqp)3 ,2 ,0(320mmm2、(每小题 3分) (1)21RR= , ( )11R =, (1) 求12RR=,、 ( 每小题
9、3 分) (1) （4 分）精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 5 页，共 9 页 - - - - - - - - - - 1234691224（2） （3 分）A的极大元 9,24 ; 极小元 1; （3） （2 分）B=4,6 的上确界 12 下确界 2。、画图 (7 分) W（T）=55(2 分) 331115823861422四、证明题（共 20 分）1、 （7 分）证明：附加前提证明法.1 分r rpp . 3分)(sqp精品资料 - - - 欢迎下载 - - - - - - - -
10、 - - - 欢迎下载 名师归纳 - - - - - - - - - -第 6 页，共 9 页 - - - - - - - - - - sq . 5分qs . 7分2、证明： （1） （5 分）自反性。对于),(),(,),(baRbababaAba自反性成立对称性。对于dcbadcRbaAdcba),(),(,),(),(如果),(),(baRdcbadc所以对称性成立传递性。),(),(),(),(,),(),(),(yxRdcdcRbaAyxdcba如果),(),(,yxRbayxbayxdcdcba从而所以传递性成立（2）A/R=(0,0),(0,1),(1,0),(1,3),(2,2
11、),(3,1),(2,3) （2 分）3、证明： （每步各 2 分）（1）S不空：,G是群，设 e是,G的单位元，那么SeyeeyGy,都有，所以 S 不空。（2）221121,yxyxyxyxGySxx都有那么对于)()()()()()(212121212121xxyxyxxyxyxxyxxyxx那么所以,21Sxx（3）1111,yxxxxyxxyxxySySx都有那么对于yxyx11即所以,Sx1S是 G的子群 .精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 7 页，共 9 页 - - - - - - - - - - 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 8 页，共 9 页 - - - - - - - - - - 文档编码：KDHSIBDSUFVBSUDHSIDHSIBF-SDSD587FCDCVDCJUH 欢迎下载 精美文档欢迎下载 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 9 页，共 9 页 - - - - - - - - - -