离散数学简答题.docx

1、离散数学简答题1、设简单图G所有结点的度数之和为12，则G一定有_条边。 问题反馈【教师释疑】正确答案：【6 】6 2、设X=a,b,c,Ix是X上恒等关系，要使Ixa,b，b,c，c,a，b,aR为X上的等价关系，R应取_. 问题反馈【教师释疑】正确答案：【 a,c,c,b 】a,c,c,b 3、命题公式的任意两个不同极小项的合取式一定为_. 问题反馈【教师释疑】正确答案：【永假式 】永假式 4、一个公式在等价意义下，_范式写法是唯一的。 问题反馈【教师释疑】正确答案：【 主析取 】 主析取 5、若P：他聪明；Q：他用功；则“他虽聪明，但不用功”，可符号化为_ 问题反馈【教师释疑】正确答案：

2、【 PQ 】PQ 6、设R是A上的二元关系,且RRR为R的子集,可以肯定R应是_关系。 问题反馈【教师释疑】正确答案：【传递 】传递 7、设集合A1, 2, 3, 4，A上的二元关系R(1,1),(1,2),(2,3), S(1,3),(2,3),(3,2)。则RS_, 问题反馈【教师释疑】正确答案：【(1,3),(2,2) 】(1,3),(2,2) 8、设谓词的定义域为a, b,将表达式任意xR(x)彐xS(x)中量词消除，写成与之对应的命题公式是_. 问题反馈【教师释疑】正确答案：【(R(a)R(b)(S(a)S(b) 】(R(a)R(b)(S(a)S(b) 9、设集合A,B，其中A1,2

3、,3, B= 1,2, 则A - B_; 问题反馈【教师释疑】正确答案：【 3 】3 10、设G是完全二叉树，G有7个点，其中4个叶点，则G的总度数为_ 问题反馈【教师释疑】正确答案：【12 】12 11、设A、B为两个集合, A= 1,2,4, B = 3,4, 则从AB_; 问题反馈【教师释疑】正确答案：【 4 】4 12、设A=a, b, a, b， B=a, b，则BA =_ 问题反馈【教师释疑】正确答案：【 】 13、设G是具有8个顶点的树，则G中增加_条边才能把G变成完全图。 问题反馈【教师释疑】正确答案：【21 】21 14、设集合A2, 3, 4, 5, 6，R是A上的整除，则

4、R以集合形式(列举法)记为_. 问题反馈【教师释疑】正确答案：【 (2, 2),(2, 4),(2, 6),(3, 3),(3, 6),(4, 4),(5, 5),(6, 6) 】(2, 2),(2, 4),(2, 6),(3, 3),(3, 6),(4, 4),(5, 5),(6, 6) 15、 设A,B,R是三个集合，其中R是实数集，A = x | -1x1, xR, B = x | 0x 2, xR,则A-B = _. 问题反馈【教师释疑】正确答案：【 x | -1x 0, xR 】x | -1x 0, xR 16、设R是集合A上的等价关系，则R所具有的关系的三个特性是_, 对称性,传递

5、性. 问题反馈【教师释疑】正确答案：【 自反性 】自反性 17、设G是连通平面图，有5个顶点，6个面，则G的边数是_条。 问题反馈【教师释疑】正确答案：【9 】9 18、p：天气好；q：我去游玩命题 ”如果天气好，则我去游玩” 符号化为_ 问题反馈【教师释疑】正确答案：【 pq 】pq 19、设A=2,4,6，A上的二元运算*定义为：a*b=maxa,b，则在独异点中，零元是_。 问题反馈【教师释疑】正确答案：【6 】6 20、设A=3,6,9，A上的二元运算*定义为：a*b=mina,b，则在独异点中，单位元是_ 问题反馈【教师释疑】正确答案：【9 】9 21、命题“你喜欢唱歌吗？”的真值为

6、_. 问题反馈【教师释疑】正确答案：【F 】F 22、命题“存在一些人是大学生”的否定是_。 问题反馈【教师释疑】正确答案：【 所有人都不是大学生 】所有人都不是大学生 23、永真式的否定是_. 问题反馈【教师释疑】正确答案：【永假式 】永假式 24、集合A上的偏序关系的三个性质是自反性、_和传递性。 问题反馈【教师释疑】正确答案：【 反对称性 】反对称性 25、集合A=1,2,10上的关系R=|x+y=10,x,y A，则R 的性质为_. 问题反馈【教师释疑】正确答案：【对称的 】对称的 26、设A=2,4,6，A上的二元运算*定义为：a*b=maxa,b，则在独异点中，单位元是_。 问题反

7、馈【教师释疑】正确答案：【2 】2 27、设A=3,6,9，A上的二元运算*定义为：a*b=mina,b，则在独异点中，零元是_. 问题反馈【教师释疑】正确答案：【 3 】3 28、设G,*是一个群，若a,b,xG，a* x=a* b，则x=_. 问题反馈【教师释疑】正确答案：【b 】b 29、代数系统是一个群，则G的等幂元是_。 问题反馈【教师释疑】正确答案：【 单位元 】单位元 30、 素数阶群一定是_群 问题反馈【教师释疑】正确答案：【 循环 】循环 31、有限布尔代数的元素的个数一定等于_的正整数次幂 问题反馈【教师释疑】正确答案：【 2 】2 32、 设G是一个哈密尔顿图，则G一定是

8、_图 问题反馈【教师释疑】正确答案：【 连通 】连通 33、 一棵无向树的顶点数n与边数m关系是_. 问题反馈【教师释疑】正确答案：【m=n-1 】m=n-1 34、 设T=V,E是一棵树，若|V|1，则T中至少存在_片树叶。 问题反馈【教师释疑】正确答案：【 2 】2 35、 若一棵完全二元（叉）树有2n-1个顶点，则它_片树叶。 问题反馈【教师释疑】正确答案：【 n 】n 36、判断一个语句是否为命题，首先要看它是否为 _，然后再看它是否具有唯一的真值。 问题反馈【教师释疑】正确答案：【 陈述句 】陈述句 37、在一棵根树中，仅有一个结点的入度为 ，称为树根。 问题反馈【教师释疑】正确答案

9、：【 0 】0 38、 所谓_是指不能再分解的命题 问题反馈【教师释疑】正确答案：【 原子命题 】原子命题 39、 在命题演算中，两个永真式的合取、析取、条件、双条件均为_式。 问题反馈【教师释疑】正确答案：【 永真 】永真 40、 树是不包含_的连通图。 问题反馈【教师释疑】正确答案：【 回路 】回路 41、设X=1，3，5，9，15，45，R是X上的整除关系，则R是X上的偏序，其最大元是_. 问题反馈【教师释疑】正确答案：【 45 】45 42、格L是分配格，当且仅当L既不含有与五角格同构的子格，也不含有与_同格的子格。 问题反馈【教师释疑】正确答案：【钻石格 】钻石格 43、有理数集Q中

10、的*运算定义如下：a*b=a+b-ab，则*运算的单位元是_。 问题反馈【教师释疑】正确答案：【 0 】0 44、 在根树中，如果每一个结点的出度_m或0，则称这棵树为完全m叉树。 问题反馈【教师释疑】正确答案：【 等于 】等于 45、一个重言式与一个矛盾式的析取是_式。 问题反馈【教师释疑】正确答案：【 重言 】重言 46、 设复合函数gf是从A到C的函数，如果g f是满射，那么_必是满射。 问题反馈【教师释疑】正确答案：【g 】g 47、 设是格，其中A=1，2，3，4，6，8，12，24，为整除关系，则3的补元是_。 问题反馈【教师释疑】正确答案：【 8 】8 48、 设S是非空有限集，

11、代数系统中，其中P（S）为集合S的幂集，则P（S）对运算的零元是_。 问题反馈【教师释疑】正确答案：【 S 】S 49、 设(x)x+1，(x)x-1 都是从实数集合到的函数，则。_. 问题反馈【教师释疑】正确答案：【 x 】x 50、 设Z是整数集，E=，-4，-2，0，2，4，f：ZE，f（x）=2x，则f是_射。 问题反馈【教师释疑】正确答案：【 双 】双 51、 设无向图G的边数为m，结点数为n，则G是树的条件是_. 问题反馈【教师释疑】正确答案：【 G连通且n=m+1 】G连通且n=m+1 52、 一个连通的无向图G，如果它的所有结点的度数都是偶数，那么它具有一条_ 问题反馈【教师释

12、疑】正确答案：【 欧拉回路 】欧拉回路 53、 是集合，|A|=10，则|P(A)|= _ 问题反馈【教师释疑】正确答案：【 1024 】1024 54、 一颗二叉树后序遍历的结果是bdeca，中序遍历的结果是badce，则根结点的右子树有_个结点。 问题反馈【教师释疑】正确答案：【 3 】3 55、 设G是有5个顶点的完全图，则从G中删去_条边可以得到树。 问题反馈【教师释疑】正确答案：【 6 】6 56、任意一个具有2个或以上元的半群，它不可能是_。 问题反馈【教师释疑】正确答案：【 群 】群 57、 设R1，R2是集合A1，2，3，4上的两个关系，其中R1(1，1)，(2，2)，(2，3

13、)，(4，4)，R2(1，1)，(2，2)，(2，3)，(3，2)，(4，4)，则R2是R1的_闭包 问题反馈【教师释疑】正确答案：【 对称 】对称 58、 含有5个结点，3条边的不同构的简单图有_个。 问题反馈【教师释疑】正确答案：【 4 】4 59、 设 A =1，2，3，则商集A/IA = ( ) 问题反馈【教师释疑】正确答案：【 1，2，3 】1，2，3 60、设R和S是集合A上的关系,当R是偏序关系,S是等价关系 则RS必为_关系 问题反馈【教师释疑】正确答案：【 反对称 】反对称 61、 P=a、b、c、d的最大划分是（ ） 问题反馈【教师释疑】正确答案：【 a,b，c，d 】a,

14、b，c，d 62、 设集合A=a,b,c，A上所有互不相同的等价关系的数目为_. 问题反馈【教师释疑】正确答案：【 5 】5 63、若集合S的基数|S|=5，则S的幂集的基数|P(S)|=_。 问题反馈【教师释疑】正确答案：【 32 】32 64、在任何图中必定有_个度数为奇数的结点。 问题反馈【教师释疑】正确答案：【 偶数 】偶数 65、 棵树有5个3度结点，2个2度结点，其它的都是l度结点，那么这棵树的结点数是_. 问题反馈【教师释疑】正确答案：【 14 】14 66、 在布尔代数L中，表达式(ab)(abc)(bc)的等价式是_. 问题反馈【教师释疑】正确答案：【 b(ac) 】b(ac

15、) 67、设G是连通简单平面图，G中有11个顶点5个面，则G中的边是_个。 问题反馈【教师释疑】正确答案：【 14 】14 68、 仅由一个孤立点组成的图称为_图。 问题反馈【教师释疑】正确答案：【 平凡 】平凡 69、 无向简单图G是棵树，当且仅当_ 问题反馈【教师释疑】正确答案：【G连通且边数比结点数少1 】G连通且边数比结点数少1 70、设S=1,2,则在S上可以定义_个二元关系.。 问题反馈【教师释疑】正确答案：【 16 】16 71、 设 A =1，2，3，4，A 上的二元关系 R =x，y（x-y）能被3整除，则自然映射 g：AA/R使 g(1) =_. 问题反馈【教师释疑】正确答

16、案：【 1,4 】1,4 72、集合A=1,2,3,A上的关系R(1,1),(2,2),(2,3),(3,2),(3,3)，则R不具备_性. 问题反馈【教师释疑】正确答案：【反对称 】反对称 73、令 p：经一堑；q：长一智。命题只有经一堑，才能长一智符号化为_. 问题反馈【教师释疑】正确答案：【 qp 】qp 74、 命题公式(qq)p 的真值为_. 问题反馈【教师释疑】正确答案：【 0 】0 75、 非平凡的无向树至少有_片树叶 问题反馈【教师释疑】正确答案：【 2 】2 76、若一棵完全二元（叉）树有2n-1个顶点，则它_片树叶。 问题反馈【教师释疑】正确答案：【 n 】n 77、集合

17、1，2，3，5，6，15，30 关于整除关系构成_ 问题反馈【教师释疑】正确答案：【 格 】格 78、 A,B为任意集合，则他们的共同子集是_. 问题反馈【教师释疑】正确答案：【 ; 】; 79、设函数f：NN（N 为自然数集），f(n)=n+1，则f是_射. 问题反馈【教师释疑】正确答案：【 单 】单 80、 设无向图中有6条边，有一个3度顶点和一个5度顶点，其余顶点度为2，则该图的顶点数是_. 问题反馈【教师释疑】正确答案：【 4 】4 81、设集合 A =1，2，a，4，3，命题1 A 的真值为 _. 问题反馈【教师释疑】正确答案：【 F 】F 82、若集合A的元素个数为10，则其幂集的

18、元素个数为_ 问题反馈【教师释疑】正确答案：【 1024 】1024 83、 如果R1和R2是A上的自反关系，则R1R2，R1R2，R1-R2中自反关系有_个 问题反馈【教师释疑】正确答案：【 2 】2 84、设A= a,b, B = x | x*x(a+b) x+ab = 0, 则两个集合的关系为:A_B. 问题反馈【教师释疑】正确答案：【 = 】= 85、设A, B为任意集合，命题A-B=A=B的真值为_ 问题反馈【教师释疑】正确答案：【 0 】0 86、若关系R具有自反性，当且仅当在关系矩阵中，主对角线上元素都为_； 问题反馈【教师释疑】正确答案：【 1 】1 87、设有向图D的邻接矩阵

19、A(D)如下所示，那么|E| . 问题反馈【教师释疑】正确答案：【 7 】7 88、 设s,*是群，则那么s中除_外，不可能有别的幂等元 问题反馈【教师释疑】正确答案：【 单位元 】单位元 89、若H1H2Hn是_，则称H1,H2,Hn是相容的 问题反馈【教师释疑】正确答案：【 可满足式 】可满足式 90、 数集A=1，2，3与运算“min”构成的代数系统的零元是 。 问题反馈【教师释疑】正确答案：【 1 】1 91、一个连通的（n,m）平面图，它的面数为k，则m,n,k满足的Euler公式为 。 问题反馈【教师释疑】正确答案：【 n-m+k=2 】n-m+k=2 92、 下列图中是Euler

20、图的是 _ 问题反馈【教师释疑】正确答案：【 (d) 】(d) 93、 n个命题变元的_称为小项 问题反馈【教师释疑】正确答案：【 合取式 】合取式 94、 前提引入规则：在证明的任何步骤上都可以引入前提，简称_规则。 问题反馈【教师释疑】正确答案：【 P 】P 95、 自由变元代入规则是指对某_出现的个体变元可用个体常元或用与原子公式中所有个体变元不同的个体变元去代入，且处处代入。 问题反馈【教师释疑】正确答案：【 自由 】自由 96、 设代数系统是环，则是_群。 问题反馈【教师释疑】正确答案：【 阿贝尔 】阿贝尔 97、 若一条路中，所有的_均不相同，称为迹。 问题反馈【教师释疑】正确答案

21、：【 边 】边 98、设是一个偏序集，如果A中任意两个元素都有最小上界与最大下界，则称为_。 问题反馈【教师释疑】正确答案：【 格 】格 99、n点完全图记为Kn，那么当_时，Kn是平面图 问题反馈【教师释疑】正确答案：【 n4 】n4 100、 设A=l，2，3，4，A上的二元关系R=，S=，则RS)-1=_。 问题反馈【教师释疑】正确答案：【 , 】,1、设A=1,2,3,4,5,6,7,8,9,10，R是A上的二元关系，R=|x,yA x+y=10 说明R具有哪些性质。 问题反馈【教师释疑】正确答案：【R=, , , , , , , 易知 R既不是自反也不是反自反的R是对称的 R不是反对

22、称的 R不是传递的。 】R=, , , , , , , 易知 R既不是自反也不是反自反的R是对称的 R不是反对称的 R不是传递的。 2、在一棵有2个2度顶点，4个3度顶点，其余顶点都是树叶的无向树中，应该有几片树叶？ 问题反馈【教师释疑】正确答案：【一个有限图中，各结点的度数总和是边数的2倍；而树中的边数为结点数减1。根据这两点，可知树中各结点的度数总和=2（树中点数-1），设树叶有x个，于是，22+34+x2（2+4+x-1）得x6 】一个有限图中，各结点的度数总和是边数的2倍；而树中的边数为结点数减1。根据这两点，可知树中各结点的度数总和=2（树中点数-1），设树叶有x个，于是，22+34

23、+x2（2+4+x-1）得x6 3、在具有n个顶点的完全图Kn中删去多少条边才能得到树？ 问题反馈【教师释疑】正确答案：【n个顶点的完全图Kn中共有n（n-1）/2条边，n个顶点的树应有n-1条边，于是，删去的边有：n（n-1）/2-（n-1）=（n-1）（n-2）/2 】n个顶点的完全图Kn中共有n（n-1）/2条边，n个顶点的树应有n-1条边，于是，删去的边有：n（n-1）/2-（n-1）=（n-1）（n-2）/2 4、一棵树有两个结点度数为2，一个结点度数为3，三个结点度数为4，问它有几个度数为1的结点？ 问题反馈【教师释疑】正确答案：【我们知道一个有限图中，各结点的度数总和是边数的2倍

24、；而树中的边数为结点数减1。根据这两点，可知树中各结点的度数总和=2（树中点数-1），设树叶有x个，于是，22+3+34+x=2（2+1+3+x-1）得x=9。 】我们知道一个有限图中，各结点的度数总和是边数的2倍；而树中的边数为结点数减1。根据这两点，可知树中各结点的度数总和=2（树中点数-1），设树叶有x个，于是，22+3+34+x=2（2+1+3+x-1）得x=9。 5、已知无向图G有11条边，2度与3度顶点各2个，其余都是4度顶点，求G中共有几个顶点。（写出过程） 问题反馈【教师释疑】正确答案：【我们知道一个有限图中，各结点的度数总和是边数的2倍,于是，设共有x个结点，得22+32+4

25、（x22）211解得，x7所以图G中共有7个顶点 】我们知道一个有限图中，各结点的度数总和是边数的2倍,于是，设共有x个结点，得22+32+4（x22）211解得，x7所以图G中共有7个顶点 6、对60个学生参加课外活动的情况进行调查。结果发现，25人参加物理小组，26人参加化学小组，26人参加生物小组。9人既参加物理小组又参加生物小组，11人既参加物理小组又参加化学小组，8人既参加化学小组又参加生物小组。8人什么小组也没参加，回答下列各问题：（1）有多少人参加了3个小组？ （2）只参加一个小组的有多少人？ 问题反馈【教师释疑】正确答案：【A=x|x参加物理小组,|A|=25B=x|x参加化学小组,|B|=26C=x|x参加生物小组,|C|=26E=x|x设同时参加3个小组的人数为x，即|ABC|=x 则由已知条件得：|AB|-|ABC|=11-x |AC|-|ABC|=9-x |BC|-|ABC|=8-x |A-(BC)=|A|-(11-x)-(9-x)-x=25-11+x-9+x-x=5+x 同理 |B-(AC)|=26-11+x-8+x-x=7+x