华南农业大学离散结构期末考试2010试卷

1装订线华南农业大学期末考试试卷（A卷）2010学年第一学期考试科目：离散结构考试类型：（闭卷）考试考试时间：120分钟学号姓名年级专业题号一二三四总分得分评阅人□林旭东□黄华伟□朱梅阶考试注意事项：①本试题分为试卷与答卷2部分。试卷有四大题，共5页。②所有解答必须写在答卷上，写在试卷上不得分。一、选择题（本大题共15小题，每小题2分，共30分）1、给定语句如下，则______是复合命题。A、15是素数B、2x+23C、小王和小李是好朋友。D、小王和小李成绩都好。2、给定下列语句中，是真命题的是______。A、这个男孩真勇敢呀。B、明年5月1日是晴天。C、如果2+2=6，则3是奇数。D、2x+233、下列哪个表达式错误_____。A、)x(xQ)x(xP))x(Q)x(P(xB、))()(()()(xQxPxxxQxxPC、)()())()((xxQxxPxQxPx得分2D、)()())()((xxQxxPxQxPx4、斯科特先生、他的妹妹、儿子、女儿都是网球选手，关于这四个人，有如的情况：最佳选手的孪生同胞与最差选手性别不同；最佳选手与最差选手年龄相同。则_______是最佳选手。A、斯科特B、斯科特妹妹C、斯科特儿子D、斯科特女儿5、)(xM：x是人，)(xF：x活百岁以上；则“有人能活百岁以上”可表示为______。A、)()(xMxFB、)()(xMxxFC、))()((xMxFxD、))()((xFxMx6、给定解释I如下：个体域ID为整数集合；ID中特定元素1,010aa；ID特定函数yxyxgyxyxf),(,),(；ID上特定谓词),(yxF为yx。给定下面各公式：A、)),(),,((11axgaxfFB、)),(),,((yxgyxfyFxC、)),(),,((yxgyxfyFxD、)))),(),,(((),((0yxgyxfFxayFy则公式________真值为假。7、若3||A，则AA上可以定义______个二元关系。A、9B、27C、81D、5128、下列关于关系的等式不成立的是______。3装订线A、)()(HGFHGFB、111)(GFGFC、)()()(HGHFHGFD、)()()(HGHFHGF9、若关系R的关系矩阵为对称矩阵，则关系R一定具有______。A、自反性B、对称性C、反对称D、传递性10、若T为树，以下叙述不正确的是_____。A、T是连通的且每个点都是割点B、T的每对顶点之间有唯一的一条路径C、T是连通的且每条边都是割边D、T是连通的且不含回路11、在下列选项中，不是群的是_____。A、),(Q，Q为有理数，*为乘法运算B、),(R，R为非零实数集，为乘法运算C、全体实对称矩阵集合，对于矩阵的加法运算D、),(Q，Q为有理数，+为加法运算12、给定下列各序列，可以构成无向简单图的度数序列为______。A、1,1,2,2,3B、1,1,2,2,2C、0,1,3,3,3D、1,3,4,4,513、5个顶点非同构的根树有______个。A、7B、8C、9D、1014、下面编码______不是前缀码。A、11，00，10，01B、01，11，011，1001C、101，11，001，011，0104D、010，11，011，1011，1001，1010115、无向完全带权图nK)2(n中，按权计算最多有______条不同的哈密顿回路。A、!nB、)!1(nC、2/)!1(nD、2/!n二、填空题（本大题共15空，每空2分，共30分）1、若有限集合A上的等价关系R有三个等价类，则其关系图的连通分支数为_______。2、设个体域为整数集合，命题)0)()((yxyx的真值为：______。3、)),(),((yxyGyxFx的前束范式为：______。4、设R是集合A上的二元关系，如果关系R同时具有自反性、______和传递性，则称R是A上的偏序关系。5、设}10,...,3,2,1{S，定义S上的关系}10,|,{yxSyxyxR，则R具有______性质。6、在有理数集Q上定义二元运算，Qyx,有xyyxyx，则关于运算的幺元是______。7、在群、半群、独异点中，______满足消去律。8、35条边，每个顶点的度数至少为3的图最多有______个顶点。9、设n阶图G中有m条边，每个顶点的度数不是k就是1k，若G中有_____个k度顶点（用关于m、n、k的表达式表示）。10、若10阶平面图G中有5个面，则图G中有______条边。11、一颗带权为1，2，3，4，5，6的最优三元树，其权为______。12、群,6Z中（为模6加法运算），则5的阶为______。13、若某个简单图不是欧拉图但具有欧拉通路，则图中奇度数的顶点个数一定为______。14、n个顶点的无向树是平面图，它的无穷面的次数为：_______。15、求满足不等式6321xxx的正整数解的个数有______。得分5装订线三、计算题：（本大题共4个小题，每题5分，共20分）1、画出下列集合关于整除关系的哈斯图}24,15,12,8,6,5,4,3,2,1{，并指出它的极小元、最小元、极大元、最大元。2、已知：有向图EVD,，}4,3,2,1{V，E={3,2,4,1,2,1，1,3,4,2,4,3}，求有向图D的邻接矩阵和可达矩阵。3、带有n个顶点的2元完全正则树有多少树叶？4、设有a、b、c、d、e、f、g七个人，他们分别会讲的语言如下：a：英，b：汉、英，c：英、西班牙、俄，d：日、汉，e：德、西班牙，f：法、日、俄，g：法、德，能否将这七个人的座位安排在圆桌旁，使得每个人均能与他旁边的人交谈？四、证明题：（本大题共4个小题，每题5分，共20分）1、)()(RPQRQP2、设1R和2R是集合A上的等价关系，且1221RRRR，证明：21RR是集合A上的对称关系。3、设G为n阶无向简单图，证明：若G为自补图（若一个图的补图为本身则称为自补图），则kn4或14kn，其中k为正整数。4、证明：设,R是一个代数系统，*是R上的二元运算，,,Rbaabbaba，则0是幺元，且,R是含幺半群。（R为实数集合）。得分1.5CM