【学历类职业资格】离散数学自考题模拟3及答案解析.doc

上传人:eveningprove235 文档编号:1377302 上传时间:2019-12-01 格式:DOC 页数:12 大小:152.50KB
下载 相关 举报
【学历类职业资格】离散数学自考题模拟3及答案解析.doc_第1页
第1页 / 共12页
【学历类职业资格】离散数学自考题模拟3及答案解析.doc_第2页
第2页 / 共12页
【学历类职业资格】离散数学自考题模拟3及答案解析.doc_第3页
第3页 / 共12页
【学历类职业资格】离散数学自考题模拟3及答案解析.doc_第4页
第4页 / 共12页
【学历类职业资格】离散数学自考题模拟3及答案解析.doc_第5页
第5页 / 共12页
点击查看更多>>
资源描述

1、离散数学自考题模拟 3 及答案解析(总分:100.00,做题时间:90 分钟)一、第部分 选择题(总题数:15,分数:15.00)1.下列图中是格的是_ A B C D (分数:1.00)A.B.C.D.2.下列四个格中,是分配格的是_ A B C D (分数:1.00)A.B.C.D.3.任意一条链都是_(分数:1.00)A.分配格B.有补格C.有界格D.有界分配格4.设B,“,0,1是布尔代数, (分数:1.00)A.ab=1B.(a“)“=aC.(ab)“=a“b“D.1 是运算的零元5.在简单无向图 G=V,E中,如果 V 中的每个顶点都与其余的顶点邻接,则该图称为_(分数:1.00)

2、A.正则图B.完全图C.强连通图D.连通图6.设图 G=V,E,则下列结论成立的是_ Adeg(v)=|E| Bdeg(v)=2|E| C D (分数:1.00)A.B.C.D.7.下列数组中,能构成无向图的顶点度数的数组是_(分数:1.00)A.(1,1,2,3)B.(2,2,2,2)C.(3,2,3,4,5)D.(0,1,3,3)8.设 G=V,E是无向图,若每个顶点的度数至少为 2,则 G 包含_条初级回路。(分数:1.00)A.1B.2C.3D.49.无向连通图 G=V,E的点割集为 V 1 ,边割集为 E 1 ,则子图 GE 1 所含的连通分量个数为_(分数:1.00)A.1B.2C

3、.3D.410.设无向图 G 的邻接矩阵为 (分数:1.00)A.5B.6C.8D.911.下列图是欧拉图的是_ A B C D (分数:1.00)A.B.C.D.12.设 G 是连通平面图,有 v 个顶点,e 条边,且其平面表示中共有 r 个面,则 e=_(分数:1.00)A.v+r+2B.r-v+2C.r+v-2D.v-r+213.无向简单图 G 是棵树,当且仅当_(分数:1.00)A.G 连通且边数比结点数少 1B.G 连通且结点数比边数少 1C.G 的边数比结点数少 1D.G 中没有回路14.一棵高度为 h 的正则 k 叉树中,叶结点的个数为_ A.kh-1 B.kh C.2h-1 D

4、.2h(分数:1.00)A.B.C.D.15.若 T 是有 n 个结点的完全二叉树,则 T 有_个叶结点。 An+1 B Cn(n+1) D (分数:1.00)A.B.C.D.二、第部分 非选择题(总题数:10,分数:20.00)16.设图 G 1 =V 1 ,E 1 ,G 2 =V 2 ,E 2 ,且 (分数:2.00)17.若回路中,除起点与终点外, 1 均不相同, 2 也均不相同,则此回路称为初级回路。 (分数:2.00)18.设给定图 G(如下图所示),则图 G 的点割集是 1。 (分数:2.00)19.设图 G=V,E为有向图,V=v 1 ,v 2 ,v 3 ,v 4 ,若 G 的邻

5、接矩阵 (分数:2.00)20.设有向图 G 为欧拉图,则图 G 中每个顶点的入度 1 出度。(填“大于”“等于”“小于”) (分数:2.00)21.一个图是欧拉图的充要条件是 1,树 2(填“是”“不是”“不一定是”)欧拉图。 (分数:2.00)22.设 G 是具有 n 个顶点的简单图,如果 G 中每一对顶点度数之和大于等于 1,则在 G 中存在一条哈密顿回路。 (分数:2.00)23.n 个结点的完全图记为 K n ,那么当 1 时,K n 是平面图;当 2 时,K n 是非平面图。 (分数:2.00)24.连通无向图 G 有 6 个顶点、9 条边,从 G 中删去 1 条边才有可能得到 G

