《离散数学》课程教学资源（试卷习题）试卷（答案）20

离散数学试卷（二十）参考答案 一、填空20% 1、2:2、(A4): 3.PA-0A-RV-PA-0Rv(-PA0n-v-P V(PA-OA-RV(PA-QAR)Y(PAOAR)=2343 111) 4、xy(P(x)AQy)→R(x,y):5、111:6、n-1: 111 7、x(G)≤2(G)≤6(G):8、m≤3n-6:9、xoy∈H: 10、含么元，可交换，无零因子。 二、选择10% 题号1 23 4 5 答案 B c D B 三、12% 解：前提：3r(P(x)A(Dy)→L(x,y》,x(P(x)→(L(x,y)→Qy》 结论：(Dy)→一Q(y》 演绎推理： (1)3x(P(x)ADy)→L(x,y》 (2)Pe)A(Dy)→L(e,y) ES(1) (3)x(Px)→L(x,y)→Qy》 (4)P(e)→y(L(e,y)→-Qy》 US(3) (5)Pe T(2)I (6)(L(e,y)→Q》 T4(51 (7)L(e,c)→-Qc) US(6) (8)y(Dy→L(e,y) T2)L

离散数学试卷（二十）参考答案 133 一、填空 20% 1、 n 2 ； 2、 ( ) 1 i n i A =   ； 3、 0,1,2,3,4,5,7 ( ) ( ) ( ) ( ) ( ) ( ) ( )             =                     P Q R P Q R P Q R P Q R P Q R P Q R P Q R ； 4、xy(P(x)  Q( y) → R(x, y)) ；5、           1 1 1 1 1 1 1 1 1 ； 6、n-1 ； 7、 (G)  (G)   (G) ； 8、 m  3n −6 ； 9、 x y  H −1  ； 10、含幺元，可交换，无零因子。 二、选择 10% 题号 1 2 3 4 5 答案 C B C D B 三、12% 解：前提： x(P(x)  y(D( y) → L(x, y)) , x(P(x) → y(L(x, y) → Q( y))) 结论： y(D( y) → Q( y)) 演绎推理： （1） x(P(x)  y(D( y) → L(x, y)) P （2） P(e)  y(D( y) → L(e, y)) ES(1) （3） x(P(x) → y(L(x, y) → Q( y))) P （4） P(e) → y(L(e, y) → Q( y)) US(3) （5） P(e) T(2)I （6） y(L(e, y) → Q( y)) T(4)(5)I （7） L(e,c) → Q(c) US(6) （8） y(D( y) → L(e, y)) T(2)I

离散数学试卷（二十）参考答案 (9)D(c)→L(e,c) US(8) (10)Dc)→-0c) T(97)1 (11)Dy)-→-Qy) UG(10) 四、解： ①A中最大元为x,最小元不存在： ②{x,x4,x}上界x,x,上确界x:下界无，下确界无。 五、解： 证：y∈Y,因g是映射，故必存在：∈Z使gy)=2,由于g°f(x)=z即 g(f(x》=:=gy),因g是单射，所以f(x)=y说明y∈Y,必有 xeX使得f(x)=y,故f(x)是满射。 六、解： 证：因为G是结点数n之3的简单连通平面图，所以m≤3n-6,又由于m≥2且连通 简单平面图的每个面至少有3条边围成，于是3r≤2m≤2(3n-6),所以r≤2n-4。 七、解： 用100乘各频率得权数： w1=35,w=20,w=15,w=10,w=10,w6=5,W,=5将其由小到大排列用 Huffman算法可求得最优树。 551010152035 101010152035 2010152035 20252035 402535 4060 100 134

离散数学试卷（二十）参考答案 134 （9） D(c) → L(e,c) US(8) （10） D(c) → Q(c) T(9)(7)I （11） y(D( y) → Q( y)) UG(10) 四、解： ① A 中最大元为 1 x ，最小元不存在； ② { , , } 3 4 5 x x x 上界 1 3 x , x ，上确界 1 x ；下界无，下确界无。 五、解： 证： y Y ，因 g 是映射，故必存在 z  Z 使 g( y) = z ，由于 g  f (x) = z 即 g( f (x)) = z = g( y) ，因 g 是单射，所以 f (x) = y 说明 y Y ，必有 x X 使得 f (x) = y ，故 f (x) 是满射。 六、解： 证：因为 G 是结点数 n  3 的简单连通平面图，所以 m  3n −6 ，又由于 m  2 且连通 简单平面图的每个面至少有 3 条边围成，于是 3r  2m  2(3n − 6) ，所以 r  2n − 4 。 七、解： 用 100 乘各频率得权数： w1=35， w2=20， w3=15， w4=10， w5=10， w6=5， w7=5 将其由小到大排列用 Huffman 算法可求得最优树。 5 5 10 10 15 20 35 10 10 10 15 20 35 20 10 15 20 35 20 25 20 35 40 25 35 40 60 100

离散数学试卷（二十）参考答案 最优二叉树为 20 10 10 1 编码树为： 0 9 1 01 90 101 前缀码：a:11:b:01:c:101:d:100:e:001:f0000:g:0001 八、解： 设I为T中最长的基本道路且以u为起点，V为终点，即1=m2.yv 。一如果d()≠1，则u的邻接点除了y,之外还有一点，不妨 设为4，雨4不在上，有测工中存在国路号即名。一。之 与T为树矛盾。于是得到一条1'=山m,y2.yy是比I更长的基本道路，这与1是最长的道路矛 盾，故d()=1。同理可证d()=1。 九、证： "→”因为b1。a∈H所以(b1。a)1=al。b∈H, 又b=(aoa)ob=ao(aob)∴.b∈alH a=(bob-)oa=bo(b-oa)∴.a∈bH x∈alH→x=aoh=(boh)h=b(hoh)∈bH∴.aH bH 同理可证bH aH所以aH=bH 故aHbH=alH≠Φ 135

离散数学试卷（二十）参考答案 135 最优二叉树为 编码树为： 前缀码：a：11； b：01； c：101； d：100； e：001；f：0000；g：0001 八、解： 设 l 为 T 中最长的基本道路且以 u 为起点，v 为终点，即 l uv v v v = 1 2  k 如果 d(u)  1 ，则 u 的邻接点除了 1 v 之外还有一点，不妨 设为 1 u ，而 1 u 不在 l 上，否则 T 中存在回路 uv1 v2 u1u 即 与 T 为树矛盾。于是得到一条 l u uv v v v = 1 1 2  k  是比 l 更长的基本道路，这与 l 是最长的道路矛 盾，故 d(u) = 1 。同理可证 d(v) = 1 。 九、证： "" 因为 b a  H b a = a b H − − − −    1 所以 （ 1 ）1 1 ， 又 b = a a b = a a b  baH − − ( ) ( ) 1 1     a = b b a = b b a  a bH − − ( ) ( ) 1 1     xaH  x = a  h1 = (b  h) h1 = b (h  h1 )bH  aH  bH 同理可证 bH  aH 所以 aH = bH 故 aH bH = aH   u v1 vk v u v1 u1 vk v

离散数学试卷（二十）参考答案 "="若aH∩bH≠Φ设x∈aH⌒bH则 3h,h2∈H使x∈aoh=boh 可得：b-1oa=h2oh∈H。 136

离散数学试卷（二十）参考答案 136 "" 若 aH bH   设 xaH bH 则  h1 , h2  H 使 a h1 b h2 x  =  可得： b a = h h  H − −1 2 1 1  