试卷二十试题与答案

一、填空20%（每空2分）

1．n 个命题变元有 个互不等价的极小项。

n2．按De-Morgan定理，

A1A2AnAii1= 。

3．公式P(QR)的主析取范式为 。

4．设P(x)：x是大象，Q(x)：x是老鼠，R(x,y)：x比y重，则命题“大象比老鼠重”的符号化为

。

101MR110111X{a,b,c}，则 5．设，X上的关系R的关系矩阵是

MRR

。 6．在具有n个结点的有向图中，任何基本通路的长度都不超过 。

7．任何图的点连通度(G)，边连通度(G)，最小点度(G)的关系为

。

8．结点数n（n3）的简单连通平面图的边数为m，则m与n的关系为 。

9．群G的非空子集H是G的子群当且仅当若x , yH 则 。 10．代数系统A,,是环，若对运算“· ”还满足 则A,,是整环。

二、选择10%（每小题2分）

nA{xx2,nN}对（ ）运算封闭。

1．集合

A、加法； B、减法； C、乘法； D、

xy。

2．设I为整数集合，m是任意正整数，Zm是由模m的同余类组成的同余类集合，在Zm上

m]，则代数系统Zm,m最确切的性质是定义运算[i][j][(ij)mod（ ）。

A、封闭的代数系统； B、半群； C、独异点； D、群。

3．设N,是偏序格，其中N是自然数集合，“≤”是普通的数间“小于等于” 关系，则

a,bN有ab（ ）。

A、a ； B、b ； C、max(a，b) ； D、min(a，b)。

4．连通非平凡的无向图G有一条欧拉回路当且仅当图G ( )。

A、只有一个奇度结点； B、只有两个奇度结点； C、只有三个奇度结点； D、没有奇度结点。

5．设无向图GV,E是连通的且Vn,Em若（ ）则G是树。 A、M=N+1 ； B、n=m+1 ； C、m3n6； D、n3m6。

三、12%逻辑推理：

符号化命题“有些病人相信医生，但是没有病人相信法轮功，因此医生都不信法轮功”。用演绎法证明其结论。（P(x)：x是病人，D(x)：x是医生，Q(x)：x是法轮功练习者，L(x , y)：x相信y）

四、序关系8%：

设A{x1,x2,x3,x4,x5}，偏序集A,R的Hass图为

求 ① A中最小元与最大元； ② {x3,x4,x5}的上界和上确界，下界和下确界。

五、函数8%

设f:XY和g:YZ是映射且使得gf是满射，若g是入射，证明f是满射。

六、图8%

设G是连通简单平面图，结点数为n（n3），边数为m，面数为r，则r2n4。

七、树的应用12%

设7个符号在通讯中使用的频率如下：

a：35% ，b：20% ，c：15% ，d：10% ， e：10% ，f：5% ，g ：5%

编一个相应的二元前缀码，使通讯中出现的符号尽可能地减少，并画出对应的二叉树及求二叉树的过程。

八、道路的基本性质10%

设u ，v是树T的两个不同的结点，从u至v的基本通路（结点不同的道路）是T中最长的基本道路，证明：d(u)=d(v)=1。

九、子群12%

1若H是G的子群，a,bG，则 baHaHbH 。

答案

一、填空20%

1、2； 2、

n(Ai)i1n；

(PQR)(PQR)(PQR)(PQR)3、

(PQR)(PQR)(PQR)0,1,2,3,4,5,7；

111111111； 6、n-1 ； 4、xy(P(x)Q(y)R(x,y))；5、7、(G)(G)(G)； 8、m3n6； 9、xy10、含幺元，可交换，无零因子。

1H；

二、选择10%

题号 答案 1 C 2 B 3 C 4 D 5 B 三、12% 解：前提：x(P(x)y(D(y)L(x,y)), 结论：y(D(y)Q(y)) 演绎推理：

（1）x(P(x)y(D(y)L(x,y)) （2）P(e)y(D(y)L(e,y)) P

x(P(x)y(L(x,y)Q(y)))

ES(1)

（3）x(P(x)y(L(x,y)Q(y))) P （4）P(e)y(L(e,y)Q(y)) US(3) （5）P(e) T(2)I （6）y(L(e,y)Q(y)) T(4)(5)I

（7）L(e,c)Q(c) US(6) （8）y(D(y)L(e,y)) （9）D(c)L(e,c) T(2)I

US(8)

（10）D(c)Q(c) T(9)(7)I （11）y(D(y)Q(y)) UG(10)

四、解：

① A中最大元为x1，最小元不存在； ② {x3,x4,x5}上界x1,x3，上确界x1；下界无，下确界无。

五、解：

证：yY，因g是映射，故必存在zZ使g(y)z，由于gf(x)z即 g(f(x))zg(y)，因g是单射，所以 f(x)y 说明yY，必有 xX使得f(x)y，故f(x)是满射。

六、解：

证：因为G是结点数n3的简单连通平面图，所以 m3n6，又由于m2且连通简单平面图的每个面至少有3条边围成，于是3r2m2(3n6)，所以 r2n4 。

七、解：

用100乘各频率得权数：

w1=35， w2=20， w3=15， w4=10， w5=10， w6=5， w7=5 将其由小到大排列用 Huffman算法可求得最优树。 5 5 10 10 15 20 35 10 10 10 15 20 35 20 10 15 20 35 20 25 20 35 40 25 35

40

100

最优二叉树为

60

编码树为：

前缀码：a：11； b：01； c：101； d：100； e：001；f：0000；g：0001

八、解：

设l为T中最长的基本道路且以u 为起点，v 为终点，即luv1v2vkv

u v 如果d(u)1，则u 的邻接点除了v1之外还有一点，

v1 vk

l上，否则 不妨设为u1，而u1不在T中存在回路uv1v2u1u即 u v1 u1 vk v

l是最长的道与T为树矛盾。于是得到一条lu1uv1v2vkv是比l更长的基本道路，这与

路矛盾，故d(u)1。同理可证 d(v)1 。

九、证：

\"\"

1111baH所以（ba）abH， 因为

11又 b(aa)ba(a a(bb)ab(b1b)a)baH abH

1xaHxah1(bh)h1b(hh1)bH aHbH

同理可证 bHaH 所以 故 aHbHaH

aHbH

\"\" 若 aHbH 设 xaHbH 则

h1,h2H 使 xah1bh2 可得：b

1ah2h11H。