试卷十四试题与答案试卷教案

试卷十四试题与答案

一、 填空 10％ (每小题 2分）

1、 设A,,,是由有限布尔格A,诱导的代数系统,S是布尔格A,，

中所有原子的集合,则A,,,～。 2、 集合S=｛α，β,γ,δ}上的二元运算＊为

* α β γ δ

那么,代数系统〈S, ＊>中的幺元是 ， α的逆元是.

3、 设I是整数集合，Z3是由模3的同余类组成的同余类集，在Z3上定义+3如下：

α δ α β α β α β γ δ γ β γ γ γ δ γ δ γ δ [i]3[j][(ij)mod3]，则+3的运算表为;

〈Z+,+3〉是否构成群。

4、 设G是n阶完全图，则G的边数m= 。

5、 如果有一台计算机，它有一条加法指令,可计算四数的和。现有28个数需要计算和，

它至少要执行次这个加法指令。

二、 选择 20％ （每小题 2分）

1、 在有理数集Q上定义的二元运算*，x,yQ有x*yxyxy，

则Q中满足（）。

A、 所有元素都有逆元; B、只有唯一逆元； C、xQ,x1时有逆元; D、所有元素都无逆元。

2、 设S=｛0，1｝，＊为普通乘法，则〈 S , * 〉是（）。

A、 半群,但不是独异点; B、只是独异点，但不是群；

C、群； D、环,但不是群.

3、图给出一个格L，则L是（)。

A、分配格; B、有补格； C、布尔格； D、 A，B,C都不对。

3、 有向图D=A、0； B、1; C、2； D、3 。

，则v1到v4长度为2的通路有（)条。

4、 在Peterson图

A、1; B、2; C、4； D、5 .

中，至少填加（）条边才能构成Euler图。

三、 判断 10％ （每小题 2分)

1、 在代数系统11aae则它一定唯一且.（）

2、 设是群〈G，＊>的子群，则中幺元e是〈S,*〉中幺元。（） 3、 设A{x|xab3,统〈A，+，·>是域。（）

4、 设G=〈V ,E 〉是平面图，｜V｜=v, ｜E|=e,r为其面数，则v—e + r=2。（） 5、 如果一个有向图D是欧拉图，则D是强连通图。（）

a,b均为有理数}， +，·为普通加法和乘法，则代数系

四、证明 46%

ˆA，使得xˆ*xe, 1、 设，是半群,e是左幺元且xA,x则是群。（10分）

2、 循环群的任何非平凡子群也是循环群。（10分）

3、 设aH和bH是子群H在群G中的两个左陪集，证明：要末aHbH，要末

aHbH。（8分）

4、 设,是一个含幺环，｜A｜〉3，且对任意aA,都有aaa，则〈A ,+ ，·〉

不可能是整环（这时称〈A，+，·>是布尔环）。（8分） 5、 若图G不连通，则G的补图是连通的。（10分）

五、布尔表达式 8%

设

E(x1,x2,x3)(x1x2)(x2x3)(x2x3)是布尔代数

{0,1},,,上的一个布尔表达式，试写出其的析取范式和合取范式。

六、图的应用 16%

1、 构造一个结点v与边数e奇偶性相反的欧拉图。（6分）

2、 假设英文字母，a，e,h，n，p，r,w，y出现的频率分别为12%,8％，15％，7％,6％，10%，

5%，10%，求传输它们的最佳前缀码，并给出happy new year的编码信息。(10分） 答案

一、

+3 [0] [1］ ［2]

[0] 填空 10％（每小题2分）

1、

；2、β，γ;3、是;

［1］ [2] [2] ［0］ [0］ [1］ [1］ [2] [2] 1n(n1)24、;5、9

［0] [1］ 二、 选择 10%（每小题 2分） 题目

1 2 3 4 5

答案

C B D B D 三、 判断 10%（每小题2分） 题目 答案

四、 证明 46％

1、（10分)证明：

（1）a,b,cA,若a*ba*c则bc

1 N 2 Y 3 Y 4 N 5 Y ˆ使aˆ*(a*b)aˆ*(a*c)事实上:a*ba*caˆ*a)*b(aˆ*a)*c,e*be*c(a即:bc（2） e 是之幺元。

事实上：由于e是左幺元，现证e是右幺元。

ˆ使xˆ*(x*e)(xˆ*x)*ee*eexˆ*xxA,x*eA,x由(1)即x*ex,e为右幺元1xA,则xA (3)

ˆ)*xx*(xˆ*x)x*exe*x事实上:xA(x*xˆe故有xˆ*xx*xˆex有逆元xˆx*x

由（2），（3）知：〈A，＊〉为群。 2、（10分）证明：

设〈G，*〉是循环群，G=(a),设的子群。且S{e},SG,则存在最小

ml正整数m，使得：aS,对任意aS，必有ltmr,0rm,t0,

故：aarltmal*atmal*(am)tS即:alar*(am)tS

lmtrma(a) 0rmaSaS所以但m是使的最小正整数,且，所以r=0即：

这说明S中任意元素是的乘幂。所以〈G，*〉是以为生成元的循环群。 3、(8分）证明：

对集合aH和bH,只有下列两种情况： （1）aHbH；（2）aHbH

1h,hHahbhabhhaHbH121221，这时任意对于,则至少存在，使得，即有

ahaH,有ahbh2h1hbH，故有aHbH

1

同理可证：bHaH所以aHbH 4、(8分）证明：

反证法:如果〈A，+，·〉，是整环,且有三个以上元素，则存在aA,a,a1且aaa 即有：a,a1但a(a1)aaaaa这与整环中无零因子条件矛盾。因此〈A，+,·>不可能是整环。 5、（10分）证明：

因为G=< V，E>不连通，设其连通分支是G(V1),,G(Vk)种情况：

（1） u , v，分别属于两个不同结点子集Vi，Vj，由于G(Vi) ， G（Vj)是两连通分支，故

（u , v)在不G中，故u ， v 在中连通。

（2） u ,v ，属于同一个结点子集Vi，可在另一结点子集Vj中任取一点w，故(u , w）,(w ,

v )均在中，故邻接边（ u ,w ） ( w , v ） 组成的路连接结点u和v，即u ， v在中也是连通的。

五、布尔表达式 8% 函数表为：

(k2)，u,vV，则有两

0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 E(x1,x2,x3) 0 1 0 1 0 1 1 1 0 0 0 0 1 1 1 1 E(x1,x2,x3)(x1x2x3)(x1x2x3)(x1x2x3)析取范式：

(x1x2x3)(x1x2x3)

合取范式：E(x1,x2,x3)(x1x2x3)(x1x2x3)(x1x2x3)

六、 树的应用 16%

1、（6分）解：

2、（10分）解:

根据权数构造最优二叉树：

传输它们的最佳前缀码如上图所示，happy new year的编码信息为:

10 011 0101 0101 001 110

111 0100 001 111 011 000

附:最优二叉树求解过程如下：