2011秋远程离散数学期末模拟考试试题答案(2011.(2)

二、判断下列各题的是非

1、11 条边的无向图 G 中，所有顶点的度数之和为 22 [ ]

2、每条边都是桥的无向连通图必是树。 [ 是 ] 3、11 阶无向简单图G中有 6个奇数度顶点，其补图中必有 5个奇数度顶点 [ x ] 4、10 阶无向连通图 G 有m 条边，则生成树 T 对应的基本割集数目为9。 ［ ］

5、边数 m 等于 n-1 的 n 阶无向图都是树。 [ 非 ]

6、 G（n，m）图的每一棵生成树都有 n-1 条树枝。 [ 是 ] 7、5 阶无向树 T 至少 5 片树叶。 [ 非 ] 8、10 个顶点的无向树中有 9 条边 [ 是 ]

三、填空题

1、陈述句 x + y + z = z + y + x ( 是 ) 命题。

2、令 p：经一堑；q：长一智。命题 ’’只有经一堑，才能长一智’’ 符号化为 （ q→p ）

3、命题公式 A =﹁（p→q）∧q 的主析取范式为 A〈=〉（ 0 ）

4、命题公式 ﹁p 的主合取范式为 ( ∏( 1 ) )

5、设个体域是自然数集合，p 代表 x y彐z F（x－y = z），则 p 是 （ 假命题 ）。

6、任何一个命题公式都至少有 （ 1 ）个主析取范式。

7、能确定正确与错误的陈述句被称为 （ 命题 ）。

8、在一阶逻辑中，命题 ”这台机器不能用” 应符号化为 （ ﹁F（a） ）。

六、8 个字母在通讯中出现的频率分别是 A = 30%；B = 20%；C = 15%；D = 11%；

E = 9%；F = 6%；G = 5%；H = 4%； 以此百分数为权重，求： 。100

（1）最优二元树 T： 60。

30． 。30 。40

15． 。C 20。 。20

9． 。F E。。D

H． 。G

（2）T 的权 W（T）= 274。

（3）每个字母的编码： A（01），B（11），C（001），D（101），E（100），

F（0001），G（00001），H（00000）。

七、证明题