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

1装订线华南农业大学期末考试试卷（A卷）2013-2014学年第一学期考试科目：离散结构考试类型：（闭卷）考试考试时间：120分钟学号姓名年级专业题号一二三四总分得分评阅人考试注意事项：①本试题分为试卷与答卷2部分。试卷有四大题，共6页。②所有解答必须写在答卷上，写在试卷上不得分。一、选择题（本大题共25小题，每小题2分，共50分）1、下面语句是简单命题的为_____。A、3不是偶数B、李平既聪明又用功C、李平学过英语或日语D、李平和张三是同学2、设p:他主修计算机科学,q:他是新生，r:他可以在宿舍使用电脑，下列命题“除非他不是新生，否则只有他主修计算机科学才可以在宿舍使用电脑。”可以符号化为______。A、rqpB、rqpC、rqpD、rqp3、下列谓词公式不是命题公式P→Q的代换实例的是______。A、)()(yGxFB、),(),(yxyGyxxFC、))()((xGxFxD、)()(xGxxF4、设个体域为整数集，下列公式中其值为1的是_____。A、)0(yxyxB、)0(yxxyC、)0(yxyxD、)0(yxyx得分25、下列哪个表达式错误_____。A、BxxABxAx)())((B、BxxABxAx)())((C、BxxABxAx)())((D、)())((xxABxABx6、下述结论错误的是____。A、存在这样的关系，它可以既满足对称性，又满足反对称性B、存在这样的关系，它可以既不满足对称性，又不满足反对称性C、存在这样的关系，它可以既满足自反性，又满足反自反性D、存在这样的关系，它可以既不满足自反性，又不满足反自反性7、集合A上的关系R为一个等价关系，当且仅当R具有_____。A、自反性、对称性和传递性B、自反性、反对称性和传递性C、反自反性、对称性和传递性D、反自反性、反对称性和传递性8、下列说法不正确的是：______。A、R是自反的，则2R一定是自反的B、R是反自反的，则2R一定是反自反的C、R是对称的，则2R一定是对称的D、R是传递的，则2R一定是传递9、设R和S定义在P上，P是所有人的集合，R{xPyxyx,|,是y的父亲}，S{xPyxyx,|,是y的母亲}，则关系{yPyxyx,|,是的x外祖父}的表达式是：______。A、11RRB、11SRC、11SSD、11RS10、右图描述的偏序集中，子集},,{feb的上界为_____。A、cb,B、ba,C、bD、cba,,11、以下整数序列，能成为一个简单图的顶点度数序列的是_____。A、1，2，2，3，4，53装订线B、1，2，2，3，3，5C、2，2，3，4，5，6D、1，1，2，3，4，512、设无向图G的关联矩阵为00000210010111000111，则G的顶点数与边数分别为_____。A、4,5B、4,10C、5,4D、5,1013．设G是简单有向图，可达矩阵P(G)刻划了_____的关系。A、点与边B、边与点C、点与点D、边与边14．设},,,,,{fedcbaV，},,,,,,,,,,,{efeddaaccbbaE，则有向图EVG,是_____。A、强连通的B、单向连通的C、弱连通的D、不连通的15、以下无向图中，不是二部图的是_____。A、B、C、D、16、下图中既不是欧拉图，也不是哈密尔顿图的是_______。A、B、C、D、17、以下无向图中，不是平面图的是_____。A、B、C、D、18、已知一棵无向树T中有4度、3度和2度分支点各1个，其余顶点均为树4叶，则T有个树叶。A、2B、3C、4D、519、具有6个顶点，12条边的连通简单平面图中，次数为3的面有______个。A、5B、6C、7D、820、下面编码_____不是前缀码。A、11，00，10，01B、01，11，101，1001C、11，101，001，011，010D、11，010，011，1011，0101，1010121、满足等式84321xxxx的正整数解的个数有______。A、47CB、48CC、311CD、411C22．在自然数集N上，下列_____运算是可结合的。（对任意Nba,）A、babaB、),max(babaC、baba5D、baba23、设V1=R*,+，V2=R*,是代数系统,R*为非零实数的集合，+为普通加法，为普通乘法，下面函数中是V1到V2的同态映射的是_____。A、f(x)=2xB、f(x)=xC、f(x)=1/xD、f(x)=ex24、设,6Z是代数系统，}5,4,3,2,1,0{6Z，为模6加法运算，则(5)4=_____。A、1B、1/625C、4D、225．具有如下定义的代数系统,G，_____不构成群。A、}10,1{G，*是模11乘B、}9,5,4,3,1{G，*是模11乘C、}1,0{G，*是普通加法D、QG（有理数集），*是普通加法5装订线二、计算题：（本大题共5个小题，每题5分，共25分）1、求下列谓词公式的前束范式，请写出推导过程：)),(),((yxyGyxyFx2、给出集合}12,10,9,8,6,4,3,2{A，分别求出：(1)画出集合A的整除偏序关系的哈斯图；(2)指出集合A的最大元，最小元，极大元，极小元；(3)指出集合}6,4,2{B的上界，下界，最小上界，最大下界。3、如下图所示的赋权图表示某六个城市621,,,VVV，及预先算出它们之间直接通信线路造价(以百万元为单位)，试给出一个设计方案，使得各城市之间能够通信而且总造价最小，并计算出最小造价。4、画出5阶所有非同构的根树。5、四个人比赛，名次允许并列，总共有多少种比赛结果。三、证明题：（本大题共4个小题，每题5分，共20分）1、用等值演算法证明下列等值式。p(qr)(pq)(pr)得分得分V1V2V6V3V5V41352467891.5CM62、设ZZA,在A上定义二元关系R如下：|,,,{dcbaR,,ZZba,,ZZdc}cbda证明：R是A上的等价关系。3、设T=V,E是n阶非平凡的无向树，证明：T至少有两片树叶。4、实数集R上定义运算*，2baba，·为普通乘法。判断R,*能构成半群、独异点和群中的何种代数系统。写出详细证明过程。四、应用题（2选1，两道都做仅以第1道算分；5分）1、构造一个与英文字母b,d,g,o,ye对应的前缀码，并画出该前缀码对应的二叉树，写出goodbye的编码信息。2、计算机系期末要安排7门公共课的考试，课程编号为1到7，下列每一对课程有学生同时选修：1和2、1和3、1和4、1和7、2和3、2和4、2和5、2和7、3和4、3和6、3和7、4和5、4和6、5和6、5和7、6和7。这7门课的考试至少要安排在几个不同的时间段？给出一个安排方案。得分