资源描述：
《《离散数学》试题（卷）a&答案解析》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。
1、第1学期《离散数学》试卷A（试卷共6页，答题时间120分钟）题号一二三四总分统分人复核人得分得分阅卷人一、选择题（每小题2分，共20分。请将答案填在下面的表格内）题号12345678910答案1、从集合分类的角度看,命题公式可分为( ) A.永真式、矛盾式 B.永真式、可满足式、矛盾式 C.可满足式、矛盾式 D.永真式、可满足式 2、设B不含有x，等值于 ( )A. B.C. D.3、设S,T,M是集合，下列结论正确的是（ ）A．如果S∪T=S∪M，则T=MB．如果S-
2、T=Φ，则S=TC．D．4、设R是集合A上的偏序关系，则R不一定是( )A.自反的 B.对称的 C.反对称的 D.传递的5设R为实数集，定义R上4个二元运算，不满足结合律的是（）。A.f1(x,y)=x+yB.f2(x,y)=x-yC.f3(x,y)=xy D.f4(x,y)=max{x,y}6、设是一个格，则它不满足( )A.交换律 B.结合律 C.吸收律 D.消去律7、设A={1,2},则群的单位元和零元是( )A.与A B. A 与 C.{1}与
3、 D.{1}与A 8、下列编码是前缀码的是( ).A.{1,11,101} B.{1,001,0011}C. {1,01,001,000} D.{0,00,000}9、下图中既是欧拉图又是哈密顿图的是（ ）A．B．C．D．10、下图所示的二叉树中序遍历的结果是（ ）A．abcdeB．edcbaC．bdecaD．badce得分阅卷人二、填空题（每题3分，共24分）1、含3个命题变项的命题公式的主合取范式为,则它的主析取范式为。()2、〈，〉模4加群，则3是阶元，33=，3的逆元是。3、设V=,
4、其中“+”是普通加法。，令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点开始，用普里姆算法构造最小生成树，加入生成树的第三条边是（）。得分阅卷人三、计算题（每题9分，共36分）1、已知命题公式，(1)构造真值表。
5、(2)求主析取范式(要求通过等值演算推出)。2、R1={<1,2>,<1,3>,<2,3>},R2={<2,2>,<2,3>,<3,4>},求：(1) （２） (３)求３、设为一个偏序集，其中，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）。得分阅卷人四、证明题（共20分）1、（7分）前提：结论:2、（7
6、分）A={(0,0),(0,1),(1,0),(1,3),(2,2),(2,3),(3,1)},R={<(a,b),(c,d)>
7、(a,b),(c,d)A且a+b=c+d}.(1)证明：R是A上的等价关系．(2)给出R确定的对A的划分(分类).3、（6分）设是群,,证明S是G的子群.《离散数学》试卷A参考答案一、选择题（每小题2分，共20分。请将答案填在下面的表格内）题号12345678910答案cadbbdbcaa得分阅卷人二、填空题（每题3分，共24分）1、2、4,2,13、24、（123）（45）。4、5、存在经
8、过每个顶点的回路7、9.8、d,c或c，d三、计算题（每题9分，共36分）1、(1)构造真值表(4分)p,q0001101,1011110111011(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分）
9、1、（7分）证明：附加前提证明法..1分①r②③①②…………..3分④⑤③④…………..5分⑥⑦⑤⑥………….7分2、证明：（1）（5分）自反性。对于自反性成立对称性。对于对称性成立传递性。传递性成立（2）A/R={{(0,0)},{(0,1),(1,0)},{(1,3),(2,2),(3,1)},{(2,3)}}（2分）3、证明
