；B、1、1、2；C、2、1、2；D、1、2、2。3、一棵无向树T有8个顶点，4度、3度、2度的分枝点各1个，其余顶点均为树叶，则T中有（）片树叶。A、3；B、4；C、5；D、6）时A，
4、设A，，是代数系统，其中，为普通的加法和乘法，则A（，是整环。A、xx2
Z；C、xx0且xZ；B、xx2
1
Z；
4D、xxab5
abR。
f5、设A1，2，…，10，则下面定义的运算关于A封闭的有（A、xymaxxy；B、xy质数p的个数使得xpy；
）。
C、xygcdxy；gcdxy表示x和y的最大公约数；D、xylcmxy（lcmxy表示x和y的最小公倍数）。
三、证明45
2m4。1、设G是（
m）简单二部图，则（8分）
2、设G为具有
个结点的简单图，且
m
1
1
22则G是连通图。（8分）
3、设G是阶数不小于11的简单图，则G或G中至少有一个是非平图。（14分）4、记“开”为1，“关”为0，反映电路规律的代数系统0，1，，的加法运算和乘法运算。如下：0100111001000101
证明它是一个环，并且是一个域。（15分）
四、生成树及应用10
1、（10分）如下图所示的赋权图表示某七个城市
v1v2v7及预先测算出它们之间的一些直接通信线路
造价，试给出一个设计方案，使得各城市之间既能够通信而且总造价最小。2、（10分）构造H、A、P、N、E、W、R、对应的前缀码，并画出与该前缀码对应的二叉树，写出英文短语HAPPYNEWYEAR的编码信息。
五、5
对于实数集合R，在下表所列的二元远算是否具有左边一列中的性质，请在相应位上填写“Y”或“N”。MaxMi

f可结合性可交换性存在幺元存在零元
答案：十六、填空15（每小题3分）
0001
121、；2、0
b、没有十七、选择15（每小题3分）题目答案1A2A3C
1011
0101
1100；3、；4、2
t1；5、a，c，a、
4D
5A，C
十八、
证明45
1、（8分）：设G（V，E），VXYX
1
Y
2则
1
2


2m
1
2
1
1
12
1
1224对完全二部图有
1
当

2
2时，完全二部图
m的边数m有最大值4。

2m4。故对任意简单二部图
m有
2、（8分）反证法：若G不连通，不妨设G可分成两个连通分支G1、G2，假设G1和G2的顶点数分别为
1和
2，显然
1
2
。

11
21
1
1
2
1
m
1
11
2
21
1
1r