09秋夜大离散数学模拟题答（09.12李）

2009 级计算机科学与技术专业夜大离散数学模拟题答案

姓名 标准答案 学号 序号 成绩 100 注意事项：1、本试卷满分 100 分，考试时间 120 分钟； 2、请将答案一律写在试卷空白处。 统分栏：

题号 得分 一 15 二 15 三 10 四 20 五 20 六 20 总分 100

一、单项选择题（每题 2.5 分，共 15 分）

1、令 p：经一堑；q：长一智。将命题 ’’经一堑，长一智’’ 符号化为 [Ｂ ] A． p→q； B． q→p； C． p∧q； D． ﹁q→﹁p

2、10 阶无向简单图 G 中有 4 个奇数度顶点，其补图中必有 r 个奇数度顶点 [ C ]

A．r = 4； B．r = 5； C．r = 6； D．r = 7

3、命题公式A= p∧﹁p→q 的主析取范式为 [ C ] A． A= ∑（0,1,2）。 B． A= ∑（0,2,3）。 C． A= ∑（0,1,2,3）。 D． A= ∑（1,2,3）。

4、19 个顶点的 2-元正则树有多少片树叶？ [ C] A．38； B．19； C．10； D．9。

5、10 阶无向连通图G 的边数为m，则其生成树的树枝数为 [ A ] A． 9； B． 10； C． 11； D． m 。

6、下列公式中哪个是关于 p，q 的主合取范式 [ A ]

A．p∨q； B．﹃p∧q； C．p∧﹃q； D．﹃p∨p。

二、判断下列各题的是非（题中,m,n 分别为边,顶点数.每题 2.5 分，共 15 分） 。 1、任何无向图都有一棵生成树。 [ 非 ] 2、令 F（x）：x是兔子；G（y）：y是乌龟；H（x，y）：x 比y 跑得快。 将命题 “ 所有兔子比某些乌龟跑得快” 符号化为： ?x（F（x）→彐y（G（y）∧H（x，y）））。 [ 是 ]

3、无向连通图 G（m,n）的每一条边都可以成为他的某一生成树的树枝。 [ 非 ]

4、个体域是有理数集合，则?x?y彐z （x-y = z）为假命题 [ 非 ]

5、A=(2,3,1) R为A上的全域关系,则自然映射f:A→A/R为单射函数 常 [ 非 ]

6、命题公式 A=﹁q 的主析取范式为 A〈=〉∑（0）。 [ 是]

1

三、计算题( 10 分)

1、无向图G中有10条边,4个3度顶点,其余顶点度数全是2,共有 几 个顶点. [ 8 ]

2、图Ｇ中２个３度顶点，３个４度顶点，４个５度顶点，则Ｇ中有几条边． [ 18 ]

3、一棵树中有 i 个顶点的度数为 i（i=2，…k），其余顶点都是树叶。

问树叶多少片？ 树叶数 x = Σi（i—2） i + 2，（i = 2，3，……k）。

4、一棵树中有 i 个顶点的度数为 i（i=2，…k），其余顶点都是树叶。

当 k = 4 时，问树叶多少片？x=(0+3+8)+2 [ 13 ]

四、填空题（每题 2.5 分，共 20 分）

1、一阶逻辑公式 彐x F（x）→彐y G（y）的类型是 可满足式

2、三元正则树的叶子总数 t 必须是 大于等于３的奇数 。

3、无向图 G 有生成树的充分必要条件是 连通 。

4、无向图 G（n，m）中，若边 m 大于等于顶点 n，则图中必有 圈 。

5、高度为 k 的二元树的树叶数目 不一定 少于同高的三元树的树叶．

6、任何连通图G中,边数 m 不一定 大于顶点数 n.

7、命题公式不一定是命题。因为公式中有 命题变项 .

8、5 阶非平凡无向树至少有 2 片树叶..

五、1.在网络上给外国友人发邮件时,”Hello” 最少用二进制前缀码多少个? (20分) 1、最优二元树 T； 2、每个字母的码字； 3、10个； 4.等长码?

2、奥运会到了,给外国友人发电子邮件 ”福娃”-- Friendlies 的最佳前缀码共用

二进制码多少位? (20 分)

1、最优二元树 T； 2. 30位； 3、每个字母的码字； 4.等长码? F--000,r--001,i--01,n--1000,d--1001,e--101,l--110,s--111.

六、证明题（20 分）

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

前提：P，q∨﹁r，q→（p→s）。 结论中的前提 r移过来,与前提2，构成

结论：r→s. 公式3,从而得到 q,q与前提3构成公式

3,从而得到（p→s）再与前提1构成公3

得S.证毕.

扣题:推理正确.

2

3