《离散数学》考试试卷(试卷库14卷)及答案

《离散数学》考试试卷（试卷库14卷）试题总分：100分考试时限：120分钟阅卷人题号得分一二三四五总分一、选择题（每题2分，共20分）1.下述命题公式中，是重言式的为()（A）（C）（B）（D）2.对任意集合A,B,C,下列结论正确的是（）（A）若AB,BC,则AC；（B）若AB,BC,则AC；（C）若AB,BC,则AC；（D）若AB,BC,则AC；3.设，定义上的等价关系,,则由R产生的（A）4上一个划分共有()个分块。（B）5（C）6（D）94.下列偏序集()能构成格5.连通图G是一棵树当且仅当G中()（A）有些边是割边（B）每条边都是割边（C）所有边都不是割边（D）图中存在一条欧拉路径6.有n个结点（A），条边的连通简单图是平面图的必要条件()（B）（C）（D）7.设P,Q的真值为0,R,S的真值为1,则下面命题公式中真值为1的是（）（A）R（B）QS（C）PS（D）QR8.在图G=<V,E>中,结点总度数与边数的关系是（P）（A）（B）（C）（D）9.设有33盏灯,拟公用一个电源,则至少需有五插头的接线板数（）（A）７（B）８（C）９（D）１４10.设集合A上有四个元素,则A上的不同的等价关系的个数为（）（A）11（B）14（C）17（D）15二、填空题（每题2分，共20分）1.设A={a，b，c，d}，其上偏序关系R的哈斯图为则R=。2.设，定义A上的二元运算*为普通乘法、除法和加法，则代数系统<A，*>中运算*关于运算具有封闭性。3.A，B，C表示三个集合，文氏图中阴影部分的集合表达式为。4.矛盾式又叫式，其定义为。5.的图称为无向图。6.设<A,≤>是一个偏序集合，在A的一个子集中，如果，则称这个子集为链。7.在真值表中，一个公式的真值为Ｆ的指派所对应的大项的合取，即为此公式的范式。8.设R是非空集合A上的等价关系，对任意的aA，定义为a关于R的等价类。9.设<G,*>是一个群，A，B∈P(G)且A≠，B≠，则A和B的积AB=。10.的无向图称为树。三、判断题（每题1分，共10分）1.公式的前束范式为。（）2.(AB)C=(AC)(BC)。（）3.不存在既对称又反对称的关系。（）4.若无向连通图G中存在桥，则G的点连通度和边连通度都是1。（）{Ø，{{Ø}}}。（）6.任意图结点度数的总和等于边数的两倍。（）7.设一定为有补分配格。（）5.{{Ø}}是布尔代数，则8.群中有零元。（）9.质数阶群没有非平凡子群。（）10.(x)A(x)∨(x)B(x)(x)(A(x)∨B(x))（）四、解答题（3小题，共20分）1.（5分）考虑在七天内安排七们功课的考试，使得同一位教师所任的两们课程考试不安排在接连的两天里，试说明如果没有教师担任多于四门课程，则符合上述要求的考试安排总是可能的。2.3.（8分）求公式(QP)∧P∧R的主析取范式和主合取范式。4.（7分）已知无向图G有11条边,2度与3度顶点各2个,其余都是4度顶点,求G中共有几个顶点，写出过程。五、证明（5小题，共30分）1.（10分）用推理P,T规则证明：P→(Q→R)，R→(Q→S)P→(Q→S)。a*kb=a*b(modk),这里a,b∈Nk。当k＝2.对于正整数k,Nk＝{0,1,2,…,k-1},设*k是Nk上的一个二元运算,使得4时构造出的*k运算表。（4分）3.（6分）设R为集合A上的二元关系，如果R是反自反的和可传递的，则R一定是反对称的。A(BC)＝(A－B)－C。4.（4分）设Ａ，Ｂ，Ｃ是三个集合，证明：－5.（6分）设G是连通简单平面图，结点数为n（试题参考答案及评分标准），边数为m，面数为r，则。一、选择题（每题2分，共20分）ADBCBADCBD二、填空题（每题2分，共20分）1.{<a,b>,<a,c>,<a,d>,<b,d>,<c,d>}2.乘法3.4.永假公式给定一个命题公式，若无论对分量作怎样的指派，其对应的真值永为F，则称该命题公式为矛盾式。5.所有边都是无向边6.每两个元素都是有关系的7.主合取8.[a]R={xA|aRx}9.{a*b|a∈A,b∈B}10.连通且无回路三、判断题（每题1分，共10分）×√×√×√√×√×四、解答题（3小题，共20分）1．（5分）设G为七个结点的图，每一个结点对应一门功课的考试，如果这两个结点对应的课程的考试是由不同教师担任的，那么这两个结点之间有一条边，因为每个教师所任的课程不超过4，故每个结点的度数至少是3，任两个结点度数的和至少是6，故G总包含一条汉密尔顿路，它对应于一个七门考试课目的一个适当安排。2．（8分）各4分，步骤对，结果错，适当扣分，如果求出其一个，另一个直接写出，也不扣分