离散数学简答题.docx
《离散数学简答题.docx》由会员分享，可在线阅读，更多相关《离散数学简答题.docx（41页珍藏版）》请在冰点文库上搜索。
离散数学简答题
1、设简单图G所有结点的度数之和为12，则G一定有_____条边。
问题反馈
【教师释疑】
正确答案：
【6】
6
2、设X={a,b,c},Ix是X上恒等关系，要使Ix∪{〈a,b〉，〈b,c〉，〈c,a〉，〈b,a〉}∪R为X上的等价关系，R应取_______.问题反馈
【教师释疑】
正确答案：
【{〈a,c〉,〈c,b〉}】
{〈a,c〉,〈c,b〉}
3、命题公式的任意两个不同极小项的合取式一定为_________.问题反馈
【教师释疑】
正确答案：
【永假式】
永假式
4、一个公式在等价意义下，_______范式写法是唯一的。
问题反馈
【教师释疑】
正确答案：
【主析取】
主析取
5、若P：
他聪明；Q：
他用功；则“他虽聪明，但不用功”，可符号化为_______问题反馈
【教师释疑】
正确答案：
【P∧┐Q】
P∧┐Q
6、设R是A上的二元关系,且RRR为R的子集,可以肯定R应是_____关系。
问题反馈
【教师释疑】
正确答案：
【传递】
传递
7、设集合A＝{1,2,3,4}，A上的二元关系R＝{（1,1）,（1,2）,（2,3）},S＝{（1,3）,（2,3）,（3,2）}。
则R×S＝__________________,问题反馈
【教师释疑】
正确答案：
【{（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，其中A＝{1,2,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},则从A∩B＝_________________________;问题反馈
【教师释疑】
正确答案：
【{4}】
{4}
12、设A={a,b,{a,b}}，B={a,b}，则B－A=________问题反馈
【教师释疑】
正确答案：
【Φ】
Φ
13、
设G是具有8个顶点的树，则G中增加_________条边才能把G变成完全图。
问题反馈
【教师释疑】
正确答案：
【21】
21
14、设集合A＝{2,3,4,5,6}，R是A上的整除，则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|-1≤x≤1,x∈R},B={x|0≤x<2,x∈R},则A-B=__________________________.问题反馈
【教师释疑】
正确答案：
【{x|-1≤x<0,x∈R}】
{x|-1≤x<0,x∈R}
16、设R是集合A上的等价关系，则R所具有的关系的三个特性是_________,对称性,传递性.问题反馈
【教师释疑】
正确答案：
【自反性】
自反性
17、设G是连通平面图，有5个顶点，6个面，则G的边数是_____条。
问题反馈
【教师释疑】
正确答案：
【9】
9
18、p：
天气好；q：
我去游玩．命题”如果天气好，则我去游玩”符号化为_________问题反馈
【教师释疑】
正确答案：
【p→q】
p→q
19、设A={2,4,6}，A上的二元运算*定义为：
a*b=max{a,b}，则在独异点中，零元是_____。
问题反馈
【教师释疑】
正确答案：
【6】
6
20、设A={3,6,9}，A上的二元运算*定义为：
a*b=min{a,b}，则在独异点中，单位元是____问题反馈
【教师释疑】
正确答案：
【9】
9
21、命题“你喜欢唱歌吗？
”的真值为_____.问题反馈
【教师释疑】
正确答案：
【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=max{a,b}，则在独异点中，单位元是_____。
问题反馈
【教师释疑】
正确答案：
【2】
2
27、设A={3,6,9}，A上的二元运算*定义为：
a*b=min{a,b}，则在独异点中，零元是_____.问题反馈
【教师释疑】
正确答案：
【3】
3
28、设〈G,*〉是一个群，若a,b,x∈G，a*x=a*b，则x=_____.问题反馈
【教师释疑】
正确答案：
【b】
b
29、代数系统是一个群，则G的等幂元是_______。
问题反馈
【教师释疑】
正确答案：
【单位元】
单位元
30、素数阶群一定是_______群问题反馈
【教师释疑】
正确答案：
【循环】
循环
31、有限布尔代数的元素的个数一定等于______的正整数次幂问题反馈
【教师释疑】
正确答案：
【2】
2
32、设G是一个哈密尔顿图，则G一定是______图问题反馈
【教师释疑】
正确答案：
【连通】
连通
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、
在一棵根树中，仅有一个结点的入度为，称为树根。
问题反馈
【教师释疑】
正确答案：
【0】
0
38、所谓_______是指不能再分解的命题问题反馈
【教师释疑】
正确答案：
【原子命题】
原子命题
39、在命题演算中，两个永真式的合取、析取、条件、双条件均为____式。
问题反馈
【教师释疑】
正确答案：
【永真】
永真
40、树是不包含_____的连通图。
问题反馈
【教师释疑】
正确答案：
【回路】
回路
41、设X={1，3，5，9，15，45}，R是X上的整除关系，则R是X上的偏序，其最大元是___.问题反馈
【教师释疑】
正确答案：
【45】
45
42、格L是分配格，当且仅当L既不含有与五角格同构的子格，也不含有与______同格的子格。
问题反馈
【教师释疑】
正确答案：
【钻石格】
钻石格
43、
有理数集Q中的*运算定义如下：
a*b=a+b-ab，则*运算的单位元是__________。
问题反馈
【教师释疑】
正确答案：
【0】
0
44、在根树中，如果每一个结点的出度______m或0，则称这棵树为完全m叉树。
问题反馈
【教师释疑】
正确答案：
【等于】
等于
45、一个重言式与一个矛盾式的析取是________式。
问题反馈
【教师释疑】
正确答案：
【重言】
重言
46、设复合函数g·f是从A到C的函数，如果g·f是满射，那么________必是满射。
问题反馈
【教师释疑】
正确答案：
【g】
g
47、设是格，其中A={1，2，3，4，6，8，12，24}，≤为整除关系，则3的补元是________。
问题反馈
【教师释疑】
正确答案：
【8】
8
48、设S是非空有限集，代数系统中，其中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：
Z→E，f（x）=2x，则f是___射。
问题反馈
【教师释疑】
正确答案：
【双】
双
51、设无向图G的边数为m，结点数为n，则G是树的条件是___________.问题反馈
【教师释疑】
正确答案：
【G连通且n=m+1】
G连通且n=m+1
52、一个连通的无向图G，如果它的所有结点的度数都是偶数，那么它具有一条_______问题反馈
【教师释疑】
正确答案：
【欧拉回路】
欧拉回路
53、Ａ是集合，|A|=10，则|P（A）|=_____问题反馈
【教师释疑】
正确答案：
【1024】
1024
54、一颗二叉树后序遍历的结果是bdeca，中序遍历的结果是badce，则根结点的右子树有____个结点。
问题反馈
【教师释疑】
正确答案：
【3】
3
55、设G是有5个顶点的完全图，则从G中删去_______条边可以得到树。
问题反馈
【教师释疑】
正确答案：
【6】
6
56、任意一个具有2个或以上元的半群，它不可能是____。
问题反馈
【教师释疑】
正确答案：
【群】
群
57、设R1，R2是集合A＝{1，2，3，4}上的两个关系，其中R1＝{（1，1），（2，2），（2，3），（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是等价关系则R∩S必为_____关系问题反馈
【教师释疑】
正确答案：
【反对称】
反对称
61、P={a、b、c、d}的最大划分是（）问题反馈
【教师释疑】
正确答案：
【{{a},{b}，{c}，{d}}】
{{a},{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中，表达式（a∧b）∨（a∧b∧c）∨（b∧c）的等价式是_________.问题反馈
【教师释疑】
正确答案：
【b∧（a∨c）】
b∧（a∨c）
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：
A→A/R使g
（1）=________.问题反馈
【教师释疑】
正确答案：
【｛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：
长一智。
命题"只有经一堑，才能长一智"符号化为______.问题反馈
【教师释疑】
正确答案：
【q→p】
q→p
74、命题公式┐（q→q）∧p的真值为____.问题反馈
【教师释疑】
正确答案：
【0】
0
75、非平凡的无向树至少有____片树叶．问题反馈
【教师释疑】
正确答案：
【2】
2
76、若一棵完全二元（叉）树有2n-1个顶点，则它_____片树叶。
问题反馈
【教师释疑】
正确答案：
【n】
n
77、集合{1，2，3，5，6，15，30}关于整除关系构成___问题反馈
【教师释疑】
正确答案：
【格】
格
78、A,B为任意集合，则他们的共同子集是______.问题反馈
【教师释疑】
正确答案：
【;】
;
79、设函数f：
N→N（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，则其幂集的元素个数为______．问题反馈
【教师释疑】
正确答案：
【1024】
1024
83、如果R1和R2是A上的自反关系，则R1∪R2，R1∩R2，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＝的邻接矩阵A（D）如下所示，那么|E|＝.
问题反馈
【教师释疑】
正确答案：
【7】
7
88、设〈s,*〉是群，则那么s中除______外，不可能有别的幂等元问题反馈
【教师释疑】
正确答案：
【单位元】
单位元
89、若H1∧H2∧…∧Hn是______，则称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图的是____
问题反馈
【教师释疑】
正确答案：
【（d）】
（d）
93、n个命题变元的___________称为小项问题反馈
【教师释疑】
正确答案：
【合取式】
合取式
94、前提引入规则：
在证明的任何步骤上都可以引入前提，简称___________规则。
问题反馈
【教师释疑】
正确答案：
【P】
P
95、自由变元代入规则是指对某_______出现的个体变元可用个体常元或用与原子公式中所有个体变元不同的个体变元去代入，且处处代入。
问题反馈
【教师释疑】
正确答案：
【自由】
自由
96、设代数系统是环，则是___________群。
问题反馈
【教师释疑】
正确答案：
【阿贝尔】
阿贝尔
97、若一条路中，所有的_____均不相同，称为迹。
问题反馈
【教师释疑】
正确答案：
【边】
边
98、设是一个偏序集，如果A中任意两个元素都有最小上界与最大下界，则称为____。
问题反馈
【教师释疑】
正确答案：
【格】
格
99、n点完全图记为Kn，那么当________时，Kn是平面图问题反馈
【教师释疑】
正确答案：
【n≤4】
n≤4
100、设A={l，2，3，4}，A上的二元关系R={<1，2>，<2，3>，<3，2>}，S={，<2，3>，<4，3>}，则R—S）-1=________。
问题反馈
【教师释疑】
正确答案：
【{<2,1>,<2,3>}】
{<2,1>,<2,3>}
1、设A={1,2,3,4,5,6,7,8,9,10}，R是A上的二元关系，
R={|x,y∈A∧x+y=10}说明R具有哪些性质。
问题反馈
【教师释疑】
正确答案：
【R={<1,9>,<2,8>,<3,7>,<4,6>,<5,5>,<9,1>,<8,2>,<7,3>,<6,4>}易知R既不是自反也不是反自反的R是对称的R不是反对称的R不是传递的。
】
R={<1,9>,<2,8>,<3,7>,<4,6>,<5,5>,<9,1>,<8,2>,<7,3>,<6,4>}易知R既不是自反也不是反自反的R是对称的R不是反对称的R不是传递的。
2、在一棵有2个2度顶点，4个3度顶点，其余顶点都是树叶的无向树中，应该有几片树叶？
问题反馈
【教师释疑】
正确答案：
【一个有限图中，各结点的度数总和是边数的2倍；而树中的边数为结点数减1。
根据这两点，可知树中各结点的度数总和=2´（树中点数-1），设树叶有x个，于是，2´2+3´4+x＝2´（2+4+x-1）得x＝6】
一个有限图中，各结点的度数总和是边数的2倍；而树中的边数为结点数减1。
根据这两点，可知树中各结点的度数总和=2´（树中点数-1），设树叶有x个，于是，2´2+3´4+x＝2´（2+4+x-1）得x＝6
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倍；而树中的边数为结点数减1。
根据这两点，可知树中各结点的度数总和=2´（树中点数-1），设树叶有x个，于是，2´2+3+3´4+x=2´（2+1+3+x-1）得x=9。
】
我们知道一个有限图中，各结点的度数总和是边数的2倍；而树中的边数为结点数减1。
根据这两点，可知树中各结点的度数总和=2´（树中点数-1），设树叶有x个，于是，2´2+3+3´4+x=2´（2+1+3+x-1）得x=9。
5、已知无向图G有11条边，2度与3度顶点各2个，其余都是4度顶点，求G中共有几个顶点。
（写出过程）问题反馈
【教师释疑】
正确答案：
【我们知道一个有限图中，各结点的度数总和是边数的2倍,于是，设共有x个结点，得2×2+3×2+4（x－2－2）＝2×11解得，x＝7所以图G中共有7个顶点】
我们知道一个有限图中，各结点的度数总和是边数的2倍,于是，设共有x个结点，得2×2+3×2+4（x－2－2）＝2×11解得，x＝7所以图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，即|A∩B∩C|=x①则由已知条件得：
|A∩B|-|A∩B∩C|=11-x②|A∩C|-|A∩B∩C|=9-x③|B∩C|-|A∩B∩C|=8-x④|A-（B∪C）=|A|-（11-x）-（9-x）-x=25-11+x-9+x-x=5+x⑤同理|B-（A∪C）|=26-11+x-8+x-x=7+x
升级会员 