2012-2013离散数学试卷及答案B卷.doc

浙江工业大学期终考试命题稿 2010 /2011 学年第 1 学期 课程名称 离散数学 使用班级 09级信管 教师份数 1 学生份数 70 命题人 韩毅 审核人 命题总页数 页 每份需白纸页数 3 大张  命题注意事项： 一、命题稿请用A4纸电脑打印，或用教务处印刷的命题纸，并用黑墨水书写，保持字迹清晰，页码完整。 二、两份试题必须同等要求，卷面上不要注明A、B字样，由教务处抽定A、B卷。 三、命题稿必须经学院审核，并在考试前两周交教务处。 浙江工业大学2012/2013 学年 第1学期试卷 课程＿＿＿＿＿＿＿＿ 姓名 ＿＿＿＿＿＿＿＿ 班级＿＿＿＿＿＿＿＿ 学号 ＿＿＿＿＿＿＿＿ 题序 一 二 三 四 五 六 七 八 九 十 总分 计分 一、选择 15分 （每小题 3分） 1．下列语句是命题的是（ ）。 A、离散数学是必修课B、 C、D、 2． A、 B、 C、 D、 3．（）。 A、 B、 C、 D、4．设，则 =（）。 A、 ； B、A×； C、×A； D、。 5． A、； B、； C、； D、。 二、填空题15分 （每小题 3分） 12．设A={1，2，3，4}，A上二元关系R=}。3． 三、计算或推理题（30’，每题分） 1、 2、(Q，Q(R，P(S，(S ( R 证明： (1) (S P前提 (2) P(S P前提 (3) (P T(1)(2)I拒取式 (4) P(Q P前提 (5) Q T(3)(4)I析取三段论 (6) Q(R P前提 (7) R T(5)(6)I假言推理 3． 4． A={a,b,c,d,e,f,g,h} R={ b,d,b,e,b,f,c,d, c,e,c,f,d,f,e,f, g,h}∪IA 5． 只要求出A上的全部划分，即为等价关系。 划分为一个块的情况：1种，即{a,b,c,d} 划分为两个块的情况：7种，即 {{a,b},{c,d}}，{{a,c},{b,d}}，{{a,d},{b,c}} {{a},{b,c,d}}，{{b},{a,c,d}}，{{c},{a,b,d}}， {{d},{a,b,c}} 划分为三个块的情况：6种，即 {{a,b},{c},{d}}，{{a,c},{b},{d}}，{{a,d},{b},{c}}, {{a},{b},{c,d}}，{{a},{c},{b,d}}，{{a},{d},{b,c}} 划分为四个块的情况：1种，即{a},{b},{c},{d}} 因此，共有15种不同的等价关系。 四 逻辑推理(10’)： 结论： 五 树的应用（10’） 假设a, b, c, d, e的分别为128、15、7、6，求传输它们的最佳前缀码（构造最优二叉树） a: 00 c: 11 e: 101 b: 01 d: 100 六、（10’）画出该图形的对偶图形，为对偶图按韦尔奇.鲍威尔方法按步骤进行着色（颜色用数字表示）。要求着色的过程和每一步骤都要具体写出。 排序 ：a b c d e f 第一次：a e 第二次：b f 第三次：c 第四次：d 七、包含排斥原理（10’） 241门外语. 英语：13； 日语：5； 德语：10； 法语：9 英日：2; 英德：4； 英法：4； 法德：4 会日语的不会法语、德语 求：只会 1 种语言人数，会 3 种语言人数？ ● x+2(4-x)+y1+2=13 x+2(4-x)+y2=10 x+2(4-x)+y3=9 x+3(4-x)+y1+y2+y3=19 x=1, y1=4, y2=3, y3=2