离散数学试卷及答案(20)

离散数学试卷（二十）130一、填空20%（每空2分）1．n个命题变元有个互不等价的极小项。2．按De-Morgan定理，ininAAAA121=。3．公式)(RQP的主析取范式为。4．设P(x)：x是大象，Q(x)：x是老鼠，R(x,y)：x比y重，则命题“大象比老鼠重”的符号化为。5．设},,{cbaX，X上的关系R的关系矩阵是111011101RM，则RRM。6．在具有n个结点的有向图中，任何基本通路的长度都不超过。7．任何图的点连通度)(G，边连通度)(G，最小点度)(G的关系为。8．结点数n（3n）的简单连通平面图的边数为m，则m与n的关系为。9．群G的非空子集H是G的子群当且仅当若x,yH则。10．代数系统,,A是环，若对运算“·”还满足则,,A是整环。二、选择10%（每小题2分）1．集合},2{NnxxAn对（）运算封闭。A、加法；B、减法；C、乘法；D、yx。2．设I为整数集合，m是任意正整数，mZ是由模m的同余类组成的同余类集合，在mZ上定义运算]mod)[(][][mjiji，则代数系统mmZ,最确切的性质是（）。A、封闭的代数系统；B、半群；C、独异点；D、群。离散数学试卷（二十）1313．设,N是偏序格，其中N是自然数集合，“≤”是普通的数间“小于等于”关系，则Nba,有ba（）。A、a；B、b；C、max(a，b)；D、min(a，b)。4．连通非平凡的无向图G有一条欧拉回路当且仅当图G()。A、只有一个奇度结点；B、只有两个奇度结点；C、只有三个奇度结点；D、没有奇度结点。5．设无向图EVG,是连通的且mEnV,若（）则G是树。A、M=N+1；B、n=m+1；C、63nm；D、63mn。三、12%逻辑推理：符号化命题“有些病人相信医生，但是没有病人相信法轮功，因此医生都不信法轮功”。用演绎法证明其结论。（P(x)：x是病人，D(x)：x是医生，Q(x)：x是法轮功练习者，L(x,y)：x相信y）四、序关系8%：设},,,,{54321xxxxxA，偏序集RA,的Hass图为求①A中最小元与最大元；②},,{543xxx的上界和上确界，下界和下确界。五、函数8%设ZYgYXf::和是映射且使得fg是满射，若g是入射，证明f是满射。六、图8%设G是连通简单平面图，结点数为n（3n），边数为m，面数为r，则42nr。七、树的应用12%设7个符号在通讯中使用的频率如下：a：35%，b：20%，c：15%，d：10%，e：10%，f：5%，g：5%编一个相应的二元前缀码，使通讯中出现的符号尽可能地减少，并画出对应的二叉树及求二叉树的过程。离散数学试卷（二十）132八、道路的基本性质10%设u，v是树T的两个不同的结点，从u至v的基本通路（结点不同的道路）是T中最长的基本道路，证明：d(u)=d(v)=1。九、子群12%若H是G的子群，Gba,，则bHaHHab1。一、填空20%1、n2；2、)(1iniA；3、7,5,4,3,2,1,0)()()()()()()(RQPRQPRQPRQPRQPRQPRQP；4、)),()()((yxRyQxPyx；5、111111111；6、n-1；7、)()()(GGG；8、63nm；9、Hyx1；10、含幺元，可交换，无零因子。二、选择10%题号12345答案CBCDB三、12%解：前提：)))(),(()((,)),()(()((yQyxLyxPxyxLyDyxPx结论：))()((yQyDy演绎推理：（1）)),()(()((yxLyDyxPxP（2）)),()(()(yeLyDyePES(1)离散数学试卷（二十）133（3）)))(),(()((yQyxLyxPxP（4）))(),(()(yQyeLyePUS(3)（5）)(ePT(2)I（6）))(),((yQyeLyT(4)(5)I（7）)(),(cQceLUS(6)（8）)),()((yeLyDyT(2)I（9）),()(ceLcDUS(8)（10）)()(cQcDT(9)(7)I（11）))()((yQyDyUG(10)四、解：①A中最大元为1x，最小元不存在；②},,{543xxx上界31,xx，上确界1x；下界无，下确界无。五、解：证：Yy，因g是映射，故必存在Zz使zyg)(，由于zxfg)(即)())((ygzxfg，因g是单射，所以yxf)(说明Yy，必有Xx使得yxf)(，故)(xf是满射。六、解：证：因为G是结点数3n的简单连通平面图，所以63nm，又由于2m且连通简单平面图的每个面至少有3条边围成，于是)63(223nmr，所以42nr。七、解：用100乘各频率得权数：w1=35，w2=20，w3=15，w4=10，w5=10，w6=5，w7=5将其由小到大排列用Huffman算法可求得最优树。离散数学试卷（二十）1345510101520351010101520352010152035202520354025354060100最优二叉树为编码树为：前缀码：a：11；b：01；c：101；d：100；e：001；f：0000；g：0001八、解：设l为T中最长的基本道路且以u为起点，v为终点，即vvvuvlk21如果1)(ud，则u的邻接点除了1v之外还有一点，不妨设为1u，而1u不在l上，否则T中存在回路uuvuv121即与T为树矛盾。于是得到一条vvvuvulk211是比l更长的基本道路，这与l是最长的道路矛盾，故1)(ud。同理可证1)(vd。九、证：uv1vkvuv1u1vkv离散数学试卷（二十）135因为HbaabHab1111）（所以，又aHbbaabaab)()(11bHaabbabba)()(11bHhhbhhbhaxaHx)()(111bHaH同理可证aHbH所以bHaH故aHbHaH若bHaH设bHaHx则Hhh21,使21hbhax可得：Hhhab1121。