离散数学复习题(期末测试卷).docx

离散数学复习题(期末测试卷)

第一篇：离散数学复习题(期末测试卷)复习题一、填空题（请将每空的正确答案写在答题纸相应位置处，答在试卷上不得分。每小题2分，共16分。）1．谓词公式xy(P(x,y)Q(y,z))xR(x,y)中x的辖域是。2．命题公式(pq)的成真赋值为。3．在1和1000之间（包括1和1000在内）不能被4和5整除的数有个。4．设R是定义在集合A{1,2,3,4}上的二元关系R{1,1,1,2,2,3,1,4}，则R的对称闭包s(R)。5．A{1,2,3,4},xymin{x,y},则代数系统A,中的零元是。6．具有10个结点的无向完全图的边数=。7．一次同余方程3x1(mod5)的最小正整数解是。8．84与198的最大公约数是。二、单项选择题（从下列各题四个备选答案中选出一个正确答案，并将其代号写在答题纸相应位置处。答案错选或未选者，该题不得分。每小题2分，共16分。）1.设F(x):x是有理数，G(x)：x能表示成分数。在一阶逻辑中，命题“没有不能表示成分数的有理数”可符号化为()。A.x(F(x)G(x))B.x(F(x)G(x))C.x(F(x)G(x))D.x(F(x)G(x))2.设个体域是整数集，则下列命题的真值为真的是()。A．yx(xy1)B．xy(xy0)C．xy(xyy2)D．yx(xyx2)3.集合A{1,2,,10}上的关系R{x,y|xy10,x,yA}，则R的性质为()。A、自反的B、传递的、对称的C、对称的D、反自反的、传递的4．对自然数集合N，下列定义的运算中()是不可结合的。A.abab3B.aba2bC.abab(mod3)D.abmin{a,b}5．下列各图中既是欧拉图，又是汉密尔顿图的是()。A．B．C．D．6．对于下列度数序列，可画成简单无向图的是()。A．(1，1，1，2，3)B．(1，2，2，3，4，5)C．(1，2，3，4，5，5)D．(2，3，3，4，5，6)7.含有5个结点、3条边的不同构的简单图有()个。A.2B.3C.4D.5【】8．5的模6逆等于()。A．1B．3C．4D．5三、计算题（第1、2、3、4小题各7分，第5、6小题各8分共44分。）1．求命题公式(pq)(pr)的主析取范式和主合取范式。2．设A,R为偏序集，其中A{1,2,3,4,6,9,24,54}，R是A上的整除关系。（1）画出A,R的哈斯图；（2）求A中的极大元；（3）令B{4,6,9}，求B的上确界和下确界。3．求下图1中带权无向图的最小生成树，并求出该最小生成树的权值。4．求解递推方程：an7an112an20,a04,a16。5．有向图D如图2所示，求：（1）D中v1到v3长度为3的通路有几条？（2）D中v1到v1长度为3的回路有几条？（3）D是哪类连通图？v4图1图2v36．在通讯中要传输字母a,b,c,d,e,f,g，它们出现的频率为：a:30%,b:20%,c:15%,d:10%,e:10%,f:9%,g:6%，设计传输上述字母的最佳二元前缀码，画出最优树，并求传输100个按上述频率出现的字母所需二进制字个数。四、证明题（每小题8分，共16分。）1．设R为自然数集N上的关系，定义N上的关系R如下：x,yRxy是偶数。（1）证明R为等价关系；（2）求商集N/R。2．设Z为整数集合，在Z上定义二元运算如下：证明：x,yZ,xyxy2，Z,是群。五、符号化下列命题，并在自然推理系统P中论证结论的有效性（8分。）若小张喜欢数学，则小李或小赵也喜欢数学。若小李喜欢数学，则他也喜欢物理。小张确实喜欢数学，可小李不喜欢物理。所以，小赵喜欢数学。参考答案一、填空题（请将每空的正确答案写在答题纸相应位置处，答在试卷上不得分。每小题2分，共16分。）1．P(x,y)Q(y,z)2．10，11，003．6004．{1,1,1,2,2,3,1,4,2,1,3,2,4,1}5．16．457．38．6二、单项选择题（从下列各题四个备选答案中选出一个正确答案，并将其代号写在答题纸相应位置处。答案错选或未选者，该题不得分。每小题2分，共16分。）1．C2．C3．C4．B5．C6．A7．C8．D三、计算题（第1、2、3、4小题各7分，第5、6小题各8分共44分。）1．解：主合取范式为：（5分）(pq)(pr)(pq)(pr)((pq)(rr))((pr)(qq))(pqr)(pqr)(pq