资源描述：
《2012-2013(1)离散数学试卷及答案b卷》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、浙江工业大学期终考试命题稿2010/2011学年第1学期课程名称离散数学使用班级09级信管教师份数1学生份数70命题人韩毅审核人命题总页数页每份需白纸页数3大张命题注意事项：一、命题稿请用A4纸电脑打印，或用教务处印刷的命题纸，并用黑墨水书写，保持字迹清晰，页码完整。二、两份试题必须同等要求，卷面上不要注明A、B字样，由教务处抽定A、B卷。三、命题稿必须经学院审核，并在考试前两周交教务处。浙江工业大学2012/2013学年第1学期试卷课程＿＿＿＿＿＿＿＿姓名＿＿＿＿＿＿＿＿班级＿＿＿＿＿＿＿＿学号＿＿＿＿＿＿＿＿题序一二三四五六七八九十总分计分一、选择15分（每小题3分）1
2、．下列语句是命题的是（A）。A、离散数学是重要的一门必修课。B、1+101=110？C、我正在说谎。D、全体起立！2．图的邻接矩阵为(C)。A、B、C、D、3．下列排列能构成图的顶点度序列的是（A）。A、1,2,2,3,4B、2,3,4,5,6,7C、2,1,1,1,2D、3,3,5,6,04．设，则IA=（D）。A、A；B、A×IA；C、IA×A；D、。5．下述命题公式中，是重言式的为（C）。A、；B、；C、；D、。二、填空题15分（每小题3分）1已知一棵无向树T有三个3度顶点,一个2度顶点,其余的都是1度顶点,则T中有5个1度顶点。2．设A={1，2，3，4}，A上二元
3、关系R={<2,2>,<2,3>,<3,2>,<3,1>}，则S(R)={<2,2>,<2,3>,<3,2>,<3,1>,<1,3>}。3．A={1，2，3，4，5，6}，A上二元关系，则用列举法给出T={<2,1>,<3,1>,<1,1>,<2,2>,<3,3>,<4,4>,<5,5>,<6,6>,<4,2>,<6,3>,<5,1>,<6,2>}。4．任何(n,m)图G=(V,E),边数与顶点数的关系是m=n-1/sum(d(vi))=2m5．设P（x）：x是素数，E(x)：x是偶数，O(x)：x是奇数N(x,y)：x可以整数y。则谓词的自然语言是对于任何素数都存在一个能
4、整除它的奇数三、计算或推理题（30’，每题6分）1、求前束范式。2、证明：PÚQ，Q®R，P®S，ØSÞR证明：(1)ØSP前提(2)P®SP前提(3)ØPT(1)(2)I拒取式(4)PÚQP前提(5)QT(3)(4)I析取三段论(6)Q®RP前提(7)RT(5)(6)I假言推理3．设A={a,b,c,d}，R为A上的关系，R={,,,,}，求r(R)，s(R)，t(R)。r(R)={,,,,,,,,}s(R)={,
5、,,,,,,}t(R)={,,,,,,,,,,,}4．已知偏序集的哈斯图如图所示，试求出集合A和关系R的表达式。A={a,b,c,d,e,f,g,h}R={,,,,,,,,}∪IA5．列举集合A＝{a,b,c,d}上所有不同的等价关系。只要求出A上的全部划分，即为等价关系。划分为一个块的情况：1种，
6、即{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’)：有些女孩
7、喜欢各种香水，但女孩都不喜欢有毒物体，所以香水都不是有毒物体。答：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:00c:11e:101b:01d:100六、（10’）●画出该图形的对偶图形，为对偶图按韦尔奇.鲍威尔方法按步骤进行着色（颜色用数字表示）。要求着色的过程和每一步骤都要具体写出。排序：abcdef
