电大201307离散数学试题及答案

试卷代号：1009中央广播电视大学2012—2013学年度第二学期“开放本科”期末考试(半开卷)离散数学(本)试题2013年7月一、单项选择题(每小题3分，本题共15分)1．若集合A={a，b}，则下列表述正确的是()。A．∈AB．{a}∈AC．{a，b}∈AD．{a}⊆A2．设A={1，2，3，4，5，6}，B=“{”1，2，3}，A到B的关系R={（x，y）︳x,∈A,y∈B,，x=y²}则R=()。A．{1，1，2，4)B．(1，1，4，2}C．{1，1，6，3)D．{1，1，2，1)3．n阶无向完全图Kn的边数及每个结点的度数分别是()。A．n(n一1)／2，n一1B．n一1，nC．n(n一1)，n一1D．n(n一1)，，n4．设无向完全图Kn有n个结点(n≥2)，m条边，当()时，Kn中存在欧拉回路。A．m为奇数B．n为偶数C．n为奇数D．m为偶数5．设个体域为整数集，则公式∀x∃y(x+y=0)的解释可为()。A．存在一整数x有整数y满足x+y=0B．对任一整数x存在整数y满足x+y=0C．存在一整数x对任意整数y满足x+y=0D．任一整数x对任意整数y满足z+y=O二、填空题(每小题3分。本题共15分)6．设集合A={1，2，3，4)，B={3，4，5，6)，C={5，6，7，8)，则A∩BUC等于————。7．设A=(a，6)，B={1，2)，C={4，5)，从A到B的函数f={a，1，b，2}，从B到C的函数g={1，5，2，4}，则等于————。8．设G是一个图，结点集合为V，边集合为E，则G的结点度数之和为————。9．设G是具有n个结点m条边k个面的连通平面图，则n+k-m等于————。10．设个体域D={1，2，3，4)，A(x)为“x等于3”，则谓词公式(∃x)A(x)的真值为————。三、逻辑公式翻译(每小题6分，本题共12分)。11．将语句“他们明天去旅游，仅当明天天晴．”翻译成命题公式．12．将语句“小王是个学生，小李是个职员，而小张是个军人．”翻译成命题公式．四、判断说明题(每小题7分，本题共14分)。判断下列各题正误，并说明理由．13．设A={1，2，3)，R={1，1，2，2，1，2，2，1}，则R是等价关系．14．谓词公式(∃x)P(x，y)→(∀z)Q(z，y，z)中∃x量词的辖域为P(z，y)→(∀z)Q(x，y，z)．五、计算题(每小题12分，本题共36分)。15．设集合A={a，{b}，c)，B={{a}，C}，试计算：(1)(A∩B)；(2)(B—A)；(3)(A∩B)×B)．16．设G=V，E，V={v1，v2，v3，v4，v5)，E={(v1，v3)，(v1，v5)，(v2，v3)，(v2，v5)，(v3，v4))，试：(1)给出G的图形表示；(2)写出其邻接矩阵；(3)求出每个结点的度数；(4)画出其补图的图形．17．试求出如图一所示赋权图中的最小生成树(要求写出求解步骤)，并求此最小生成树的权．六、证明题(本题共8分)18．试证明：试卷代号：1009中央广播电视大学2012—2013学年度第二学期“开放本科”期末考试(半开卷)离散数学(本)试题答案及评分标准(供参考)2013年7月一、单项选择题(每小题3分，本题共15分)。1．D2．B3．A，4．C5．B二、填空题(每小题3分，本题共15分)。6．{3，4，5，6，7，8}︱7．{a，5，b，4)8．2︱E︱l(或“边数的两倍”)9．210．真(或T，或1)三、逻辑公式翻译(每小题6分，本题共12分)。11．设P：他们明天去旅游，Q：明天天晴．则命题公式为：P→Q．12．设P：小王是个学生，Q：小李是个职员，R：小张是个军人．则命题公式为：P∧Q∧R四、判断说明题(每小题7分，本题共14分)。13．错误。R不是等价关系，因R中不包含3，3，故不满足自反性．14．错误．因为紧接于量词之后最小的子公式称为量词的辖域，所以∃x量词的辖域为P(z，y)．五、计算题(每小题12分，本题共36分)。15．(1)(A∩B)={c};(2)(B—A)={{a))；(3)(A∩B)×B={c，{a}，c，c}．16．(1)G的图形表示如图二所示：(2)邻接矩阵：(3)v1，v2，v3，v4，v5结点的度数依次为2，2，3，1，2或deg(v1)=2，deg(v2)=2，deg(v3)=3，deg(v4)=1，deg(v5)=2(4)补图如图三所示：17．用Kruskal算法求产生的最小生成树．步骤为：ωvl，v7)=1选el=vlv7ωv3，v4)=3：选e2=v3v4ωv2，v7)=4选e3=-v2v7ω(v3，v7)=9选e4=v3v7ω(v4，v5)=8选e5=v4v5ω(v1，v6)=22选e6=vlv6最小生成树如图四所示：最小生成树的权为：ω(T)=22+1+4+9+3+18=57．如果采用破圈法，可参照评分．六、证明题(本题共8分)18．证明：(1)﹁1(A∧﹁B)P(2)﹁1A∨BT(1)E(3)((﹁B∨C)P(4)﹁CP﹁﹂(5)﹁1BT(3)(4)I(6)﹁AT(2)(5)I说明：1．因证明过程中，公式引用的次序可以不同，一般引用前提正确得1分，利用两个公式得出有效结论得l或2分，最后得出结论得2或1分．2．可以用真值表验证．