11-12-2离散数学A卷试题

共3页第1页总印份（附卷纸1页）说明：1、除填空题、图解及特殊要求外，一般不留答题空间2、装订试卷、考生答卷纸不得拆开或在框外留有任何标记，否则按零分计西安邮电大学课程考试试题（A卷）（2011——2012学年度第2学期）课程名称：离散数学试卷类型：A卷考试专业、年级：计科、软件11级题号一二三四五六七八九十总分得分评卷人答卷说明：1、试题满分100分．答题开始前，考生务必检查试题是否有无缺页、重页或印刷不清楚的地方，如有，请立即向监考人员示意调换;2、考试过程中不许撕开试卷，否则以作弊论处；3、试题解答过程应写在相应题目的空白处，否则不得分．一、（16分，每小题2分）判断题：将判定结果真（T）或假（F）直接填入到题前的括号中。（）1.设个体域D={1,2,3}，():2Pxx，命题()(2)xPxP的真值为真。（）2.设A、B是集合，0[][]KAKB，则[][]KABKA。（）3.设A={1,2,3}，R是集合A上的关系，R的关系矩阵为010000010RM，则R的传递闭包()tRR。（）4.设{,}Sab，()PS是S的幂集，则(),PS是循环群。（）5.设Q是有理数集合，在Q上定义二元运算如下：对任意,abQ，ababab，则运算在A上是可交换的。（）6.若图G是不连通的，则G的补图G是连通的。（）7.二部图2,3K（如右图所示）是汉密尔顿图。（）8.若无向图G中恰有两个奇数度结点，则这两个结点间必有一条路。二、（20分，每小题2分）单项选择题1.(,):Lxyxy，当个体域为_______时，公式(,)xyLyx不是有效的。A．自然数集B．整数集C．有理数集D．实数集2.设P：2是素数，Q：3是素数，R：2是有理数。下列复合命题中_______是假命题。A．()PQPB．()RPQC．()PQRD．()PRQ3.设集合{2,3}A，{3,4}B，下列命题_______不正确。A．[][]KAKBB．|()|4PABC．{2,4}ABD．{2}AB4.设A={1,2,3}，R是集合A上的关系，{1,1,1,2,2,3}R，则R是_______。A．自反的B．反自反的C．反对称的D．传递的5.下列集合中基数为的是________。A．{,|,Apqpq都是整数}B．{,|,Apqpq都是有理数}C．A是由实数轴上所有两两不相交的有限开区间所组成的集合D．A是由所有半径为1，圆心在x轴上的圆周所组成的集合6.下列集合中________对于数的加法和乘法同时满足封闭性。A．{0,1}AB．{2|,}CababZ，Z是整数集C．{1,1}BD．A={x|x是素数}7.设R是实数集合，“”、“”分别是普通数字的加法和乘法，:fRR定义为：对任意xR，()xfxe，那么f是从,R到,R的一个_______。A．既非单一同态，也非满同态B．单一同态而非满同态C．满同态而非单一同态D．同构8.设无向图G中有12条边，已知G中有6个3度数结点，其余结点的度数均小超过2，则G中至少有________个结点。A．6B．8C．9D．129.连通简单平面图G有5个结点7条边，G的面数为________。A．4B．5C．6D．810.下列关于树的语句是真命题的是________。A．一个回路和任何一颗生成树至少有一条公共边B．任何图G都至少有一棵生成树C．设图G是一个有n个结点，1n条边的无向图，则G是一棵树D．设图G是连通图，e是G的割边，则e在G的每棵生成树中三、（20分，每空2分）填空题1.命题公式()PQ的主合取范式为_____________________________。专业班级姓名学号线线订订装装2012年7月4日考试用共3页第2页总印份（附卷纸1页）说明：1、除填空题、图解及特殊要求外，一般不留答题空间2、装订试卷、考生答卷纸不得拆开或在框外留有任何标记，否则按零分计2.设{1,0,1,2}A，在集合A上定义二元关系如下：对任意,abA，aRb当且仅当||||ab，则R是A上的等价关系，商集/AR______________________________________________。3.令{1,2,3}A，{,}Bab，则可以定义______个A到B的函数，在A上可以定义______个等价关系。4.设,G是4阶群，,H是,G的非平凡子群，则,H是_______阶群。5.设4阶循环群,G的运算表如下，eabceeabcaabcebbceacceab则在,G中，c为_______阶元，,G的生成元总共有_______个。6.若图,GVE是自对偶的，且||Vn，则||E_____________。7.设完全m叉树T有n片树叶，则T有____________________条边。8.设有图,GVE如右图所示，其最小生成树的树权=_________。四、（8分，每小题2分）命题符号化1.只有努力工作，才能改善生活。（P：努力工作，Q：改善生活）2.甲和乙至多有一人参加比赛。（P：甲参加比赛，Q：乙参加比赛）3.并非所有的素数都不是偶数。（()Px：x是素数，()Ex：x是偶数）4.每个人都有一些缺点。（()Mx：x是人，()Gy：y是缺点，(,)Fxy：x有y）五、（9分）逻辑证明：(()())xPxQx，(()())xPxRx，()xQx()xRx六、（9分）设{1,2,3,4,6,8,12}A，D为A上的整除关系。1．试说明,AD是偏序关系；2．画出D的哈斯图；3．试求子集{2,3,4,6}B的极大元与极小元。线订装专业班级姓名学号线订装33322222111243332222211124共3页第3页总印份（附卷纸1页）说明：1、除填空题、图解及特殊要求外，一般不留答题空间2、装订试卷、考生答卷纸不得拆开或在框外留有任何标记，否则按零分计七、（11分）设Q是有理数集合，在Q上定义二元运算如下：对任意,abQ，ababab，1．证明0是幺元且,Q是独异点；2．,Q是否有零元？若有零元，找出其零元；3．任意aQ，若a有逆元，找出其逆元。八、（7分）一个村庄地下有A、B、C、D四个防空洞如下图所示，相邻两个防空洞之间有一条通道，同时每个防空洞都有一条通道与地面相通。问能否从地面出发，每条通道都只走一遍再回到地面？用图论的有关知识证明你的回答。ABDC地面地面通道ABDC地面地面通道线订装专业班级姓名学号线订装