厦大离散数学期末试卷2009-试题+完整答案.doc

(完整版)厦大离散数学期末试卷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(      ）。
A．只是约束变元
B．只是自由变元
C．既非约束变元又非自由变元
D．既是约束变元又是自由变元

4。 下列关系中，（ ）不是等价关系。
A. 非空集合的幂集的元素间包含关系；
B. 集合之间的等势关系；
C. 公式之间的等值关系；
D. 图之间的同构关系.
5。 下面等值式中,( ）是不正确的.
A.
B.
C.
D.
6．下列关于集合的势的叙述中，（ ）是错误的.
A. 实数集比自然数集优势;
B。 任一无限集合都存在与自己等势的真子集;
C。 集合之间的优势关系是偏序关系；
D。 有理数集比整数集优势.
7．设A,B,C是集合，F是关系，，则下列式子中不正确的是（ ）。A． B.
C。 D。
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快.则命题“不存在比所有火车都快的汽车"符号化形式为_________________。
2． 公式的主析取范式为______________。
3． 集合A={a，b，c,d｝上的等价关系共有______个.
4． 自对偶图的顶点数n和边数m之间满足关系式为m =_______________。
5．设T是有t片树叶的2叉正则树，则T应该有_______个顶点。
6．P（{Φ，｛Φ}｝） = _｛Φ，{Φ},{Φ,{Φ}｝,{{Φ｝}}____.
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=｛<a，a>，〈a，b>，<b，a〉，〈c,d>,<b,c>｝ 求：（1）画出R的关系图.(2分）
（2）R的自反闭包、对称闭包和传递闭包的关系图.（2分，2分和2分)
3．（8分）设〈A,R>为一偏序集，其中A=｛1，2，…，12｝,R是A上的整除关系。
（1）画出<A，R〉的哈斯图;（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分）
答案及评分标准

一 选择题
CDDAC DCADD
二
1。
或者
2.
3。 15
4. m=2n-2
5。 2t-1
6.
7. 26
8。 （该小题每空1分）

三
1 （1) 前提引入
（2） 前提引入
(3） (1）(2）析取三段论
(4） 前提引入
（5） 置换
(6） （3)（5）析取三段论

若未注明推理规则，或标注有错,扣1分。

2 （1） 如图1

（2)

该题要求画出三个闭包的关系图。 每个关系图2分,共6分. 边少画或多画一律判错.
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分）。欧拉回路标序如下图：
８
１
２
３
４
５
６
７
９
10
11
12
133
14

找的欧拉回路正确再2分
（2）判断下图是否为哈密顿图,若是，请给出一哈密顿回路(用阿拉伯数字在顶点上标明顺序即可）;若不是，请说明原因（4分）
答：该图不是哈密顿图(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之间存在路径，用“扩大路径法”扩大这条路径，设最后得到的“极大路径"为Γt=v0v1…vt,则t≥k，事实上若存在“极大路径” Γs=v0v1…vs且s<k，则v0只能与Γs中的顶点相邻，因为G为简单图,所以与v0相邻的顶点最多为s个,而s<k，这与δ(G）≥k矛盾，所以“极大路径”长度大等于k.
在Γt上构造圈，由于δ(v0）≥δ(G)≥k≥2，因而v0除与Γt上的v1相邻外，还存在Γt上的k-1个顶点与v0相邻，则为一个圈且长度大等于k+1。
注意：也可直接设Γ是G的最长路径.
６．(8分)在一棵有3个2度顶点，2个4度顶点,其余顶点都是树叶的无向树中，应该有几片树叶？（2分）
请画出所有这样的非同构的无向树.（6分)
答:设树叶有x片，则边数m=3+2+x—1=4+x，由握手定理知，2m=2*（4+x）=∑d(vi)=3＊2+2*4+x 解得x=6，所以应该有６片树叶。共有十个非同构的无向树，如下：
(1) 两个４度点相邻的情况：

(2) 两个４度点中间有一个２度点的情况：

(3) 两个４度点中间有两个２度点的情况：

(4) 两个４度点中间有三个２度点的情况：

(请酌情扣分)

9