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

北京大学现代远程教育 2009 年秋季学期期末考试试卷 A 离 散 数 学（603 标准答案） 专业及层次： 教学中心： 姓名： 标准答案 学号： 注意事项：1、本试卷满分 100 分，考试时间 90 分钟； 2、请将答案一律写在试卷空白处。 统分栏： 一 二 三 四 五 六 七 总分 18 18 16 12 12 12 12 100 一、 选择题（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 + +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； Cx 2 ； Dx。 7、A,B 为任意集合，则他们的共同子集是 D AA； BB； CAB； D 。 8、在自然数集合上，下列那种运算是可结合的 A A. x*Y=max(x,y) ； Bx*y=2x+y ； Cx*y=x 2+y2 ； 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 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 = x，yx y ，试完 成下列要求（每要求 3 分，共 12 分） 本试卷共 3 页，第 3 页 1、给出 R 的所有元素。R=I S。 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（10