6、 的一棵生成树。 (分数:2.00)25.在有根树中,若每一个结点的出度 1m,称这棵树为 m 叉树。如果每一个结点的出度 2m 或 0,则称这棵树为完全 m 叉树。 (分数:2.00)三、计算题(总题数:5,分数:30.00)26.在全体正整数集 Z + 中规定,为:对任意的 a,bZ + , ab=a,b,即求 a,b 的最小公倍数; ab=(a,b),即求 a,b 的最大公约数; 则运算,满足结合律,交换律和吸收律,于是Z + ,是一个格。试判断下列集合是否是Z + ,的子格。 (1)A=1,2,3,9,12,72; (2)A=1,2,3,12,18; (3)A=5,5 2 ,5 3 ,

7、5 n ; (4)T=2Z + =2k|kZ + 。 (分数:6.00)_27.画出 K 4 的 2 条边的所有非同构的生成子图。 (分数:6.00)_试画出顶点数为 3 的:(分数:6.00)(1).强连通图;(分数:1.50)_(2).单侧连通图;(分数:1.50)_(3).弱连通图;(分数:1.50)_(4).非连通图。(分数:1.50)_28.用矩阵的方法求下图中顶点 v 3 、v 4 之间长度为 3 的通路的数目。 (分数:6.00)_29.用二叉树表示算术表达式(a-b*c)*d+e)(f*g+h)。 (分数:6.00)_四、证明题(总题数:3,分数:21.00)30.设图 G 有

8、 n 个顶点,n+1 条边,证明:G 中至少有一个顶点的度数大于等于 3。 (分数:7.00)_31.设 G 为 n(n3 且为奇数)阶无向简单图,G 为 G 的补图,证明:G 与 (分数:7.00)_32.设有完全 m 又树 T,其叶结点数为 t,分支结点数为 i。证明:(m-1)i=t-1。 (分数:7.00)_五、综合应用题(总题数:2,分数:14.00)33.有向图 D=V,E,如下图所示。 (分数:7.00)_34.求下图所给的带权无向图的最小生成树,并计算它的权。 (分数:7.00)_离散数学自考题模拟 3 答案解析(总分:100.00,做题时间:90 分钟)一、第部分 选择题(总

9、题数:15,分数:15.00)1.下列图中是格的是_ A B C D (分数:1.00)A.B. C.D.解析:考点 本题主要考查的知识点为格的定义。 解析 选项 A 不是格,因为a,b不存在最大下界;C 项不是格,因为a,b没有最大下界,e,f没有最小上界;D 项不是格,因为a,b没有最小上界。2.下列四个格中,是分配格的是_ A B C D (分数:1.00)A.B.C. D.解析:3.任意一条链都是_(分数:1.00)A.分配格 B.有补格C.有界格D.有界分配格解析:4.设B,“,0,1是布尔代数, (分数:1.00)A.ab=1 B.(a“)“=aC.(ab)“=a“b“D.1 是运

10、算的零元解析:5.在简单无向图 G=V,E中,如果 V 中的每个顶点都与其余的顶点邻接,则该图称为_(分数:1.00)A.正则图B.完全图 C.强连通图D.连通图解析:考点 本题主要考查的知识点为完全图。 解析 每个顶点都与其余顶点邻接的图称为完全图。6.设图 G=V,E,则下列结论成立的是_ Adeg(v)=|E| Bdeg(v)=2|E| C D (分数:1.00)A.B.C.D. 解析:7.下列数组中,能构成无向图的顶点度数的数组是_(分数:1.00)A.(1,1,2,3)B.(2,2,2,2) C.(3,2,3,4,5)D.(0,1,3,3)解析:考点 本题主要考查的知识点为无向图的顶

