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

华南农业大学期末考试试卷（A卷）2011-2012学年第 一 学期 考试科目： 离散结构 考试类型：（闭卷）考试 考试时间：120 分钟学号 姓名 年级专业 题号一二三四五总分得分评阅人 林旭东 黄华伟 朱梅阶 黄沛杰考试注意事项： 本试题分为试卷与答卷2部分。试卷有五大题，共4页。所有解答必须写在答卷上，写在试卷上不得分。得分一、选择题（本大题共 10 小题，每小题 2 分，共 20 分）1、重言式的否定是（ ）A、重言式 B、矛盾式 C、可满足式 D、 A-C均有可能2、：在北京工作，：是北京人；则命题“在北京工作的人都是北京人。”可表示为_。A、 B、C、 D、3、设 p:天冷, q:小王穿羽绒服，下列命题中，和命题“只要天冷，小王就穿羽绒服。”一样符号化为 pq 的是_。A、如果天不冷，则小王不穿羽绒服。B、小王穿羽绒服仅当天冷的时候。C、除非小王穿羽绒服，否则天不冷。D、只有天冷，小王才穿羽绒服4、下列哪个表达式错误_。A、 B、 C、 D、 5、设，定义A上的关系，则R具有的性质为_。A、自反的 B、对称的C、传递的，对称的 D、传递的6、设V=是代数系统, R*为非零实数的集合，为普通乘法，下面函数中是V 的自同态的是_。A、f(x)=2x B、f(x)= -x C、 f(x)=1/x D、f(x)=x+17、设V=是代数系统, Z为整数的集合，+为普通加法在，则 (-2)-3= _。A、-8 B、8 C、-6 D、68、给定下列各序列，可以构成无向简单图的度数序列为_。A、1,1,2,2,3 B、1,1,2,3,3 C、0,1,1,3,3 D、1,3,4,4,59、具有6 个顶点，12条边的连通简单平面图中，次数为3的面有_个。A、5 B、 6C、 7D、 810、在下面所示的4个图中，_不是单向连通图。A、B、C、D、得分二、填空题（本大题共 15 空，每空 2 分，共 30 分）1、pq 的主合取范式是_。2、表达式中谓词的个体域是，将其中的量词消去，写成与之等价的命题公式为_。3、若明天是星期一或星期三，我就有课。若有课，今天必备课。我今天下午备课。 所以，明天不是星期一和星期三。将命题中的4个简单命题依次符号化为，p：明天是星期一，q：明天是星期三，r：我有课，s：我备课。则推理的形式结构为：前提：_；结论：_。4、的前束范式为：_。5、设R，S是集合上的两个关系，其中，,则_。6、设偏序集的哈斯图如右所示，若A的子集，则B的最大下界为_。7、在整数集上定义二元运算，有，则关于运算 的幺元是_。8、设a是12阶群的生成元，则a3是 阶元素9、若连通平面图G有4个结点，3个面，则G有 条边。10、在右边的PERT图中，关键路径为_。11、一颗带权为2,3,5,7,8,9的最优2元树，其权为_。12、1400 的不同的正因子个数为_。13、满足等式的非负整数解的个数有_。14、n阶无向树至少有_片树叶。（n=2）得分1.5CM三、计算题：（6+4+6+6，共 22 分）1、设A=1, 2, 3, 4，R=|xA，yA且x+y5（1）写出R的集合表达式和关系矩阵，画出R的关系图。（2）画出关系R的自反闭包r(R)、对称闭包s(R)和传递闭包t(R)的关系图。2、分别画出下面无向图A的关联矩阵和有向图B的邻接矩阵。v1v2v3v4图Be1e2e3e5e4v1v2V4V3图Ae2e1e3e4e53、求下面带权图中v1到其它顶点的最短路径及对应的权。v1v4v2v3v5v631064322244、设有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为整数集合，在 AA上定义二元关系R：,R x+y = u+v，证明：R是AA上的等价关系。3、符号化下列各命题，并说明结论是否有效（用推理规则）。甲乙丙丁四人参加拳击比赛，如果甲获胜，则乙失败；如果丙获胜，则乙也获胜，如果甲不获胜，则丁不失败。所以，如果丙获胜，则丁不失败。4、设是群，给定aG，令H=y| y*a=a*y, yG，证明：是G的子群。五、应用题（共4分）若有n个人，每个人都恰有三个朋友，则n必为偶数。华南农业大学期末考试参考答案（A卷）得分一、选择题（本大题共 10 小题，每小题 2 分，共 20 分）1B2D3C4C5B6C7D8B9D10C得分二、填空题（本大题共 15 空，每空 2 分，共 30 分）1、 pq ； 2、； 3、 (pq)r, rs, s ； p q ；4、；5、； 6、 2 ；7、 2 ； 8、 4 ； 9、 5 ； 10、v1v3v7v8； 11、 83 ； 12、 24 ； 13、 165（或，或） 14、 2 得分1.5CM三、计算题：（6+4+6+6，共 22 分）1、 R的集合表达式： R的关系矩阵: R的关系图： R的自反闭包r(R)关系图： 对称闭包s(R)关系图： 传递闭包t(R)关系图： 2、图A的关联矩阵： 图B的邻接矩阵： 3、解：用标号法解题如下：r viv1v2v3v4v5v6003413/ v141324/ v176376/ v31047/ v3959/ v4w034769v1到v2的最短路径: v1 v2 ，对应的权为3v1到v3的最短路径: v1 v3 ，对应的权为4v1到v4的最短路径: v1 v3 v4 ，对应的权为7v1到v5的最短路径: v1 v3 v5 ，对应的权为6v1到v6的最短路径: v1 v3 v4 v6 ，对应的权为94、 解：将本题用带权图来描述，如下图(a)，于是求解此题便成为求带权图的最小生成树问题。按Kruskal算法，下图中(b)-(e) 就是求解最小生成树的过程。总造价=3+4+7+10=24万元得分四、证明题：（本大题共 4 个小题，每题 5 分，共 20 分）1、 证明：从左边开始演算: 2、证明：(1)自反性：对于任意的(2)对称性：对于任意的(3)传递性：对于任意的 3、证明：1. 解：设p: 甲获胜； q：乙获胜；r：丙获胜；s：丁不败（或丁获胜）。前提为：； 结论为：（1）（2）（3）（4）（5）（6）（7）4、证明： 对于任一aG，e*a=a*e，群G的幺元 e H, 所以H是 G 的非空子集。 任取 a, bH，下面证明 a*b-1与 G 中所有的元素都可交换. xG，有 (a*b-1) *x = a*b-1*x = a*b-1* (x-1) -1 = a* (x-1*b) -1 = a* (b*x-1) -1 = a* (x*b-1) = (a*x) *b-1