.页脚
.页脚城市
7
2
1
,
,
,v
v
v 及预先算出它
们之间的一些直接通信线路造
价，试给出一个设计方案，使得
各城市之间能够通信而且总造价
最小。
树权C(T)=23+1+4+9+3+17=57即为总造价。
答
题
3设是一个群，这里+6是模6加法，Z6={[0 ]，[1]，[2]，
[3]，[4]，[5]}，试求出
的所有子群。答: 子群有<{[0]},+6>；<{[0],[3]},+6>；<{[0],[2],[4]},+6>；<{Z6},+6> 简
答
题
8 8.3 3
4权数1，4，9，16，25，36，49，64，81，100构造一棵最优二叉答: 简
答
8 7.2 3
树。题
5集合X={<1,2>, <3,4>, <5,6>, …}，
R={<,>|x1+y2 =
x2+y1} 。
1）说明R是X上的等价关系。
（6分）
2）求出X关于R的商集。（2分）答: 1）、
1、自反性：y
x
y
x
X
y
x+
=
+
>∈
<
∀由于
,
,
自反
R
R
y
x
y
x
>>∈
<
>
<<
∴,
,
,
2、对称性：X
y
x
X
y
x>∈
<
∀
>∈
<
∀
2
2
1
1
,
,
,
时
当R
y
x
y
x>>∈
<
>
<<
2
2
1
1
,
,
,
2
1
1
2
1
2
2
1
y
x
y
x
y
x
y
x+
=
+
+
=
+也即
即
有对称性
故R
R
y
x
y
x
>>∈
<
>
<<
1
1
2
2
,
,
,
3、传递性：X
y
x
X
y
x
X
y
x>∈
<
∀
>∈
<
∀
>∈
<
∀
3
3
2
2
1
1
,
,
,
,
简
答
题
8 4.4 3
.页脚
.页脚
时且当R y x y x R y x y x >>∈<><<>>∈<><<33222211,,,,,,
⎩⎨
⎧+=++=+)
2()1(2
3321221y x y x y x y x 即
23123221)
2()1(y x y x y x y x +++=++++
即1331y x y x +=+
有传递性故R R y x y x >>∈<><<3311,,,
由（1）（2）（3）知：R 是X 上的先等价关系。
2）、X/R=}]2,1{[R ><
6
设集合A={ a ,b , c , d }上关系
R={< a, b > , < b , a > , < b , c > , < c , d >}
要求 1）、写出R 的关系矩阵和关系图。（4分） 2）、用矩阵运算求出R 的传递闭包。（4分）
答:
1、⎪⎪
⎪
⎪
⎪
⎭
⎫
⎝⎛=000010000101
0010
R M ； 关系图
2、⎪⎪
⎪⎪
⎪
⎭
⎫
⎝
⎛==000000001010
01012
R R R M M M 简答
题
8 4.1;4.3 4
.页脚
.页脚
7，8的最优二叉树T 。（4分）2)求T 对应的二元前缀码。（4分）
（2）最佳前缀码为：000，001，01，10，11
答题
9
下图所示带权图中最优投递路线并求出投递路线长度（邮局在D 点）。
答: 图中奇数点为E 、F ，d(E)=3,d(F)=3,d(E,F)=28 p=EGF 复制道路EG 、GF ，得图G ‘，则G ‘是欧拉图。 由D 开始找一条欧拉回路：DEGFGEBACBDCFD 。 道路长度为：
35+8+20+20+8+40+30+50+19+6+12+10+23=281。
简答题
8 7.2 5
10
设S={1 , 2 , 3 , 4, 6 , 8 , 12 ,
24}，“≤”为S 上整除关系，问：（1）偏序集≤><,S 的Hass
答: (1)≤={<1,2>,<1,3>,<1,4>,<1,6>,<1,8>,<1,12>,<1,24>,<2,4>,<2,6>,<2,8>，<2,12>,<2,24>,<3,6>,<3,12>,<3,24>,<4,8>,<4,12>,<4,24>,<6,12>,<6,24>,<8,24>,<12,24>}S I ⋃
简答题
8 4.4 4
