试卷代号= 1009 座位号匚口
中央广播电视大学2012-2013学年度第二学期“开放本科”期末考试（半开卷）
离散数学（本）试题
2013年7月
题号 一 二 三 四 五 六 总分
分数
一、单项选择题（每小题3分，本题共15分）
1.若集合A={a,5）,则下列表述正确的是（ ）.
A.0EA B. {a}€A
C. D.
2. 设 A={l,2,3,4,5,6}tB=（l,2,3）,A 到 B 的关系 {<xty） |xG B,x=y},
则 R =（ ）.
A. {<1,1>,<2,4>} B. {<1,1>,V4,2>}
C. {<1,1>,<6,3>} D. （<1,1>,<2,1>}
3.n阶无向完全图K“的边数及每个结点的度数分别是（ ）.
A. —1）/2,n—1 B. n~i ,n
C. n（n — 1） ,n — 1 D. «（« — !）,«
4. 设无向完全图K„有&个结点（n22）,m条边，当（ ）时,K.中存在欧拉回路.
A.zn为奇数 B. 〃为偶数
C.n为奇数 D.m为偶数
5.设个体域为整数集，则公式Vi 3丿（工+、= 0）的解释可为（ ）.
A.存在一整数工有整数了满足x+y = 0
B.对任一整数了存在整数v满足工+、= 0
C.存在一整数工对任意整数》满足z+v = o
D.任一整数工对任意整数y满足x+y = 0
6.设集合 A={1,2,3,4},B={3,4,5,6},C={5,6,7,8},则 A Cl B U C 等 于 .
7.设 A={a,b},B={l,2},C={4,5},从 A 到B 的函数/=（<a,l>,<6,2>},从 B 到 C 的函数g = {Vl,5>,<2,4>},则 g。/等于 .
8.设G是一个图，结点集合为V,边集合为E,则G的结点度数之和 为 .
9.设G是具有”个结点m条边£个面的连通平面图，则n+k-m等于 .
10.设个体域D= {1,2,3, 4}, A 3）为“h等于3”，则谓词公式（3x）A（x）的真值 为 .
得分评卷人
三、逻辑公式翻译（每小题6分，本题共12分}
H.将语句“他们明天去旅游，仅当明天天晴.”翻译成命题公式.
12.将语句“小王是个学生，小李是个职员，而小张是个军人.”翻译成命题公式.
得分评卷人
四、判断说明题（每小题7分，本题共14分）
判断下列各题正误,并说明理由.
13.设 A={1,2,3} ,K = {<1,1>,<2,2>,<1,2>,<2,1>),则 R 是等价关系.
14. 谓词公式(3 x)P(x,y)-*( V z)Q(x, y ,z)中 3 x 量词的辖域为 z)Q(.x,
15.设集合 A= {a,{b} ,c) ,c},试计算：
(2)(B-A), (3)(A0B)XB).
16.设 G=<V,E>, V= {V], , v5}，E= {(ui ,v3), ,v5) ,(v2 ,v3) ,(v2,v5), (v3,
vt)},试：
(1)给岀G的图形表示； (2)写出其邻接矩阵；
(3)求出每个结点的度数； (4)画出其补图的图形.
17.试求岀如图一所示赋权图中的最小生成树(要求写出求解步骤)，并求此最小生成树
的权.
18.试证明：r (AA rB)A(rBVC)ArC = rA.
试卷代号：1009
中央广播电视大学2012-2013学年度第二学期“开放本科”期末考试（半开卷）
离散数学（本）试题答案及评分标准
（供参考）
2013年7月
一、 单项选择题（毎小题3分，本题共15分）
1.D 2. B 3. A 4.C 5.B
二、 填空题（每小题3分，本题共15分）
6.{3,4,5,6,7,8}
7.{<a,5>,<6,4>）
8.2|E|（或“边数的两倍”）
9.2
以真（或T,或1）
三、 逻辑公式翻译（每小题6分，本题共12分）
11. 设P：他们明天去旅游,Q：明天天晴. （2分）
则命题公式为:P —M2. （6分）
12.设小王是个学生,Q：小李是个职员，R：小张是个军人. （2分）
则命题公式为：PAQAR. （6分）
四、 判断说明题（毎小题7分，本题共14分）
13.错误. （3分）
R不是等价关系，因R中不包含V3,3>,故不满足自反性. （7分）
14.错误. （3分）
因为紧接于量词之后最小的子公式称为量词的辖域，
所以3工量词的辖域为P（£,y）. （7分）
五、 计算題（每小题12分，本题共36分}
15.（l）（AnB） = （c）; （4 分）
（2）（B-A） = “a}}； (8分)
<3}（AnB）XB={<c,{a}>,<c,c>}, （12 分）
16. (DG的图形表示如图二所示：
V1
（3分）
卩3〜 〜卩4
图二
(2)邻接矩阵:
0 0 1 0 r
0 0 10 1
110 10 （6分）
0 0 10 0
110 00_
(3)边，边,％，以，*结点的度数依次为2,2,3,1,2 （9分）
或 deg（w】）=2,deg（x；2）= 2,deg（a）=3,deg（s）= l,deg（w5）= 2
(4)补图如图三所示：
Vl(12 分)
卩3 v4
图三
17.用Kruskal算法求产生的最小生成树.步骤为：
W（Vi , v7） = 1选幻=边v7
,5）= 3选 e2=v3v4
W（I^2） = 4选幻=血为
w（ s , s ） = 9选S 5
疆，寸5 ) =18选好=辺与5
最小生成树的权为：s（T） = 22 + l + 4 + 9 + 3 + 18 = 57. （12分）
如果采用破圈法，可参照评分.
六、证明题（本题共8分）
18.证明:
(l)-(AA 槌) P (1分)
(2) -AVB T(1)E （3分）
(3X-BVO P (4分)
(4)-C P (5分)
(5)-B T(3)(4)I （6分）
(6)「A T(2)(5)J （8分）
说明：
1.因证明过程中，公式引用的次序可以不同，一般引用前提正确得1分，利用两个公式得 出有效结论得1或2分，最后得出结论得2或1分.
2.可以用真值表验证.
点点赞赏，手留余香
给TA打赏
评论0