《离散数学》试题带答案(三)

《离散数学》试题带答案

试卷十四试题与答案

一、 填空 10% （每小题 2分）

1、 设?A,?,?,??是由有限布尔格?A,??诱导的代数系统，S是布尔格

?A,??，中所有原子的集合，则

?A,?,?,??～ 。

2、 集合S={α，β，γ，δ}上的二元运算*为

* α β γ δ

那么，代数系统中的幺元是 , α的逆元是 。 3、 设I是整数集合，Z3是由模3的同余类组成的同余类集，在Z3上定义+3如下：

α δ α β α β α β γ δ γ β γ γ γ δ γ δ γ δ [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存在，

?1?1a?ae则它一定唯一且。（ ）

?12、 设是群的子群，则中幺元e是中幺元。（ ） 3、 设A?{x|x?a?b3,a,b均为有理数}， +,·为普通加法和乘法，则代数系

统是域。（ ）

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

四、证明 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分） 答案

一、

+3 [0] [1] [0] [0] [1] 填空 10%（每小题2分）

[1] [1] [2] [2] [2] [0]