离散数学华东交通大学1-4大作业

华东交大离散数学期中考试试题一、单项选择题1、若一个代数系统是独异点（含幺半群），则以下选项中一定满足的是（）。

A. 封闭性，且有零元;B. 结合律，且有幺元；C. 交换性，且有幺元;D. 结合律，且每个元素有逆元.2、下面代数系统中,中（）不是群A、G为整数集合， *为加法B、G为偶数集合， *为加法C、G为自然数集合，*为加法D、G为实数集合，*为加法3．下列选项中，（）满足交换律。

A．Klein四元群B．半群C．独异点D．群4．三个结点最多可以构成__________个非同构的无向简单图。

A．1 B．2 C．3 D．45. 下列四组数据中，不能成为任何4阶无向简单图的度数序列的为（）A. 1,1,1,3B. 3,2,2,3C. 2,2,2,2D. 1,2,3,46．无向图的关联矩阵中，每行的元素之和为（）。

A．边数的2倍B．2 C．顶点数D．顶点的度数7、二部图（偶图）K2,3是（）。

A．欧拉图 B．哈密顿图 C．非平面图 D．平面图8．3阶无向完全图（K3）不是以下哪种图？（）A．欧拉图B．平面图C．二部图D．哈密顿图二、填空题1．设S ={1, 2, 3}，S上定义的二元运算*如表所示，S中关于*运算的幺元是_____________。

零元是__________。

2、设Z5={0,1,2,3,4,5}，⊕为模6加法，即? x,y∈ Z6 ，x⊕y=（x+y）mod 6，则代数系统中元素2的逆元为_______,代数系统的生成元为__________。

3、一个无向图有4个结点，4条边，其中的3个顶点度数分别为1，2，3，则第4个结点度数一定是_______。

要成为欧拉图至少要添加_____________条边。

4、无向完全图K45．完全二部图K2,3是平面图，它的平面嵌入共有______________个面。

6. 一棵无向树T有4度、3度、2度的分枝点各1个，其余顶点均为树叶，则T中有_____________片树叶。