11、点度数。 解析 无向图的顶点度数总和必为偶数且为其边的 2 倍,故选 B。8.设 G=V,E是无向图,若每个顶点的度数至少为 2,则 G 包含_条初级回路。(分数:1.00)A.1 B.2C.3D.4解析:9.无向连通图 G=V,E的点割集为 V 1 ,边割集为 E 1 ,则子图 GE 1 所含的连通分量个数为_(分数:1.00)A.1B.2 C.3D.4解析:考点 本题主要考查的知识点为连通分量。 解析 无向连通图 G=V,E的点割集为 V 1 ,边割集为 E 1 ,则子图 G-E 1 所含的连通分量个数必为2,而子图 G-V 1 中所含的连通分量的个数不能确定。10.设无向图 G 的邻接矩

12、阵为 (分数:1.00)A.5 B.6C.8D.9解析:11.下列图是欧拉图的是_ A B C D (分数:1.00)A.B.C.D. 解析:考点 本题主要考查的知识点为欧拉图。 解析 无向连通图 G 是欧拉图的充分必要条件是 G 是连通的且无奇点。12.设 G 是连通平面图,有 v 个顶点,e 条边,且其平面表示中共有 r 个面,则 e=_(分数:1.00)A.v+r+2B.r-v+2C.r+v-2 D.v-r+2解析:13.无向简单图 G 是棵树,当且仅当_(分数:1.00)A.G 连通且边数比结点数少 1 B.G 连通且结点数比边数少 1C.G 的边数比结点数少 1D.G 中没有回路解析

13、:14.一棵高度为 h 的正则 k 叉树中,叶结点的个数为_ A.kh-1 B.kh C.2h-1 D.2h(分数:1.00)A. B.C.D.解析:考点 本题主要考查的知识点为正则 k 叉树。 解析 正则 k 叉树的高度为 h,则它的最大层数为 h-1,即叶结点位于第 h-1 层。第 0 层为根,第 1 层有k 个结点,第 2 层有 k 2 个结点,第 3 层有 k 3 个结点,依次类推,第 h-1 层有 k h-1 个结点,即叶结点个数为 k h-1 。15.若 T 是有 n 个结点的完全二叉树,则 T 有_个叶结点。 An+1 B Cn(n+1) D (分数:1.00)A.B.C.D.

14、解析:二、第部分 非选择题(总题数:10,分数:20.00)16.设图 G 1 =V 1 ,E 1 ,G 2 =V 2 ,E 2 ,且 (分数:2.00)解析:17.若回路中,除起点与终点外, 1 均不相同, 2 也均不相同,则此回路称为初级回路。 (分数:2.00)解析:其余顶点;所有边18.设给定图 G(如下图所示),则图 G 的点割集是 1。 (分数:2.00)解析:2,0,3 考点 本题主要考查的知识点是图的点割集。 解析 删除顶点 2,得到的子图为 ,删除顶点 0、3,得到的子图为 19.设图 G=V,E为有向图,V=v 1 ,v 2 ,v 3 ,v 4 ,若 G 的邻接矩阵 (分数

15、:2.00)解析:2;1 考点 本题主要考查的知识点为有向图中顶点的出度和入度。 解析 由 G 的邻接矩阵 A,可得 G 的图如下, 20.设有向图 G 为欧拉图,则图 G 中每个顶点的入度 1 出度。(填“大于”“等于”“小于”) (分数:2.00)解析:等于21.一个图是欧拉图的充要条件是 1,树 2(填“是”“不是”“不一定是”)欧拉图。 (分数:2.00)解析:连通且无奇点;不是22.设 G 是具有 n 个顶点的简单图,如果 G 中每一对顶点度数之和大于等于 1,则在 G 中存在一条哈密顿回路。 (分数:2.00)解析:n23.n 个结点的完全图记为 K n ,那么当 1 时,K n

