试卷十四试题与答案

1、试卷十四试题与答案填空10%每题2分1、设A,a,-是由有限布尔格A,E诱导的代数系统,S是布尔格中所有原子的集合,那么AW,八,一A2、集合S=a,3,丫,8上的二元运算*为*a3丫8a8a3丫3a3丫8丫3丫丫丫8a8Y8那么,代数系统S,*中的幺元是,a的逆元是.3、设I是整数集合,Z3是由模3的同余类组成的同余类集,在Z3上定义+3如下:r3j=i+jmod3,那么+3的运算表为；Z+,+3是否构成群°4、设G是n阶完全图,那么G的边数m=.5、如果有一台计算机,它有一条加法指令,可计算四数的和.现有28个数需要计算和,它至少要执行次这个加法指令.选择20%每题2分1、在有理

2、数集Q上定义的二元运算*,Vx,yWQ有x*y=x+y-xy,那么Q中满足.A、所有元素都有逆元；B、只有唯一逆元；C、VxWQ,x#1时有逆元x,；D、所有元素都无逆元.2、设S=0,1,*为普通乘法,那么S,*是A、半群,但不是独异点；B、只是独异点,但不是群;C、群；D、环,但不是群.3、图给出一个格L,那么L是3、A、分配格；B、有向图D=<V,E>有补格；C、布尔格；D、A,B,C都不对.,那么vi到v4长度为2的通路有条.4、图.至少填加条边才能构成EulerA、1;B、2;C、4;D、5.三、判断10%每题2分1、在代数系统A,*中如果元素aA的左逆元ae存在,J_1

3、那么它一定唯一且a=黑.2、设S,*是群G,*的子群,那么G,*中幺元3是$,*中幺元.3、设A=x|x=a+b,3,a,b均为有理数,+,为普通加法和乘法,那么代数系统A,+,是域.4、设G=V,E是平面图,|V|=v,|E|=e,r为其面数,那么v-e+r=2.5、如果一个有向图D是欧拉图,那么D是强连通图.四、证实46%1、 设<人,*>,是半群,e是左幺元且VxwA,三欠三A,使得X*x=e,那么<人,*>是群.10分2、 循环群的任何非平凡子群也是循环群.10分3、 设aH和bH是子群H在群G中的两个左陪集,证实：要末aHcbH=9,要末aH=bH.8分4、

4、设四,+,>,是一个含幺环,|A|>3,且对任意VawA,都有a,a=a,那么小,+,>不可能是整环这时称<A,+,>是布尔环.8分5、 假设图G不连通,那么G的补图G是连通的.10分五、布尔表达式8%设EX1,X2,X3=X1AX2VX2AX3vx2AX3是布尔代数<01,V,A,>上的一个布尔表达式,试写出其的析取范式和合取范式.六、图的应用16%1、构造一个结点v与边数e奇偶性相反的欧拉图.6分2、假设英文字母,a,e,h,n,p,r,w,y出现的频率分别为12%,8%,15%,7%,6%,10%,5%,10%,求传输它们的最正确前缀码,并给出h

5、appynewyear的编码信息.10分+30121、 <P(S),1-n(n-1)4、2;001211202201一、填空10%每题2分答案5',>；2、3,丫；3、是；5、9选才i10%(每题2分)题目12345答案CBDBD三、判断10%(每题2分)题目12345答案NYYNY四、证实46%1、(10分)证实：Va,b,cA,假设a*b=a*c贝Jb=c事实上：:a*b=a*c/.三a?使a?*(a*b)=a?*(a*c)(a?*a)*b=(a?*a)*c,.e*b=e*c即：b=c(2)e是人,*之幺元.事实上：由于e是左幺元,现证e是右幺元.Vx=A,x*ewA,

6、安使*(x*e)=(?*x)*e=e*e=e=?*x由(1)即x*e=x,.e为右幺元(3)VxwA,那么x,wA事实上:_xA(x*M*x=x*(?*x)=x*e=x=e*xx*?=e故有*x=x*5?=e,x有逆元由(2),(3)知：a,*为群.2、(10分)证实：m,设6,*是循环群,G=(a),设$,*是6,*的子群.且S*e,S*G,那么存在最小正整数使得：amws,对任意alws,必有1=tm+r,0rm,t0,rl-tmltmlm、-tlrmtc故：a=a=a*a=a*(a)=S即：a=a*(a)=Srm1mt所以auS但m是使a=S的最小正整数,且0Mrm,所以r=0即：a-(

7、a)这说明S中任意元素是am的乘哥.所以G,*是以am为生成元的循环群.3、(8分)证实：对集合aH和bH,只有以下两种情况：(1)aH'bH¥；(2)aHbHIll对于aHcbH,那么至少存在,h2wH,使得ahi=bh2,即有a=bh?'一,这时任,IIJi,意ah-H,有ah=附2儿二wbH故有aH三bH同理可证：bH=aH所以aH=bH4、(8分)证实：反证法：如果A,+,是整环,且有三个以上元素,那么存在awA,a#H,a#1且a,a=a即有：a#e,a-1#日但aa1)=aaa=aa=日这与整环中无零因子条件矛盾.因此A,+,不可能是整环.5、(10分)证

8、实：由于G=V,E不连通,设其连通分支是G(V1),G(Vk)(k之2),7u,vWV,那么有两种情况：(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%函数表为:X1X2X3E(X1,X2,X3)00000011010001111000101111011111E(Xi,X2,X3)=(xiX2X3)(xiX2X

9、3)(X1X2X3)析取范式:(XiX2X3)(XiX2X3)合取范式：E(Xi,X2,X3)=(Xix2X3)(XiX2X3)(xiX2X3)六、树的应用i6%i、6分解：结点数5,边数6,每个结点度数均为偶数,所以它是欧拉图口结点数6,边数7,每个结点度数均为偶数,所以它是欧拉图口附：最优二叉树求解过程如下:2、i0分解：根据权数构造最优二叉树:传输它们的最正确前缀码如上图所示,happynewyear的编码信息为：io0ii0i0i0i0i00iiioiii0i0000iiii0ii000117g1010121578101012151510101215111520121515202315

10、2023304330小草急急忙忙的返青依旧；细雨迷迷濠濠的飘洒依旧.盈盈月下来,照亮你的山歌依旧；灿灿星升起,白杨树绿影婆娑依旧.好风似水,不惊你安眠依旧；鸟儿呢哝,爱的春天依旧.可我,望尽了我的花季,望尽了长长的一路落英缤纷呵！岑凯伦的绵绵春雨依旧,戴望舒的深深雨巷依旧!漂泊的船,寻找一个温馨港口；孤寂的心,渴望一声温暖问候.是你在我最落寞的时候,把亲切放在我左右；是你在我最失意的时候,把慰藉放在我心头.红酥手,黄藤酒；春如旧,人空瘦.蝴蝶双飞影孤单,泪痕红泡蚊绡透!那一叶小舟,那一双眼眸,望穿了几层山水几层楼那一缕相思,那一缕离愁,孤独了多少暮风晨雨后春风依旧,桃花依旧；春水依旧,明月依旧；渡口依旧,时光依旧.前世的情缘,今生的守候,多少次梦里相逢,追忆难收,点点相思堆成无言