《华南农业大学离散数学期末考试21试卷及答案》由会员分享，可在线阅读，更多相关《华南农业大学离散数学期末考试21试卷及答案（8页珍藏版）》请在金锄头文库上搜索。
1、0华南农业大学期末考试试卷（华南农业大学期末考试试卷（A A 卷）卷）2011-2012 学年第学年第 一一 学期学期 考试科目：考试科目： 离散结构离散结构 考试类型：（闭卷）考试考试类型：（闭卷）考试 考试时间：考试时间： 120 分钟分钟学号 姓名 年级专业 题号题号一一二二三三四四五五总分总分得分得分评阅人评阅人 林旭东林旭东 黄华伟黄华伟 朱梅阶朱梅阶 黄沛杰黄沛杰考试注意事项：考试注意事项：本试题分为试卷与答卷本试题分为试卷与答卷 2 2 部分。试卷有部分。试卷有五五大题，共大题，共 4 4 页。页。 所有解答必须写在答卷上，写在试卷上不得分。所有解答必须写在答卷上，写在试卷上不得
2、分。一、选择一、选择题题（本大题共 10 小题，每小题 2 分，共 20 分）1、重言式的否定是（ ）A、重言式 B、矛盾式 C、可满足式 D、 A-C 均有可能2、：在北京工作，：是北京人；则命题“在北京工作的人都是)(xAx)(xBx北京人。 ”可表示为_。A、 )()(xBxxAB、)()(xBxAxC、 )()(xBxxAD、)()(xBxAx3、设 p:天冷, q:小王穿羽绒服，下列命题中，和命题“只要天冷，小王就穿羽绒服。 ”一样符号化为 pq 的是_。A、如果天不冷，则小王不穿羽绒服。B、小王穿羽绒服仅当天冷的时候。C、除非小王穿羽绒服，否则天不冷。得分得分1装订线D、只有天冷，
3、小王才穿羽绒服4、下列哪个表达式错误_。A、 BxxABxAx)()(B、 BxxABxAx)()(C、 )()()()(xxQxxPxQxPxD、 )()()()(xxQxxPxQxPx5、设，定义 A 上的关系，则10,.,3 , 2 , 1A10,|,yxSyxyxRR 具有的性质为_。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
4、、-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、 6 C、 7 D、 810、在下面所示的4个图中，_不是单向连通图。二、填空题题（本大题共 15 空，每空 2 分，共 30 分）得分得分A、B、C、D、21、pq 的主合取范式是_。2、表达式中谓词的个体域是，将其中的量词消去，写成),(yxyAx,baD 与之等价的命题公式为_。3、若明天是星期一或星期三，我就有课。若有课，今天必备
5、课。我今天下午备课。 所以，明天不是星期一和星期三。 将命题中的4个简单命题依次符号化为，p：明天是星期一，q：明天是星期三，r：我有课，s：我备课。则推理的形式结构为：前提：_；结论：_。4、的前束范式为：_。),(),(yxyGyxyFx5、设R，S是集合上的两个关系，其中4 , 3 , 2 , 1A，,4 , 4,3 , 2,2 , 2,1 , 1R4 , 4,2 , 3,3 , 2,2 , 2,1 , 1S则_。1)(SRo6、设偏序集的哈斯图如右所示，若A的子集，,A5 , 4 , 3B则B的最大下界为_。7、在整数集上定义二元运算 ，有，ZZyx ,2yxyx则关于运算 的幺元是_
6、。8、设a是12阶群的生成元，则a3是 阶元素9、若连通平面图 G 有 4 个结点，3 个面，则 G 有 条边。10、在右边的PERT图中，关键路径为_。11、一颗带权为2,3,5,7,8,9的最优2元树，其权为_。12、1400 的不同的正因子个数为_。13、满足等式的非负整数解的个数有_。84321xxxx14、n阶无向树至少有_片树叶。 （n=2）三、计算题三、计算题：（6+4+6+6，共 22 分）得分得分1.5CM3装订线1、设A=1, 2, 3, 4，R=|xA，yA且x+y,R x+y = u+v，证明：R是AA上的等价关系。3、符号化下列各命题，并说明结论是否有效（用推理规则）
7、 。甲乙丙丁四人参加拳击比赛，如果甲获胜，则乙失败；如果丙获胜，则乙也获胜，如果甲不获胜，则丁不失败。所以，如果丙获胜，则丁不失败。4、设是群，给定aG，令H=y y*a=a*y, yG，证明：是G的子群。五、应用题（共五、应用题（共 4 分）分）若有 n 个人，每个人都恰有三个朋友，则 n 必为偶数。4华南农业大学期末考试参考答案（华南农业大学期末考试参考答案（A A 卷）卷）一、选择一、选择题题（本大题共 10 小题，每小题 2 分，共 20 分）1B2D3C4C5B6C7D8B9D10C二、填空题题（本大题共 15 空，每空 2 分，共 30 分）1、 pq ； 2、； ),(),(),
8、(),(bbAabAbaAaaA3、 (pq)r, rs, s ； p q ；4、；),(),(zxGyxFzyx5、； 6、 2 ；7、 2 1,1 ,2,2 ,2,3 ,3,2 ,3,34,4 ； 8、 4 ； 9、 5 ； 10、v1v3v7v8； 11、 83 ； 12、 24 ； 13、 165（或，或） 14、 2 8 11C3 11C三、计算题：（三、计算题：（6+4+6+6，共 22 分）1、 R的集合表达式： 1 , 3,2 , 2,1 , 2,3 , 1,2 , 1,1 , 1RR的关系矩阵: R的关系图：0000000100110111R的自反闭包r(R)关系图： 对称闭
9、包s(R)关系图： 传递闭包t(R)关系图：得分得分得分得分得分得分1.5CM5装订线2、图A的关联矩阵： 图B的邻接矩阵：1000011000001100111200002000100100103、解：用标号法解题如下：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
10、 v4 v6 ，对应的权为94、 解：解：将本题用带权图来描述，如下图(a)，于是求解此题便成为求带权图的 最小生成树问题。按 Kruskal 算法，下图中(b)-(e) 就是求解最小生成树的过程。6总造价=3+4+7+10=24万元四、证明题：（四、证明题：（本大题共 4 个小题，每题 5 分，共 20 分）1、 证明：证明：从左边开始演算:)()(RPQP)()(RPQP)(RQP)(RQP2、证明：、证明：(1)自反性：对于任意的AyxA,Ryxyxyxyx,(2)对称性：对于任意的Rvuyx,Ryxvuyxvuvuyx,(3)传递性：对于任意的RsrvuRvuyx,Rsryxsryxs
11、rvuvuyx,得分得分7装订线3、证明：证明：1. 解：设 p: 甲获胜； q：乙获胜；r：丙获胜；s：丁不败（或丁获胜） 。前提为：； 结论为：qpqr sp sr （1） r（2） qr （3） q（4） qp（5） p（6） sp （7） s4、证明、证明： 对于任一aG，e*a=a*e，群G的幺元 e H, 所以H是 G 的非空子集。 任取 a, bH，下面证明 a*b1与 G 中所有的元素都可交换. xG，有 (a*b1) *x = a*b1*x = a*b1* (x1) 1 = a* (x1*b) 1 = a* (b*x1) 1= a* (x*b1) = (a*x) *b1 = (x*a) *b1 = x* (a*b1)由此可知，a*b1 H 由子群判定定理可知是G的子群。五、应用题：（五、应用题：（共4分）证明：证明：证明：将每个人用结点表示，当两个人是朋友时，则对应两结点连一条边，则得一无向图。因为每个人恰有三个朋友，所以，EVG,，由任意图奇数度结点一定是偶数个，可知，此图结点数一定是)(,3)deg(Vuu偶数。得分得分
