一、 填空 10% (每小题 2分)
1、 设?A,?,?,??是由有限布尔格?A,??诱导的代数系统,S是布尔格?A,??,中所有原子的集合,则
?A,?,?,?? ~ 。
2、 集合S={α,β,γ,δ}上的二元运算*为
* α β γ δ α δ α β α β α β γ δ γ β γ γ γ δ γ δ γ δ 那么,代数系统中的幺元是 , α的逆元是 。
3、 设I是整数集合,Z3是由模3的同余类组成的同余类集,在Z3上定义+3如下:[i]?3[j]?[(i?j)mod3],则+3的运算表为 ;
5、 如果有一台计算机,它有一条加法指令,可计算四数的和。现有28个数需要计算和,它至少要执行 次这个加法指令。
二、 选择 20% (每小题 2分)
1、 在有理数集Q上定义的二元运算*,?x,y?Q有x*y?x?y?xy,则Q中满足( )。 A所有元素都有逆元; B、只有唯一逆元;C、?x?Q,x?1时有逆元x; D、所有元素都无逆元。 2、设S={0,1},*为普通乘法,则< S , * >是( )。
A半群,但不是独异点; B、只是独异点,但不是群;C、群; D、环,但不是群。
?13、图 给出一个格L,则L是( )。
A、分配格; B、有补格; C、布尔格; D、 A,B,C都不对。
2、 有向图D=
,则v1到v4长度为2的通路有( )条。
A、0; B、1; C、2; D、3 。
3、 在Peterson图中,至少填加( )条边才能构成Euler图。
A、1; B、2; C、4; D、5 。
三、 判断 10% (每小题 2分)
1、 在代数系统中如果元素a?A的左逆元ae存在,则它一定唯一且a?1?1?ae?1。( )
2、 设是群中幺元。( ) 3、 设A?{x|x?a?b3,a,b均为有理数}, +,·为普通加法和乘法,则代数系统是域。( )
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分)
1、
;2、β,γ;3、 + 3 [0] [1] [2] 是; 4、
一、 选择 10%(每小题 2分) 题目 答案 二、
1 C 2 B 3 D 4 B 5 D 1n(n?1);5、9 2[0] [1] [2] [0] [1] [2] [1] [2] [0] [2] [0] [1] 判断 10%(每小题2分)
1 N 2 Y 3 Y 4 N 5 Y 题目 答案 三、 证明 46% 1、(10分)证明:
(1)?a,b,c?A,若a*b?a*c则b?c
?使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为右幺元(3)?x?A,则x?1
?A
?)*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分)证明:
a?S,设是
必有l?tm?r,故:a?arl?tmml0?r?m,t?0,
?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的乘幂。 所以
mm3、(8分)证明:
对集合aH和bH,只有下列两种情况: (1)aH?bH?? ; (2)aH?bH??
对于aH?bH??,则至少存在h1,h2?H,使得ah1?bh2,即有a?bh2h1?1,这时任意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(k?2),?u,v?V,则有两种情况:
(1) 中连通。 (2)
u , v,分别属于两个不同结点子集Vi,Vj,由于G(Vi) , G(Vj)是两连通分支,故(u , v)在不G中,故u , v 在Gu ,v ,属于同一个结点子集Vi,可在另一结点子集Vj中任取一点w,故(u , w),(w , v )均在G中,故邻接边( u ,w )
( w , v ) 组成的路连接结点u和v,即u , v在G中也是连通的。
五、布尔表达式 8%
函数表为:
x1 0 0 0 0 1 1 1 1 x2 0 0 1 1 0 0 1 1 x30 1 0 1 0 1 0 1 E(x1,x2,x3) 0 1 0 1 0 1 1 1
析取范式:
E(x1,x2,x3)?(x1?x2?x3)?(x1?x2?x3)?(x1?x2?x3)?(x1?x2?x3)?(x1?x2?x
3)合取范式:E(x1,x2,x3)?(x1?x?2x3)?(x1?x2?x3)?(x1?x2?x3) 六、
树的应用 16%
1、(6分)解:
2、(10分)解:
根据权数构造最优二叉树:
传输它们的最佳前缀码如上图所示,happy 码信息为:
10 011 0101 0101 001 110 111 0100 001
附:最优二叉树求解过程如下:
一、单项选择题(本大题共15小题,每小题1分,共15分)
1.设P:天下大雨,Q:他在室内运动,命题“除非天下大雨,否则他不.
在室内运动”可符合化为(A.?P∧QB.?P→QC.?P→?QD.P→?Q
2.下列命题联结词集合中,是最小联结词组的是( )
new year的编
111 011 000
)
离散数学试卷及答案



