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

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