厦大离散数学期末试卷2009_试题 完整答案厦大离散数学期末试卷2009_试题 完整答案
厦门大学《离散数学》课程试卷
软件学院2008年级
主考教师:金贤安 试卷类型:,A卷,
一、 选择题(共10题,每题3分,共30分)
1、下列语句为命题的是( )。 A(勿踏草地;。
B(你去图书馆吗,; C(月球上有水;
D(本命题为假。
2(下列推理中,( )是错误的。
A. 如果x是有理数,则它为整数。1/2是有理数。所以1/2是整数。 B. 若周末气温超过30度,小红就去游泳。小红周末没去游泳。所以周末气温没超过30度。
C. 下午小明或者去看电影,...
厦大离散数学期末试卷2009_试题 完整答案
厦门大学《离散数学》课程试卷
软件学院2008年级
主考教师:金贤安 试卷类型:,A卷,
一、 选择题(共10题,每题3分,共30分)
1、下列语句为命题的是( )。 A(勿踏草地;。
B(你去图书馆吗,; C(月球上有水;
D(本命题为假。
2(下列推理中,( )是错误的。
A. 如果x是有理数,则它为整数。1/2是有理数。所以1/2是整数。 B. 若周末气温超过30度,小红就去游泳。小红周末没去游泳。所以周末气温没超过30度。
C. 下午小明或者去看电影,或者去打篮球。下午小明没去打篮球。因此下午小明去看电影了。
D. 若a能被4整除,则a能被2整除。a能被2整除。因此a能被4整除。 3(谓词公式中的x( )。 ,x(P(x),,yR(y)),Q(x)
A(只是约束变元
B(只是自由变元
C(既非约束变元又非自由变元
D(既是约束变元又是自由变元
4. 下列关系中,( )不是等价关系。
A. 非空集合的幂集的元素间包含关系;
B. 集合之间的等势关系;
C. 公式之间的等值关系;
D. 图之间的同构关系。
5. 下面等值式中,( )是不正确的。
A. ,x(A(x),B(x)),,xA(x),,xB(x)
B. ,x(A(x),B(x)),,xA(x),,xB(x)
C. ,x(A(x),B),,xA(x),B
D. ,x(A,B(x)),A,,xB(x)
1
6(下列关于集合的势的叙述中,( )是错误的。
A. 实数集比自然数集优势;
B. 任一无限集合都存在与自己等势的真子集;
C. 集合之间的优势关系是偏序关系;
D. 有理数集比整数集优势。
7(设A,B,C是集合,F是关系,,则下列式子中不正确的是( )。G:A,B,D,A
,1A( B. A,B,,,A,B,BG(G(D)),DC. D. F[A,B],F[A],F[B](A,B),C,A,(B,C)8. 以下序列中,( )是简单可图的。
A. (4,4,3,3,2,2); B. (3,3,3,1); C. (5,4,3,2,2); D. (6,6,3,2,2,2,1)。
9. 下列叙述中错误的是( )。
A(n(n?2)阶竞赛图都具有哈密顿通路;
B(非平凡树不是欧拉图,也不是哈密顿图;
C(n(n?3且为奇数)阶的二部图一定不是哈密顿图;
D(欧拉回路包含图的所有顶点,哈密顿回路包含图的所有边。 10(下列关于图的连通性的叙述中正确的是( )。
A. 有向图是连通的是指它是强连通的;
B. 任一无向图的点连通度都不超过它的边连通度;
C. 在一n阶圈Cn(n?4)上任意去掉两个顶点得到得图都有2个连通分支; D. n阶无向完全图的点连通度为n;
二、填空题(共8题,每题3分,共24分)
1(令F(x):x是汽车,G(y):y是火车,H(x,y):x比y快。则命题“不存在比所有火车都
快的汽车”符号化形式为_________________。 ,,x(F(x),(,y(G(y),H(x,y)))2(公式的主析取范式为______________。 (p,q),rm0,m4,m63(集合A={a,b,c,d}上的等价关系共有______个。
4(自对偶图的顶点数n和边数m之间满足关系式为m =_______________。 5(设T是有t片树叶的2叉正则树,则T应该有_______个顶点。 6(P({Φ,{Φ}}) = _{Φ,{Φ},{Φ,{Φ}},{{Φ}}}____。
2
7(在1到100之间(包含1和100)即不能被2,也不能被3,还不能被5整除的自然数有
_______个。
8(“p仅当q”,“只有q才p”,“除非q才p”这三个命题的符号化分别为_____ , ____
和 _____ 。(请按顺序填写)
三、应用、计算和
题(共6题,46分)
1((6分) 在命题逻辑的自然推理系统中构造下面推理的证明。
前提:?(P??Q),?Q?R,?R
结论:?P
2((8分)设集合A={a,b,c,d},A上的关系R={
,,,,}
求:(1)画出R的关系图。(2分)
(2)R的自反闭包、对称闭包和传递闭包的关系图。(2分,2分和2分) 3((8分)设为一偏序集,其中A={1,2,„,12},R是A上的整除关系。
(1)画出的哈斯图;(4分)
(2)求A的所有极大元和极小元(2分)
(3)求B={2,3,6}的最小上界和最大下界(2分)。
4.(8分)
判断左图是否为欧拉图,若是,请给出一欧拉回路(用阿拉伯数字在边上标明顺序即可);
若不是,请说明原因;(4分)
判断右图是否为哈密顿图,若是,请给出一哈密顿回路(用阿拉伯数字在顶点上标明顺
序即可);若不是,请说明原因(4分);
5((8分) 设G是无向简单图且δ(G)?k?2,试证明G中存在长度大于等于k+1的初级回
路(圈)。
6((8分)在一棵有3个2度顶点,2个4度顶点,其余顶点都是树叶的无向树中,应该有
几片树叶,(2分)
请画出所有这样的非同构的无向树。(6分)
3
答案及评分标准
一 选择题
CDDAC DCADD
二
1. ,,x(F(x),,y(G(y),H(x,y)))或者 ,x(F(x),,y(G(y),,H(x,y)))2. m,m,m137
3. 15
4. m=2n-2
5. 2t-1
6. {,,{,},{{,}},{,,{,}}}
7. 26
8. (该小题每空1分) p,q,p,q,p,q
三
1 (1) 前提引入 ,Q,R
(2) 前提引入 ,R
(3) (1)(2)析取三段论 ,Q
(4) 前提引入 ,(P,,Q)
(5) 置换 ,P,Q
(6) ,P (3)(5)析取三段论
若未注明推理,或标注有错,扣1分.
2 (1) 如图1
0 (2) r(R),R,R,R,I,{,a,a,,,a,b,,,b,a,,,c,d,,,b,c,},IAA
,1 s(R),R,R,{,a,a,,,a,b,,,b,a,,,c,d,,,b,c,,,d,c,,,c,b,}
2t(R),R,R,?,{,a,a,,,a,b,,,a,c,,,a,d,,,b,b,,,b,d,,b,a,,,c,d,,,b,c,}
该题要求画出三个闭包的关系图. 每个关系图2分,共6分. 边少画或多画一律判错.
4
3 (1)如图2
(2)A的极大元有:7,8,9,10,11,12
A的极小元有:1
(3)B的上界是{6,12},最小上界是6
B的下界是1,最小下界是1
哈斯图中若出现水平的边,扣1分.
4((,分)
(,)判断下图是否为欧拉图,若是,请给出一欧拉回路(用阿拉伯数字在边上标明顺序即可);若不是,
请说明原因;(4分)
答:因为该图是连通图且图中没有奇度顶点,所以该图是欧拉图(只要判断正确给2分)。欧拉回路标序如
下图:
, ,
, , 14 ,
10 11
12 , 13, 3
, , 找的欧拉回路正确再2分
(2)判断下图是否为哈密顿图,若是,请给出一哈密顿回路(用阿拉伯数字在顶点上标明顺序即可);
若不是,请说明原因(4分)
5
答:该图不是哈密顿图(2分)。取,,,,,,,,,,从图中删除,,得五个连通分支,如下图所示,所以该图不是哈密顿图。(2分)
另一证明:反证若有哈密顿圈,由于点5,7,9都是二度点,因此该哈密顿圈必包含边
(4,5)(5,6)(6,7)(7,8)(8,9)(9,4),这6条边构成一个圈,矛盾.
,
,
,
, , , ,
10 10
, , , ,
, , , ,
,((8分)设G是无向简单图且δ(G)?k?2,试证明G中存在长度大于等于k+1的初级回路(圈)。 证明:不妨设,是连通图,若G不连通,因为,的各连通分支的最小度也都大等于k,因而可对它的某个连通分支进行讨论。设u,v为G中任意两个顶点,由G是连通图,因而u,v之间存在路径,用“扩大路径法”扩大这条路径,设最后得到的“极大路径”为Γ=vv„v,则t?k,事实上若存在“极大路径” Γ=vv„vt01ts01s且s
本文档为【厦大离散数学期末试卷2009_试题 完整答案】,请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑,
图片更改请在作品中右键图片并更换,文字修改请直接点击文字进行修改,也可以新增和删除文档中的内容。
[版权声明] 本站所有资料为用户分享产生,若发现您的权利被侵害,请联系客服邮件isharekefu@iask.cn,我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。