《09春远程离散数学A答(09.06北大)》由会员分享，可在线阅读，更多相关《09春远程离散数学A答(09.06北大)（3页珍藏版）》请在金锄头文库上搜索。
1、北京大学现代远程教育2009年春季学期期末考试试卷A离 散 数 学（603标准答案）专业及层次： 教学中心： 姓名： 标准答案 学号： 注意事项：1、本试卷满分 100 分，考试时间 90 分钟； 2、请将答案一律写在试卷空白处。统分栏：一二三四五六七总分18181612121212100一、 选择题（4 个备选中只有 1 个正确，填入括号内。每题 2 分，共 18 分）1. 把至少具有一个共同性质的事物的集体称为A集合； B关系； C函数； D代数系统。2设集合 A =1，2，a，4，3，下面命题为真是 B A2 A； B1 A； C5 A； D2 A。A,B为任意集合，则他们的共同子集是
2、D AA； BB； CAB； D 。N, Z+ 分别是自然数集合,正整数集合,则 C AN=Z+ +0 BN=Z+ + 0 CN=Z+ 0 DN=Z+. 0 .5设 A =1，2，3，A 上的二元关系 R =x，yx = y ，R 的性质为 D A只有反自反性; B只有对称性； C只有反对称性； D等价关系 .6设(x)+，(x)-都是从实数集合到的函数，则。 D A x+1； Bx-1； Cx2 ； Dx。 设 A = a，b，B = 1，2，问A 到 B 的函数的数目有 D 。A1； B2； C3； D4 。设函数：，（），为自然数集合，则函数性质为A只为单射 B只为满射 C双射 D,都不
3、是 . 9、自然数 N 与其上的普通加法 + 构成的代数系统 N，+ 是 C A 只是代数系统； B半群； C含幺半群； D 群.二、判断下列各题的是非（题中,m,n分别为边数及顶点数.每题2分，共18分）1、11 条边的图 G 中，所有顶点的度数之和为22 是 2、每条边都是桥的无向连通图必是树。 是 3、阶无向树 T 至少 1 片树叶 非 4、11 阶无向简单图有条边，则不可能是连通图 非 5、余树一定不是树. 非6、阶无向简单连通图中，顶点间的最大距离为。 对 7、平凡图不可能是树。 x 8、无向连通图 G（m,n）的每一条边都可以成为他的某一生成树的树枝。 x 9、无向图有条边，个度顶
4、点，个度顶点此命题为真三、填空题.(每题 2 分，共 16 分）1、在一阶逻辑中，命题”这台机器能用”应符号化为 ( F（） ) 。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 ，试完成下列要求（每要求
5、 3 分，共 12 分）1、给出 R 的所有元素。R=IS。2、给出 domR 的表达式。 domR = ，。3、给出 ranR 的表达式。 ranR = ， 4、指出 R 的性质。自反，对称，传递。五、设 Z 为整数集合，在 Z 上定义二元运算 。，对于所有 x，y Z 都有 x 。y = x + y 10 ，试问Z，。能否构成群，为什麽 ？（12 分） 答：二元运算满足结合律，半群；有幺元 10，独异点；每个元素都有逆，群。六、8 个字母在通讯中出现的频率分别是 A = 30%；B = 20%；C = 15%；D = 11%；E = 9%；F = 6%；G = 5%；H = 4%；以此百分数为权重，求：（共15 分） 。100（1）最优二元树 T： 60。30 。30 。40 15 。C 20。 。209 。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）。七、用构造证明法证明下面推理的正确性（12 分）如果天下雨,则不上体育课.天下雨了.所以我们不上体育课.前提：Pq, p; 结论：q. 推理正确。本试卷共 3 页，第 3 页
