《离散数学》测试题答案

测试题——离散数学一、选择题1、G是一棵根树，则（）。A、G一定是连通的B、G一定是强连通的C、G只有一个顶点的出度为0D、G只有一个顶点的入度为12、下面哪个语句不是命题（）。A、中国将成功举办2008年奥运会B、一亿年前地球发生了大灾难C、我说的不是真话D、哈密顿图是连通的3、设R是实数集合，在上定义二元运算*：a，b∈R，a*b=a+b-ab，则下面的论断中正确的是（）。A、0是*的零元B、1是*的幺元C、0是*的幺元D、*没有等幂元4、下面说法中正确的是（）。A、所有可数集合都是等势的B、任何集合都有与其等势的真子集C、有些无限集合没有可数子集D、有理数集合是不可数集合5、无向完全图K3的不同构的生成子图有（）个。A.6B.5C.4D.36、下面哪一种图不一定是无向树?A、无回路的连通图B、有n个顶点n-1条边的连通图C、每对顶点间都有通路的图D、连通但删去一条边则不连通的图7、设集合A＝{{1,2,3},{4,5},{6,7,8}}，则下列各式为真的是()。A.1AB.{{4,5}}AC.{1,2,3}AD.A8、在有界格中，若一个元素有补元，则补元()。A、必惟一B、不惟一C、不一定惟一D、可能惟一9、设集合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、集合X中的关系R，其矩阵是111011101M，则关于R的论述中正确的是（）。A、R是对称的B、R是反对称的C、R是反自反的D、R中有7个元素11.下列各组数中，哪个可以构成无向图的度数列（）。A.1，1，1，2，2B.2，2，2，2，3C.1，2，2，4，6D.2，3，3，312.是定义在Z上的二元运算，yxxyyxZyx,,，则的幺元和零元分别是（）。A.不存在，0B.0，1C.1，不存在D.不存在，不存在13.设NNNf,:为自然数，且为偶数若为奇数若xxxxf21)(则})0({)0(ff和分别是（）。A.0，0B.0，{0}C.{0}，{0}D.{0}，014.下列命题公式中是矛盾式的有（）。A.ppp)(B.ppq)(C.)()(pqqpD.rqp)(15.下列各Hasse图中，是格的有（）。A.B.C.D.16．下列命题公式中是永假式的有（）。A.ppp)(B.ppq)(C.)()(pqqpD.rqp)(17.设命题公式(P(QP))，记作G，则使G的真值指派为0的P，Q的取值是()。A.(0,0)B.(0,1)C.(1,0)D.(1,1)18.与命题公式P（QR）等值的公式是()。A.(PQ)RB.(PQ)RC.(PQ)RD.P(QR)19.命题公式(PQ)P是()。A.永真式B.永假式C.可满足式D.合取范式20.设命题公式)(),(PQPHQPG，则G与H的关系是()。A.HQB.GHC.GHD.HG21．谓词公式)())()((xQyyRxPx中量词x的辖域是()。A))()((yyRxPxB.P(x)C.)()(yyRxPD.)(xQ22．设个体域为整数集，下列公式中其值为1的是()。A.)0(yxyxB.)0(yxxyC.)0(yxyxD.)0(yxyx23．设L(x)：x是演员，J(x)：x是老师，A(x,y)：x佩服y.那么命题“所有演员都佩服某些老师”符号化为()。A.),()(yxAxxLB.)),()(()((yxAyJyxLxC.)),()()((yxAyJxLyxD.)),()()((yxAyJxLyx24．在谓词演算中，P(a)是)(xxP的有效结论，根据是()。A.US规则B.UG规则C.ES规则D.EG规则25.在图G＝V,E中，结点总度数与边数的关系是()。A.deg(vi)=2EB.deg(vi)=EC.VvEv2)deg(D.VvEv)deg(26.设G是有n个结点的无向完全图，则图G的边数为()；设D是有n个结点的有向完全图，则图D的边数为()。A.n(n－1)B.n(n+1)C.n(n－1)/2D.n(n+1)/227.仅有一个孤立结点的图称为()。A.零图B.平凡图C.补图D.子图28.设G＝V,E为无向简单图，V=n，(G)为G的最大度，则有（）。A.(G)nB.(G)nC.(G)nD.(G)n29.图G与G的结点和边分别存在一一对应关系，是G≌G(同构)的()。A.充分条件B.必要条件C.充分必要条件D.既非充分也非必要条件30.设},,,{dcbaV，则与V能构成强连通图的边集合是()。A.},,,,,,,,,{cdbcdbabdaEB.},,,,,,,,,{cddbcbabdaEC.},,,,,,,,,{cdadcbabcaED.},,,,,,,,,{dcdbdacabaE31.相邻矩阵具有对称性的图一定是()。A.有向图B.无向图C.混合图D.简单图32.无向图G是欧拉图，当且仅当()。A.G的所有结点的度数全为偶数B.G的所有结点的度数全为奇数C.G连通且所有结点的度数全为偶数D.G连通且所有结点的度数全为奇数33.设mEnVEVG,,,为连通平面图且有r个面，则r＝()。A.m－n+2B.n－m－2C.n+m-2D.m+n+234.设G是由5个结点组成的完全图，则从G中删去()条边可以得到树。A.4B.5C.6D.1035.由5个结点可构成的根树中，其叉数m最多为()。A.2B.3C.5D.436.下图是()。A.完全图B.哈密顿图C.欧拉图D.平面图37.设集合A＝{1,2,3,…,10},在集合A上定义的运算，不是封闭的为()。A.a,bA,ab=lcm{a,b}(最小公倍数)B.a,bA,ab=gcd{a,b}(最大公约数)图C.a,bA,ab=max{a,b}D.a,bA,ab=min{a,b}38.在自然数N上定义的二元运算，满足结合律的是()。A.ab=a－bB.ab=a+2bC.ab=max{a,b}D.ab=a－b39.下列代数系统(G,*)中，其中*是加法运算.()不是群。A.G为整数集合B.G为偶数集合C.G为有理数集合D.G为自然数集合40.设1，2，3是三个置换，其中1＝(12)(23)(13),2=(24)(14),3=(1324)则3可以表成()。A.21B.12C.22D.2141.下列图表示的偏序集中，是格的为()。A.B.C.D.42.设)1,0,,,,(B是布尔代数，baBba,,，则下式不成立的是()。A.0baB.1baC.abaD.1ba43.布尔代数式)(cbcabab=()。A.baB.cbC.cbD.cb44.设集合A＝{1,2}，B={a,b,c},C={c,d},则A×(BC)＝()。A.{c,1,2,c}B.{1,c,2,c}C.{c,1,c,2}D.{1,c,c,2}45.设A＝{0,a},B={1,a,3},则AB的恒等关系是()。A.{0,01,1,3,3,a,a}B.{0,0,1,1,3,3}C.{1,1,a,a,3,3}D.{0,1,1,a,a,3,3,0}46.设A={a，b，c}，R={a，a，b，b}，则R具有性质（）。A.自反的B.反自反的C.反对称的D.等价的47.设集合},,,{},,,,{3214321bbbBaaaaA是从A到B的函数，,,{21ba},,,,,341322bababa，则是()。A.双射B.满射但不是单射C.单射但不是满射D.非单射也非满射48.下列式子中正确的是（）。A.=0B.C.{a,b}D.{}49.有向图的邻接矩阵中，行元素之和是对应结点的()，列元素之和是对应结点的()。A.度数B.出度C.最大度数D.入度50.给定无向图如下所示，下面给出的顶点集子集中，不是点割集的是（）。A.{b,d}B.{d}C.{e}D.{f,h}51．谓词公式xA(x)xA(x)的类型是（）。A.永真式B.矛盾式C.非永真式的可满足式D.不属于(A),(B),(C)任何类型52.谓词公式)(yyP取真值为1的充分必要条件是()。A.对任意y，使P(y)都取真值1B.存在一个y0，使P(y0)取真值1C.存在某些y，使P(y)都取真值1D.存在y0，使P(y0)取真值053.设G是群，当G有（）个元素时，不能肯定G是交换群。A.4B.5C.6D.754．若集合A＝{a,b,c},为空集合，则下列表示正确的是()。A.{a}AB.{a}AC.aAD.A55.设A,B,C都是集合，如果AC＝BC，则有()。A.A＝BB.ABC.当A－C＝B－C时,有A=BD.当C=U时,有AB56.设S1＝，S2＝{},S3＝P({}),S4＝P()，以下命题为假的是()。A.S2S4B.S1S3，C.S4S2D.S4S357.设G是有6个元素的循环群，a是生成元素，则G的子集（）是子群。afbgch图deA.{a}B.{a,e}C.{e,a3}D.{e,a,a2}58.设集合A={a,b,c,d,e},半序关系R的哈斯图如下，假设A的子集B={c,d,e},则元素c为B的（）。A.下界B.最大下界C.最小上界D.以上答案都不对59.设GxyP(x,y)Q(z,w)，下面三个命题为真的是()。A.G是前束范式B.G不是前束范式C.G不是一阶公式D.G是永真式60．对任意集合S，S＝S，满足()。A.幂等律B.零一律C.同一律D.互补律61．设命题公式RQPG:，则使公式G取真值为1的P，Q，R赋值分别是()。A.0，0，0B.0，0，1C.0，1，0D.1，0，062．设a是集合A的元素，则以下正确的是()。A.aaB.AaC.AaD.Aa63．设集合A{1，2，3，4}，B：{2，4，6，9}，那么集合A，B的对称差A⊕B＝()。A.{1，3}B.{2，4，6}C.{1，3，6，9}D.{1，2，3，4，6，9}64.有向完全图D＝Ｖ，Ｅ，则图D的边数是()。A.｜Ｅ｜(｜E｜—1)／2B.｜Ｖ｜(｜Ｖ｜一1)／2C.｜Ｅ｜(｜Ｅ｜－１)D.｜Ｖ｜(｜Ｖ｜－１)65．设G是有n个结点，m条边的连通阻，必须删去G的()条边，才能确定G的一棵生成树。A.m一n＋1B.n一mC.m＋n＋1D.n—m＋166.设N为自然数集合，N，在下面4种运算下不构成代数系统的是（）。A.xy=x+y－2xyB.xy=x+yC.xy=xyD.xy=|x|+|y|67.已知图G的相邻矩阵为0010000110010110，则G有（）。A.6个点，度为4B.5个点，度为6C.4个点，度为3D.4个点，度为668.设集合A={1，2，3，……，10}，半序关系是A上的整除关系，则半序集（A，）上的元素10是集合A的（）。A.最大元B.最小元C.极大元D.极小元二、填空题1.代数格（L，，）中的运算和满足的算律有_______、__________、__________。2、A是含有3个元素的集合，在A上可以定义______个不同的等价关系。