华南农业大学期末考试试卷(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
![](/skin/haowen/images/icon_star.png)
![](/skin/haowen/images/icon_star.png)
![](/skin/haowen/images/icon_star.png)
![](/skin/haowen/images/icon_star.png)