16、是平面图;当 2 时,K n 是非平面图。 (分数:2.00)解析:n4;n524.连通无向图 G 有 6 个顶点、9 条边,从 G 中删去 1 条边才有可能得到 G 的一棵生成树。 (分数:2.00)解析:4 考点 本题主要考查的知识点为连通图的边数与树的树枝数间的关系。 解析 一棵含有 6 个结点的树的边数为 5,而无向连通图 G 的边数有 9 条,故需要删去 9-5=4 条边,才有可能得到 G 的一棵生成树。25.在有根树中,若每一个结点的出度 1m,称这棵树为 m 叉树。如果每一个结点的出度 2m 或 0,则称这棵树为完全 m 叉树。 (分数:2.00)解析:小于等于;等于三、计算题(

17、总题数:5,分数:30.00)26.在全体正整数集 Z + 中规定,为:对任意的 a,bZ + , ab=a,b,即求 a,b 的最小公倍数; ab=(a,b),即求 a,b 的最大公约数; 则运算,满足结合律,交换律和吸收律,于是Z + ,是一个格。试判断下列集合是否是Z + ,的子格。 (1)A=1,2,3,9,12,72; (2)A=1,2,3,12,18; (3)A=5,5 2 ,5 3 ,5 n ; (4)T=2Z + =2k|kZ + 。 (分数:6.00)_正确答案:()解析:(1),(2)中的 A 虽然都是 Z + 的子集,(1)中 2,3A,但是 23=2,3=6 A,(2)

18、中2,3A,但 23=2、3=6 27.画出 K 4 的 2 条边的所有非同构的生成子图。 (分数:6.00)_正确答案:()解析:K 4 的两条边的非同构的生成子图共有 2 个。由图中边与度数之间的关系知,两条边共产生 4 度,分配给 4 个顶点,其图如下: 试画出顶点数为 3 的:(分数:6.00)(1).强连通图;(分数:1.50)_正确答案:()解析:(2).单侧连通图;(分数:1.50)_正确答案:()解析:(3).弱连通图;(分数:1.50)_正确答案:()解析:(4).非连通图。(分数:1.50)_正确答案:()解析:28.用矩阵的方法求下图中顶点 v 3 、v 4 之间长度为

19、3 的通路的数目。 (分数:6.00)_正确答案:()解析:题中的有向图的邻接矩阵为 29.用二叉树表示算术表达式(a-b*c)*d+e)(f*g+h)。 (分数:6.00)_正确答案:()解析:算术表达式(a-b*c)*d+e)(f*g+h)的二叉树表示如下图: 四、证明题(总题数:3,分数:21.00)30.设图 G 有 n 个顶点,n+1 条边,证明:G 中至少有一个顶点的度数大于等于 3。 (分数:7.00)_正确答案:()解析:用反证法。 假设图 G 有 n 个顶点,n+1 条边,且 G 中每个顶点的度数都小于等于 2,由图的顶点度数与边数的关系得,2(n+1)=2n+22n,而 2

20、n+22n 是个矛盾式,所以假设不成立,原命题成立。31.设 G 为 n(n3 且为奇数)阶无向简单图,G 为 G 的补图,证明:G 与 (分数:7.00)_正确答案:()解析:设 的顶点集分别为 ,由 之间的关系可知, ,并记它们都等于 V。 ,记 v 在 中的度数分别为 ,则必有 。由于 n 为奇数,所以 n-1 为偶数,因而,若 deg G (v)为奇数,必有 为奇数,于是 G 与 32.设有完全 m 又树 T,其叶结点数为 t,分支结点数为 i。证明:(m-1)i=t-1。 (分数:7.00)_正确答案:()解析:设完全 m 叉树 T 的结点数为 n,则 n=t+i。 另一方面,每个分

21、支结点的出度为 m,则所有结点的出度和=m*i。除根外,每个结点的入度均为 1,所有结点的入度和=n-1。树中出度和等于入度和,即 m*i=n-1=t+i-1,整理得,(m-1)i=t-1。五、综合应用题(总题数:2,分数:14.00)33.有向图 D=V,E,如下图所示。 (分数:7.00)_正确答案:()解析: (1)v 2 到 v 4 长度为 1,2,3,4 的通路分别为 0 条,1 条,0 条,1 条。 (2)D 的可达矩阵为 34.求下图所给的带权无向图的最小生成树,并计算它的权。 (分数:7.00)_正确答案:()解析:取 a 1 =2,a 2 =2,a 3 =3,a 5 =10,a 5 =15,a 6 =6,得出下图的最小生成树如下:

