W(T)?2?4?3?4?5?3?9?2?7?2?8?2?83
（1） 用0000传输a、0001传输b、001传输c、01传输f、10传输d、11传输e 传输它们的最优前缀码为{0000，0001，001，01，10，11} 。
试卷十四试题与答案
九、 填空 10% （每小题 2分）
1、 设?A,?,?,??是由有限布尔格?A,??诱导的代数系统，S是布尔格
?A,??，中所有原子的集合，则
?A,?,?,??～ 。
2、 集合S={α，β，γ，δ}上的二元运算*为
* α β γ δ
那么，代数系统
α δ α β α β α β γ δ γ β γ γ γ δ γ δ γ δ [i]?3[j]?[(i?j)mod3]，则+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时有逆元x； D、所有元素都无逆元。
?1
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图
图。
中，至少填加（ ）条边才能构成Euler
A、1； B、2； C、4； D、5 。
十一、 判断 10% （每小题 2分）
1、 在代数系统中如果元素a?A的左逆元ae存在，
则它一定唯一且a?1?1?ae。（ ）
?12、 设
统是域。（ ）
4、 设G=
四、证明 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，则
不可能是整环（这时称是布尔环）。（8分） 5、 若图G不连通，则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分）
答案
十二、 填空 10%（每小题2分）
+3 [0] [1] [2]
十三、 选择 10%（每小题 2分） 题目 答案
十四、 判断 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 1 C 2 B 3 D 4 B 5 D [0] [0] [1] [2] [1] [1] [2] [0] [2] [2] [0] [1] 1、
?,?,~>；2、β
，γ；3、
1n(n?1)24、；5、9
?使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）知：为群。 2、（10分）证明：
设
ml使得：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
lmtrm所以a?S但m是使a?S的最小正整数，且0?r?m，所以r=0即：a?(a)
这说明S中任意元素是a的乘幂。 所以
对集合aH和bH，只有下列两种情况： （1）aH?bH??； （2）aH?bH??
对于aH?bH??，则至少存在h1,h2?H，使得ah1?bh2，即有a?bh2h1，这时任意ah?aH，有ah?bh2h1h?bH，故有aH?bH 同理可证：bH?aH所以 aH?bH 4、（8分）证明：
反证法：如果，是整环，且有三个以上元素，则存在a?A,a??,a?1且a?a?a 即有：a??,a?1??但a?(a?1)?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 在G中连通。
（2） u ,v ，属于同一个结点子集Vi，可在另一结点子集Vj中任取一点w，故(u , w),(w , v )
均在G中，故邻接边( u ,w ) ( w , v ) 组成的路连接结点u和v，即u , v在G中也是连通的。
五、布尔表达式 8% 函数表为：
?1?1mm(k?2)，?u,v?V，则有两
x1 0 0 0 0 x2 0 0 1 1 x3 0 1 0 1 E(x1,x2,x3) 0 1 0 1