《离散数学》考试试卷(试卷库14卷)及答案
更新时间:2023-11-12 20:38:01 阅读量: 教育文库 文档下载
- 离散数学考试题及答案推荐度:
- 相关推荐
《离散数学》考试试卷(试卷库14卷)
试题总分: 100 分 考试时限:120 分钟
题号 得分 一 二 三 四 五 总分 阅卷人 一、选择题(每题2分,共20分)
1. 下述命题公式中,是重言式的为( )
(A)(p?q)?(p?q) (B)p?q?((p?q)?(q?p))
(C)?(p?q)?q
(D)(p??q)?q
2. 对任意集合A,B,C,下列结论正确的是( )
(A)若A?B,B?C,则A?C; (B)若A?B,B?C,则A?C; (C)若A?B,B?C,则A?C; (D)若A?B,B?C,则A?C; 3. 设S?{ 1, 2, 3 },定义S?S上的等价关系,
S?S上一个划分共有( )个分块。
(A)4
(B)5
(C)6
(D)9
,则由R产生的
4. 下列偏序集( )能构成格
5. 连通图G是一棵树当且仅当G中( )
(A)有些边是割边 (B)每条边都是割边
(C)所有边都不是割边 (D)图中存在一条欧拉路径
6. 有n个结点(n?3),m条边的连通简单图是平面图的必要条件( )
(A) m?3n?6
(B)n?3m?6 (C)m?3n?6 (D) n?3m?6
7. 设P,Q的真值为0,R,S的真值为1,则下面命题公式中真值为1的是( )
(A)R?P (B)Q?S (C)P?S (D)Q?R 8. 在图G=
(A)deg(vi)?2|E|
(B)deg(vi)?|E|
(C)
?deg(v)?2|E|
iv?V(D)
?deg(v)?|E|
iv?V9. 设有33盏灯,拟公用一个电源,则至少需有五插头的接线板数( )
(A)7 (B)8 (C)9 (D)14 10. 设集合A上有四个元素,则A上的不同的等价关系的个数为( )
(A)11 (B)14 (C)17 (D)15
二、填空题(每题2分,共20分)
1. 设A={a,b,c,d},其上偏序关系R的哈斯图为
则R= 。
2. 设A?{x|x?2,n?N},定义A上的二元运算*为普通乘法、除法和加法,则代数系统中运算*关于 运算具有封闭性。
3. A,B,C表示三个集合,文氏图中阴影部分的集合表达式为
。
A B C n。 4. 矛盾式又叫 式,其定义为 。 5. 的图称为无向图。
第 1 页/共 4 页
6. 设是一个偏序集合,在A的一个子集中,如果 ,则称这个子集为链。 7. 在真值表中,一个公式的真值为F的指派所对应的大项的合取,即为此公式的 范式。
8. 设R是非空集合A上的等价关系,对任意的a?A,定义 为a关于R的等价类。 9. 设
三、判断题(每题1分,共10分)
1. 公式?xP(x)??yQ(x,y)的前束范式为?x?y(P(x)?Q(x,y))。( ) 2. (A?B)?C=(A?C) ?(B?C)。( ) 3. 不存在既对称又反对称的关系。( )
4. 若无向连通图G中存在桥,则G的点连通度和边连通度都是1。( ) 5. {{?}}?{ ?,{{?}}}。( )
6. 任意图结点度数的总和等于边数的两倍。( )
7. 设?A,?,??是布尔代数,则?A,?,??一定为有补分配格。( ) 8. 群中有零元。( )
9. 质数阶群没有非平凡子群。( )
10. (?x)A(x)∨(?x)B(x) ?(?x)(A(x)∨B(x))( )
四、解答题(3小题,共20分)
1. (5分)考虑在七天内安排七们功课的考试,使得同一位教师所任的两们课程考试不安排在接连的两天里,试说明如果没有教
师担任多于四门课程,则符合上述要求的考试安排总是可能的。 2.
3. (8分)求公式(Q?P) ∧P∧R的主析取范式和主合取范式。
4. (7分)已知无向图G有11条边,2度与3度顶点各2个,其余都是4度顶点,求G中共有几个顶点,写出过程。
第 2 页/共 4 页
五、证明(5小题,共30分)
1. (10分)用推理P,T规则证明:P→(Q→R),R→(Q→S) ? P→(Q→S)。
2. 对于正整数k,Nk={0,1,2,…,k-1},设*k是Nk上的一个二元运算,使得a*kb=a*b(mod k),这里a,b∈Nk。当k=4时构造出的*k
运算表。(4分)
3. (6分)设R为集合A上的二元关系,如果R是反自反的和可传递的,则R一定是反对称的。
4. (4分)设A,B,C是三个集合,证明:A-(B?C)=(A-B)-C。
5. (6分)设G是连通简单平面图,结点数为n(n?3),边数为m,面数为r,则r?2n?4。
试题参考答案及评分标准
一、选择题(每题2分,共20分) ADBCB ADCBD 二、填空题(每题2分,共20分)
1.{,,,,
2. 乘法
3. B?C?A?B?C
4.永假公式 给定一个命题公式,若无论对分量作怎样的指派,其对应的真值永为F,则称该命题公式为矛盾式。 5. 所有边都是无向边
6. 每两个元素都是有关系的 7. 主合取
8. [a]R = {x?A | aRx} 9. {a*b|a∈A,b∈B} 10. 连通且无回路
三、判断题(每题1分,共10分)×√×√× √√×√× 四、解答题(3小题,共20分) 1.(5分)设G为七个结点的图,每一个结点对应一门功课的考试,如果这两个结点对应的课程的考试是由不同教师担任的,那么这两个结点之间有一条边,因为每个教师所任的课程不超过4,故每个结点的度数至少是3,任两个结点度数的和至少是6,故G总包含一条汉密尔顿路,它对应于一个七门考试课目的一个适当安排。 2.(8分)各4分,步骤对,结果错,适当扣分,如果求出其一个,另一个直接写出,也不扣分。只有结果,且结果对,给一半分,只有结果,且结果错,不给分。 解:主析取范式:(P∧Q∧R)
主合取范式: (P∨Q∨R)∧(P∨┐Q∨R)∧(P∨Q∨┐R)∧(P∨┐Q∨┐R) ∧(┐P∨Q∨R)∧(┐P∨Q∨┐R)∧(┐P∨┐Q∨R) 3.(7分)解:设图G中有4度的顶点的个数为X,总的顶点的个数为V,则有V=2+2+X 根据顶点度数之和与边的数目的关系,则有2*2+3*2+4*X=2*11 (5分) 由此式得X=3 (3分)
总的顶点个数V=2+2+3=7 (2分)
五、证明(4小题,共30分)
1. (10分)每步约2分,没有P,T标识扣3分,没有序号扣3分。证明过程: (1)P→(Q→R) P (2)R→(Q→S) P (3)(Q→R)→S T(2)E (4)(Q→R)→(Q→S) T(3)E (5)P→(Q→S) T(1)(4)I 2. (4分) *4 0 1 2 3 0 0 0 0 0 1 0 1 2 3 2 0 2 0 2 3 0 3 2 1 3. (6分) 证明:设R不是反对称的,即存在
A-(B?C)=A?~(B?C) = A?(~B?~C)= (A?~B)?~C=(A-B)-C(4分)
第 3 页/共 4 页
5. (6分)证明过程:设G是连通简单平面图,结点数为n(n?3),边数为m,面数为r,则r?2n?4。
当n=3,m=2时,r=1, r?2n?4成立。(1分)
当m?3时,则每一个面的次数不小于3,由于各面的次数之和为2m,因此 2m?3r,(3分)
代入欧拉公式得n+r-m=2,消去m得r?2n?4(2分)
第 4 页/共 4 页
正在阅读:
煤矿窄轨铁路轨道(讲座)06-12
电力企业员工个人工作业绩总结04-29
安全社区建设基本要求04-30
多晶硅生产工艺—西门子法07-11
宁波公交线路09-02
2019高考考试大纲九科全解读02-23
- exercise2
- 铅锌矿详查地质设计 - 图文
- 厨余垃圾、餐厨垃圾堆肥系统设计方案
- 陈明珠开题报告
- 化工原理精选例题
- 政府形象宣传册营销案例
- 小学一至三年级语文阅读专项练习题
- 2014.民诉 期末考试 复习题
- 巅峰智业 - 做好顶层设计对建设城市的重要意义
- (三起)冀教版三年级英语上册Unit4 Lesson24练习题及答案
- 2017年实心轮胎现状及发展趋势分析(目录)
- 基于GIS的农用地定级技术研究定稿
- 2017-2022年中国医疗保健市场调查与市场前景预测报告(目录) - 图文
- 作业
- OFDM技术仿真(MATLAB代码) - 图文
- Android工程师笔试题及答案
- 生命密码联合密码
- 空间地上权若干法律问题探究
- 江苏学业水平测试《机械基础》模拟试题
- 选课走班实施方案
- 试卷
- 离散
- 答案
- 数学
- 考试
- 华工理论力学-静力学主观试题
- RFID复习题目
- 服装史课后思考题及名词解释分析
- 小区物业管理满意度调查报告
- 工程化学基础第二版浙江大学课后题答案陈根生-2019年文档资料
- 小学语文古诗文课堂教学设计及反思
- 2016行政事业单位国有资产损溢、资金挂账核实申请表
- “学习身边人,做好当前事”活动方案
- 校本课程立项申请书
- 234G互操作规范-诺基亚(4G)V1.11
- 学而思寒扩展题五年级
- 《自悼赋》《自伤赋》-班婕妤
- 2016年咨询工程师继续教育-通信市场与投资分析试卷及答案
- 苏教版六年级语文上册22 古诗两首(1)
- 质量缺陷处理专项施工方案
- 职业健康检查工作方案(外出体检流程)案例
- 中国传统民居与评论(上) - 图文
- 标后预算管理办法
- 霍乱防疫措施
- 第三章过滤计算(课堂版)