[理学]离散数学题库.doc

常熟理工学院20 ～20 学年第 学期 《离散数学》考试试卷（试卷库01卷） 试题总分： 100 分 考试时限：120 分钟 题号 一 二 三 四 五 总分 阅卷人 得分 一、单项选择题（每题2分，共20分） 下列表达式正确的有( ) （A）（B）（C） （D） P：2×2=5，Q：雪是黑的，R：2×4=8，S：太阳从东方升起，下列( )命题的真值为真。 （A） （B） （C） （D） 集合A={1,2,…,10}上的关系R={x,y|x+y=10,x,yA}，则R 的性质为( ) （A）自反的　　（B）对称的　　 （C）传递的，对称的 （D）传递的 ，，其中表示模3加法，*表示模2乘法，上定义如下运算： 有称为的积代数的积代数幺元是( ) （A）0，0（B）0，1（C）1，0（D）1，1Eular图，也不是Hamilton图的图是( ) 设为无向图，，则G一定是( ) （A）Q （B）QP （C）P(Q （D） 在有n个结点的连通图中,其边数（ ） （A）最多有n-1条 （B）最多有n 条 （C）至少有n-1条 （D）至少有n条 设A－B＝,则有（ ） （A）B＝ （B）B （C）AB （D）AB 设集合A上有3个元素,则A上的不同的等价关系的个数为（ ） （A）5 （B）（C）（D）L，≤〉为有界格，a为L中任意元素，如果存在元素b∈L,使 ，则称b是a的补元。 设*，Δ是定义在集合A上的两个可交换二元运算，如果对于任意的x,y∈A,都有 ,则称运算*和运算Δ满足吸收律。 设T是一棵树，则T是一个连通且 的图。 一个公式的等价式称作该公式的主合取范式是指它仅由 组成。 量词否定等价式( ((x)P(x) ( ，( ((x)P(x) ( 。 二叉树有5个度为2的结点，则它的叶子结点数为 。 设G，*G，* 。 集合S={α，β，γ，δ}上的二元运算*为 * α β γ δ α δ α β γ β α β γ δ γ β γ γ γ δ α δ γ δ 那么，代数系统S， * ， 　 。 设A={1，2，2，4，3，3}，B={1，3，2，4，4，2} = 。 三、判断题（每题1分，共10分） 命题公式是一个矛盾式。（ ） ，则必有。（ ） 设S为集合X上的二元关系，则S是传递的当且仅当(S(S)S。（ ） 任何一棵二叉树的结点可对应一个前缀码。（ ） 代数系统中一个元素的左逆元一定等于该元素的右逆元。（ ） 一个有限平面图，面的次数之和等于该图的边数。（ ） A(B = B(A （ ） 设*定义在集合A上的一个二元运算，如果A中有关于运算*的左零元θl和右零θr,则A中有零元。（ ） 一个循环群的生成元不是唯一的。（ ） 任何一个前缀码都对应一棵二叉树。（ ） 四、解答题（5小题，共30分） （5分）什么是欧拉路？如何用欧拉路判定一个图G是否可一笔画出？ （8分）求公式 (P∨Q)R 的主析取范式和主合取范式。 （5分）已知一棵无向树中有2个2度顶点、1个3度顶点、3个4度顶点，其余顶点度数都为1。问它有多少个1度顶点？ （7分）权数1，4，9，16，25，36，49，64，81，100构造一棵最优二叉树。 （5分）集合上的关系，，写出关系矩阵，画出关系图并讨论R的性质。 五、证明（3小题，共20分） （10分）用推理P,T规则证明：PQ， P→R, Q→S RS。 （5分）设Ａ，Ｂ，Ｃ是三个集合，证明：(A－B)(A－C)=A－(BC)。 （5分）设G,*是群，aG。令H={xG|a*x=x*a}。试证：H 是G 的子群。 常熟理工学院20 ～20 学年第 学期 《离散数学》考试试卷（试卷库02卷） 试题总分： 100 分 考试时限：120 分钟 题号 一 二 三 四 五 总分 阅卷人 得分 一、选择题（每题2分，共20分） 下列公式中哪些是永真式？( ) （A）(┐PQ)→(Q→R) （B） (PQ)→P （C） P→(Q→Q) （D）P→(PQ) (