2014秋远程离散数学期末模拟考试试题答案分析(2014.12).doc

北京大学现代远程教育2014年秋季期末模拟考试题答案及分析离 散 数 学专业及层次： 教学中心： 姓名： 标准答案 学号： 注意事项：1、本试卷满分 100 分，考试时间 90 分钟； 2、请将答案一律写在试卷空白处。统分栏：一二三四五六七总分100一、 选择题（4 个备选中只有 1 个正确，填入括号内。）1、下面命题为真的一个是 C A ； B ，a； C ； D 答案分析： 是包括 在内的任何集合的子集，但不是 的真子集。所以，只能选 C，而不选 D。2、整数集合 Z 与其上的普通减法 - 构成的代数系统 Z，- 是 A A 只是代数系统； B半群； C含幺半群； D 群.答案分析：减法不满足结合律，所以不能是半群，或群。但满足封闭性，构成代数系统。3、设集合 S =N，Z，Q，R，下面命题为真的是 A ANQ，QR，则 NR； B. -1Z，ZS， 则 -1S ；CNQ，QR，则 NS； D1N，NS， 则 1S 。答案分析：参看作业标准答案。4、集合P = 0，1，3，5，7，其正确的谓词表达是 C AP= xx = 2n +1 且 n N + 0 ； B. P= N xx =2 n 且 n N ；CP= xx = 0 或x =2n +1 且 n N； DP = Z+答案分析：A中，+不是集合运算；B中，相对补运算把 0 也扣除了；D中，没有 0，但多了偶数。选择的唯一性就确定了。5、设函数 f：1，2a，则 f 是 B 。A.只是单射函数; B.只是满射函数; C.是双射函数; D.不是函数。答案分析：题中，该函数把1，2，都射到a 上，当然不是单射，从而也不是双射，只有选满射。6、S =a,b,S上的二元关系至多有 D A.2; B.4; C.8; D.16 答案分析：两个元素的集合，作笛卡尔积后成一个4元集合。一个4元集合的所有子集都是该集合 S 上的二元关系，共 16 个。7、A,B,C 为任意集合，则他们的共同子集是 D AA； BB； CC； D 答案分析： 是任何集合的子集。见四版书58页，五版57页，定理 3-1。8、设 A = a，b，B = 1，2，A 到 B 的函数的数目有 B 。A.3; B.4; C.5; D.6 答案分析：参看四版书96页，五版94页，定义4-24；二、判断下列各题的是非1、11 条边的无向图 G 中，所有顶点的度数之和为22 是 答案分析：握手定理：图中所有顶点的度数之和=边的两倍。2、每条边都是桥的无向连通图必是树。 是 答案分析：四版书191页，五版157页，树的性质等价定理。3、11 阶无向简单图G中有 6个奇数度顶点，其补图中必有 5个奇数度顶点 x 答案分析：参看书四版158页，五版121页：完全图与补图诸性质。4、10 阶无向连通图 G 有m 条边，则生成树 T 对应的基本割集数目为9。 是答案分析：连通图的生成树中必须有n-1条边。一条边对应一个基本割集。5、边数 m 等于 n-1 的 n 阶无向图都是树。 非 答案分析：无向连通图才行！6、 G（n，m）图的每一棵生成树都有 n-1 条树枝。 是 答案分析：树的性质等价定理。四版书191页，五版157页。7、5 阶无向树 T 至少 5 片树叶。 非 答案分析：四版191页，五版157页，定理9-2。非平凡无向树至少 2 片叶。8、10 个顶点的无向树中有 9 条边 是 答案分析：树的性质定理-边=顶点-1。三、填空题1、陈述句 x + y + z = z + y + x ( 是 ) 命题。答案分析：能说出对错的陈述句。2、令 p：经一堑；q：长一智。命题 只有经一堑，才能长一智 符号化为 （ qp ） 答案分析：书四版，五版，都是第3页，例题1-4。3、命题公式 A =（pq）q 的主析取范式为 A=（ 0 ）答案分析：永假式的主析取范式只能这样写。4、命题公式 p 的主合取范式为 ( ( 1 ) )答案分析：用真值表后，立刻看明白，谁是成假赋值！同时，谁是该公式的成真赋值，也就给出来了！任何一个公式的主析取范式，主合取范式，都展示在这个真值表中！5、设个体域是自然数集合，p 代表 xy彐z F（xy = z），则 p 是 （ 假命题 ）。答案分析：四版书45页，五版44页，例题2-8。6、任何一个命题公式都至少有 （ 1 ）个主析取范式。答案分析：主范式存在定理。四版书18页，五版14页。7、能确定正确与错误的陈述句被称为 （ 命题 ）。答案分析：命题定义。8、在一阶逻辑中，命题”这台机器不能用”应符号化为 （ F（a） ）。答案分析：本题须注意三点.第一,必须用谓词,而不能用第一章的符号p,q,r 等;第二,必须先用肯定形式 F(x):x能用,然后再将其否定;最后,这台机器用 a 表示,为个体常项.结果如是。四、1. 设 S =1，2，3，S上的关系 R 如下：R = x，yx =y ，试完成下列要求:(1) 给出 R 的所有元素。R= IS。(2) 给出 ranR 的表达式。 ranR = 1，2，3 (3) 指出 R 的性质。自反，对称，传递。答案分析：参考2014秋 分析。本题关键在于看清R 中有序对配对的条件是什麽。因为是x =y，就决定了R 的对称性而不是反对称；是自反性而没有反自反。 2、设 A =-2，-1，0，1，2，R =x，yx=y是A上的关系，试求：（1）R 的表达式。 =-2，2，-1，1，2，-2，1，-1IA （2）R 的性质。 自反，对称，传递.答案分析：参考2014秋 分析。五、1.设 Z 为整数集合，在 Z 上定义二元运算 。，对于所有 x，y Z 都有 x 。y = x + y 试问Z，。能否构成群，为什麽 ？ 答：二元运算满足结合律，半群；有幺元0，独异点；每个元素都有逆，群。2、设 Z 为整数集合，在 Z上定义二元运算 。，对于所有 x，yZ 都有 x 。y = x - y 试问Z，。能否构成群，为什麽 ？ 答：二元运算不满足结合律，只是一般代数系统。六、（1）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。 。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）。（2）树叶权为 1，3，4，5，6 的二元树 T 的最小权及 T 产生的前缀码。1、最优二元树 T； 2.树叶的码字构成的前缀码； 3.权 W（T）= 42。 19 。 8。 4。 。 。11 。 。 4 。 。1 3 5 6编码如下：1（000），3（001），4（01），6（11），5（01）.本题给的树叶的权，没有归一，与上题不同。实际上，等于是5个符号例如：a,b,c,d,e,在要传送的符号群中，分别出现1次，3次，等等。七、用构造证明法证明下面推理的正确性.如果天下雨,则不上体