离散数学题库

常熟理工学院20～20学年第学期《离散数学》考试试卷（试卷库01卷）试题总分：100分考试时限：120分钟题号一二三四五总分阅卷人得分一、单项选择题（每题2分，共20分）1.下列表达式正确的有()（A）（B）（C）（D）2.设P：2×2=5，Q：雪是黑的，R：2×4=8，S：太阳从东方升起，下列()命题的真值为真。（A）（B）（C）（D）3.集合A={1,2,…,10}上的关系R={x,y|x+y=10,x,yA}，则R的性质为()（A）自反的（B）对称的（C）传递的，对称的（D）传递的4.设，，其中表示模3加法，*表示模2乘法，在集合上定义如下运算：有称为的积代数，则的积代数幺元是()（A）0，0（B）0，1（C）1，0（D）1，15.下图中既不是Eular图，也不是Hamilton图的图是()6.设为无向图，，则G一定是()（A）完全图（B）树（C）简单图（D）多重图7.设P：我将去镇上,Q：我有时间。命题“我将去镇上,仅当我有时间”符号化为（）。（A）PQ（B）QP（C）PQ（D）8.在有n个结点的连通图中,其边数（）（A）最多有n-1条（B）最多有n条（C）至少有n-1条（D）至少有n条9.设A－B＝,则有（）（A）B＝（B）B（C）AB（D）AB10.设集合A上有3个元素,则A上的不同的等价关系的个数为（）（A）5（B）7（C）3（D）6二、填空题（每题2分，共20分）1．n个命题变元组成的命题公式共有种不同的等价公式。2．设〈L，≤〉为有界格，a为L中任意元素，如果存在元素b∈L,使，则称b是a的补元。3．设*，Δ是定义在集合A上的两个可交换二元运算，如果对于任意的x,y∈A,都有,则称运算*和运算Δ满足吸收律。4．设T是一棵树，则T是一个连通且的图。5．一个公式的等价式称作该公式的主合取范式是指它仅由组成。6．量词否定等价式Ø(x)P(x)Û，Ø($x)P(x)Û。7．二叉树有5个度为2的结点，则它的叶子结点数为。8．设G，*是一个群，G，*是阿贝尔群的充要条件是。9．集合S={α，β，γ，δ}上的二元运算*为*αβγδαδαβγβαβγδγβγγγδαδγδ那么，代数系统S，*中的幺元是，α的逆元是。10．设A={1，2，2，4，3，3}，B={1，3，2，4，4，2}=。=。三、判断题（每题1分，共10分）1.命题公式是一个矛盾式。（）2.，若，则必有。（）3.设S为集合X上的二元关系，则S是传递的当且仅当(SS)S。（）4.任何一棵二叉树的结点可对应一个前缀码。（）5.代数系统中一个元素的左逆元一定等于该元素的右逆元。（）6.一个有限平面图，面的次数之和等于该图的边数。（）7.A´B=B´A（）8.设*定义在集合A上的一个二元运算，如果A中有关于运算*的左零元θl和右零θr,则A中有零元。（）9.一个循环群的生成元不是唯一的。（）10.任何一个前缀码都对应一棵二叉树。（）四、解答题（5小题，共30分）1.（5分）什么是欧拉路？如何用欧拉路判定一个图G是否可一笔画出？2.（8分）求公式(P∨Q)R的主析取范式和主合取范式。3.（5分）已知一棵无向树中有2个2度顶点、1个3度顶点、3个4度顶点，其余顶点度数都为1。问它有多少个1度顶点？4.（7分）权数1，4，9，16，25，36，49，64，81，100构造一棵最优二叉树。5.（5分）集合上的关系，，写出关系矩阵，画出关系图并讨论R的性质。五、证明（3小题，共20分）1.（10分）用推理P,T规则证明：PQ，P→R,Q→SRS。2.（5分）设Ａ，Ｂ，Ｃ是三个集合，证明：(A－B)(A－C)=A－(BC)。3.（5分）设G,*是群，aG。令H={xG|a*x=x*a}。试证：H是G的子群。常熟理工学院20～20学年第学期《离散数学》考试试卷（试卷库02卷）试题总分：100分考试时限：120分钟题号一二三四五总分阅卷人得分一、选择题（每题2分，共20分）1.下列公式中哪些是永真式？()（A）(┐PQ)→(Q→R)（B）(PQ)→P（C）P→(Q→Q)（D）P→(PQ)2.下列推导错在()①P②US①③ES②④UG③（A）②（B）④（C）③（D）无3.集合A={1，2，3，4}上的偏序关系图为图(0)，则它的Hass图为()4.设R是实数集合，“”为普通乘法，则代数系统R，×不是()（A）群（B）独异点（C）半群（D）广群5.连通非平凡的无向图G有一条欧拉回路当且仅当图G()（A）只有一个奇度结点（B）只有两个奇度结点（C）只有三个奇度结点（D）没有奇度结点6.若一棵完全二元（叉）树有2n-1个顶点，则它()片树叶（A）n（B）2n（C）n-1（D）27.在谓词演算中,是的有效结论,根据是（）。（A）US规则（B）UG规则（C）ES规则（D）EG规则8.设在上海工作；是上海人。则命题“在上海工作的人未必都是上海人”的符号化为（）。A．（B）（C）（D）9.集合A上的关系R是相容关系的必要条件是（）（A）自反,反对称的（B）反自反,对称的（C）传递,自反的（D）自反,对称的10.下列各式错误的是（）（A）（B）（C）（D）二、填空题（每题2分，共20分）1.设P、Q是命题公式，填写如下的基本等价关系式：（1）┐(P∨Q)；（2）PQ；2.若集合A上的关系R满足的三个性质，则R是偏序关系。3.设A，B是两命题公式，当且仅当。4.给定无孤立点图G，若存在一条路满足，该条路称为欧拉路。5.一个称为布尔格。6.对于实数集合R，在下表所列的二元远算是否具有左边一列中的性质，请在相应位上填写“Y”或“N”MaxMin+可结合性可交换性存在幺元存在零元7.设A,£为偏序集，BÍA，记B­={y|yÎA且y是B的上界}，若B­有最小元，则称该最小元为B的。8.一个公式的等价式称作该公式的主析取范式是指它仅由组成。9.由集合A和B的所有共同元素组成的集合称为A和B的交集，记作AÇB，即AÇB={}。10.的图称为完全图。三、判断题（每题1分，共10分）1.“北京与天津的距离很近”是复合命题。（）2.如果A∨CB∨C，则有AB。（）3.设R1和R2是集合A上的关系，且R1R2，则有r(R1)r(R2)。（）4.若平面图共有v个结点，e条边和r个面，则v-e+r=2。（）5.任何循环群必定是阿贝尔群，反之亦真。（）6.命题公式是没有真假值的。（）7.格〈L,≤〉所诱导的代数系统为〈L,∧，∨〉，则运算∧，∨满足交换律。（）8.设函数f:A→B,则f的逆关系是函数当且仅当f是入射。（）9.群G,*的运算表中的每一行或每一列不一定是G的元素的一个置换。（）10.任何一棵二叉树可对应一个前缀码。（）四、解答题（3小题，共20分）1.（5分）简述二叉树的定义。如何将任何一棵有序树（m叉树）改写为对应的二叉树？2.（8分）求公式(P→Q)R的主析取范式和主合取范式。3.（7分）如下图所示的赋权图表示某七个城市及预先算出它们之间的一些直接通信线路造价，试给出一个设计方案，使得各城市之间能够通信而且总造价最小。五、证明（4小题，共30分）1.（10分）用推理P,T规则证明：P→Q，QR，R，SPS。2.（10分）若R和S都是非空集A上的等价关系，则RS是A上的等价关系。3.（6分）若图G不连通，则G的补图是连通的。4.（4分）I(整数集)上的二元运算*定义为：a,bI，a*b=a+b-2。证明I,*是群。常熟理工学院20～20学年第学期《离散数学》考试试卷（试卷库03卷）试题总分：100分考试时限：120分钟题号一二三四五总分阅卷人得分一、单项选择题（每题2分，共20分）1.在下述公式中不是重言式为()（A）（B）（C）（D）2.设，则B－A是()（A）（B）（C）（D）3.设A={1，2，…，10}，则下面定义的运算*关于A封闭的有()（A）x*y=max(x，y)（B）x*y=质数p的个数使得（C）x*y=gcd(x，y)(gcd(x，y)表示x和y的最大公约数)（D）x*y=lcm(x，y)（lcm(x，y)表示x和y的最小公倍数）4.设A，是偏序集，“”定义为：，则当集合A=()时，A，是格（A）{1,2,3,4,6,12}（B）{1,2,3,4,6,8,12,14}（C）{1,2,3,…,12}（D）{1,2,3,4}5.在有n个顶点的连通图中，其边数()（A）最多有n-1条（B）至少有n条（C）最多有n条（D）至少有n-1条6.一棵树有2个2度顶点，1个3度顶点，3个4度顶点，则其1度顶点为()（A）5（B）7（C）8（D）97.公式G=P￢P,则G是（）（A）永真的（B）永假的（C）可满足的（D）析取的8.设P,Q的真值为0,R,S的真值为T,则下面命题公式中真值为T的是（）.（A）RP（B）QS（C）PS（D）QR9.A={1,2,3}上的关系R={1,11,21,33,3},则R具备（）（A）传递性与反对称性（B）传递性与对称性（C）自反性与对称性（D）反自反性与对称性10.连通图G是一颗树,当且仅当满足下述条件中那一个（）（A）有些边不是割边。（B）每条边都是割边（C）每条边都不是割边（D）无割边集二、填空题（每题2分，共20分）1.设P、Q是命题公式，填写如下的基本等价关系式：（1）P→Q；（2）PQ；2.若对命题P赋值T，Q赋值F，则命题PQ的真值为。3.代数系统A，*中，|A|1，如果分别为A，*的幺元和零元，则的关系为（填相等或不相等）。4.设集合A={1，2，3，4，5，6，7，8，9，10}，定义A上的二元关系“≤”为x≤y=x|y，则xy=。5.公式的根树表示为。6.重言式又叫式，其定义为。7．给定无孤立点图G，若存在一条回路满足，该回路称为欧拉回路。8．设R为X到Y的关系，S为从Y到Z上的关系，R°S称为R和S的复合关系，则R°S=。9．设G,*为群，若在G中存在一个元素a,使得，则称该群为循环群。10．设G是一个连通平面图，一个面的称作该面的次数。三、判断题（每题1分，共10分）1.设命题“所有的研究生都读过大学”符号化为：。（）2.设P，Q是两个命题，当且仅当P，Q的真值均为T时，PQ的值为T。（）3.设A={a，b，c}，RA×A且R={a，b，a，c}，则R是传递的。（）4.在有向图中顶点间的相互可达关系是等价关系。（）5.代数系统中一个元素若有左逆元，则该元素一定也有右逆元。（）6.合式公式的定义是用一个递归形式给出的。（）7.格〈L,≤〉所诱导的代数系统为〈L,∧，∨〉，则运算∧，∨满足分配律。（）8.设函数f:A→B,则f的逆关系是函数当且仅当f是满射。（）9.群G,*的运算表中的每一行或每一列都是G的元素的一个置换。（）10.K3，3不是平面图。（）四、解答题（4小题，共30分）1.（5分）请解释谓词演算推理理论的US规则，UG规则，ES规则和EG规则。2.（8分）求公式(P→Q)(RP)的主析取范式和主合取范式。3.（10分）集合上的偏序关系R为整除关系。设，，试画出R的哈斯图，并求A，B，C的最大元素、极大元素、下界、上确界。4.（7分）假设英文字母，a，e，h，n，p，r，w，y出现的频率分别为12%，8%，15%，7%，6%，10%，5%，10%，求传输它们的最佳前缀码，并给出happynewyear的编码信息。五、证明（3小题，共20分）1.（8分）用推理P,T规则证明：BD，(E→F)→D，EB。2.（6分）证明在6个结点12条边的简单连通平面图中，每个面的次数都是3。3.（6分）I,+是一个群,设IE＝{x|x=2n,n∈I},证明IE,+是I,+的子群。常熟理工学院20～20学年第学期《离散数学》考试试卷（试卷库04卷）试题总分：100分考试时限：120分钟题号一二三四五总分阅卷人得分一、选择题（每题2分，共20分）1.命题“尽管有人聪明，但未必一切人都聪明”的符号化（P(x)：x是