一、填空 10% （每小题 2分）
1、设是由有限布尔格诱导的代数系统，S是布尔格，中所有原子的集合，则 ～ 。 2、集合S={α，β，γ，δ}上的二元运算*为
* | α | β | γ | δ |
α | δ | α | β | γ |
β | α | β | γ | δ | 颜真卿书法讲座
γ | β | γ | γ | γ |
δ | α | δ | γ | δ |
| | | | |
那么，代数系统<S, *>中的幺元是 , α的逆元是 。
3、设I是整数集合，Z3是由模3的同余类组成的同余类集，在Z3上定义+3如下：，则+3的运算表为 ；<Z+,+3>是否构成 。
4、设G是n阶完全图，则G的边数m= 。
5、如果有一台计算机，它有一条加法指令，可计算四数的和。现有28个数需要计算和，它至少要执行 次这个加法指令。
二、选择 20% （每小题 2分）
1、在有理数集Q上定义的二元运算*，有，则Q中满足（ ）。
A所有元素都有逆元； B、只有唯一逆元；C、时有逆元； D、所有元素都无逆元。
2、设S={0，1}，*为普通乘法，则< S , * >是（ ）。
A半，但不是独异点； B、只是独异点，但不是；C、； D、环，但不是。
3、图 给出一个格L，则L是（ ）。
A、分配格； B、有补格； C、布尔格； D、 A,B,C都不对。
2、有向图D=<V , E>，则长度为2的通路有（ ）条。
A、0； B、1； C、2； D、3 。
3、在Peterson图中，至少填加（ ）条边才能构成Euler图。
A、1； B、2； C、4； D、5 。
三、判断 10% （每小题 2分）
1、在代数系统<A,*>中如果元素的左逆元存在，则它一定唯一且。（ ）
2、设<S,*>是<G,*>的子，则<G,*>中幺元e是<S,*>中幺元。（ ）
3、设， +,·为普通加法和乘法，则代数系统<A，+，·>是域。（ ）
4、设G=<V ,E >是平面图，|V|=v, |E|=e，r为其面数，则v-e + r=2。（ ）wimax网络
5、如果一个有向图D是欧拉图，则D是强连通图。（ ）
四、证明 46%
1、设<A,*>，是半，e是左幺元且，使得，则<A , *>是。（10分）
2、循环的任何非平凡子也是循环。（10分）
3、设aH和bH是子H在G中的两个左陪集，证明：要末，要末 。（8分）
4、设<A ,+ ,·>，是一个含幺环，|A|>3，且对任意，都有，则<A ,+ ,·>不可能是整环（这时称<A，+，·>是布尔环）。（8分）
5、若图G不连通，则G的补图是连通的。（10分）
五洲国际码头五、布尔表达式 8%
设是布尔代数上的一个布尔表达式，试写出其的析取范式和合取范式。
六、图的应用 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] |
[0] | [0] | [1] | [2] |
[1] | [1] | [2] | [0] |
[2] | [2] | [0] | [1] |
| | | |
1、<P (S), >；2、β，γ；3、 是；
4、忏悔录奥古斯丁；5、9
一、选择 10%（每小题 2分）
二、判断 10%（每小题2分）
三、证明 46%
1、（10分）证明：
（1）
(2) e 是<A，*>之幺元。
事实上：由于e是左幺元，现证e是右幺元。
（3）
由（2），（3）知：<A,*>为。
2、（10分）证明：
设<G,*>是循环,G=(a)，设<S,*>是<G,*>的子。且，则存在最小正整数m，使得：，对任意，必有，
故： 即：
所以 但m是使的最小正整数，且，所以r=0即：
这说明S中任意元素是的乘幂。 所以<G,*>是以为生成元的循环。
3、（8分）证明：
（1） ； （2）
对于，则至少存在，使得，即有，这时任意，有，故有
同理可证：所以
4、（8分）证明：
反证法：如果<A，+，·>，是整环，且有三个以上元素，则存在
即有： 这与整环中无零因子条件矛盾。因此<A，+，·>不可能是整环。
5、（10分）证明：
因为G=< V，E>不连通，设其连通分支是，，则有两种情况：
（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%
杜家台分洪函数表为：
| | | |
0 | 0 | 0 | 0 |
0 | 0 | 1 | 1 |
0 | 1 | 0 | 0 |
0 | 1 | 1 | 1 |
1 | 0 | 0 | 0 |
1 | 0 | 1 | 1 |
1 | 1 | 0 | 1 |
1 | 1 | 1 | 1 |
| | | |
析取范式：
合取范式：
六、树的应用 16%
1、（6分）解：
2、（10分）解：
根据权数构造最优二叉树：
传输它们的最佳前缀码如上图所示，happy new year的编码信息为：
庄荣昌10 011 0101 0101 001 110 111 0100 001 111 011 000
附：最优二叉树求解过程如下：
一、单项选择题(本大题共15小题，每小题1分，共15分)
1.设P：天下大雨,Q：他在室内运动,命题“除非天下大雨，否则他不在室内运动”可符合化为（ ）
A.P∧QB.P→QC.P→QD.P→Q
2.下列命题联结词集合中，是最小联结词组的是（ ）
A.{， }B.{，∨，∧}C.{，∧}D.{∧，→}
3.下列命题为假命题的是（ ）
A.如果2是偶数，那么一个公式的析取范式惟一B.如果2是偶数，那么一个公式的析取范式不惟一 C.如果2是奇数，那么一个公式的析取范式惟一D.如果2是奇数，那么一个公式的析取范式不惟一
4.谓词公式x(P(x)∨yR(y))→Q(x))中变元x是（ ）
A.自由变元B.约束变元C.既不是自由变元也不是约束变元D.既是自由变元也是约束变元
5.若个体域为整数减，下列公式中值为真的是（ ）
A.xy(x+y=0) B.yx(x+y=0)C.xy(x+y=0) D.xy(x+y=0)
6.下列命题中不正确的是（ ）
A.x∈{x}-{{x}}B.{x}{x}-{{x}}C.A={x}∪x,则x∈A且xAD.A-B=A=B
7.设P={x|(x+1)2≤4}，Q={x|x2+16≥5x},则下列选项正确的是（ ）
A.PQB.PQC.QPD.Q=P
8.下列表达式中不成立的是（ ）
A.A∪(BC)=(A∪B) (A∪C) B.A∩(BC)=(A∩B) (A∩C)
C.(AB)×C=(A×C) (B×C) D.(A-B) ×C=(A×C)-(B×C)
9.半、及独异点的关系是（ ）
A.{}{独异点}{半}B.{独异点}{半}{}C.{独异点}{}{半}D.{半}{}{独异点}
10.下列集合对所给的二元运算封闭的是（ ）
A.正整数集上的减法运算B.在正实数的集R+上规定为ab=ab-a-b a,b∈R+
C.正整数集Z+上的二元运算为xy=min(x,y) x,y∈Z+D.全体n×n实可逆矩阵集合Rn×n上的矩阵加法
11.设集合A={1，2，3}，下列关系R中不是等价关系的是（ ）
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议