文档介绍：离散数学试卷(六) 35 一、填空 15% (每小题 3分) 1、n 阶完全图结点 v 的度数 d(v) =。 2、设n 阶图 G 中有 m 条边,每个结点的度数不是 k 的是 k+1 ,若 G 中有 N k个k 度顶点, N k+1个 k+1 度顶点,则 N k=。 3、算式)*()*)*( ((fedcba??的二叉树表示为。 4、如图给出格 L ,则 e 的补元是。 5、一组学生,用二二扳腕子比赛法来测定臂力的大小,则幺元是。二、选择 15% (每小题 3分) 1 、设 S={0,1,2,3}, ≤为小于等于关系,则{S,≤} 是( )。 A 、群; B 、环; C 、域; D 、格。 2 、设[{a ,b, c}, *] 为代数系统, * 运算如下: * 则零元为( )。 A、a;B、b;C、c;D 、没有。离散数学试卷(六) 36 3 、如右图相对于完全图 K 5 的补图为( )。 4 、一棵无向树 T有7 片树叶, 3个3 度顶点,其余顶点均为 4 度。则 T 有( )4度结点。 A、1;B、2;C、3;D、4。 5、设[A ,+,·] 是代数系统, 其中+,· 为普通加法和乘法,则 A= ()时, [A ,+,·] 是整环。 A、},2|{Znnxx??;B、},12|{Znnxx???; C、},0|{Zxxx??且;D、},,5|{ 4Rbabaxx???。三、证明 50% 1 、设 G 是( n,m )简单二部图,则 4 2nm?。( 10 分) 2 、设 G 为具有 n 个结点的简单图,且)2 )(1(2 1???nnm ,则 G 是连通图。( 10 分) 3、记“开”为1,“关”为0, 反映电路规律的代数系统[{0 , 1},+,·] 的加法运算和乘法运算。如下: +01·01 001000 110101 证明它是一个环,并且是一个域。( 14 分) 4、],,[??L 是一代数格, “≤”为自然偏序,则[L,≤] 是偏序格。( 16 分) 离散数学试卷(六) 37 四、 10% 设)()()(),,( 3 23221321xxxxxxxxxE??????是布尔代数],, },1,0 [{???上的一个布尔表达式,试写出),,( 321xxxE 的析取范式和合取范式( 10 分) 五、 10% 如下图所示的赋权图表示某七个城市 721,,,vvv?及预先算出它们之间的一些直接通信成路造价(单位:万元) ,试给出一个设计方案,使得各城市之间既能够通信又使总造价最小。一、填空 15% (每小题 3 分) 1、 n-1 ;2、 n(k+1)-2m ;3 、如右图; 4、0;5 、臂力小者二、选择 15% (每小题 3 分) 三、证明 50% 1、证 : 设 G= (V,E)nnnnYnXYXV?????? 2121,,, 对完全二部图有 4 )2 ()( 2211 211121nnnnnnnnnnnm???????????当2 1nn?时,完全二部图),(mn 的边数 m 有最大值 4 2n 故对任意简单二部图),(mn 有4 2nm?。 2、证:反证法:若 G 不连通,不妨设 G 可分成两个连通分支 G 1、G 2 ,假设 G 1和G 2 的顶题目 12345 答案 DCAAD 离散数学试卷(六) 38 点数分别为 n 1和n 2