德州学院离散数学期末复习题

离散数学一、单选题1.设谓词代表“x等于y”，个体变元x，y的个体域都为{1，2，3}，则以下选项真值为1的是？A.B.C.D.E.F.答案：A2.设D的结点数大于1，D=是强连通图，当且仅当A.D中至少有一条通路B.D中至少有一条回路C.D中有通过每个结点至少一次的通路D.D中有通过每个结点至少一次的回路答案：D3.下列符号串哪个不是命题公式？A.B.C.D.E.F.答案：A4.以下选项错误的为A.B.C.(t代表永真式)D.答案：D5.n阶无向完全图的边数是_____，结点度数是_____A.B.C.D.答案：A6.若一个集合基数为3，那么其幂集基数为A.B.C.D.答案：A7.设无向图G有16条边且每个顶点的度数都是2，则图G有()个顶点A.10B.4C.8D.16答案：D8.下面哪一种图不一定是树A.有n个顶点n—1条边的连通图B.无回路的连通图C.连通但删去一条边则不连通的图D.每对结点间都有路的图答案：D9.若，则下列哪个结论不可能正确？（）A.B.C.D.答案：D10.下列建立在集合的诸多关系中，满足传递性的是（）。A.B.C.D.答案：B11.设T是有n个结点的二元正则树，则树T的叶子数为．A.n－1B.2n－1C.(n+1)/2D.(n+2)/3答案：C12.对下面文法，产生的语言是A.B.C.D.答案：A13.永真式的否定是A.永真式B.永假式C.可满足式D.(1)--(3)均有可能答案：B14.设G是有n个结点，m条边的连通图，必须删去G的()条边，才能确定G的一棵生成树．A.m-n+1B.m-nC.m-n-1D.其余选项皆不正确答案：A15.设G是一棵树，则G的生成树有（）棵？A.0B.1C.2D.不确定答案：A16.以下命题正确的是()．A.连通且满足的图是树B.阶完全图都是欧拉图C.阶完全图都是哈密顿图D.阶完全图都是平面图答案：A17.含有5个命题变元（要求名字中不含数字）和5个联结词的公式对应的完整真值表上能看到多少布尔量0或1？（请回忆标准的真值表结构）A.320B.640C.32D.3200E.6400F.1024答案：A18.令F(x):x是有理数，G(x):x是实数。将命题“所有的有理数都是实数，但有的有实数不是有理数”符号化为A.∀x(F(x)∧G(x))∧∃x(G(x)→¬F(x))B.∀x(F(x)→G(x))∧∃x(G(x)∧¬F(x))C.∀x(F(x)∧G(x))∧∃x(G(x)∧¬F(x))D.∀x(F(x)→G(x))∧∃x(G(x)→¬F(x))答案：B19.设集合A,B，其中则＝_________________;＝______________A.B.C.D.答案：A20.下列命题公式中，不是重言式的是（）A.B.C.D.答案：A21.设命题公式G＝(PQ)，H＝P(QP)，则G与H的关系是__________A.GHB.HGC.G＝HD.以上都不是.答案：A22.设是三个集合，其中是实数集，,则__________________________________,A.B.C.D.答案：A23.设集合A={1，2，3}，下列关系R中不是等价关系的是A.R={＜1,1＞,＜2,2＞,＜3,3＞}B.R={＜1,1＞,＜2,2＞,＜3,3＞,＜3,2＞,＜2,3＞}C.R={＜1,1＞,＜2,2＞,＜3,3＞,＜1,2＞}D.R={＜1,1＞,＜2,2＞,＜3,3＞,＜1,2＞,＜2,1＞,＜1,3＞,＜3,1＞,＜2,3＞,＜3,2＞}答案：C24.设集合,上的关系,则具有A.传递性B.对称性C.自反性D.反自反性E.反对称性答案：A25.若供选择答案中的数值表示一个简单图中各个顶点的度，能画出图的是_____________A.(1,2,2,3,4,5)B.(1,2,3,4,5,5)C.(1,1,1,2,3)D.(2,3,3,4,5,6).答案：C26.设谓词P(x)：x是奇数，Q(x)：x是偶数，谓词公式x(P(x)Q(x))在哪个个体域中为真?A.自然数B.实数C.复数D.(1)--(3)均成立答案：A27.下列各命题哪一个是假命题A.{a,b}Í{a,b,c,{a,b,c}}B.{a,b}Î{a,b,c,{a,b,c}}C.{a,b}Î{a,b,{a,b}D.{a,b}Î{{a,b}}答案：B28.下列语句中是真命题的为（）。A.我正在说谎。B.如果2+3=5，那么雪是黑色的。C.严禁在教室里吸烟！D.如果2+3=8，那么雪是黑色答案：D29.设是三个集合，其中是实数集，,则__________________________________,A.B.C.D.答案：A30.具有6个顶点，12条边的联通简单平面图中，每个面都是由（）条边围成？A.2B.4C.3D.5答案：C31.一棵树有2个2度顶点，1个3度顶点，3个4度顶点，则其1度顶点个数为（）。A.5B.7C.8D.9答案：D32.设G是一个哈密尔顿图，则G一定是个（）。A.欧拉图B.树C.平面图D.联通图答案：D33.设集合A={1,2,3,4},A上的关系R＝{(1,1),(2,3),(2,4),(3,4)},则R具有__________A.自反性B.传递性C.对称性D.以上答案都不对答案：B34.设全体域D是正整数集合，确定下列命题的真值A.xy(xy=y)B.xy(x+y=y)C.xy(x+y=x)D.xy(y=2x)答案：D35.若p表示“a是偶数”，q表示“a是奇数”，r表示“a是素数”，s代表“a=2”,那么“若a不是奇数且a不等于2，那么a不是素数”可以形式化为A.B.C.D.E.答案：A36.设一阶逻辑公式，则与G等价的是A.B.C.D.答案：A37.判断下列命题哪个为真?()A.A-B=B-A=＞A=BB.空集是任何集合的真子集C.空集只是非空集合的子集D.若A的一个元素属于B，则A=B答案：A38.在0（）之间写上正确的符号A.=B.C.D.答案：D39.下面说法正确的为A.非空集合上的相等关系不是反对称的B.微信好友关系是一种序关系C.世界上任意找六个人，则他们之中必有三个人相互认识或者相互不认识D.无向欧拉图的所有节点度数不全为偶数答案：C40.设P：我去看电影，Q：我有时间，将命题“我去看电影，仅当我有时间”可符号化为（）。A.B.C.D.答案：A41.下面哪一个函数有逆函数？(R代表实数集）A.B.C.,[x]代表向下取整函数D.Q代表有理数，上面加横线代表无理数答案：B42.设集合,A上的关系,,则=______________________,=________________________,=________________________________.A.B.C.D.以上皆不正确答案：A43.设P={x|(x+1)4且xR},Q={x|5x+16且xR},则下列命题哪个正确A.B.C.D.答案：C44.设A={a,b,c},B={1,2,3}，则下列关系中能构成A到B函数的是A.f1={＜a,1＞,＜a,2＞,＜a,3＞}B.f2={＜a,1＞,＜b,1＞,＜b,2＞}C.f3={＜a,1＞,＜b,1＞,＜c,1＞}D.f4={＜a,1＞,＜a,2＞,＜b,2＞,＜c,3＞}答案：C45.若集合S的基数，则S的幂集的基数________A.B.C.D.答案：A46.设集合A={2,{a},3,4}，B={{a},3,4,1}，E为全集，则下列命题正确的是__________A.{2}AB.{{a}}BEC.{{a},1,3,4}答案：B47.下面说法正确的是A.微信好友关系是一种等价关系B.二分图总能得到完全匹配C.不同的语法一定会产生不同的语言D.设R是具有相容性质的机器同余，则机器M和它的商机器M/R识别相同的语言答案：D48.已知是集合A上的两个等价关系，则下列一定还是等价关系的是（）。A.B.C.D.答案：A49.下面给出的集合中，哪一个不是前缀码()A.{a，ab，110，a1b11}B.{01，001，000，1}C.{1，2，00，01，0210}D.{12，11，101，002，0011}答案：A50.下面符号串哪个是命题公式？A.B.C.D.E.F.答案：A51.设R是集合A={a,b,c,d}上的二元关系，R={＜a,a＞,＜a,b＞,＜a,c＞,＜a,d＞,＜c,b＞,＜d,b＞,＜d,c＞}，则R具有关系的哪些性质A.自反性、反对称性B.反自反性、传递性C.自反性、对称性D.反对称性、传递性答案：D52.下列数组中，不能构成无向图的度数列的数组是_____.A.B.C.D.答案：A53.图，其中，对应边的权值依次为2、1、2、3、6、1、4及5，则最小生成树的权值是（）A.7B.6C.8D.9答案：A54.设集合A={1，2，3}，A上的关系R={＜1，1＞，＜1，2＞，＜2，2＞，＜3，3＞，＜3，2＞}，则R不具备A.传递性B.对称性C.自反性D.反对称性答案：B55.连通简单无向图有17条边，则该图至少有多少节点？A.7B.6C.8D.9答案：A56.谓词公式中变元χ是A.自由变元B.既不是自由变元也不是约束变元C.约束变元D.既是自由变元又是约束变元答案：D57.下列语句中，____________是命题。A.请把门关上B.地球外的星球上也有人C.x+5＞6D.下午有会吗？答案：B58.设集合A＝{1,2,3,4,6,8,9,12}，他的哈斯图如图所示，那么它的最大元，最小元，极大元，极小元：______.A.无最大元，最小元是1，极大元8,12,9，极小元是1B.无最大元，最小元是1，极大元12，极小元是1C.最大元是12，最小元是1，极大元8,12,9，极小元是1D.其余选项皆不正确答案：A59.判断下列命题哪几个正确A.所有空集都不相等B.C.答案：B60.设，从到的关系，则_________A.B.C.D.答案：A61.，则关系R是A.B.C.D.答案：A62.下列定义正确的是_____A.不含平行边和环的图称为简单图B.含平行边或环的图称为多重图C.不含平行边或环的图称为简单图D.含平行边和环的图称为多重图答案：A63.一阶逻辑公式"xP(x)®$xP(x)是A.永真的B.永假的C.可满足的D.前束范式.答案：A64.设图G的相邻矩阵为上图所示，则G的顶点数与边数分别为_____________A.4,5B.5,6C.4,10D.5,8.答案：D65.设有限集合,则关系________.（将一个关系作为最小单位，而不再细分到有序集的定义）A.B.C.D.E.F.答案：A66.设有限集合A,,则关系________.（将一个关系作为最小单位，而不再细分到有序集的定义）A.B.C.D.答案：A67.设A,B为集合，当________时A－B＝B.A.A＝BB.ABC.BAD.A＝B＝.答案：D68.设，R是A上的整除关系，，则集合B的最大元、最小元、上界、下确界依次为()．A.无、2、无、2B.8、2、8、2C.6、2、6、2D.8、1、6、1答案：A69.设,有划分，则，分别为A.,B.,C.,D.,答案：A70.设A={1,2,3,4,5,6,7,8}，R是A上的整除关系，B={1,2,3,6}，则集合B的最大元、极小元、上界、最大下界依次为()．A.6,1,6,1B.6,无,6,1C.6,1,6,无D.无,1,6,无答案：A71.集合A={1,2,…,10}上的关系R={|x+y=10,x,yA}，则R的性质为（）A.自反的B.对称的C.传递的，对称的D.传递的答案：B72.设是三个集合，其中是实数集，,则____________________________A.B.C.D.答案：A73.设，上关系,，则关系矩阵为A.B.C.D.答案：A74.集合上的关系，则R的性质为_________A.对称性B.自反性C.传递性D.反自反性E.反对称性答案：A75.设无向图G有18条边且每个顶点的度数都是3，则图G有（）个顶点。A.10B.4C.8D.12答案：D76.公式中，既是自由变元，又是约束变元的是.A.B.C.D.不存在E.x和yF.x,y,z答案：A77.设G是5个顶点的完全图，则从G中删去__________条边可以得到树.A.6B.5C.10D.4.答案：A78.设R、Z、N分别为实数集、整数集，自然数集，则下列关系中能构成函数的是A.B.C.D.E.答案：A79.某案件有四名嫌疑犯，经调查得知（1）只有B是罪犯，C才是罪犯（2）如果C不是罪犯，那么D是罪犯（3）或者A是罪犯，或者B不是罪犯（4）A不是罪犯那么谁是罪犯？A.DB.BC.CD.没有人是罪犯E.C和D都是F.A和C都是答案：A80.张三说李四在说谎，李四说王五在说谎，王五说张三和李四都在说谎。到底谁在说谎？A.只有张三B.只有李四C.张三和王五D.只有王五E.李四和王五F.张三和李四答案：C81.判断下列命题哪个为真？A.B.空集是任何集合的真子集C.空集只是非空集合的子集D.若A的全部元素都属于B，则A=BE.和不等价答案：A82.设G、H是一阶逻辑公式，P是一个谓词，G＝xP(x),H＝xP(x),则一阶逻辑公式GH是__________A.恒真的B.恒假的C.可满足的D.前束范式答案：C83.图G=＜V,E＞如下图所示，从a到d有多少条简单通路A.5B.6C.7D.8答案：C84.设无向图G有16条边且每个顶点的度数都是2，则图G有_____个顶点。A.16B.32C.8D.12答案：A85.在自然数集N上，下列哪种运算是可结合的A.B.C.D.答案：B86.语句的形式化：“如果买不到薯条，他什么也不吃。”（:他买到薯条，:他吃饭）A.B.C.D.E.答案：A87.设P表示“天下大雨”，Q表示“他在室内运动”，则命题“除非天下大雨，否则他不在室内运动”符号化为（）。A.B.C.D.答案：A88.设。下列哪个是A的划分？A.B.C.D.其余三项皆不是答案：A89.设谓词的定义域为,将表达式中量词消除，写成与之对应的命题公式是A.B.C.D.其它选项皆不正确答案：A90.四个顶点的非同构简单图有多少个？A.11B.10C.8D.13答案：A91.设G是一棵树，n,m分别表示顶点数和边数，则A.n=mB.m=n+1C.n=m+1D.不能确定答案：C92.谓词公式∃x(P(x)∨∃yR(y))→Q(x)中变元x是A.自由变元B.约束变元C.既不是自由变元也不是约束变元D.既是自由变元也是约束变元答案：D93.设G=(V,E)为任意一图（无向或有向的），顶点个数为n，边的条数为m，则各顶点的度数之和等于.A.nB.mC.2nD.2m答案：D94.设集合，其中,则_________________;＝______________A.;B.;C.;D.;E.;答案：A95.设I是如下一个解释：,,,,.则在解释下取真值为1的公式是().A.B.C.D.答案：A96.设、是一阶逻辑公式，是一个谓词，,,则一阶逻辑公式是A.可满足的B.恒真的C.恒假的D.其他答案皆不正确答案：A97.在集合论中，若集合A={1,2,3}，集合B={2,3,4}，则A∪B（A与B的并集）等于什么？A.{1,2,3}B.{2,3,4}C.{1,2,3,4}D.{2,3}答案：C98.设集合A={1,2,3}，则A的幂集P(A)中元素的个数为（）A.3B.6C.8D.9答案：C99.设无向图G是一棵具有n个顶点的树，则图G的边数为（）A.n-1B.nC.n+1D.2n答案：A100.下列关于集合上二元关系性质的描述中，正确的是（）A.整数集Z上的“小于等于”（≤）关系既是等价关系，也是偏序关系B.整数集Z上的“模n同余”关系是一个等价关系，但不是偏序关系C.若一个关系R是自反的和对称的，那么它一定是等价关系D.偏序关系与等价关系的核心区别在于，偏序关系要求满足对称性，而等价关系要求满足反对称性答案：B二、多选题1.下面说法正确的有A.可识别的语言必定可枚举B.可枚举的语言必定可判定C.图灵机思想以冯诺依曼体系基础D.现代电子计算机是对通用图灵机的一种模拟答案：AD2.R是A={1,2,3,4,5,6}上的等价关系,则R诱导的划分中应当包含的集合是A.{3,6}B.{2,4}C.{1,5}D.{2,6}E.{1,2}答案：ABC3.A.AB.BC.CD.D答案：ABCD4.关于上图的说法正确的有A.它能识别001100111001B.它不能识别101001011000101C.这是一个非确定有限自动机D.该机器能识别的字符串如果将其倒转过来并视为二进制数，则该数必能被3整除答案：AD5.下列公式中哪些是永真式A.B.C.D.答案：BCD6.判断下列语句是不是命题。若是，给出命题的真值A.北京是中华人民共和国的首都B.陕西师大是一座工厂C.你喜欢唱歌吗？D.若7+8＞18，则三角形有4条边E.前进！F.给我一杯水吧！答案：ABD7.A.AB.BC.CD.DE.E答案：BD8.A国只有两种人，一种永远说真话，一种永远说假话，你来到A国，到了二叉路口不知道哪条道通向首都，路口有这个国家的一个守卫人员（A国人），你只能问一个问题，守卫只回答是或不是，请问怎样问才能确定哪条路是通往首都的路？A.（你指向一条路，问他）如果我问你“这条路是去首都的路吗”，你会回答“是”，是不是？B.（你指向一条路，问他）这条路通向首都吗？C.（你指向一条路，问他）和你不同类的人会对我说这条路通向首都吗？（假设他们自己知道本国人分两类）D.（你指向一条路，问他）如果我问你“这条路不是去首都的路吧”，你会回答“不是”，是不是？E.（你指向一条路，问他）这条路不能通向首都吗？答案：ACD9.以下说法错误的有A.二分图一定是树，树也一定是二分图B.正则二分图（|X|=|Y|）总能找到完全匹配C.两个同构的树，其排序后的度数序列有可能不同D.G是一棵根树，那么它只有一个顶点的度为1E.根树一定是连通的答案：ACD10.以下说法正确的有A.图灵机能解决一切问题B.图灵机的各个变种都可以用单带图灵机模拟C.停机问题的本质是一阶谓词逻辑的不完备性D.图灵机所能识别的语言也一定能为某个有限状态机所识别答案：BC11.下面说法正确的有A.只有双射函数存在逆函数B.根树的边数恰比节点数少1C.参与关系运算的两个关系，其前域可以不同D.{¬,→}是功能完备集答案：ABD12.设G=＜V,E＞是n()阶m条边的连通平面简单图，r为面的次数，下面说法正确的有A.最大度B.C.图的每个面的次数都大于等于3D.成立欧拉公式答案：ABCD13.以下说法错误的有A.非空集合上自反关系必然不是反自反的B.非空集合上关系不是对称的就是反对称的C.非空集合A上的全关系A×A，具有自反、对称和传递的性质D.非空集合上的相等关系是自反、反自反、对称、反对称和传递的答案：BD14.下面哪个语句是命题？A.我明天或后天去天津。B.明天一定不会下雨。C.如果买不到机票，我哪儿也不去。D.请注意你的举止。E.今天怎么这么堵车！F.请问去故宫怎么走？G.祝大家新年快乐！答案：ABC15.下面说法正确的有A.个体域的改变有可能影响谓词公式的真值B.如果图G有两个顶点，且G中所有回路长度都是偶数，则G是二分图C.是边数最少的非平面图D.关系R是传递的，当且仅当答案：ABD16.A.AB.BC.CD.DE.EF.FG.GH.H答案：ABCDE17.下面说法正确的有A.个体域的改变有可能影响谓词公式的真值B.如果图G有两个顶点，且G中所有回路长度都是偶数，则G是二分图C.K5是边数最少的非平面图D.关系R是传递的，当且仅当答案：ABD18.A.AB.BC.CD.D答案：BCD19.设T=＜V,E＞是n阶m条边的树，以下说法正确的有A.T无回路，且m=n-1B.T是连通的，且T的每条边都是割边C.T无回路，但任意增加一条边产生惟一一条回路D.T中每对结点有路，但可以有多条。答案：ABC20.关于集合论中的基本概念，