您好,欢迎来到年旅网。
搜索
您的当前位置:首页离散数学模拟习题与解析 (13)

离散数学模拟习题与解析 (13)

来源:年旅网
离散数学试卷(十三)

一、 填空 10% (每小题 2分)

1、Z,对于*运算{x|xZx0},*表示求两数的最小公倍数的运算(Z表示整数集合)

的幺元是 ,零元是 。 2、代数系统中,|A|>1,如果e和分别为的幺元和零元,

则e和的关系为 。

3、设是一个群,是阿贝尔群的充要条件是 。

4、图的完全关联矩阵为 。

5、一个图是平面图的充要条件是 。

二、 选择 10% (每小题 2分)

1、 下面各集合都是N的子集,( )集合在普通加法运算下是封闭的。 A、{x | x 的幂可以被16整除}; B、{x | x 与5互质}; C、{x | x是30的因子}; D、{x | x是30的倍数}。

2、 设G1{0,1,2},,G2{0,1},*,其中表示模3加法,*表示模2乘法,则积代

数G1G2的幺元是( )。

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度结点。

82

离散数学试卷(十三)

A、1; B、2; C、3; D、4 。

三、判断10% (每小题 2分)

1、( )设S={1,2},则S在普通加法和乘法运算下都不封闭。

2、( )在布尔格中,对A中任意原子a,和另一非零元b,在ab或ab中有且

仅有一个成立。

3、( )设S{x|xZx0}N,+,·为普通加法和乘法,则是域。 4、( )一条回路和任何一棵生成树至少有一条公共边。

5、( )没T是一棵m叉树,它有t片树叶,i个分枝点,则(m-1)i = t-1。

四、证明 38%

1、(8分)对代数系统,*是A上二元运算,e为A中幺元,如果*是可结合的且每个元素都有右逆元,则(1)中的每个元素在右逆元必定也是左逆元。

(2)每个元素的逆元是唯一的。

2、(12分)设A , ,,是一个布尔代数,如果在A上定义二元运算☆,为

a☆b(ab)(ab),则是一阿贝尔群。

3、(10分)证明任一环的同态象也是一环。 4、(8分)若GV,E图,则e(Vv,Ee)是每一个面至少由k(k≥3)条边围成的连通平面

k(v2) 。

k2五、应用 32%

1、 (8分)某年级共有9门选修课程,期末考

试前必须提前将这9门课程考完,每人每天只在下午考一门课,若以课程表示结点,有一人同时选两门课程,则这两点间有边(其图如右),问至少需几天?

83

离散数学试卷(十三)

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分)

84

离散数学试卷(十三)

一、 填空 10%(每小题2分)

1、1, 不存在;2、e;3、a,bG有(a*b)*(a*b)(a*a)*(b*b); 4、

e1 1 -1 0 0 e2 1 0 -1 0 e3 1 0 0 -1 e4 0 0 1 -1 e5 0 1 -1 0 v1 v2 v3 v4

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

二、 选择 10%(每小题 2分)

题目 答案

三、 判断 10%

题目 答案

四、 证明 38% 1、(8分)证明:

(1)设a,b,cA,b是a的右逆元,c是b的右逆元,由于b*(a*b)b*eb,

1 Y 2 Y 3 N 4 N 5 N 1 A,D 2 B 3 C 4 D 5 A eb*cb*(a*b)*c(b*a)*(b*c)(b*a)*eb*a

所以b是a的左逆元。

(2)设元素a有两个逆元b、c,那么

bb*eb*(a*c)(b*a)*ce*cc

a的逆元是唯一的。 2、(12分)证明:

[乘],,在A上封闭,  运算☆在A上也封闭。

85

离散数学试卷(十三)

[群] a,b,cA

(a☆b)☆c((ab)(ab))☆c(((ab)(ab))c)((ab)(ab)c)(abc)(abc)((ab)(ab)c)(abc)(abc)(((ab)(ab))c)(abc)(abc)(abc)(abc)同理可得:a☆(b☆c)(abc)(abc)(abc)(abc)(a☆b)☆ca☆(b☆c) 即☆满足结合性。

[幺] aA,a☆00☆a(0a)(0a)0(1a)0aa 故全下界0是A中关于运算☆的幺元。

[逆] aA,(a☆a)(aa)(aa)000 即A中的每一个元素以其自身为逆元。

[交] a☆b(ab)(ab)(ba)(ba)b☆a 即运算☆具有可交换性。 所以是Abel群。 3、(10分) 证明:

设A,,是一环,且f(A),,是关于同态映射f的同态象。 由A,是Abel群,易证f(A),也是Abel群。

A,是半群,易证f(A),也是半群。

现只需证:对是可分配的。

b1,b2,b3f(A),则必有相应的a1,a2,a3使得:f(ai)bi,i1,2,3 于是 b1(b2b3)f(a1)(f(a2)f(a3))f(a1)(f(a2a3))f(a1(a2a3))f((a1a2)(a1a3))f(a1a2)f(a1a3)(f(a1)f(a2))(f(a1)f(a3))(b1b2)(b1b3)同理可证(b2b3)b1(b2b1)(b3b1) 因此f(A),,也是环。

86

离散数学试卷(十三)

5、(8分)证明:

设G有r个面,

deg(ri)2e,而deg(ri)ki1r(1ir)2ekr即r2e k而ver2,故ve2rk(v2) 。 2即ekk2五、 应用32% 1、(8分)

解:(G)即为最少考试天数。

用Welch-Powell方法对G着色:v9v3v7v1v2v4v5v8v6 第一种颜色的点 v9v1v4v6,剩余点v3v7v2v5v8 第二种颜色的点 v3v7v5,剩余点v2v8 第三种颜色的点 v2v8 所以(G)≤3

任v2v3v9构成一圈,所以(G)≥3 故(G)=3

所以三天下午即可考完全部九门课程。 2、(8分)

0011解:A(G)10100001

0100

0011i 1:A[2,1]=1,A10110001; i2:0100 87

0A[4,2]=1,A101011011001111

离散数学试卷(十三)

0011i3: A[1,3]=A[2,3]=A[4,3]=1,A10110001 11111111i4: A[k,4]=1,k=1,2,3,4,A11111111

1111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)

W(T)24345392728283

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

88

通和

条无

因篇幅问题不能全部显示,请点此查看更多更全内容

Copyright © 2019- oldu.cn 版权所有 浙ICP备2024123271号-1

违法及侵权请联系:TEL:199 1889 7713 E-MAIL:2724546146@qq.com

本站由北京市万商天勤律师事务所王兴未律师提供法律服务