资源描述：
《华南农业大学 离散数学 期末考试2011试卷及答案》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、装订线华南农业大学期末考试试卷（A卷）2011-2012学年第一学期 考试科目： 离散结构 考试类型：（闭卷）考试 考试时间： 120 分钟学号姓名年级专业题号一二三四五总分得分评阅人□林旭东□黄华伟□朱梅阶□黄沛杰考试注意事项：①本试题分为试卷与答卷2部分。试卷有五大题，共4页。②所有解答必须写在答卷上，写在试卷上不得分。得分一、选择题（本大题共10小题，每小题2分，共20分）1、重言式的否定是（）A、重言式 B、矛盾式 C、可满足式 D、A-C均有可能2、：在北京工作，：是北京人；则命题“在
2、北京工作的人都是北京人。”可表示为______。A、B、C、D、3、设p:天冷,q:小王穿羽绒服，下列命题中，和命题“只要天冷，小王就穿羽绒服。”一样符号化为p®q的是______。A、如果天不冷，则小王不穿羽绒服。B、小王穿羽绒服仅当天冷的时候。C、除非小王穿羽绒服，否则天不冷。7装订线D、只有天冷，小王才穿羽绒服4、下列哪个表达式错误_____。A、B、C、D、5、设，定义A上的关系，则R具有的性质为______。A、自反的 B、对称的 C、传递的，对称的D、传递的6、设V=是代数系
3、统,R*为非零实数的集合，×为普通乘法，下面函数中是V的自同态的是______。A、f(x)=2xB、f(x)=-xC、f(x)=1/xD、f(x)=x+17、设V=是代数系统,Z为整数的集合，+为普通加法在，则(-2)-3=_____。A、-8B、8C、-6D、68、给定下列各序列，可以构成无向简单图的度数序列为______。A、1,1,2,2,3B、1,1,2,3,3C、0,1,1,3,3D、1,3,4,4,59、具有6个顶点，12条边的连通简单平面图中，次数为3的面有______个。A
4、、5 B、6 C、7 D、810、在下面所示的4个图中，______不是单向连通图。A、B、C、D、得分二、填空题（本大题共15空，每空2分，共30分）1、p→q的主合取范式是____________________。7装订线2、表达式中谓词的个体域是，将其中的量词消去，写成与之等价的命题公式为__________________。3、若明天是星期一或星期三，我就有课。若有课，今天必备课。我今天下午备课。所以，明天不是星期一和星期三。 将命题中的4个简单命题依次符号化为，p：明天是星期一，q：明天
5、是星期三，r：我有课，s：我备课。则推理的形式结构为：前提：______________________________；结论：_____________________。4、的前束范式为：____________________。5、设R，S是集合上的两个关系，其中，,则____________________。6、设偏序集的哈斯图如右所示，若A的子集，则B的最大下界为_____。7、在整数集上定义二元运算，有，则关于运算的幺元是______。8、设a是12阶群的生成元，则a3是阶元素9、若连通平面
6、图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={
7、xÎA，yÎA且x+y<5}7装订线（1）写出R的集合表达式和关系矩阵，画出R的关系图。（2）
8、画出关系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)
9、=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：<,>ÎRÛx+y=u+v，证明：R是A´A上的等价关系。3、符号化下列各命题，并说明结论是否有效（用推理规则）。甲乙丙丁四人参加拳击比赛，如果甲获胜，则乙失败；如果丙
