2013年9月份考试离散数学第二次作业

2013年9月份考试离散数学第二次作业一、单项选择题（本大题共40分，共20小题，每小题2分）1.设S={1,2,3,4}，R={1,1,2,2,3,3}，则R的性质是（）A.自反、对称、传递的B.自反、对称、反对称的C.对称、反对称、传递的D.只有对称性2.在下列命题中，为真的命题是（）A.汉密顿图一定是欧拉图B.无向完全图都是欧拉图C.度数为奇数的结点个数为0个或2个的连通无向图G可以一笔画出D.有割点的连通图是汉密顿图3.设P：我去踢球，Q：明天下雨，命题“如果我踢球，当且仅当明天不下雨”的符号化表示为（）。A.P→QB.Q→PC.D.PQ4.设A为一集合，（P(A),）为有补格，P(A)中每个元素的补元（）。A.存在且唯一B.不存在C.存在且不唯一D.可能存在5.下图哪个能一笔画？（）A.B.C.D.6.若X是Y的子集，则一定有（）。A.X不属于YB.X∈YC.X真包含于YD.X∩Y=X7.若集合A的基数|A|=10，则其幂集的基数为（）A.1024B.100C.20D.128.下面哪一个命题是命题“2是偶数或-3是负数”的否定？（）A.2是偶数或-3不是负数B.2是奇数或-3不是负数C.2不是偶数且-3不是负数D.2是奇数且-3不是负数9.对于下面某个偏序集的哈斯图，其中集合{a,b,c,e}的最大元是（）A.cB.dC.eD.无10.设G是n个顶点的无向简单图，则下列说法不正确的是（）。A.若G是树，则其边数等于n-1B.若G是欧拉图，则G中必有割边C.若G中有欧拉路，则G是连通图，且有零个或两个奇数度顶点D.若G中任意一对顶点的度数之和大于等于n-1,则G中有汉密顿路11.在谓词演算中，P(a)是∀xP(x)的有效结论，其理论根据是（）。A.全称指定规则（US）B.全称推广规则（UG）C.存在指定规则（ES）D.存在推广规则（EG）12.设有33盏灯，拟公用一个电源，则至少需要5个插头的接线板数（）A.7B.8C.9D.1413.函数的复合满足（）A.交换律B.结合律C.幂等律D.分配律14.以下叙述正确的是（）A.代数系统能构成半群，其中运算o定义为：aob=|a-b|。B.对于自然数集合，运算a*b=min{a,b}是可结合的。C.代数系统是半群，其中运算“-“表示普通的减法运算。D.以上的叙述均不对。15.以下叙述正确的是（）A.{b,c,a,aa,ac,abb}是前缀码。B.在有界格中，若有一个元素有补元，则补元必唯一。C.在有向图中，结点间的可达关系是等价关系。D.连通图的最小生成树不一定是唯一的。16.以下叙述正确的是：（）。A.的幂集没有任何元素。B.整数集上关于加法运算的幺元是0。C.整数集上的任何元素x关于乘法运算均有逆元1/x。D.整数集上的关于乘法运算的幺元是0。17.命题公式PQR的对偶式为？（）A.P（QR）B.P（QR）C.P（QR）D.P（QR）18.Q(PQ)主合取范式为（）A.PQB.PQC.(PQ)(PQ)(PQ)D.(PQ)(PQ)(PQ)19.设Z+为正整数集合，S为正偶数集合，则Z+,|与格S,|（其中|表示整除关系）的关系为（）。A.自同构B.同构C.自同态D.非同构20.设G=为无环的无向图，|V|=6,|E|=16,则G是（）A.完全图B.零图C.简单图D.多重图二、多项选择题（本大题共30分，共10小题，每小题3分）1.相容关系需要满足的特性为：（）A.对称性B.传递性C.自反性D.反对称性2.以下关系中哪些是AB的函数，其中A={a,b,c}B={1,2,3}()A.{a,1,a,2,b,3}B.{a,3,b,1,c,1}C.{a,3,b,1,c,2}D.{b,3,a,2,b,13.在下列命题中，为真的命题是（）A.具有6个结点的无向完全图共有15条边。B.无向完全图都是欧拉图。C.度数为奇数的结点个数为0个或2个的连通无向图G可以一笔画出。D.有割点的连通图是汉密顿图。4.以下叙述正确的是（）。A.若A＝{φ,1,2}，则A的幂集有8个元素B.朋友关系是等价关系C.具有5个顶点的完全图，需要删去6条边才能得到树D.集合B={{a},3,4,1}，E为全集，则φ{{a}}BE5.设Z是整数集合，+是一般加法，则下述函数中哪些是群（Z，+）的自同态？（）A.f(x)=2xB.f(x)=1000xC.f(x)=|x|D.f(x)=06.以下表达方式正确的是：（）A.小明打开箱子并拿出一件衣服。设P：小明打开箱子；Q：小明拿出一件衣服。原命题表示为：PQB.如果骑自行车，我就没法按时到校。设P：我骑自行车；Q：我按时到校；原命题可表示为：P→QC.我打开门，走了进来。设M：我打开门；N：我走进来。原命题为：M→ND.小红和小华是好朋友。设H：小红是好朋友；J：小华是好朋友；原命题为：HJ7.设偏序集,≤的哈斯图如下所示，若A的子集B={2,3,4},则元素为B的极大元为()。A.5B.6C.3D.48.对于下列各式，是永真式的有（）。A.(P∧(P→Q))→QB.P→(P∨Q)C.Q→(P∧Q)D.((P∧(P(Q))→QE.(P→Q)→Q9.设集合A={1,2,3,…10}，下面定义的哪种运算关于集合A是封闭的（）A.x*y=max{x,y}B.x*y=min{x,y}C.x*y=GCD(x,y)即x,y的最大公约数D.x*y=LCM(x,y)即x,y的最小公倍数10.设T是一棵具有n个结点m条边（n2）的树，则T（）。A.连通B.包含有环C.m=n-1D.至少有两个度为1的结点三、判断题（本大题共30分，共10小题，每小题3分）1.{1，01，001，000}是前缀码。（）2.若f：NN,f(x)=x2+2，则f是满射函数。（）3.能一笔画出的图一定是欧拉图。（）4.为矛盾式。（）5.交换群必是循环群。（）6.任何图中必有偶数个度数为奇数的结点。（）7.设S={0,1},S是关于普通的加法和乘法运算，则S上的加法与乘法运算满足封闭性、结合性。（）8.为重言式。（）9.设是一个代数系统，且集合A中元素的个数大于1。如果该代数系统中存在幺元e和零元，则e。（）10.设e为无向连通图G中的一条边，e在G的任何生成树中，则e是桥。（）答案：一、单项选择题（40分，共20题，每小题2分）1.C2.C3.C4.A5.D6.D7.A8.C9.D10.B11.A12.B13.B14.B15.D16.B17.D18.C19.B20.D二、多项选择题（30分，共10题，每小题3分）1.AC2.BC3.AC4.ACD5.ABD6.BC7.CD8.ABD9.ABC10.ACD三、判断题（30分，共10题，每小题3分）1.√2.×3.×4.√5.×6.√7.×8.√9.√10.√