2021年国家开放大学《离散数学（本）》形考任务（1-4）试题及答案解析形考任务1（正确答案解析附题目之后）单项选择题题目1正确获得5.00分中的5.00分未标记标记题目题干设A={1, 2, 3, 4, 5, 6, 7, 8}，R是A上的整除关系，B={2, 4, 6}，则集合B的最大元、最小元、上界、下界依次为( )．选择一项：A. 无、2、无、2B. 8、2、8、2C. 8、1、6、1D. 6、2、6、2反馈你的回答正确正确答案是：无、2、无、2题目2正确获得5.00分中的5.00分未标记标记题目题干设集合A={1 , 2 , 3 , 4}上的二元关系R={<1, 1>，<2, 2>，<2, 3>，<4, 4>}，S={<1, 1>，<2, 2>，<2, 3>，<3, 2>，<4, 4>}，则S是R的（）闭包．选择一项：A. 自反和传递B. 传递C. 自反D. 对称反馈你的回答正确正确答案是：对称题目3正确获得5.00分中的5.00分未标记标记题目题干若集合A的元素个数为10，则其幂集的元素个数为（）．选择一项：A. 1024B. 1C. 100D. 10反馈你的回答正确正确答案是：1024题目4正确获得5.00分中的5.00分未标记标记题目题干设集合A = {1, 2, 3, 4, 5}上的偏序关系的哈斯图如图所示，若A的子集B = {3, 4, 5}，则元素3为B的（）．选择一项：A. 最大下界B. 下界C. 最小元D. 最小上界反馈你的回答正确正确答案是：最小上界题目5正确获得5.00分中的5.00分未标记标记题目题干设集合A={1, 2, 3}，B={3, 4, 5}，C={5, 6, 7}，则A∪B–C =( )．选择一项：A. {4, 5, 6, 7}B. {1, 2, 3, 5}C. {2, 3, 4, 5}D. {1, 2, 3, 4}反馈你的回答正确正确答案是：{1, 2, 3, 4}题目6正确获得5.00分中的5.00分未标记标记题目题干设集合A={1，2，3，4，5}，偏序关系是A上的整除关系，则偏序集<A，>上的元素5是集合A的（）．选择一项：A. 极大元B. 最大元C. 最小元D. 极小元反馈你的回答正确正确答案是：极大元题目7正确获得5.00分中的5.00分未标记标记题目题干设集合A ={1 , 2, 3}上的函数分别为：f = {<1, 2>，<2, 1>，<3, 3>}，g = {<1, 3>，<2, 2>，<3, 2>}，h = {<1, 3>，<2, 1>，<3, 1>}，则h =（）．选择一项：A. g◦gB. g◦fC. f◦fD. f◦g反馈你的回答正确正确答案是：f◦g题目8正确获得5.00分中的5.00分未标记标记题目题干设集合A={2, 4, 6, 8}，B={1, 3, 5, 7｝，A到B的关系R={<x, y>| y = x +1｝，则R= ( )．选择一项：A. {<2, 2>, <3, 3>, <4, 6>}B. {<2, 1>, <4, 3>, <6, 5>}C. {<2, 3>, <4, 5>, <6, 7>}D. {<2, 1>, <3, 2>, <4, 3>}反馈你的回答正确正确答案是：{<2, 3>, <4, 5>, <6, 7>}题目9正确获得5.00分中的5.00分未标记标记题目题干集合A={1, 2, 3, 4}上的关系R={<x，y>|x=y且x, yA}，则R的性质为（）．选择一项：A. 反自反B. 不是对称的C. 传递的D. 不是自反的反馈你的回答正确正确答案是：传递的题目10正确获得5.00分中的5.00分未标记标记题目题干集合A={1, 2, 3, 4, 5, 6, 7, 8}上的关系R={<x，y>|x+y=10且x, yA}，则R的性质为（）．选择一项：A. 传递且对称的B. 反自反且传递的C. 自反的D. 对称的反馈你的回答正确正确答案是：对称的未标记标记题目信息文本判断题题目11正确获得5.00分中的5.00分未标记标记题目题干空集的幂集是空集．（）选择一项：对错反馈正确的答案是“错”。

华东交通大学2009—2010学年第一学期考试卷试卷编号： （ A ）卷离散数学 课程 课程类别：必修 考试日期： 月 日 开卷(范围：可带含课程内容的手写的不超过A4大小的纸一张） 题号 一 二 三 四 五 六 七 八 九 总分 累分人签名题分100得分注意事项：1、本试卷共 8 页（其中试题4页），总分 100 分，考试时间 120 分钟。

2、所有答案必须填在答题纸上，写在试卷上无效；3、考试结束后，考生不得将试卷、答题纸和草稿纸带出考场。

一、单项选择题 （2分×10=20分）1．下列语句是命题的有[ ]。

A. 122>+y x ；B. 2010年的国庆节是晴天；C. 青年学生多么朝气蓬勃呀！D. 学生不准吸烟!2．若一个代数系统是独异点（含幺半群），则以下选项中一定满足的是[ ]。

A. 封闭性，且有零元; B. 结合律，且有幺元； C. 交换性，且有幺元; D. 结合律，且每个元素有逆元. 3．Z 是整数集合，下列函数都是Z →Z 的映射，则[ ]是单射而非满射函数。

A ．ϕ (x) =0 B ．ϕ (x) =x 2 C ．ϕ (x) =2x D ．ϕ (x) =x 4. 与命题p ∧ (p ∨q)等值的公式是 [ ]。

A. p ；B. q ；C. p ∨q ；D. p ∧q.承诺：我将严格遵守考场纪律，知道考试违纪、作弊的严重性，还知道请他人代考或代他人考者将被开除学籍和因作弊受到记过及以上处分将不授予学士学位，愿承担由此引起的一切后果。

专业 班级 学号 学生签名：5. 设M={a,b,c}，M上的等价关系R={<a,a>,<b,b>,<c,c>,<b,c>,<c,b>}确定的集合M的划分是[ ]。

A.{{a},{b},{c}}B.{{a,c},{b,c}}C.{{a,c},{b}}D.{{a},{b,c}}6. 设D：全总个体域，F(x)：x是花，M(x) ：x是人，H(x,y)：x喜欢y ，则命题“每个人都喜欢某种花”的逻辑符号化为[ ]。

离散数学图论部分形成性考核书面作业4答案离散数学作业4离散数学图论部分形成性考核书面作业本课程形成性考核书面作业共3次，内容主要分别是集合论部分、图论部分、数理逻辑部分的综合练习，基本上是按照考试的题型（除单项选择题外）安排练习题目，目的是通过综合性书面作业，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握。

本次形考书面作业是第二次作业，大家要认真及时地完成图论部分的综合练习作业。

一、填空题1．已知图G 中有1个1度结点，2个2度结点，3个3度结点，4个4度结点，则G 的边数是 15 ．2．设给定图G (如右由图所示)，则图G 的点割集是 {f} ．3．设G 是一个图，结点集合为V ，边集合为E ，则 G 的结点 度数之和 等于边数的两倍．4．无向图G 存在欧拉回路，当且仅当G 连通且 等于出度 ． 5．设G=<V ，E >是具有n 个结点的简单图，若在G 中每一对结点度数之和大于等于 n-1 ，则在G 中存在一条汉密尔顿路．6．若图G=<V , E>中具有一条汉密尔顿回路，则对于结点集V 的每个非空子集S ，在G 中删除S 中的所有结点得到的连通分支数为W ，则S 中结点数|S|与W 满足的关系式为 W(G-V1) ≤∣V 1∣ ．7．设完全图K n 有n 个结点(n ≥2)，m 条边，当 n 为奇数 时，K n中存在欧拉回路．8．结点数v 与边数e 满足 e=v-1 关系的无向连通图就是树．姓 名： 学 号： 得 分： 教师签名：4．设G是一个有7个结点16条边的连通图，则G为平面图．解：(1) 错误假设图G是连通的平面图，根据定理，结点数v，边数为e，应满足e小于等于3v-6，但现在16小于等于3*7-6，显示不成立。

所以假设错误。

5．设G是一个连通平面图，且有6个结点11条边，则G有7个面．(2) 正确根据欧拉定理，有v-e+r=2，边数v=11，结点数e=6，代入公式求出面数r=7三、计算题1．设G=<V，E>，V={ v1，v2，v3，v4，v5}，E={ (v1,v3)，(v2,v3)，(v2,v4)，(v3,v4)，(v3,v5)，(v4,v5) }，试(1) 给出G的图形表示；(2) 写出其邻接矩阵；(3) 求出每个结点的度数；(4) 画出其补图的图形．解：(1)οοοοvοv vv v(2) 邻接矩阵为⎪⎪⎪⎪⎪⎪⎭⎫⎝⎛0110010110110110110000100(3) v 1结点度数为1，v 2结点度数为2，v 3结点度数为3，v 4结点度数为2，v 5结点度数为2(4) 补图图形为2．图G =<V , E >，其中V ={ a , b , c , d , e }，E ={ (a , b ), (a , c ), (a , e ), (b , d ), (b , e ),(c , e ), (c , d ), (d , e ) }，对应边的权值依次为2、1、2、3、6、1、4及5，试（1）画出G 的图形； （2）写出G 的邻接矩阵； （3）求出G 权最小的生成树及其权值． （1）G 的图形如下：οο ο οv οv v vv（2）写出G的邻接矩阵（3）G权最小的生成树及其权值3．已知带权图G如右图所示．(1) 求图G的最小生成树；(2)计算该生成树的权值．解：(1) 最小生成树为(2) 该生成树的权值为(1+2+3+5+7)=184．设有一组权为2, 3, 5, 7, 17, 31，试画出相应的最优二叉树，计算该最优二叉树的权．12357权为 2*5+3*5+5*4+7*3+17*2+31=131四、证明题1．设G 是一个n 阶无向简单图，n 是大于等于3的奇数．证明图G 与它的补图G 中的奇数度顶点个数相等．证明：设,G V E =<>，,G V E '=<>．则E '是由n 阶无向完全图n K 的边删去E 所得到的．所以对于任意结点u V ∈，u 在G 和G 中的度数之和等于u 在n K 中的度数．由于n 是大于等于3的奇数，从而n K 的每个结点都是偶数度的（ 1 (2)n -≥度），于是若u V ∈在G 中是奇数度结点，则它在G 中也是奇数度结点．故图G 与它的补图G 中的奇数度结点个数相等．35251717311362．设连通图G 有k 个奇数度的结点，证明在图G 中至少要添加2k条边才能使其成为欧拉图．证明：由定理3.1.2，任何图中度数为奇数的结点必是偶数，可知k 是偶数． 又根据定理4.1.1的推论，图G 是欧拉图的充分必要条件是图G 不含奇数度结点．因此只要在每对奇数度结点之间各加一条边，使图G 的所有结点的度数变为偶数，成为欧拉图．故最少要加2k条边到图G 才能使其成为欧拉图．。

交大版《离散的数学结构》标准答案离散数学辅助教材概念分析、结构思维和推理证明离散数学习题解答习题六（第六章图论）1.列出日常生活中的三个例子，自然地从这些例子中导出两个无向图和一个有向图。

[解]①用v代表全国城市的集合，e代表各城市间的铁路线的集合，则所成之图g=（v，e）是全国铁路交通图。

是一个无向图。

② V代表中国象棋中的格点集，e代表任意两个相邻小方块的对角线集，那么图G=（V，e）就是“马”在中国象棋中可以走的路线图。

是一个无向图。

③用v代表fortran程序的块集合，e代表任两个程序块之间的调用关系，则所成之图g+（v，e）是fortran程序的调用关系图。

是一个有向图。

2．画出下左图的补图。

[解决方案]左图的补充图如右图所示。

3．证明下面两图同构。

图11v1′v6v6′v2′v5v5′[证明]双射函数的存在性？：五、→ V'和双射函数？：E→e′?(v1)=v1′?(v2)=v2′?(v3)=v3′?(v4)=v4′?(v5)=v5′?(v6)=v6′（v1，v2）=（v1′，v2′？（v2，v3）=（v2′，v3′？（v3，v4）=（v3′，v4′？（v4，v5）=（v4′，v5）？（v5，v6）=（v5′，v6′？（v6，v1）=（v6′，v1′？（v1，v4）=（v1′，v4′？（v2，v5）=（v2′，v5′？（v3，v6）=（v3′，v6′）显然使下式成立：（vi，vj）=（vi，vj′）？？（vi）=vi′∧? （VJ）=VJ'（1≤ ij≤ 6）那么图G与图G’同构。

4．证明（a），（b）中的两个图都是不同构的。

v1v5v2Gg′Gg′v6v8v7v4v1？v5？v3v2？v6？v8？v7？v3？v3v4?v2v1v5v2？v4v3？v1？v5v4？二图g中有一个长度为4的圈v1v2v6v5v1，其各顶点的度均为3点，而在图g′中却没有这样的圈，因为它中的四个度为3的顶点v1?，v5?，v7?，v3?不成长度的4的圈。

2017年11月上交的离散数学形考任务一本课程的教学内容分为三个单元，其中第三单元的名称是（A ）．选择一项：A. 数理逻辑B. 集合论C. 图论D. 谓词逻辑题目2答案已保存满分10.00标记题目题干本课程的教学内容按知识点将各种学习资源和学习环节进行了有机组合，其中第2章关系与函数中的第3个知识点的名称是（D ）．选择一项：A. 函数B. 关系的概念及其运算C. 关系的性质与闭包运算D. 几个重要关系题目3答案已保存满分10.00标记题目题干本课程所有教学内容的电视视频讲解集中在VOD点播版块中，VOD点播版块中共有（B）讲．选择一项：A. 18B. 20C. 19D. 17题目4答案已保存满分10.00标记题目题干本课程安排了7次形成性考核作业，第3次形成性考核作业的名称是（ C）．选择一项：A. 集合恒等式与等价关系的判定B. 图论部分书面作业C. 集合论部分书面作业D. 网上学习问答题目5答案已保存满分10.00标记题目题干课程学习平台左侧第1个版块名称是：（C）．选择一项：A. 课程导学B. 课程公告C. 课程信息D. 使用帮助题目6答案已保存满分10.00标记题目题干课程学习平台右侧第5个版块名称是：（D）．选择一项：A. 典型例题B. 视频课堂C. VOD点播D. 常见问题题目7答案已保存满分10.00标记题目题干“教学活动资料”版块是课程学习平台右侧的第（ A ）个版块．选择一项：A. 6B. 7C. 8D. 9题目8答案已保存满分10.00标记题目题干课程学习平台中“课程复习”版块下，放有本课程历年考试试卷的栏目名称是：（D ）．选择一项：A. 复习指导B. 视频C. 课件D. 自测请您按照课程导学与章节导学中安排学习进度、学习目标和学习方法设计自己的学习计划，学习计划应该包括：课程性质和目标（参考教学大纲）、学习内容、考核方式，以及自己的学习安排，字数要求在100—500字．完成后在下列文本框中提交．解答：学习计划学习离散数学任务目标：其一是通过学习离散数学，使学生了解和掌握在后续课程中要直接用到的一些数学概念和基本原理，掌握计算机中常用的科学论证方法，为后续课程的学习奠定一个良好的数学基础；其二是在离散数学的学习过程中，培养自学能力、抽象思维能力和逻辑推理能力，解决实际问题的能力，以提高专业理论水平。

绪论单元测试1.本课程主要介绍哪些内容？A:代数系统B:图论C:数理逻辑D:二元关系答案:ABCD第一章测试1.这个命题公式：为重言式。

A:对B:错答案:A2.下列4个推理定律中，正确的是（）A:B:C:D:答案:BC3.设p：他学习刻苦，q：他优秀，命题“他不仅学习刻苦且优秀”的符号化正确的是（）A:B:C:D:答案:B4.命题为假命题的是（）A:如果2是奇数，那么一个公式的析取范式惟一。

B:如果2是偶数，那么一个公式的析取范式惟一。

C:如果2是奇数，那么一个公式的析取范式不惟一。

D:如果2是偶数，那么一个公式的析取范式不惟一。

答案:B5.语句中不是命题的只有( )A:学生都刻苦读书。

B:人要在锻炼中成长。

C:多么优秀的大学生活呀！D:如果心情好，那么胃口就好。

答案:C第二章测试1.谓词公式的前束范式是唯一的。

A:错B:对答案:A2.的前束范式是（）A:B:C:D:答案:BC3.设个体域A={a,b}，公式”在A中消去量词后应为（）A:P(a)P(b)B:P(a)P(b)C:P(a)D:P(b)答案:B4.令F(x):x是金属，G(y):y是液体，H(x,y):x可以溶解在y中，则命题“任何金属可以溶解在某种液体中”可符号化为( )A:B:C:D:答案:C5.设M（x）:x是人，F（x）：x犯错误，命题“所有的人都会犯错误。

”符号化为（）A:B:C:D:答案:B第三章测试1.设A-B=，则有（）A:B:C:D:答案:D2.设A={a,b,c}，A上二元关系R={〈a,a〉，〈b,b〉,〈a,c〉}，则关系R的对称闭包s(R)是( )A:B:RC:D:答案:C3.设关系R={<a,a>,<a,b>,<a,c>},则R满足性质（）A:对称性、传递性B:反对称性、传递性C:反自反性、反对称性D:自反性、反对称性答案:B4.设A={1,2,3,4}，下列哪些是A上的划分（）A:{{1,3},{2,4}}B:{{1},{2},{3},{4}}C:{{1,2},{2,3},{4}}D:{{1,2},{3,4}}答案:ABD5.集合A={2,3,4,5,6,7}上的整除关系是偏序关系，A上的极小元是2、3、5、7。