离散数学年月真题
02324202210
1、【单选题】令p:天下大雨,q:小王早到。命题“只要天不下大雨,小王就会早到”的符
号化形式为
p→q
q→p
A:
B:
C:
答D:案:C
2、【单选题】设令F(x):x是火车,G(x):x是汽车,L(x,y):x比y快。命题“不存在比所有
的火车都快的汽车”的符号化形式为
A:
B:
C:
答D:案:C
3、【单选题】下列谓词公式中,_不是_前束范式的为
A:
B:
C:
答D:案:A
4、【单选题】下列_不是_欧拉图的为
A:
B:
C:
答D:案:B
5、【单选题】设集合A={a,b,c,d},现有A上的二元关系R={,,,},则A是
自反的
对称的
A:
反对称的
B:
传递的
C:
答D:案:C
6、【单选题】一个6阶简单无向图G,其各结点度数之和_不可能_为
10
12
A:
18
B:
34
C:
答D:案:D
7、【单选题】下列谓词恒等式,_不正确_的是
A:
B:
C:
答D:案:A
8、【单选题】下列度数序列_不能_构成无向树的是
{1,1,1,2,3}
{1,1,2,2,2}
A:
{1,1,1,1,4}
B:
{1,2,3,3,3}
C:
D:
答案:D
9、【单选题】存在经过图中所有边一次且仅一次的回路的图是
关系图
哈斯图
A:
欧拉图
B:
咯密顿图
C:
答D:案:C
10、【单选题】_不能_用来表达集合A上的二元关系R的方法是
关系矩阵
集合表达式
A:
关系图
B:
邻接矩阵
C:
答D:案:D
11、【单选题】已知A、B、C、D是任意集合,则下列各式_不成立_的是
(AUB)×(CUD)=(A×C)U(B×D)
(AUB)×C=(A×C)U(B×C)
A:
B:
(A-B)×C=(A×C)-(B×C)
C:
答D:案:A
12、【单选题】要从一颗4阶树得到完全图K4,需要添加的边数为
1
2
A:
3
B:
4
C:
答D:案:C
13、【单选题】设R、S是集合A上的二个不同的等价关系,则下列不是等价关系的为
RUS
R-S
A:
B:
R∩S
C:
答D:案:B
14、【单选题】下图中4个偏序集的图形,能构成格的是
A:
B:
C:
D:
答案:A
15、【单选题】下列函数均为f:NxN→N,其中_不是_满射的为
f()=xy
f()=x+y
A:
f()=x2+y2+1
B:
f()=|x-y|
C:
答D:案:C
16、【问答题】用列真值表的方法说明下列逻辑等价式成立。
答案:
17、【问答题】求命题公式((pVq)→r)→p的主析取范式。
答案:
18、【问答题】对于集合A={1,2,3}上的二元关系R={,,,,}和S={,,,},判断其是否具有右边列出的
那些性质,将题28表绘制在答题卡上作答。(具各某项性质填写“是”,不具备填写
“否”)
答案:
19、【问答题】画出下列集合关于整除关系的哈斯图:{1,2,5,10,11,22,55,110}并判
定该偏序集是否构成格。
答案:
20、【问答题】有向图D如题30图所示,回答下列问题:(1)写出D的邻接矩阵A;
(2)D中长度为1、2、3、4的通路备有多少条,其中长度为1,2,3,4的回路分别为多少条?
答案:
21、【问答题】设R1、R2为集合A上的关系,证明
答案:
22、【问答题】设是一个群,|A|=2n,n∈Z+。证明:在A中至少存在一个元素a,满
足a≠e且使得α*α=e.其中e是单位元。
答案:
23、【问答题】证明前提“在本离散教学课上的每个人都掌握一定的图论基础知识”和“小
华是本课上的学生”,可得结论“小华掌握一定的图论基础知识”。
答案:
24、【问答题】今有a、b、c、d、e、f、g共7人,已知下列情况:(1)a会讲英语;
(2)b会讲英语和汉语;(3)c会讲英语、西班牙语和俄语;(4)d会讲汉语和日语;(5)e
会讲德语和西班牙语,(6)f会讲法语、日语和俄语;(7)g会讲法语和德语。现在需要
让这7人围成一圈,应当怎样安排座位,才能让每个人都能和两边的人交谈?
答案:
25、【问答题】设R是定义在所有8位二进制数串构成的集合上的二元关系:如果s1和s2
中0的个数相同,则s1Rs2。(1)证明R是等价关系;(2)共有多少个等价类?(3)列举每
个等价类的一个成员。
答案:证明:(1)(a)显然,任意8位二进制数串与自身0的个数相同,所以R是自反的。
(b)对任意两个8位二进制数串s1和s2,如果s1和s2中0的个数相同,那么s1和s2中0
的个数也相同,即s2Rs1,所以R是对称的。(c)如果s1Rs2,即s1和s2中0的个数相同,
而且s2Rs3,即s2和s3中0的个数相同,那么s1和s3中0的个数必定相同,即s1Rs3,因
此R是传递的。综合(a)、(b)、(c)可知,R是等价关系。(2)解:所有8位二进制数串中
0的个数可以为0~8个,所以共有9个等价类。(3)列举9个等价类中每个的一个成员如
下:
00000000,00000001,00000011,00000111,00001111,00011111,00111111,01111111,111111
11
26、【填空题】设R为实数集合,f:R→R,f(x)=x2-3x+2,则f(3)=______,函数f的性质是
______。
答案:2非单非满函数(既不是单射也不是满射函数)
27、【填空题】设A={,,},B={,,},则
AUB=______,domA=______。
答案:{,,,,}{1,2,3}
28、【填空题】集合A={1,2,3,4},A上的关系R={,,,},则R2=______,R⁻¹=______。
答案:{}{,,,}
29、【填空题】设集合A有4个元素,则A的幂集P(A)有______个元素。
答案:16
30、【填空题】在整数域中,命题公式
的真值为______,命题公式
的真值为______。
答案:TF
31、【填空题】一个6阶无向简单图G为连通图,则G的边数至少为______条。
答案:5
32、【填空题】设T为完全二叉树,其叶结点数为7,则分支结点数为______。
答案:6
33、【填空题】设集合A={0,1,2,3,4,5,6},x、y∈A,x*y=(x+y)mod7、则群