《离散数学》课程教学资源（试卷习题）试卷（题目）05

离散数学试卷（五） 一、填空15%（每空3分） 1、设G为9阶无向图，每个结点度数不是5就是6，则G中至少有 一个5度结点。 2、n阶完全图，K的点数X(K)= VA 3、有向图 中从v1到v2长度为2的通路有 条。 4、设R,+,·]是代数系统，如果①R,+门是交换群②R,·]是半群 则称R,+,·为环。 5、设[L,⑧，⊕]是代数系统，则[L⑧，]满足幂等律，即对Va∈L有 二、选择15%（每小题3分） 1、下面四组数能构成无向简单图的度数列的有( ) A、(2,2,2,2,2 B、(1,1,22,3: C、(1,1,2,2,2): D、(0,1,3,3,3)。 2、下图中是哈密顿图的为( 。 IC] 3、如果一个有向图D是强连通图，则D是欧拉图，这个命题的真值为() A、真：B、假。 4、下列偏序集( ）能构成格

离散数学试卷（五） 30 一、填空 15%（每空 3 分） 1、设 G 为 9 阶无向图，每个结点度数不是 5 就是 6，则 G 中至少有 个 5 度结点。 2、n 阶完全图，Kn 的点数 X (Kn) = 。 3、有向图 中从 v1 到 v2 长度为 2 的通路有 条。 4、设[R，+，·]是代数系统，如果①[R，+]是交换群 ②[R，·]是半群 ③ 则称[R，+，·]为环。 5、设 [L,,] 是代数系统，则 [L,,] 满足幂等律，即对 a L 有 。 二、选择 15%（每小题 3 分） 1、 下面四组数能构成无向简单图的度数列的有（ ）。 A、（2，2，2，2，2）； B、（1，1，2，2，3）； C、（1，1，2，2，2）； D、（0，1，3，3，3）。 2、 下图中是哈密顿图的为（ ）。 3、 如果一个有向图 D 是强连通图，则 D 是欧拉图，这个命题的真值为（ ） A、真； B、假。 4、 下列偏序集（ ）能构成格

离散数学试卷（五） ◇ [AI ICI 天设=机2兮3子，为普适果法则是0 A、代数系统：B、半群：C、群：D、都不是 三、证明48% 1、(10%)在至少有2个人的人群中，至少有2个人，他们有相同的朋友数。 2、(8%)若图G中恰有两个奇数度顶点，则这两个项点是连通的。 3、(8%)证明在6个结点12条边的连通平面简单图中，每个面的面数都是3。 4、(10%)证明循环群的同态像必是循环群。 5、(12%)设[B,×,+,~,0,】是布尔代数，定义运算*为a*b=(a×b)+(a×b) 求证B,门是阿贝尔群。 四、计算22% 1、在二叉树中 1)求带权为2,3,5,7,8的最优二叉树T。(5分) 2)求T对应的二元前缀码。(5分) 2、下图所示带权图中最优投递路线并求出投递路线长度（邮局在D点）。 30

离散数学试卷（五） 31 5、 设 , 4} 4 1 , 3, 3 1 , 2, 2 1 s = {1, ，*为普通乘法，则[S，*]是（）。 A、代数系统； B、半群； C、群； D、都不是。 三、证明 48% 1、（10%）在至少有 2 个人的人群中，至少有 2 个人，他们有相同的朋友数。 2、（8%）若图 G 中恰有两个奇数度顶点，则这两个顶点是连通的。 3、（8%）证明在 6 个结点 12 条边的连通平面简单图中， 每个面的面数都是 3。 4、（10%）证明循环群的同态像必是循环群。 5、（12%）设 [ , , , ,0 ,1] − B  + 是布尔代数，定义运算*为 a *b = (a  b) + (a  b)， 求证[B，*]是阿贝尔群。 四、计算 22% 1、在二叉树中 1） 求带权为 2，3，5，7，8 的最优二叉树 T。（5 分） 2） 求 T 对应的二元前缀码。（5 分） 2、 下图所示带权图中最优投递路线并求出投递路线长度（邮局在 D 点）