中央电大《离散数学》13年7月试题.pdf

r 门 I 口厂一下门 少尘1 IL 马 匕土 J 中央广播电视大学2012 20 13学年度第二学期 开放本科 期末考试 半开卷 离散数学 本 试题 2013年7月 试卷代号 1009 题号 四 五 六 总分 分数 得分 评卷人 一 单项选择题 每小题3分 本题共15分 飞 若集合A一 a b 则下列表述正确的是 八 0任A B 王a eA C a b 任A D a 里A 2 设A 1 2 3 4 5 6 B l 2 3 A到B的关系R x y xEA yE B x y2 则R一 A B C D 3 n阶无向完全图K 的边数及每个结点的度数分别是 A n n一1 2 n一1 B n一1 n C n n一1 n一1 D n n一1 n 4 设无向完全图K 有n个结点 2 in条边 当 时 K 中存在欧拉回路 八 n 为奇数B n为偶数 C i 为奇数1 ii 为偶数 0 设个体域为整数集 则公式vz a y 二十y O 的解释可为 A 存在一整数I有整数y满足x y二0 B 对任一整数I存在整数y满足x y一0 C 存在一整数I对任意整数y满足 x y 0 D 任一整数I对任意整数y满足I y 0 得分 评卷人 二 填空题 每小题3分 本题共15分 6 设集合A 1 2 3 4 B一 3 4 5 6 C 5 6 7 8 则AflBUC等 7 设A a b B 1 2 C二 4 5 从A到B的函数f 从B到 C的函数g一 则g f等于 8 设G是一个图 结点集合为V 边集合为E 则G的结点度数之和 9 设G是具有 个结点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 则R是等价关系 14 谓词公式 日二 P 二 力一 V z Q x y z 中日x量词的辖域为P x y V z Q x y z 62 得分 评卷人l 五 计算题 每小题12分 本题共36分 15 设集合A a b c B a 试计算 1 A门B 2 B一A 3 A门B XB 16 设G zZVT E v Vj V2 V3 V4 Vs E v1 v3 v1 v5 v2 v3 v2 v5 V3 V4 试 1 给出G的图形表示 2 写出其邻接矩阵 3 求出每个结点的度数 4 画出其补图的图形 17 试求出如图一所示赋权图中的最小生成树 要求写出求解步骤 并求此最小生成树 的权 6 了一里 30 乃 S 图一 得分 评卷人 六 证明题 本题共8分 18 试证明 A八 13 八 BVC A iC二 iA 试卷代号 1009 中央广播电视大学20 12 2013学年度第二学期 开放本科 期末考试 半开卷 离散数学 本 试题答案及评分标准 供参考 2013年7月 一 单项选择题 每小题3分 本题共15分 I I 2 B 3 A 4 C 5 B 二 填空题 每小题3分 本题共15分 6 3 4 D 6 7 8 7 8 21E1 或 边数的两倍 9 2 10 真 或T 或1 三 逻辑公式翻译 每小题6分 本题共12分 11 设P 他们明天去旅游 Q 明天天晴 则命题公式为 尸 Q 12 设P 小工是个学生 Q 小李是个职员 R 小张是个军人 则命题公式为 尸八Q八R 四 判断说明题 每小题7分 本题共14分 13 错误 R不是等价关系 因R中不包含 3 3 故不满足自反性 14 错误 因为紧接于量词之后最小的子公式称为量词的辖域 所以3I量词的辖域为尸 x y 五 计算题 每小题12分 本题共36分 15 1 A自13 i 64 2分 6分 2分 6分 3分 7分 3分 7分 4分 8分 12分 2 B一A a 3 A门B XB 16 1 G的图形表示如图二所示 3分 图一 2 邻接矩阵 0 11 阳 师 lee卜以 we陌 曰口 010 101 010 00 6分 川川 川洲月叫 则 3 v1 v v3 v4 v3结点的度数依次为2 2 3 1 2 或deg v1 2 deg v2 2 deg v3 3 deg v 1 deg v 2 4 补图如图三所示 9分 12分 图三 17 用Kruskal算法求产生的最小生成树 步骤为 w vl V7 1选e1 V1 V7 二 V3 v4 3选e2 V3 V4 二 v7 4选e3 V2 V7 二 v3 v7 9选e 一V3 V7 w v4 v5 18选e5 V4 V5 65 w v v6 22选e 6 V1 V6 6分 最小生成树如图四所示 尸 9分 V1 18 一V 1 图四 最小生成树的权为 w T 二22十1 4 9 3 18 57 如果采用破圈法 可参照评分 六 证明题 本题共8分 18 证明 I A八 B P 2 AVB T 1 E 3 BVC P 4 C尸 5 B T 3