内容发布更新时间 : 2024/10/12 8:12:25星期一 下面是文章的全部内容请认真阅读。
中南大学考试试卷
2010 --2011 学年 上 学期期末考试试题 时间100分钟 离散数学课程48学时3学分 考试形式：闭卷
专业年级：计应09，信息安全09， 总分100分，占总评成绩70% 注：此页不作答题纸，请将答案写在答题纸上
一、判断题 (本大题共10小题，每小题1分，共10分) 1、阶大于1的树都是二部图。 （ T ）
2、?xP(x) ∧?xQ (x) => ?x (P (x)∧Q (x)) （ F ） 3、空集是任何集合的子集。 （ T ） 4、若R和S是自反的，则R?S是自反的。（T ） 5、若R和S是对称的，则R?S是对称的。（ F ）
6、任何一个合式公式都可以化简为只含逻辑运算符┐和∧的形式。 （ T ） 7、若无向图中恰有两个度为奇数的结点，则这两个结点必相互可达。 （T ） 8、
二、单向选择与填空题(本大题共20小题，每小题2分，共40分)
1、关于命题变元P1, P2,…, Pn的指派共有（ B ）种 A、 2n B、2n C、 n2 D、 22n
2、设P：我将去镇上 Q：我有时间。命题“我将去镇上，仅当我有时间”符号化为（ A ）
? A、P?Q B、Q ? P C、 P???Q D、? Q ???P
3、下面哪一个命题是假命题（ B ）
A、如果2是偶数，那么一个公式的主析取范式唯一 B、如果2是偶数，那么一个公式的主析取范式不唯一 C、如果2是奇数，那么一个公式的主析取范式唯一 D、如果2是奇数，那么一个公式的主析取范式不唯一 4、下列各式中不正确的是（ C ） A、?x(P(x)∨Q(x)) ? ?xP(x)∨?xQ(x) B、?x(P(x)∧Q(x)) ? ?xP(x)∧?xQ(x) C、?x(P(x)∨Q(x)) ? ?xP(x)∨?xQ(x) D、?x (P(x)∧Q) ? ?x P(x)∧Q
5、若公式A(P,Q,R)的主合取范式为∏（0，1，4，5），则公式A(P,Q,R)的主析取范式为（ C ）
A、∑（0，1，4，5） B、 ∏（0，1，4，5）
C、∑（2，3，6，7） D、 ∏（2，3，6，7） 6、设A={a,{a}},下列选项错误的是（ B ）
A、{a}? P(A) B、{a}?? P(A) C、{{a}}? P(A) D、{{a}}? P(A)
7、设集合A={a,b,c}, R是A上的二元关系，R={
A、反自反的 B、反对称的 C、可传递的 D、不可传递的 8、R是反对称的当且仅当（ D ）
A、IA?R B、{a}R ∩IA?=ф C、R=R-1 D、R∩R-1 ?IA? 9、任何无向图中结点间的可达系是（ B ）
A、偏序关系 B、等价关系 C、相容关系 D、拟序关系
10、设集合A={a,b,c}，则A上可以形成（ C ）种不同的等价关系
A、3 B、4 C、5 D、 6
11、Z是整数集合，Z+表示非负整数集合，函数f定义为：Z? Z+，f (x)=|x|，则f是（ B ）
A、单射 B、满射 C、双射 D、恒等
12、设N是自然数集合，f和g是N到N的函数，且f (n)=2n+1,g (n)=n2， 则复合函数f。g (n)=( C )
A、n4 B、4n+3 C、2n2+1 D、(2n+1)2
13、R是实数集，*为普通乘法，则
A、半群 B、独异点 C、群 14、若简单连通平面图G有4个结点，3个面，则G有（ C ）边 A、3 B、4 C、5 D、2 15、一棵树有两个2度顶点，一个3 度顶点，三个4 度顶点，则该树有（ D ）片树叶
A、2 B、7 C、8 D、9
16. 设A={1，2，3}，B={a,b,c},则从A到B有 6 个不同的双射函数。 17. 11阶的群有 2 个不同的子群。
18．设L（x）:x是闪光的.G(x):x是金子。命题“闪光的未必是金子” 符号化为 ┐x(L(x)→
G(x)) 。
19、设A中有n个元素，则A上有__2 n__个不同的既是对称的又是反对称的 二元关系。
20、设A是非空有限集，代数系统（P（A），∪，∩）中，P（A）对∪运算的零元是 A ，P（A）对∩运算的单位元（么元）是 A 三、证明题(共20 分) 1、（10分）请将下列命题符号化，并进行形式证明
每个智力正常并且勤奋的人都可以获得成功,有些人不曾获得过成功,所以有
些人智力不正常或者不勤奋。
（注：设个体域为全体人的集合。Z(x): x智力正常； Q(x): x勤奋, S(x):x获得成功）
2、（10分）设
四、计算及作图题(共30分)
?Q∨P∧Q∧R的主析取范式和主合取范式。 1、（10分）求解命题公式F=P∧
2、（10分）设A={a、b、c}，作出A的所有划分；设A的所有划分构成的集合是P，画出 3、（10分）请用Huffman算法求出检索频率分别为1,2,3,5,7,12的结点A，B，C，D，E，F的最优树，并根据这棵最优树写出这些字符的Huffman编码（前缀码） 4、（10分）假设现在要铺设一个连接各个城市的光纤通信网络，城市之间可以铺设网线的情况如下图，图中边上的数字表示两城市之间需铺设的网线长度，请找到一种最优的铺设方案，能让网络连通，并使得所用网线长度最短。画出最优方案的设计图，并写出所需网线的长度。 a 8 f 8 4 229 7 7 e 3g 4c 125 d 3 h 413 b 注：3，4 任选一题。 3、真真的心，想你；美美的意，恋你；暖暖的怀，抱你；甜甜的笑，给你；痴痴的眼，看你；深深的夜，梦你；满满的情，宠你；久久的我，爱你！ 4、不管从什么时候开始，重要的是开始以后不要停止；不管在什么时候结束，重要的是结束以后不要后悔。爱情来了，你还在犹豫么？ 5、美女，我注意你好久啦，就是不知道怎么表白。我翻来覆去，思来想去，最终想到一个大胆的办法，我要俘虏你的心，让你爱上我。爱上了吗？ 6、对你的爱意，早已飞过万水千山，飞到你眼前，请你睁开眼，仔细看认真听，我的眼睛为你明亮，我的嗓音为你歌唱，来吧，让我们一起舞动爱情之歌！ 7、爱你没商量，你的眼睛眨一下，我就死去，你的眼睛再眨一下，我就活过来，你的眼睛不停地眨来眨去，于是我便死去活来！ 8、因为深爱，找不到词汇诠释，因为深爱，找不到言语概括，因为深爱，只能发条短信，轻声说一声“我爱你”,这不是三个字，而是一辈子！ 9、我对你的心是鲜啤酒，清澈甘冽；我对你的情是葡萄酒，味美甘甜；我对你的爱是刀烧酒，热情浓烈；醉倒在怀，无限爱恋。 10、人生短短几十年，不要给自己留下了什么遗憾，想笑就笑，想哭就哭，该爱的时候就去爱，无谓压抑自己。人生的苦闷有二，一是欲望没有被满足，二是它得到了满足。 11、一片琼花天庭落，万里江山披银河，冰凌也有相思苦，写意窗花含泪说，昙花一现夜梦短，早有晨光盼春歌。想你，我的心会和你一起启程，祈祷每一个黎明。 12、戒指好比爱情，戴在手上，也是戴在心上；伤在心上，便也伤在手上。不敢碰的，是那心里的伤；不愿摘的，是那难舍的爱。 13、在追求爱情的列车上，透过车窗，可以欣赏到许多优美的景色，但是，请不要留恋，因为终点站才是真正的目的地。但愿我能够成为你永远的终点站！ 14、爱一个人真的好难，让我欢喜让我忧！如果不让我去爱你的话，我会更难受，更彷徨。所以为了我自己，我还是爱着你吧！ 15、诚挚的微笑，每一次心跳，或许寂然无声，却胜过虚幻的海誓山盟；真情的碰撞，灵魂的契合，或许不够浪漫，却胜过无数的真情告白。 16、此时此刻我又想起了你，想你的感觉是一种酸酸的痛！不能打电话告诉你，只想用文字亲亲你！记住爱你的人始终是我！ 17、爱你一万年，夸张！爱你五千年，无望！爱你一千年，荒唐！爱你一百年，太长！接连爱你七十年，只要我身体健康，就是我的强项！ 18、如果不爱你，不会为你守着誓言，如果不爱你，不会承受一切的罪恶感，如果不爱你，不会因你而绽放幸福的光彩。 19、一个犀利并朦胧眼神，传递心中纠结情感，我们的距离愈近或愈远。发条简朴并低调的信息，尽享真情互动，指尖点点，送你的却是心中真情满满。 20、上帝给了我这份缘，所以我每天都在天堂。生活里因为有了爱，所以我身边幸福弥漫。日子里面有了你，所以天天我都很美。