2、,则S=T题号—-二三四总分统分人复核人得分C.S3S=SA.自反的B.对称的C.反对称的D.传递D.S-T=SC(-T)4、设R是集合A上的偏序关系，则R不一定是（）注：考试期间试卷不允许拆开木试卷共6页第1页)o5设R为实数集，定义R上4个二元运算，不满足结合律的是（A.fi(x,y)=x+yB.2(x,y)=x・yC.E(x,y)=xyD.£j(x,y)=max{x,y}6、设＜L,a,v＞是一个格，则它不满足（A.交换律B.结合律C.吸收律D.消去律7、设A二{1,2},则群vP（A）,c＞的单位元和零元是（A
3、.①与AB.A与①C.⑴与①D.{1}8、下列编码是前缀码的是（).C.(B・edcbaC・bdecaD.badce得分阅卷人A.abode二.填空题（每题3分，共24分）A.{1,11,101}B.{1,001,0011}C.{1,01,001,000}D.{0,00,000}9、下图中既是欧拉图乂是哈密顿图的是（D・心310、下图所示的二叉树中序遍历的结果是1、含3个命题变项的命题公式的主合取范式为Al。aA14aM6aM7,则它的主析取范式为o（表示成mvm的形势）2、＜Z4,㊉〉模4加群，则3是阶元，3㊉3二,3
4、的逆元是o3、设V=,其中”是普通加法。VxGZ,令(Pl(x)=x,02(X)=・X，03(X)=X+5,°4(x)=2x,其中有自同构.4、设=已知命题公式(―p—>q)—>(―i<77p),(1)构造真值表。(2)求主析取范式(要求通过等值演算推出)。R!=«1,2>,<1,3>,<2,3>},R2={<2,2>,<2,3>,<3,4>},求：(1)~R2(2)(3)求/?2。尺设〈A,R〉为一个偏序集，其中，A二{1,2,3,4,6,9,12,24},R是A上的整除关系。5珂是集合A二{1,2,3,4
5、,5,6}上的一个置换，则(231546丿把它表示成不相交的轮换的积是o4、已知n阶无向简单图G有m条边，则G的补图有条边。5、一个有向图是强连通的充分必要条件是o7、已知n阶无向图G中有m条边，各顶点的度数均为3。又已知3二m,贝I」m=.8、在下图屮从A点开始，用普里姆算法构造最小生成树，加入生成树的第三条边是()。得分阅卷人计算题(每题9分,共36分)（1）画R出的哈斯图；（2）求A的极大元和极小元；（3）求B={4,6}的上确界和下确界。4、画一棵带权为1,1,1,3,3,5,8的最优二叉树T,并计算它的权W（T
6、）o得分阅卷人四、证明题（共20分）1、(7分)前提：pT(qT7结论：2、(7分)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)gA且a+b二c+d}.(1)证明：R是A上的等价关系.(2)给岀R确定的对A的划分(分类).(6分)设vG,。〉是群,S={兀
8、兀&G且对于=y。兀},证明S是G的子群.《离散数学》试卷A参考答案一、选择题（每小题2分，共20分。请将答案填在下面的表格内）得分阅卷人二、填空题（每题3分，共2
9、4分）题号12345678910答案Cadbbdbcaa3、24、(123)(45)o4、心）十25、存在经过每个顶点的回路7、98^d,c或c,d三、计算题（每题9分，共36分）1、（1）构造真值表（4分）p,q(rpTq)(F7p)(-!〃tg)Tv/?)0001101100101111,1111（2）主析取范式（5分）:(「/?Tg)T(「qvp)o(pvg)T(「qvp)O-n(p7心7(「qvp)<=>(—1/2A—iQ)V(—iQVp)<=>(—ipA—iQ)V(pA—iQ)V(J?A^)<=>om0vm2v
10、n?3o工(0,2,3)2、(每小题3分)(1)R}-R2={〈1,2〉,〈1,3〉}(2)町={<2f1>,<3,1>,<3,2>}(1)求忌。&二{〈1,2>,〈1,3>,〈1,4>,〈2,4>}3、(每小题3分)(1)(4分)24（2）（3分）A的极大元9,24;极小元1;（3）（2分）B={4,6}的上确界1
