[华南农业大学离散数学期末考试2011试卷及答案.docVIP

华南农业大学期末考试试卷（A卷） 2011-2012学年第 一 学期　 考试科目：　 离散结构 　　 考试类型：（闭卷）考试　　　 考试时间：　120 　分钟 学号 姓名 年级专业 题号 一 二 三 四 五 总分 得分 评阅人 □ 林旭东 □ 黄华伟 □ 朱梅阶 □ 黄沛杰 考试注意事项： ①本试分为试卷与答卷2部分。②所有解答必须写在答卷上，写在试卷上不得分。：在北京工作，：是北京人；则命题“在北京工作的人都是北京人。”可表示为______。 A、 B、 C、 D、 3、设 p:天冷, q:小王穿羽绒服，下列命题中，和命题“只要天冷，小王就穿羽绒服。”一样符号化为 p?q 的是______。 A、如果天不冷，则小王不穿羽绒服。 B、小王穿羽绒服仅当天冷的时候。 C、除非小王穿羽绒服，否则天不冷。 D、只有天冷，小王才穿羽绒服 4、下列哪个表达式错误_____。 A、 B、 C、 D、 5、设，定义A上的关系，则R具有的性质为______。 A、自反的　 B、对称的　　C、传递的，对称的 D、传递的 6、设V=R*,×是代数系统, R*为非零实数的集合，×为普通乘法，下面函数中是V 的自同态的是______。 A、f(x)=2x B、f(x)= -x C、 f(x)=1/x D、f(x)=x+1 7、设V=Z,+是代数系统, Z为整数的集合，+为普通加法在，则 (-2)-3= _____。 A、-8 B、8 C、-6 D、6 8、给定下列各序列，可以构成无向简单图的度数序列为______。 A、1,1,2,2,3 B、1,1,2,3,3 C、0,1,1,3,3 D、1,3,4,4,5 9、具有6 个顶点，12条边的连通简单平面图中，次数为3的面有______个。 A、5　 B、 6　　C、 7　　D、 8 10、在下面所示的4个图中，______不是单向连通图。 得分 二、填空题（本大题共 15 空，每空 2 分，共 30 分） 1、p→q 的主合取范式是____________________。 2、表达式中谓词的个体域是，将其中的量词消去，写成与之等价的命题公式为__________________。 3、若明天是星期一或星期三，我就有课。若有课，今天必备课。我今天下午备课。 所以，明天不是星期一和星期三。?将命题中的4个简单命题依次符号化为，p：明天是星期一，q：明天是星期三，r：我有课，s：我备课。则推理的形式结构为：前提：______________________________；结论：_____________________。 4、的前束范式为：____________________。 5、设R，S是集合上的两个关系，其中，,则____________________。 6、设偏序集的哈斯图如右所示，若A的子集，则B的最大下界为_____。 7、在整数集上定义二元运算，有，则关于运算 的幺元是______。 8、设a是12阶群的生成元，则a3是 阶元素 10、在右边的PERT图中，关键路径为______。1400 的不同的正因子个数为______。的非负整数解的个数有______。 14、n阶无向树至少有______片树叶。（n=2） 得分 三、计算题：（6+4+6+6，共 22 分） 1、设A={1, 2, 3, 4}，R={x，y|x?A，y?A且x+y5} （1）写出R的集合表达式和关系矩阵，画出R的关系图。 （2）画出关系R的自反闭包r(R)、对称闭包s(R)和传递闭包t(R)的关系图。 2、分别画出下面无向图A的关联矩阵和有向图B的邻接矩阵。 3、求下面带权图中v1到其它顶点的最短路径及对应的权。 4、设有5个城市，任意两城市之间的铁路造价如下（以百万元为单位）：W(v1, v2)=4, W(v1, v3)=7, W(v1, v4)=16, W(v1, v5)=10, W(v2,v3)=13, W(v2, v4)=8, W(v2, v5)=17, W(v3, v4 )=3, W(v3 ,v5)=10， W(v4, v5)=12。试求出连接5个城市的且造价最低的铁路网。 四、证明题：（本大题共 4 个小题，每题 6 分，共 24 分） 1、用等值演算法证明下面的等值式 2、设 A为整数集合，在 A′A上定义二元关系R： x,y,u,v?R ? x+y = u+v，证