离散数学试卷及答案(13).doc

离散数学试卷（十三）
一、 填空 10% （每小题 2分）
1、，*表示求两数的最小公倍数的运算（Z表示整数集合），对于*运算的幺元是 ，零元是 。
2、代数系统中，|A|>1，如果分别为的幺元和零元，
则的关系为 。
3、设是一个群，是阿贝尔群的充要条件是 。
4、图的完全关联矩阵为 。

5、一个图是平面图的充要条件是 。
二、 选择 10% （每小题 2分）
1、 下面各集合都是N的子集，（ ）集合在普通加法运算下是封闭的。
A、{x | x 的幂可以被16整除}； B、{x | x 与5互质}；
C、{x | x是30的因子}； D、{x | x是30的倍数}。
2、 设，，其中表示模3加法，*表示模2乘法，则积代数的幺元是（ ）。
A、<0,0>； B、<0,1>； C<1,0>； D、<1,1> 。
3、 设集合S={1,2,3,6}，“≤”为整除关系，则代数系统< S , ≤ >是（ ）。
A、域； B、格，但不是布尔代数； C、布尔代数； D、不是代数系统。
4、 设n阶图G有m条边，每个结点度数不是k就是k+1，若G中有Nk个k度结点，
则Nk=（ ）。
A、n·k； B、n(k+1)； C、n(k+1)-m； D、n(k+1)-2m 。
5、 一棵树有7片树叶，3个3度结点，其余全是4度结点，
则该树有（ ）个4度结点。

A、1； B2； C、3； D、4 。
三、判断10% （每小题 2分）
1、（ ）设S={1,2}，则S在普通加法和乘法运算下都不封闭。
2、（ ）在布尔格中，对A中任意原子a，和另一非零元b，在或中有且仅有一个成立。
3、（ ）设，+,·为普通加法和乘法，则是域。
4、（ ）一条回路和任何一棵生成树至少有一条公共边。
5、（ ）没T是一棵m叉树，它有t片树叶，i个分枝点，则(m-1)i = t-1。

四、证明 38%
1、（8分）对代数系统，*是A上二元运算，e为A中幺元，如果*是可结合的且每个元素都有右逆元，则（1）中的每个元素在右逆元必定也是左逆元。
（2）每个元素的逆元是唯一的。
2、（12分）设是一个布尔代数，如果在A上定义二元运算☆，为，则是一阿贝尔群。
3、（10分）证明任一环的同态象也是一环。
4、（8分）若是每一个面至少由k(k≥3)条边围成的连通平面图，则 。
五、应用 32%
1、 （8分）某年级共有9门选修课程，期末考试前必须提前将这9门课程考完，每人每天只在下午考一门课，若以课程表示结点，有一人同时选两门课程，则这两点间有边（其图如右），问至少需几天？
2、 用washall方法求图的可达矩阵，并判断图的连通性。（8分
3、 设有a、b、c、d、e、f、g七个人，他们分别会讲的语言如下：a：英，b：汉、英，c：英、西班牙、俄，d：日、汉，e：德、西班牙，f：法、日、俄，g：法、德，能否将这七个人的座位安排在圆桌旁，使得每个人均能与他旁边的人交谈？（8分）
4、 用 Huffman算法求出带权为2，3，5，7，8，9的最优二叉树T，并求W（T）。
若传递a ，b， c， d ，e， f 的频率分别为2%， 3% ，5 %， 7% ，8% ，9%求传输它的最佳前缀码。（8分）

一、 填空 10%（每小题2分）
1、1， 不存在；2、；3、有；
4、

1
1
1
0
0

-1
0
0
0
1

0
-1
0
1
-1

0
0
-1
-1
0
5、它不包含与K3, 3或K5在2度结点内同构的子图。

二、 选择 10%（每小题 2分）
题目
1
2
3
4
5
答案
A，D
B
C
D
A

三、 判断 10%
题目
1
2
3
4
5
答案
Y
Y
N
N
N

四、 证明 38%
1、（8分）证明：
（1）设，b是a的右逆元，c是b的右逆元，由于，

所以b是a的左逆元。
（2）设元素a有两个逆元b、c，那么

a的逆元是唯一的。
2、（12分）证明：
[乘] 运算☆在A上也封闭。
[群]

即☆满足结合性。
[幺] ,
故全下界0是A中关于运算☆的幺元。
[逆] ,
即A中的每一个元素以其自身为逆元。
[交]
即运算☆具有可交换性。
所以是Abel群。
3、(10分) 证明:
设是一环,且是关于同态映射f的同态象。
由是Abel群，易证也是Abel群。
是半群，易证也是半群。
现只需证：对是可分配的。
于是

同理可证
因此也是环。
5、（8分）证明：
设G有r个面，

。
五、 应用32%
1、（8分）
解：即为最少考试天数。
用Welch-Powell方法对G着色：
第一种颜色的点 ，剩余点
第二种颜色的点 ，剩余点
第三种颜色的点
所以≤3
任构成一圈，所以≥3
故=3
所以三天下午即可考完全部九门课程。
2、（8分）
解：

1：A[2，1]=1，； 2： A[4，2]=1，
3： A[1，3]=A[2，3]=A[4，3]=1，
4： A[k，4]=1，k=1，2，3，4，
p中的各元素全为1，所以G是强连通图，当然是单向连通和弱连通。
3、（8分）
解：用a,b,c,d,e,f,g 7个结点表示7个人，若两人能交谈可用一条无向边连结，所得无向图为
此图中的Hamilton回路即是圆桌安排座位的顺序。
Hamilton回路为a b d f g e c a。
4、（8分）
解：(1)

（1） 用0000传输a、0001传输b、001传输c、01传输f、10传输d、11传输e
传输它们的最优前缀码为{0000，0001，001，01，10，11} 。

88