2022年2022年离散数学期末考试及答案 .pdf

《2022年2022年离散数学期末考试及答案 .pdf》由会员分享，可在线阅读，更多相关《2022年2022年离散数学期末考试及答案 .pdf（8页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、沈阳师范大学离散考试预测题一、选择题（共 10 题，每题 3 分，共 30 分）1、下列语句为命题的是（）。A勿踏草地；。B你去图书馆吗？；C 月球上有水；D 本命题为假。2下列推理中，（）是错误的。A. 如果 x 是有理数，则它为整数。1/2 是有理数。所以1/2 是整数。B. 若周末气温超过 30 度，小红就去游泳。小红周末没去游泳。所以周末气温没超过30 度。C. 下午小明或者去看电影， 或者去打篮球。下午小明没去打篮球。 因此下午小明去看电影了。D. 若 a 能被 4 整除，则 a 能被 2 整除。 a 能被 2整除。因此 a 能被 4 整除。3谓词公式)()()(xQyyRxPx中的

2、 x( ) 。A只是约束变元B只是自由变元C 既非约束变元又非自由变元D 既是约束变元又是自由变元4. 下列关系中，（）不是等价关系。A. 非空集合的幂集的元素间包含关系；B. 集合之间的等势关系；C. 公式之间的等值关系；D. 图之间的同构关系。5. 下面等值式中，（）是不正确的。A.)()()()(xxBxxAxBxAxB.)()()()(xxBxxAxBxAxC.BxxABxAx)()(D.)()(xxBAxBAx6下列关于集合的势的叙述中，（）是错误的。A. 实数集比自然数集优势；B. 任一无限集合都存在与自己等势的真子集；C. 集合之间的优势关系是偏序关系；D. 有理数集比整数集优势

3、。7设 A,B,C 是集合， F 是关系，ADBAG,:，则下列式子中不正确的是（）。ABBABA B. DDGG)(1C. BFAFBAF D. )()(CBACBA名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 8 页 - - - - - - - - - 8. 以下序列中，（）是简单可图的。A. (4,4,3,3,2,2)； B. (3,3,3,1)； C. (5,4,3,2,2)； D. (6,6,3,2,2,2,1)。9. 下列叙述中错误的是 ( ) 。An(n2

4、)阶竞赛图都具有哈密顿通路；B非平凡树不是欧拉图，也不是哈密顿图；C n(n3 且为奇数 ) 阶的二部图一定不是哈密顿图；D 欧拉回路包含图的所有顶点，哈密顿回路包含图的所有边。10下列关于图的连通性的叙述中正确的是( ) 。A. 有向图是连通的是指它是强连通的；B. 任一无向图的点连通度都不超过它的边连通度；C. 在一 n 阶圈 Cn(n4) 上任意去掉两个顶点得到得图都有2 个连通分支；D. n 阶无向完全图的点连通度为n；二、填空题（共8 题，每题 3 分，共 24 分）1令 F(x) ：x 是汽车， G(y) ：y 是火车， H(x,y) ：x 比 y 快。则命题“不存在比所有火车都快

5、的汽车”符号化形式为_),()()(yxHyGyxFx_ 。2公式rqp)(的主析取范式为 _731mmm_。3集合 A=a,b,c,d上的等价关系共有 _15_个。4自对偶图的顶点数n 和边数 m之间满足关系式为 m =_ m=2n-2_ 。5设 T 是有 t 片树叶的 2 叉正则树，则 T 应该有 _个顶点。6P( , ) = _, , ,_ 。7在 1 到 100 之间（包含 1 和 100）即不能被 2，也不能被 3，还不能被 5 整除的自然数有_个。8“p 仅当 q”，“只有 q 才 p”，“除非 q 才 p”这三个命题的符号化分别为_ qpqpqp,_ , _ 和 _ 。（请按顺序

6、填写）三、应用、计算和证明题（共6 题，46分）1(6 分) 在命题逻辑的自然推理系统中构造下面推理的证明。前提： (P Q)， QR，R 结论： P 2（8 分）设集合 A=a，b，c，d ，A上的关系 R=, 求：（ 1）画出 R的关系图。 (2 分) （2）R的自反闭包、对称闭包和传递闭包的关系图。（2 分，2 分和 2 分）名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 8 页 - - - - - - - - - 3（8 分）设 为一偏序集，其中A=1，2，12，

7、R是 A上的整除关系。（1）画出的哈斯图；（ 4 分）（2）求 A的所有极大元和极小元（2 分）（3）求 B=2,3,6 的最小上界和最大下界（2 分）。4. （8 分）判断左图是否为欧拉图， 若是，请给出一欧拉回路（用阿拉伯数字在边上标明顺序即可）；若不是，请说明原因；（4 分）判断右图是否为哈密顿图，若是，请给出一哈密顿回路（用阿拉伯数字在顶点上标明顺序即可）；若不是，请说明原因（4 分）；5（8 分） 设 G是无向简单图且 (G)k2，试证明 G中存在长度大于等于k+1的初级回路（圈）。6（8 分）在一棵有 3 个 2 度顶点， 2 个 4 度顶点，其余顶点都是树叶的无向树中，应该有几片

8、树叶？（ 2 分）请画出所有这样的非同构的无向树。（6 分）名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 8 页 - - - - - - - - - 答案及评分标准一 选择题CDDAC DCADD二1. ),()()(yxHyGyxFx或者),()()(yxHyGyxFx2. 731mmm3. 15 4. m=2n-2 5. 2t-1 6. , ,7. 26 8. qpqpqp,(该小题每空1 分) 三1 （ 1）RQ前提引入（ 2）R前提引入（ 3）Q（1） （2）析

9、取三段论（ 4）)(QP前提引入（ 5）QP置换(6) P(3)(5)析取三段论若未注明推理规则,或标注有错 ,扣 1 分. 2 （ 1） 如图 1 （ 2）AAIcbdcabbaaaIRRRRr,)(0,)(1bccdcbdcabbaaaRRRs,)(2cbdcabdbbbdacabaaaRRRt该题要求画出三个闭包的关系图. 每个关系图2 分,共 6 分. 边少画或多画一律判错. 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 8 页 - - - - - - - -

10、- 3 (1)如图 2 （2）A 的极大元有： 7，8，9，10，11，12 A 的极小元有： 1 （3）B 的上界是 6,12, 最小上界是6 B 的下界是 1，最小下界是1 哈斯图中若出现水平的边,扣 1 分. 4（分）（）判断下图是否为欧拉图，若是，请给出一欧拉回路（用阿拉伯数字在边上标明顺序即可）；若不是，请说明原因；（4 分）答：因为该图是连通图且图中没有奇度顶点，所以该图是欧拉图(只要判断正确给2 分)。欧拉回路标序如下图：找的欧拉回路正确再2 分（2）判断下图是否为哈密顿图，若是，请给出一哈密顿回路（用阿拉伯数字在顶点上标明顺序即可）；若不是，请说明原因（4 分）答：该图不是哈密

11、顿图(2 分) 。取，从图中删除，得五个连通分支，如下图所示，所以该图不是哈密顿图。(2 分) 另一证明 : 反证若有哈密顿圈, 由于点 5,7,9都是二度点 , 因此该哈密顿圈必包含边(4,5)(5,6)(6,7)(7,8)(8,9)(9,4),这 6 条边构成一个圈,矛盾 . 10 11 12 1314 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 8 页 - - - - - - - - - （ 8 分）设 G是无向简单图且(G)k2，试证明 G中存在长度大于等于k

12、+1 的初级回路（圈）。证明：不妨设是连通图，若G不连通，因为的各连通分支的最小度也都大等于k，因而可对它的某个连通分支进行讨论。设u,v 为 G中任意两个顶点，由G是连通图，因而u,v 之间存在路径，用“扩大路径法” 扩大这条路径， 设最后得到的“极大路径” 为t=v0v1vt, 则 t k， 事实上若存在“极大路径” s=v0v1vs且 sk，则 v0只能与 s中的顶点相邻，因为G为简单图，所以与v0相邻的顶点最多为s 个，而 sk，这与(G) k 矛盾，所以“极大路径”长度大等于k。在t上构造圈，由于(v0) (G)k2，因而 v0除与 t上的 v1相邻外，还存在t上的 k-1 个顶点1

13、21121,(1)kiiikvvviiit与 v0相邻，则1210 10.kiiiv vvvvv为一个圈且长度大等于k+1。注意 : 也可直接设 是 G的最长路径 . （ 8 分）在一棵有3 个 2 度顶点， 2 个 4 度顶点，其余顶点都是树叶的无向树中，应该有几片树叶？（2 分）请画出所有这样的非同构的无向树。（6 分）答：设树叶有x 片，则边数m=3+2+x-1=4+x ，由握手定理知，2m=2*(4+x)= d(vi)=3*2+2*4+x 解得 x=6，所以应该有片树叶。共有十个非同构的无向树，如下：(1) 两个度点相邻的情况：10 10 名师资料总结 - - -精品资料欢迎下载 -

14、- - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 8 页 - - - - - - - - - (2) 两个度点中间有一个度点的情况：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 8 页 - - - - - - - - - (3) 两个度点中间有两个度点的情况：(4) 两个度点中间有三个度点的情况：(请酌情扣分 ) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 8 页 - - - - - - - - -