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

浙江工业大学期终考试命题稿2010 /2011 学年第 1 学期课程名称离散数学 使用班级09级信管教师份数1学生份数70命题人韩毅审核人命题总页数页每份需白纸页数 3 大张 命题注意事项：一、命题稿请用A4纸电脑打印，或用教务处印刷的命题纸，并用黑墨水书写，保持字迹清晰，页码完整。二、两份试题必须同等要求，卷面上不要注明A、B字样，由教务处抽定A、B卷。三、命题稿必须经学院审核，并在考试前两周交教务处。浙江工业大学2012/2013 学年第1学期试卷课程 姓名 班级 学号 题序一二三四五六 七八九十总分计分一、选择 15分 （每小题 3分）1下列语句是命题的是（ A ）。A、离散数学是重要的一门必修课。 B、1+101=110？ C、我正在说谎。D、全体起立！ 2图 的邻接矩阵为( C )。A、 B、 C、 D、 3下列排列能构成图的顶点度序列的是（ A ）。A、1,2,2,3,4 B、2,3,4,5,6,7 C、2,1,1,1,2 D、3,3,5,6,04设，则IA =（ D ）。 A、 A ； B、AIA； C、 IAA； D、。5下述命题公式中，是重言式的为（ C ）。A、； B、；C、； D、。二、填空题15分 （每小题 3分）1已知一棵无向树T有三个3度顶点,一个2度顶点,其余的都是1度顶点,则T中有 5 个1度顶点。2设A=1，2，3，4，A上二元关系R=, , ，则S(R)=,。3A=1，2，3，4，5，6，A上二元关系，则用列举法给出T=,。4任何(n,m)图 G=(V,E),边数与顶点数的关系是 m=n-1/sum(d(vi)=2m 5设 P（x）：x是素数， E(x)：x 是偶数，O(x)：x是奇数 N (x,y)：x可以整数y。则谓词的自然语言是 对于任何素数都存在一个能整除它的奇数 三、计算或推理题（30，每题6分）1、 求前束范式。2、证明：PQ，QR，PS，S R 证明：(1) S P前提(2) PS P前提(3) P T(1)(2)I拒取式(4) PQ P前提(5) Q T(3)(4)I析取三段论(6) QR P前提(7) R T(5)(6)I假言推理3设A=a,b,c,d，R为A上的关系，R=,，求r(R)，s(R)，t(R)。r(R)=,s(R)=,t(R)=,4已知偏序集的哈斯图如图所示，试求出集合A和关系R的表达式。 A=a,b,c,d,e,f,g,hR=,IA 5列举集合Aa,b,c,d上所有不同的等价关系。只要求出A上的全部划分，即为等价关系。划分为一个块的情况：1种，即a,b,c,d划分为两个块的情况：7种，即a,b,c,d，a,c,b,d，a,d,b,ca,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)：有些女孩喜欢各种香水，但女孩都不喜欢有毒物体，所以香水都不是有毒物体。答： M(x): x是女孩， D(x): x是香水， Q(x): x是有毒的， L(x,y): x喜欢y前提： 结论： 五 树的应用（10） 根据下图求最小生成树，假设生成树中五个节点a, b, c, d, e的权重分别为12、8、15、7、6，求传输它们的最佳前缀码（构造最优二叉树）。a: 00 c: 11 e: 101b: 01 d: 100六、（10）画出该图形的对偶图形，为对偶图按韦尔奇.鲍威尔方法按步骤进行着色（颜色用数字表示）。要求着色的过程和每一步骤都要具体写出。排序 ：a b c d e f 第一次：a e第二次：b f第三次：c第四次：d七、包含排斥原理（10） 24名科技人员，每人至少会1门外语.英语：13； 日语：5； 德语：10； 法语：9英日：2; 英德：4； 英法：4； 法德：4会日语的不会法语、德语求：只会 1 种语言人数，会 3 种语