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

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

ID:6574329

大小:652.50 KB

页数:5页

时间:2018-01-18

离散数学复习题(期末测试卷)_第1页
离散数学复习题(期末测试卷)_第2页
离散数学复习题(期末测试卷)_第3页
离散数学复习题(期末测试卷)_第4页
离散数学复习题(期末测试卷)_第5页
资源描述:

《离散数学复习题(期末测试卷)》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库

1、复习题一、填空题(请将每空的正确答案写在答题纸相应位置处,答在试卷上不得分。每小题2分,共16分。)1.谓词公式中的辖域是。2.命题公式的成真赋值为。3.在1和1000之间(包括1和1000在内)不能被4和5整除的数有个。4.设是定义在集合上的二元关系,则的对称闭包。5.,,则代数系统中的零元是。6.具有10个结点的无向完全图的边数=。7.一次同余方程的最小正整数解是。8.84与198的最大公约数是。二、单项选择题(从下列各题四个备选答案中选出一个正确答案,并将其代号写在答题纸相应位置处。答案错选或未选者,该题不得分。每小题2分,共16分。)1.设:是有理数,:能表示成分数。在一阶逻辑中

2、,命题“没有不能表示成分数的有理数”可符号化为()。A. B.C.D.2.设个体域是整数集,则下列命题的真值为真的是()。A.  B.C. D.3.集合上的关系,则的性质为()。A、自反的B、传递的、对称的C、对称的D、反自反的、传递的4.对自然数集合,下列定义的运算中()是不可结合的。A.B.C.D.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条边的不同构的简单图有()个。【第1页

3、共2页】A.2B.3C.4D.58.5的模6逆等于()。A.1B.3C.4D.5三、计算题(第1、2、3、4小题各7分,第5、6小题各8分共44分。)1.求命题公式的主析取范式和主合取范式。2.设为偏序集,其中,是上的整除关系。(1)画出的哈斯图;(2)求中的极大元;(3)令,求的上确界和下确界。3.求下图1中带权无向图的最小生成树,并求出该最小生成树的权值。4.求解递推方程:。5.有向图D如图2所示,求:(1)D中到长度为3的通路有几条?(2)D中到长度为3的回路有几条?(3)D是哪类连通图? 图1图26.在通讯中要传输字母,它们出现的频率为:,设计传输上述字母的最佳二元前缀码,画出最

4、优树,并求传输100个按上述频率出现的字母所需二进制字个数。四、证明题(每小题8分,共16分。)1.设为自然数集上的关系,定义上的关系R如下:是偶数。(1)证明为等价关系;(2)求商集。2.设为整数集合,在上定义二元运算如下:,证明:是群。五、符号化下列命题,并在自然推理系统P中论证结论的有效性(8分。)若小张喜欢数学,则小李或小赵也喜欢数学。若小李喜欢数学,则他也喜欢物理。小张确实喜欢数学,可小李不喜欢物理。所以,小赵喜欢数学。【第2页共2页】参考答案一、填空题(请将每空的正确答案写在答题纸相应位置处,答在试卷上不得分。每小题2分,共16分。)1.2.10,11,003.6004.5.

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分)主析取范式为:(2分)2.解:(1)的哈斯图如下图所示。(3分)(2)中的极大元是:24,54;(2分)(3)的上确界:无;的下确界:1。(2分)3.解:所求该图的最小生成树如下图所示。(5分)【第1页共3页】该最小生成树的权值之和W(t)=2+1+1+2+3+4=13(2分)4

6、.解:其特征方程为:,其特征根是:(2分)通解为:(2分)代入初值得到:解得:(2分)所以,原方程的解为:。(1分)5.解:先求图D的邻接矩阵及、。,(1分),(2分)(2分)(1)D中到长度为3的通路有3条。(1分)(2)D中到长度为3的回路有5条。(1分)(3)D是强连通图。(1分)6.解:按字母顺序,令为传输第个字母的频率,,则传输100个字母,各字母出现的频数为,得。将它们按照从小到大顺序排列,得。(2分)以为权求最优2叉树如下图所示。(4分)传输的前缀码分别为:。传100个所需二进制数字个数为:W(t)=15+30+60+100+40+20=265。(2分)四、证明题(每小题8

7、分,共16分。)1.(1)证明:因为,且是偶数,于是【第2页共3页】因此在上是自反的;(1分)若则是偶数,即是偶数,于是因此在上是对称的;(1分)若且则,于是,进而因此在上是传递的;(2分)综上所述,是上的等价关系。(1分)(2)关于等价关系的所有等价类为和,则。(3分)2.证明:显然,关于是封闭的。(1分)对于任意,由于,而,于是,即满足结合律。(2分),因为,因此2是关于的单位元。(2分),由于且,于是关于存在逆元。(2分)所以

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。