09秋远程离散数学A答(09.12李)

1、北京大学现代远程教育2009年秋季学期期末考试试卷A离 散 数 学（603标准答案）专业及层次： 教学中心： 姓名： 标准答案 学号： 注意事项：1、本试卷满分 100 分，考试时间 90 分钟； 2、请将答案一律写在试卷空白处。统分栏：一二三四五六七总分18181612121212100一、 选择题（4 个备选中只有 1 个正确，填入括号内。每题 2 分，共 18 分）1、设集合 A =1，2，a，4，3，下面命题为真是 B A2 A； B1 A； C5 A； D2 A。2、下面命题为真的一个是 C A ； B ； C ； D 3、N, Z+ 分别是自然数集合,正整数集合,则 C AN=Z+

2、 +0 BN=Z+ + 0 CN=Z+ 0 DN=Z+. 0 .4、设函数 f：1，20，则 f B A只是单射函数.； B只是满射函数.； C是双射函数.； DA,B,C都不是.5、12设 A = a，b，B = 1，2，问A 到 B 的函数的数目有 D 。A1； B2； C3； D4 。6、设(x)+，(x)-都是从实数集合到的函数，则。 D A x+1； Bx-1； Cx2 ； Dx。 7、A,B为任意集合，则他们的共同子集是 D AA； BB； CAB； D 。8、在自然数集合上，下列那种运算是可结合的 A A. x*Y=max(x,y) ； Bx*y=2x+y ；Cx*y=x2+y2

3、 ； Dx-y. 9、自然数 N 与其上的普通加法 + 构成的代数系统 N，+ 是 C A 只是代数系统； B半群； C含幺半群； D 群.二、判断下列各题的是非（题中,m,n分别为边数及顶点数.每题2分，共18分）1、T为无向连通图G(m,n) 的一棵生成树，则必有关系n-1存在 是 2、每条边都是桥的无向连通图必是树。 是 3、3阶无向树 T 至少 3 片树叶 非 4、11 阶无向简单图有条边，则不可能是连通图 非 5、余树不一定是树. 是6、阶无向简单连通图中，定点间的最大距离为。 对 7、平凡图不可能是树。 x 8、无向连通图 G（m,n）的每一条边都可以成为他的某一生成树的树枝。 x

4、 9、边数 m 等于 n-1 的 n 阶无向图都是树。 x 三、填空题.(每题 2 分，共 16 分）1、在一阶逻辑中，命题”这台机器不能用”应符号化为 ( F（a） ) 。2、能判断对错的陈述句为 ( 命题 )。3、令 p：天下雨；q：乘汽车。命题 如果天下雨，则乘汽车 符号化为 ( )4、任一个命题公式至少 ( 1 ) 个主析取范式 .5、命题公式的类型是（ 可满足 )式. 6、命题公式 p 的主合取范式为 ( ( 0 ) )7、命题公式 pqr 的主析取范式为 ( ( 5 ) )8、个体域为自然数集合,则 x+y = y+x ( 是 ) 命题。 四、设 S =，S上的关系 R 如下：R

5、= x，yx y ，试完成下列要求（每要求 3 分，共 12 分）1、给出 R 的所有元素。R=IS。2、给出 domR 的表达式。 domR = ，。3、给出 ranR 的表达式。 ranR = ， 4、指出 R 的性质。自反，对称，传递。五、设 Z 为整数集合，在 Z 上定义二元运算 。，对于所有 x，y Z 都有 x 。y = x + y 试问Z，。能否构成群，为什麽 ？（12 分） 答：二元运算满足结合律，半群；有幺元 0，独异点；每个元素都有逆，群。六、奥运年欢送外国朋友时,在网上传输 GOODBYE 的最佳前缀码,共用多少位二 进制码。 (12分).1、最优二元树 T； 2. 18位； 3、每个字母的码字；每个字母出现频率分别为：G、D、B、E、Y：14%，O：28%；(也可以不归一,某符号出现次数即为权). 。100（近似） 42。 。56 28。 。 28。 。28 。 。 14 。 。14 14 14 14所以，得到编码如下：G（000），D（001），B（100），E（101