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

北京大学现代远程教育2011年秋季学期期末模拟考试试卷答

离 散 数 学

专业及层次： 教学中心： 姓名： 标准答案 学号： 注意事项：1、本试卷满分 100 分，考试时间 90 分钟；

2、请将答案一律写在试卷空白处。

统分栏：

一、 选择题（4 个备选中只有 1 个正确，填入括号内。）

二、判断下列各题的是非

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）。

七、证明题

用附加前提法证明下面的推理： 说明如下:

前提：P，q∨﹁r，q→（p→s）。结论：r→s. 结论中的前提 r移过来,与前提2 推理正确。 构成公式3,从而得到 q,q与前提3 构成公式3,从而得到（p→s）, （p→s）再与前提1构成公式3, S.证毕.扣题说:推理正确.

本文来源：https://www.bwwdw.com/article/cjx4.html