南京农业大学《离散数学》2017-2018学年第二学期期末试卷B卷.pdf

南京农业大学20172018 学年第二学期考试试题 B 卷第 1 页共 2 页考试科目考试科目：离散数学考试时间考试时间：120 分钟试卷总分试卷总分 100 分题号一二三四五六七八九总分分值201010101010101010100得分评卷教师一、设集合一、设集合完成下列各小题完成下列各小题。（第第 1 1 小题小题 2 2 分分，第第 2 2 小题小题 5 5 分分，第第 3 3 小题小题 3 3 分分，第第 4 4 小题小题 1010 分分，共共2020 分）分）1、求S的幂集()P S。2、证明(),P S是偏序集。3、画出偏序集(),P S的哈斯图。4、在()P S上定义两个二元运算和：对任意,()A BP S，ABAB，ABAB。请填空（在横线上填是或不是并回答为什么）：代数系统(),P S格，因为。代数系统(),P S有界格，因为。代数系统(),P S有补格，因为。代数系统(),P S分配格，因为。代数系统(),P S 布尔代数，因为。二、计算（二、计算（1010 分）分）设123122323(,)()()()E x xxxxxxxx是布尔代数0,1,上的一个布尔表达式。试写出123(,)E x x x的析取范式和合取范式（用列函数表的方法）。三、回答问题三、回答问题(共共 1010 分分)。装订线班级：学号：姓名：,Sa b c第 2 页共 2页完全图nK是否是欧拉图？是否是哈密尔顿图？为什么？四、四、画图画图（1010 分）分）对于下图，利用克鲁斯克尔算法求一棵最小生成树。五、计算（五、计算（1010 分）分）一棵树有两个结点度数为 2，1 个结点度数为 3，3 个结点度数为 4，其余结点度数为 1。问该树有几个度数为 1 的结点。六、证明（六、证明（1010 分）分）(,)GV E图是无向简单图，其中|Vn Em，证明：2)1(nnm。证明因为G是简单图，所以图G中没有环和平行边，任意两结点间最多有一条边，故2(1)2nn nmC。七、证明（七、证明（1010 分）分）已知(,),:(1)(2)(3)(4)(5)(6)(7)NTNTGVVPVB C Va b cPa BCaBCCBBCaBabbBbbbCbccCcc求证*nnna b c八、设计（八、设计（1010 分）分）设计一台有限状态机M，它的输出是已经输入符号数的模 3 数（即设计模 3 计数器）。九、计算九、计算(10(10 分分)给定码 C=00000,10001,01100,10101，求码 C 中任两个码字的海明距和min()dC。