展开阅读全文
相关资源
猜你喜欢
  • ITU-T Q 1225 FRENCH-1997 Physical plane for Intelligent Network Capability Set 2《智能网能力集2物理平台 Q系列 交换和信令 智能网 11号研究组 16pp》.pdf ITU-T Q 1225 FRENCH-1997 Physical plane for Intelligent Network Capability Set 2《智能网能力集2物理平台 Q系列 交换和信令 智能网 11号研究组 16pp》.pdf
  • ITU-T Q 1225 SPANISH-1997 Physical plane for Intelligent Network Capability Set 2《智能网能力集2物理平台 Q系列 交换和信令 智能网 11号研究组 16pp》.pdf ITU-T Q 1225 SPANISH-1997 Physical plane for Intelligent Network Capability Set 2《智能网能力集2物理平台 Q系列 交换和信令 智能网 11号研究组 16pp》.pdf
  • ITU-T Q 1225-1997 Physical Plane for Intelligent Network Capability Set 2 - Series Q Switching and Signalling Intelligent Network (Study Group 11 16 pp)《IN CS-2物理平台》.pdf ITU-T Q 1225-1997 Physical Plane for Intelligent Network Capability Set 2 - Series Q Switching and Signalling Intelligent Network (Study Group 11 16 pp)《IN CS-2物理平台》.pdf
  • ITU-T Q 1228 FASCICLE 15 SPANISH-1997 Interface Recommendation for Intelligent Network Capability Set 2 Part 1《智能网络能力接口的推荐 集2:第1部分》.pdf ITU-T Q 1228 FASCICLE 15 SPANISH-1997 Interface Recommendation for Intelligent Network Capability Set 2 Part 1《智能网络能力接口的推荐 集2:第1部分》.pdf
  • ITU-T Q 1228 FASCICLE 25 SPANISH-1997 Interface Recommendation for intelligent network Capability Set 2 Part 2《智能网络能力接口的推荐 集2:第2部分》.pdf ITU-T Q 1228 FASCICLE 25 SPANISH-1997 Interface Recommendation for intelligent network Capability Set 2 Part 2《智能网络能力接口的推荐 集2:第2部分》.pdf
  • ITU-T Q 1228 FASCICLE 25-1997 Interface Recommendation for Intelligent Network Capability Set 2 Part 2 - Series Q Switching and Signalling Intelligent Network《智能网络能力接口的推荐 集2:第2部分-系.pdf ITU-T Q 1228 FASCICLE 25-1997 Interface Recommendation for Intelligent Network Capability Set 2 Part 2 - Series Q Switching and Signalling Intelligent Network《智能网络能力接口的推荐 集2:第2部分-系.pdf
  • ITU-T Q 1228 FASCICLE 35 SPANISH-1997 Interface Recommendation for intelligent network Capability Set 2 Part 3《智能网络能力接口的推荐 集2:第3部分》.pdf ITU-T Q 1228 FASCICLE 35 SPANISH-1997 Interface Recommendation for intelligent network Capability Set 2 Part 3《智能网络能力接口的推荐 集2:第3部分》.pdf
  • ITU-T Q 1228 FASCICLE 35-1997 Interface Recommendation for Intelligent Network Capability Set 2 Part 3 - Series Q Switching and Signalling Intelligent Network《智能网络能力接口的推荐 集2:第3部分-系.pdf ITU-T Q 1228 FASCICLE 35-1997 Interface Recommendation for Intelligent Network Capability Set 2 Part 3 - Series Q Switching and Signalling Intelligent Network《智能网络能力接口的推荐 集2:第3部分-系.pdf
  • ITU-T Q 1228 FASCICLE 45 SPANISH-1997 Interface Recommendation for intelligent network Capability Set 2 Part 4《智能网络能力接口的推荐 集2:第4部分》.pdf ITU-T Q 1228 FASCICLE 45 SPANISH-1997 Interface Recommendation for intelligent network Capability Set 2 Part 4《智能网络能力接口的推荐 集2:第4部分》.pdf
  • 相关搜索

    当前位置:首页 > 考试资料 > 职业资格

    copyright@ 2008-2019 麦多课文库(www.mydoc123.com)网站版权所有
    备案/许可证编号:苏ICP备17064731号-1