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，得出下图的最小生成树如下：
