华南农业大学期末考试试卷（A卷）
2012-2013学年第 一 学期 考试科目： 离散结构 考试类型：（闭卷）考试 考试时间： 120 分钟 学号 姓名 年级专业
装题号 得分 评阅人 考试注意事项： 一 二 三 四 总分 订 ①本试题分为试卷与答卷2部分。试卷有四大题，共6页。 ②所有解答必须写在答卷上，写在试卷上不得分。
线得分 一、选择题（本大题共 25 小题，每小题 2 分，共 50 分）
1、矛盾式的否定是______。
A、重言式 B、矛盾式 C、可满足式 D、 A-C均有可能 2、个体域为全体人类，B(x,y)：y是x的最好朋友；则命题“每个人恰有一个最好的朋友。”可表示为______。
A、?x?y(B(x,y)) B、?x?y(B(x,y)) C、?x?y?z(B(x,y)?(z?y)??B(x,z)) D、?x?y?z(B(x,y)?((y?z)??B(x,z)))
3、甲乙丙丁四人的车分别为白色、银色、蓝色和红色。在问到他们各自车的颜色时，甲说：“乙的车不是白色的”。乙说：“丙的车是红色的”。丙说：“丁的车不是蓝色的”。丁说：“甲、乙、丙三人中有一个人的车是红色的，而且只有这个人说的是真话”。如果丁说的是实话，那么以下说法正确的是：
A、甲的车是白色的，乙的车是银色的 B、乙的车是蓝色的，丙的车是红色的 C、丙的车是白色的，丁的车是蓝色的 D、丁的车是银色的，甲的车是红色的
1
4、甲、乙和丙，一位是山东人，一位是河南人，一位是湖北人。现在只知道：丙比湖北人的年龄大，甲和河南人不同岁，河南人比乙年龄小。由此可以推知下列说法正确的是______。
A、甲不是湖北人 B、河南人比甲年龄小 C、河南人比山东人年龄大 D、湖北人年龄最小
5、某市要建花园或修池塘，有下列4种假设：修了池塘要架桥；架了桥就不能建花园；建花园必须植树；植树必须架桥。据此不可能推出的是：
A、最后有池塘 B、最后一定有桥
C、最后可能有花园 D、池塘和花园不能同时存在 6、设 p:他主修计算机科学, q:他是新生，r:他可以从校园内访问因特网，下列命题“除非他主修计算机科学，否则只要他是新生就不可以从校园内访问因特网。”可以符号化为______。D
A、?p??q?r B、p?q?r C、p??q?r D、?p?q??r 7、下列说法不正确的是：______。
A、R是自反的，则R2一定是自反的 B、R是反自反的，则R2一定是反自反的 C、R是对称的，则R2一定是对称的 D、R是传递的，则R2一定是传递的 8、下列关于关系的等式不成立的是______。
A、(F?G)?H?F?(G?H) B、(F?G)?1?F?1?G?1
C、(F?G)?H?(F?H)?(G?H) D、(F?G)?H?(F?H)?(G?H)
10}，定义A上的关系R?{?x,y?|x,y?S?x?y?10}，则R9、设A?{1,2,3,...,具有的性质为______。
2
装订线
A、自反的 B、对称的 C、传递的，对称的 D、传递的 10、设R和S定义在P上，P是所有人的集合，R?{?x,y?|x,y?P?x是y的
父亲}，S?{?x,y?|x,y?P?x是y的母亲}，则关系{?x,y?|x,y?P?y是的x外祖母}的表达式是：______。
A、S?1?S B、R?S C、S?1?S?1 D、S?R 11、在5元素集合上有______个不同的等价关系恰有3个不同的等价类。
A、25 B、21 C、 10 D、6
12、设S?{0,1}，F是S中的字符构成的长度不超过4的串的集合，即
F?{?,0,1,00,01,...,1111}，其中?表示空串，在F上定义偏序关系R：?x,y?F，?x,y??R?x是y的前缀，则?F,R?的最小元是：______。
A、? B、0 C、0,1,? D、不存在 13、设Z??{x|x?Z?x?0}，*表示求两个数的最小公倍数的运算，则对于*运算的幺元是______。
A、0 B、1 C、 任意值 D、不存在 14、设R是实数集合，“?”为普通乘法，则代数系统
A、群 B、阿贝尔群 C、半群 D、含幺半群 15、非同构的无向的4阶自补图有______个。
A、0 B、1 C、 2 D、3
16、在一棵树中有7片树叶，3个3度结点，其余都是4度结点，则该树有______个4度结点。
A、1 B、2
C、3 D、4
17、设?Z6,??是代数系统，Z6?{0,1,2,3,4,5}，?为模6加法运算，则2?5= _____。
A、10 B、1/10 C、4 D、2 18、给定下列各序列，可以构成无向简单图的度数序列为______。
3
A、1,1,2,2,3 B、1,1,2,3,3 C、0,1,1,3,3 D、1,3,4,4,5 19、具有6 个顶点，12条边的连通简单平面图中，次数为3的面有______个。
A、5 B、 6 C、 7 D、 8
20、设A={?，{1}，{1，3}，{1，2，3}}则A上包含关系“?”的哈斯图为_______。
A、
B、
C、
D、
21、以下无向图中，不是二部图的是_____。
A、 B、
C、 D、 22、下图中既不是欧拉图，也不是哈密尔顿图的是_______。
A、 B、 C、
D、
23、以下无向图中，不是平面图的是_____。
A、 B、 C、
D、
24、由0、1、2、3这四个数字能构成_____个3位数。
A、64 B、48 C、24 D、18 25、四个人比赛，名次允许并列，则有______种比赛结果。
A、256 B、72 C、75 D、24
4
1.5CM 装订线
得分 二、计算题：（本大题共 5 个小题，每题 5 分，共 25 分）
1、设A={1, 2, 3, 4}，R={
2、设有7个字母在通信中出现的频率(%)如下：
a: 35% b: 20%, c: 15%, d: 10%, e: 10%, f: 5%, g: 5%
(1)以频率(或乘100)为权，求最优2元树。（3分）
(2)利用所求最优2元树找出每个字母的前缀码。（2分）
3、如下图所示的赋权图表示某七个城市V1,V2,?,V7 ，及预先算出它们之间直接通信线路造价(以百万元为单位)，试给出一个设计方案，使得各城市之间能够通信而且总造价最小，并计算出最小造价。
V2 5 V4 1 8 V1 2 4 7 V6 10 V7 3 V3 6 V5 9
4、通过并行的执行某些语句，计算机程序可以执行得更快。语句与前面语句的相关性可以表示成有向图，用顶点表示每条语句，请画出语句执行顺序图。例如s2一定在s1后才能执行，就画一条由s1指向s2的有向边。 s1: x=0 s2: x=x+1 s3: y=2 s4: z=y s5: x=x+2 s6: y=x+z s7: z=4 5、求下面带权图中a到其它顶点的最短路径及对应的权。
b5 d5
f 4 7 a 2 3 1 2 z
3 c 6 e 5 g4
得分 三、证明题：（6+5+5+5，共 21 分） 1、构造下面推理的证明。
前提：p?(q?s)，q，p??r
5
华南农业大学 离散数学 期末考试2012试卷 2013-01-08
