电大历年离散数学试题汇总.docx
《电大历年离散数学试题汇总.docx》由会员分享,可在线阅读,更多相关《电大历年离散数学试题汇总.docx(51页珍藏版)》请在冰点文库上搜索。
电大历年离散数学试题汇总
计算机科学与技术专业级第二学期离散数学试题
2012年1月
一、单项选择题(每小题3分,本题共15分)1.C2.C3.B4.A5.D
1.若集合A的元素个数为10,则其幂集的元素个数为().
A.10B.100C.1024D.1
2.设A={a,b},B={1,2},R1,R2,R3是A到B的二元关系,且R1={,},R2={,,},R3={,},则()是从A到B的函数.
A.R1和R2B.R2C.R3D.R1和R3
3.设A={1,2,3,4,5,6,7,8},R是A上的整除关系,B={2,4,6},则集合B的最大元、最小元、上界、下界依次为().
A.8、2、8、2B.无、2、无、2
C.6、2、6、2D.8、1、6、1
4.若完全图G中有n个结点(n≥2),m条边,则当()时,图G中存在欧拉回路.
A.n为奇数B.n为偶数C.m为奇数D.m为偶数
5.已知图G的邻接矩阵为
则G有().
A.6点,8边B.6点,6边
C.5点,8边D.5点,6边
二、填空题(每小题3分,本题共15分)
6.设集合A={a},那么集合A的幂集是{,{a}}.
7.若R1和R2是A上的对称关系,则R1∪R2,R1∩R2,R1-R2,R2-R1中对称关系有4个.
8.设图G是有5个结点的连通图,结点度数总和为10,则可从G中删去1条边后使之变成树.
9.设连通平面图G的结点数为5,边数为6,则面数为3.
10.设个体域D={a,b},则谓词公式(x)(A(x)∧B(x))消去量词后的等值式为(A(a)∧B(b))∧(A(a)∧B(b)).
三、逻辑公式翻译(每小题6分,本题共12分)
11.将语句“今天有联欢活动,明天有文艺晚会.”翻译成命题公式.
设P:
今天有联欢活动,Q:
明天有文艺晚会,(2分)
P∧Q.(6分)
12.将语句“如果小王来,则小李去.”翻译成命题公式.
设P:
小王来,Q:
小李去(2分)
P→Q.(6分)
四、判断说明题(每小题7分,本题共14分)
判断下列各题正误,并说明理由.
13.若偏序集的哈斯图如图一所示,
则集合A的最大元为a,极小元不存在.
错误.(3分)
对于集合A的任意元素x,均有R(或xRa),所以a是集合A中的最大元.(5分)
但按照极小元的定义,在集合A中b,c,d均是极小元.(7分)
14.┐P∧(P→┐Q)∨P为永假式.
错误.(3分)
┐P∧(P→┐Q)∨P是由┐P∧(P→┐Q)与P组成的析取式,
如果P的值为真,则┐P∧(P→┐Q)∨P为真,(5分)
如果P的值为假,则┐P与P→┐Q为真,即┐P∧(P→┐Q)为真,
也即┐P∧(P→┐Q)∨P为真,
所以┐P∧(P→┐Q)∨P是永真式.(7分)
另种说明:
┐P∧(P→┐Q)∨P是由┐P∧(P→┐Q)与P组成的析取式,
只要其中一项为真,则整个公式为真.(5分)
可以看到,不论P的值为真或为假,┐P∧(P→┐Q)与P总有一个为真,
所以┐P∧(P→┐Q)∨P是永真式.(7分)
或用等价演算┐P∧(P→┐Q)∨PT
五.计算题(每小题12分,本题共36分)
15.设集合A={1,2,3,4},R={|x,yA;|xy|=1或xy=0},试
(1)写出R的有序对表示;
(2)画出R的关系图;
(3)说明R满足自反性,不满足传递性.
15.
(1)R={<1,1>,<2,2>,<3,3>,<4,4>,<1,2>,<2,1>,<2,3>,<3,2>,<3,4>,<4,3>}(3分)
(2)关系图如图二:
图二(6分)
(3)因为<1,1>,<2,2>,<3,3>,<4,4>均属于R,即A的每个元素构成的有序对均在R中,故R在A上是自反的.(9分)
因有<2,3>与<3,4>属于R,但<2,4>不属于R,所以R在A上不是传递的.
(12分)
16.设图G=,V={v1,v2,v3,v4,v5},E={(v1,v2),(v1,v3),(v2,v4),(v3,v5),(v4,v5)},试
(1)画出G的图形表示;
(2)写出其邻接矩阵;
(3)求出每个结点的度数;
(4)画出图G的补图的图形.
16.
(1)关系图如图三:
(3分)
(2)邻接矩阵
(6分)
(3)deg(v1)=2
deg(v2)=2
deg(v3)=2
deg(v4)=2
deg(v5)=2(9分)
(4)补图如图四
(12分)
17.求PQ∧R的合取范式与主析取范式.
P→(R∧Q)
┐P∨(R∧Q)(4分)
(┐P∨Q)∧(┐P∨R)(合取范式)(6分)
P→(R∧Q)
┐P∨(R∧Q)
(┐P∧(┐Q∨Q))∨(R∧Q)(7分)
(┐P∧┐Q)∨(┐P∧Q)∨(R∧Q)(8分)
((┐P∧┐Q)∧(┐R∨R))∨(┐P∧Q)∨(R∧Q)(9分)
(┐P∧┐Q∧┐R)∨(┐P∧┐Q∧R)∨(┐P∧Q)∨(R∧Q)(10分)
(┐P∧┐Q∧┐R)∨(┐P∧┐Q∧R)∨((┐P∧Q)∧(┐R∨R))∨(R∧Q)
(┐P∧┐Q∧┐R)∨(┐P∧┐Q∧R)∨(┐P∧Q∧┐R)∨(┐P∧Q∧R)∨(R∧Q)
(┐P∧┐Q∧┐R)∨(┐P∧┐Q∧R)∨(┐P∧Q∧┐R)∨
(┐P∧Q∧R)∨((┐P∨P)∧(R∧Q))
(┐P∧┐Q∧┐R)∨(┐P∧┐Q∧R)∨(┐P∧Q∧┐R)∨
(┐P∧Q∧R)∨(P∧R∧Q)(主析取范式)(12分)
说明:
此题解法步骤多样,若能按正确步骤求得结果,均可给分.
六、证明题(本题共8分)
18.设连通无向图G有14条边,3个4度顶点,4个3度顶点,其它顶点的度数均小于3,试说明G中可能有的顶点数.
证明:
可利用数列可图化及握手定理解答
顶点度数和为214=28,(2分)
28-(34+43)=4,则知其他顶点度数和为4,(4分)
对于有限图,若无零度顶点,则除4度及3度顶点外,可能的顶点情况有:
2个2度点;
1个2度点和2个1度点;
4个1度点,(6分)
即对应图的顶点数分别至少为9、10、11.(8分)
2011年7月
一、单项选择题(每小题3分,本题共15分)1.A2.C3.C4.D5.B
1.若集合A={1,{1},{2},{1,2}},则下列表述正确的是().
A.{2}AB.{1,2}A
C.1AD.2A
2.设G为无向图,则下列结论成立的是().
A.无向图G的结点的度数等于边数的两倍.
B.无向图G的结点的度数等于边数.
C.无向图G的结点的度数之和等于边数的两倍.
D.无向图G的结点的度数之和等于边数.
3.图G如图一所示,以下说法正确的是().
A.{(a,b)}是边割集
B.{a,c}是点割集
C.{d}是点割集
D.{(c,d)}是边割集
图一
4.设集合A={1},则A的幂集为().
A.{{1}}B.{1,{1}}
C.{,1}D.{,{1}}
5.设A(x):
x是人,B(x):
x犯错误,则命题“没有不犯错误的人”
可符号化为().
A.┐(
x)(A(x)→┐B(x))B.┐(
x)(A(x)∧┐B(x))
C.┐(
x)(A(x)∧B(x))D.(
x)(A(x)∧B(x))
二、填空题(每小题3分,本题共15分)
6.命题公式
的真值是 真(或T,或1) .
7.若无向图T是连通的,则T的结点数v与边数e满足关系v=e+1时,T是树.
8.无向图G是欧拉图的充分必要条件是G是连通的且结点度数都是偶数.
9.设集合A={1,2}上的关系R={<2,2>,<1,2>},则在R中仅需加入一个元素<1,1>,就可使新得到的关系为自反的.
10.(x)(P(x)→R(y)∨S(z))中的约束变元有x.
三、逻辑公式翻译(每小题6分,本题共12分)
11.将语句“雪是黑色的.”翻译成命题公式.
设P:
雪是黑色的,(2分)
则命题公式为:
P.(6分)
12.将语句“如果明天下雨,则我们就在室内上体育课.”翻译成命题公式.
设P:
如果明天下雨,Q:
我们在室内上体育课,(2分)
则命题公式为:
PQ.(6分)
四、判断说明题(每小题7分,本题共14分)
判断下列各题正误,并说明理由.
13.设集合A={1,2},B={3,4},从A到B的关系为f={<1,3>,<1,4>},则f是A到B的函数.
错误.(3分)
因为A中元素1有B中两个不同的元素与之对应,故f不是A到B的函数.(7分)
14.设G是一个连通平面图,有5个结点9条边,则G有6个面.
正确.(3分)
因G是一个连通平面图,满足欧拉定理,有v-e+r=2,
所以r=2-(v-e)=2-(5-9)=6(7分)
五.计算题(每小题12分,本题共36分)
15.试求出P→(R∧Q)的合取范式.
P→(R∧Q)┐P∨(R∧Q)(6分)
(┐P∨R)∧(┐P∨Q)(合取范式)(12分)
16.设A={{1},{1,2},1},B={1,2,{2}},试计算
(1)(A∩B)
(2)(A∪B)(3)(A∩B)A.
(1)(A∩B)={1}(4分)
(2)(A∪B)={1,2,{1},{2},{1,2}}(8分)
(3)(A∩B)A=(12分)
17.试画一棵带权为2,3,3,4,5,的最优二叉树,并计算该最优二叉树的权.
最优二叉树如图二所示.
(10分)
图二
权为23+33+32+42+52=39(12分)
六、证明题(本题共8分)
18.试证明:
若R与S是集合A上的对称关系,则R∩S也是集合A上的对称关系.
证明:
设x,yA,因为R对称,所以若R,则R.(2分)
因为S对称,所以若S,则S.(4分)
于是若R∩S则R且S
即R且S(6分)
也即R∩S,故R∩S是对称的.(8分)
中央广播电视大学2010—2011学年度第一学期“开放本科”期末考试
离散数学(本)试题
2011年1月
一、单项选择题(每小题3分,本题共15分)1.A2.D3.B4.D5.C
1.若集合A={a,{1}},则下列表述正确的是().
A.{1}AB.{1}A
C.{a}AD.A
2.设图G=,vV,则下列结论成立的是().
A.deg(v)=2EB.deg(v)=E
C.
D.
3.如图一所示,以下说法正确的是().
A.(e,c)是割边B.(d,e)是割边
C.(b,a)是割边D.(b,c)是割边
4.命题公式(P∨Q)的合取范式是().
A.PB.(P∧Q)
C.(P∨P)D.(P∨Q)
5.下列等价公式成立的为().
A.PQPQB.QPPQ
C.PPQQD.PPQ
二、填空题(每小题3分,本题共15分)
6.设集合A={0,1,2},B={1,2,3,4,},R是A到B的二元关系,
则R的有序对集合为 {<1,1>,<1,2>,<2,1>,<2,2>} .
7.设G是连通平面图,v,e,r分别表示G的结点数,边数和面数,则v,e和r满足的关系式v-e+r=2.
8.设G=是有20个结点,25条边的连通图,则从G中删去6条边,可以确定图G的一棵生成树.
9.无向图G存在欧拉回路,当且仅当G所有结点的度数全为偶数且连通.
10.设个体域D={1,2},则谓词公式
消去量词后的等值式为A
(1)A
(2).
三、逻辑公式翻译(每小题6分,本题共12分)
11.将语句“如果小李学习努力,那么他就会取得好成绩.”翻译成命题公式.
12.将语句“小张学习努力,小王取得好成绩.”翻译成命题公式.
11.设P:
小李学习努力,Q:
小李会取得好成绩,(2分)
PQ.(6分)
12.设P:
小张学习努力,Q:
小王取得好成绩,(2分)
PQ.(6分)
四、判断说明题(每小题7分,本题共14分)
判断下列各题正误,并说明理由.
13.如果R1和R2是A上的自反关系,则R1R2是自反的.
14.如图二所示的图中存在一条欧拉回路.
13.正确.(3分)
R1和R2是自反的,xA,R1,R2,
则R1R2,
所以R1R2是自反的.(7分)
14.正确.(3分)
因为图G为连通的,且其中每个顶点的度数为偶数.(7分)
五.计算题(每小题12分,本题共36分)
15.设A={{2},1,2},B={1,{1,2}},试计算
(1)(AB);
(2)(A∩B);(3)A×B.
16.设G=,V={v1,v2,v3,v4,v5},E={(v1,v3),(v2,v3),(v2,v4),(v3,v4),(v3,v5)},试
(1)给出G的图形表示;
(2)写出其邻接矩阵;
(3)求出每个结点的度数;(4)画出其补图的图形.
17.设谓词公式
,试
(1)写出量词的辖域;
(2)指出该公式的自由变元和约束变元.
15.
(1)AB={2,{2}}(4分)
(2)A∩B={1}(8分)
(3)A×B={<{2},1>,<{2},{1,2}>,<1,1>,<1,{1,2}>,
<2,1>,<2,{1,2}>}(12分)
16.
(1)G的图形表示如图三:
(3分)
(2)邻接矩阵:
(6分)
(3)v1,v2,v3,v4,v5结点的度数依次为1,2,4,2,1(9分)
(4)补图如图四:
(12分)
17.
(1)x量词的辖域为
,(2分)
z量词的辖域为
(4分)
y量词的辖域为
.(6分)
(2)自由变元为
中的y,以及
中的z(9分)
约束变元为
中的x与
中的z,以及
中的y.(12分)
六、证明题(本题共8分)
18.试证明集合等式A(BC)=(AB)(AC).
18.证明:
设S=A(BC),T=(AB)(AC),若x∈S,则x∈A或x∈BC,(1分)
即x∈A或x∈B且x∈A或x∈C.(2分)
也即x∈AB且x∈AC,(3分)
即x∈T,所以ST.(4分)
反之,若x∈T,则x∈AB且x∈AC,(5分)
即x∈A或x∈B且x∈A或x∈C,(6分)
也即x∈A或x∈BC,即x∈S,所以TS.(7分)
因此T=S.(8分)
2011年1月
一、单项选择题(每小题3分,本题共15分)1.D2.B3.C4.A5.B
1.若集合A={a,b},B={a,{a,b}},则().
A.ABB.AB
C.ABD.AB
2.集合A={x|x为小于10的自然数},集合A上的关系R={|x+y=10且x,y
A},则R的性质为().
A.自反的B.对称的
C.传递且对称的D.反自反且传递的
3.设有向图(a)、(b)、(c)与(d)如图一所示,则下列结论成立的是().
图一
A.(a)仅为弱连通的B.(b)仅为弱连通的
C.(c)仅为弱连通的D.(d)仅为弱连通的
4.设图G的邻接矩阵为
则G的边数为().
A.5B.6C.7D.8
5.下列公式()为永真式.
A.PQPQB.(P(QP))(P(PQ))
C.(Q(PQ))(Q(PQ))D.(P(PQ))Q
二、填空题(每小题3分,本题共15分)
6.设集合A={1,2,3},那么集合A的幂集是{,{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}}.
7.设A={a,b},B={1,2},作f:
A→B,则不同的函数个数为4.
8.若A={1,2},R={|xA,yA,x+y<4},则R的自反闭包为{<1,1>,<2,2>,<1,2>,<2,1>}.
9.无向连通图在结点数v与边数e满足e=v-1关系时是树.
10.(x)(A(x)→B(x))∨C(x,y)中的自由变元为C(x,y)中的x与y.
三、逻辑公式翻译(每小题6分,本题共12分)
11.将语句“他们去旅游,仅当明天天晴.”翻译成命题公式.
12.将语句“今天没有下雪.”翻译成命题公式.
11.设P:
他们去旅游,Q:
明天天晴,(2分)
P→Q.(6分)
12.设P:
今天下雪,(2分)
P.(6分)
四、判断说明题(每小题7分,本题共14分)
判断下列各题正误,并说明理由.
13.汉密尔顿图一定是欧拉图.
错误.(3分)
存在汉密尔顿图不是欧拉图.(5分)
反例见图二.
(7分)
14.下面的推理是否正确,试予以说明.
(1)(x)(F(x)→G(y))前提引入
(2)F(y)→G(y)ES
(1).
1、错误.(3分)
(2)应为F(a)→G(y),换名时,约束变元与自由变元不能混淆.(7分)
五.计算题(每小题12分,本题共36分)
15.设A={0,1,2,3,4,5,6},R={|xA,yA且x+y<1},S={|xA,yA且x+y3},试求R,S,RS,R-1,S-1,r(R).
R={<0,0>}(2分)
S={<0,0>,<0,1>,<0,2>,<0,3>,<1,0>,<1,1>,<1,2>,<2,0>,<2,1>,<3,0>}(4分)
RS={<0,0>,<0,1>,<0,2>,<0,3>}(6分)
R-1={<0,0>}(8分)
S-1=S(10分)
r(R)=IA.(12分)
16.画一棵带权为1,2,2,3,6的最优二叉树,计算它们的权.
14
最优二叉树如图四:
8
6
o
o
5
o
3
o
o
o
3
2
2
1
o
o
图四(10分)
权为:
13+23+23+33+61=30(12分)
注:
其他正确的最优二叉树参照给分.
17.求(P∨Q)→(R∨Q)的析取范式,合取范式.
(P∨Q)→(R∨Q)
(P∨Q)∨(R∨Q)(4分)
(P∧Q)∨(R∨Q)
(P∨R∨Q)∧(Q∨R∨Q)
(P∨R∨Q)析取、合取范式(12分)
注:
其他正确答案参照给分.
六、证明题(本题共8分)
18.试证明集合等式A(BC)=(AB)(AC).
证明:
设S=A∩(B∪C),T=(A∩B)∪(A∩C),若x∈S,则x∈A且x∈B∪C,即x∈A且x∈B或x∈A且x∈C,
也即x∈A∩B或x∈A∩C,即x∈T,所以ST.(4分)
反之,若x∈T,则x∈A∩B或x∈A∩C,
即x∈A且x∈B或x∈A且x∈C
也即x∈A且x∈B∪C,即x∈S,所以TS.
因此T=S.(8分)
2010年7月
一、单项选择题(每小题3分,本题共15分)1.B2.D3.B4.C5.B
1.若集合A={1,{2},{1,2}},则下列表述正确的是().
A.2AB.{1}A
C.1AD.2A
2.已知一棵无向树T中有8个顶点,4度、3度、2度的分支点各一个,T的树叶数为
().
A.6B.4C.3D.5
3.设无向图G的邻接矩阵为
则G的边数为().
A.1B.7C.6D.14
4.设集合A={a},则A的幂集为().
A.{{a}}B.{a,{a}}
C.{,{a}}D.{,a}
5.下列公式中()为永真式.
A.ABABB.AB(AB)
C.ABABD.AB(AB)
二、填空题(每小题3分,本题共15分)
6.命题公式
的真值是 假(或F,或0) .
7.若无向树T有5个结点,则T的边数为4.
8.设正则m叉树的树叶数为t,分支数为i,则(m-1)i=t-1.
9.设集合A={1,2}上的关系R={<1,1>,<1,2>},则在R中仅需加一个元素<2,1>,就可使新得到的关系为对称的.
10.(x)(A(x)→B(x,z)∨C(y))中的自由变元有z,y.
三、逻辑公式翻译(每小题6分,本题共12分)
11.将语句“今天上课.”翻译成命题公式.
设P:
今天上课,(2分)
则命题公式为:
P.(6分)
12.将语句“他去操场锻炼,仅当他有时间.”翻译成命题公式.
设P:
他去操场锻炼,Q:
他有时间,(2分)
则命题公式为:
PQ.(6分)
四、判断说明题(每小题7分,本题共14分)
判断下列各题正误,并说明理由.
13.设集合A={1,2},B={3,4},从A到B的关系为f={<1,3>},则f是A到B的函数.
14.设G是一个有4个结点10条边的连通图,则G为平面图.
13.错误.(3分)
因为A中元素2没有B中元素与之对应,故f不是A到B的函数.(7分)
14.错误.(3分)
不满足“设G是一个有v个结点e条边的连通简单平面图,若v≥3,则e≤3v-6.”
(7分)
五.计算题(每小题12分,本题共36分)
15.试求出(P∨Q)→(R∨Q)的析取范式.
(P∨Q)→(R∨Q)┐(P∨Q)∨(R∨Q)(4分)
(┐P∧┐Q)∨(R∨Q)(8分)
(┐P∧┐Q)∨R∨Q(析取范式)(12分)
16.设A={{1},1,2},B={1,{2}},试计算
(1)A∩B
(2)A∪B(3)A(A∩B).
(1)A∩B={1}(4分)
(2)A∪B={1,2,{1},{2}}(8分)
(3)A(A∩B)={{1},2}(12分)
17.图G=,其