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

离散数学试卷（十四）89一、填空10%（每小题2分）1、设,,,A是由有限布尔格,A诱导的代数系统，S是布尔格,A，中所有原子的集合，则,,,A～。2、集合S={α，β，γ，δ}上的二元运算*为*αβγδαδαβγβαβγδγβγγγδαδγδ那么，代数系统S,*中的幺元是,α的逆元是。3、设I是整数集合，Z3是由模3的同余类组成的同余类集，在Z3上定义+3如下：]3mod)[(][][3jiji，则+3的运算表为；Z+,+3是否构成群。4、设G是n阶完全图，则G的边数m=。5、如果有一台计算机，它有一条加法指令，可计算四数的和。现有28个数需要计算和，它至少要执行次这个加法指令。二、选择20%（每小题2分）1、在有理数集Q上定义的二元运算*，Qyx,有xyyxyx*，则Q中满足（）。A、所有元素都有逆元；B、只有唯一逆元；C、1,xQx时有逆元1x；D、所有元素都无逆元。离散数学试卷（十四）902、设S={0，1}，*为普通乘法，则S,*是（）。A、半群，但不是独异点；B、只是独异点，但不是群；C、群；D、环，但不是群。3、图给出一个格L，则L是（）。A、分配格；B、有补格；C、布尔格；D、A,B,C都不对。3、有向图D=V,E，则41vv到长度为2的通路有（）条。A、0；B、1；C、2；D、3。4、在Peterson图中，至少填加（）条边才能构成Euler图。A、1；B、2；C、4；D、5。三、判断10%（每小题2分）1、在代数系统A,*中如果元素Aa的左逆元1ea存在，则它一定唯一且11eaa。（）2、设S,*是群G,*的子群，则G,*中幺元e是S,*中幺元。（）3、设},,3|{均为有理数babaxxA，+,·为普通加法和乘法，则代数系统A，+，·是域。（）4、设G=V,E是平面图，|V|=v,|E|=e，r为其面数，则v-e+r=2。（）离散数学试卷（十四）915、如果一个有向图D是欧拉图，则D是强连通图。（）四、证明46%1、设A,*，是半群，e是左幺元且AxAxˆ,，使得exx*ˆ，则A,*是群。（10分）2、循环群的任何非平凡子群也是循环群。（10分）3、设aH和bH是子群H在群G中的两个左陪集，证明：要末bHaH，要末bHaH。（8分）4、设A,+,·，是一个含幺环，|A|3，且对任意Aa，都有aaa，则A,+,·不可能是整环（这时称A，+，·是布尔环）。（8分）5、若图G不连通，则G的补图G是连通的。（10分）五、布尔表达式8%设)()()(),,(323221321xxxxxxxxxE是布尔代数,,},1,0{上的一个布尔表达式，试写出其的析取范式和合取范式。六、图的应用16%1、构造一个结点v与边数e奇偶性相反的欧拉图。（6分）2、假设英文字母，a，e，h，n，p，r，w，y出现的频率分别为12%，8%，15%，7%，6%，10%，5%，10%，求传输它们的最佳前缀码，并给出happynewyear的编码信息。（10分）一、填空10%（每小题2分）是；1、P(S),~,,；2、β，γ；3、4、)1(21nn；5、9+3[0][1][2][0][0][1][2][1][1][2][0][2][2][0][1]离散数学试卷（十四）92二、选择10%（每小题2分）题目12345答案CBDBD三、判断10%（每小题2分）题目12345答案NYYNY四、证明46%1、（10分）证明：（1）cbcabaAcba则若**,,,cbcebecaabaacaabaaacaba:**,*)*ˆ(*)*ˆ()*(*ˆ)*(*ˆˆ**:即使事实上(2)e是A，*之幺元。事实上：由于e是左幺元，现证e是右幺元。为右幺元即由使exexxxeeeexxexxxAexAx,*)1(*ˆ**)*ˆ()*(*ˆˆ,*,（3）AxAx1,则xxexxxxexxxexexxxxxxxAxˆˆ**ˆˆ***)*ˆ(**)ˆ*(:有逆元故有事实上由（2），（3）知：A,*为群。2、（10分）证明：设G,*是循环群,G=(a)，设S,*是G,*的子群。且GSeS},{，则存在最小正整数m，使得：Sam，对任意Sal，必有0,0,tmrrtml，故：Saaaaaatmltmltmlr)(**即：Saaatmrl)(*所以Sar但m是使Sam的最小正整数，且mr0，所以r=0即：tmlaa)(离散数学试卷（十四）93这说明S中任意元素是ma的乘幂。所以G,*是以ma为生成元的循环群。3、（8分）证明：对集合bHaH和，只有下列两种情况：（1）bHaH；（2）bHaH对于bHaH，则至少存在Hhh21,，使得21bhah，即有112hbha，这时任意aHah，有bHhhbhah112，故有bHaH同理可证：aHbH所以bHaH4、（8分）证明：反证法：如果A，+，·，是整环，且有三个以上元素，则存在aaaaaAa且1,,即有：aaaaaaaaa)1(1,但这与整环中无零因子条件矛盾。因此A，+，·不可能是整环。5、（10分）证明：因为G=V，E不连通，设其连通分支是)2()(,),(1kVGVGk，Vvu,，则有两种情况：（1）u,v，分别属于两个不同结点子集Vi，Vj，由于G(Vi),G(Vj)是两连通分支，故(u,v)在不G中，故u,v在G中连通。（2）u,v，属于同一个结点子集Vi，可在另一结点子集Vj中任取一点w，故(u,w),(w,v)均在G中，故邻接边(u,w)(w,v)组成的路连接结点u和v，即u,v在G中也是连通的。五、布尔表达式8%函数表为：1x2x3x),,(321xxxE000000110100离散数学试卷（十四）9401111000101111011111析取范式：)()()()()(),,(321321321321321321xxxxxxxxxxxxxxxxxxE合取范式：)()()(),,(321321321321xxxxxxxxxxxxE六、树的应用16%1、（6分）解：2、（10分）解：根据权数构造最优二叉树：传输它们的最佳前缀码如上图所示，happynewyear的编码信息为：10011010101010011101110100001111011000离散数学试卷（十四）95附：最优二叉树求解过程如下：