09秋夜大离散数学模拟题答(09.12李)

1、2009 级计算机科学与技术专业夜大离散数学拟案注意事项：1、本试卷满 100 分，考试间 120 分钟;2、请将答案一律写在试卷空处统分栏题号”-四五、八得分1515102020201W亠、单项择题每题 2.5 分，共 15 分)1、令 P：经一堑；q：长一智。将命题经一堑，长一智符号化为BA pfq;B qfp;C pAq;D qp-.6、下列公式中哪个是关于 p,q 的主合取范式丨 AApVq;B pAq;C pAq;D p4/po1、任何无向图都有一棵生成树。丨非2、 令 F(x):x 是兔子； G(y):y 是乌龟； H(x,y):x 比 y 跑得快。 将命题“所有兔子比某些乌龟跑得

2、快”符号化为：Kx(F(x)y(G(y)AH(x,y)。是3、无向连通 G(m,n。的每一条边都可以成为他的某一生成树的树枝丨非姓名标准答案学号序号成绩)02、10 阶无向单图G 中有 4 个奇数度顶点，其补图中有r 个奇数度顶点丨 CA.r=4;3、命题公式 A=pApfq 的主析取范式为 A A=刀(0,1,2)。C A=刀(0，1，2,3)o4、19 个顶点的 2-元正则树有多少片树叶A 38;B 19;CB A=刀（0,2,3） oDA=刀（1,2,3）。CC.10;D 9o5、10 阶无向连通 G 的边数为 m,则其生成树的树数为A 9;B 10;C 11;D mo：、判断下列各题的

3、是非(题中,m,n分为边，顶点数每题 2.5分，共 15 分)4、个体域是有理数集合，贝 Ixy 彐 z(x-y=z。为假命题丨非5、A=(2,3,1)R 为 A 上的全域关系,则自然映射 f:AfA/R 为单射数常丨非6、命题公式A=GH的主析取范式为 A=刀(0)。是三、计题（10 分）1G 中有 10 条边,4 个 3 度顶点,其余顶点度数全是 2,共有几个顶点丨 8、无向图2、图 G 中 2 个 3 度顶点，3 个 4 度顶点，4 个 5 度顶点，则 G 中有几条边183、一棵树中有 i 个顶点的度数为 i（i=2，k）,其余顶点都是树叶。问树叶多少片树叶数 x=乞i（i2）i+2,（

4、i=2,3,k）。4、一棵树中有 i 个顶点的度数为 i（i=2，k）,其余顶点都是树叶。当 k=4 时，问树叶多少片 X=（0+3+8）+213四、填空题（每题 2.5 分，共 20 分）1、一阶逻辑式彐 xF（x）-彐 yG（y）的类型是可满足式2、三元正则树的叶数 t 必须是大于等于 3 的奇数。3、无向图 G 有生成树的充分必要条件是连通4、无向图 G（n,m 中，若边 m 大于等于顶点 n，则图中必有圈。5、高度为 k 的二元树的树叶数不一定 J 的树叶.6、任何连通 G 中,边数 m 不一定于顶点数 n.7、命题公式不一定是命题。因为公式中有命题变&5 阶非平凡无向树至少有 2 片树叶2、奥运会到了，给外国友人发电邮”福娃”-Friendlies 的最佳前缀码共用二进制码多少位？（20 分）1、最优二元树 T;2.30 位；3、每个字母的码字；4.等长?F-000,r001,i01,n1000,d1001,e101,l110,s-111说明如下：结论中的前提 r 移过来与前提 2,构成五、 1.在网络上给外国友人发邮时,”Hello”最少用二进制前缀码多少个？（20 分）1、最优二元树 T;2、每个字母的码字；3、10 个；4.等长?六、证明题（20 分）用附加前提法证明下面的推理： 前提：P,qV