《离散数学试卷A》由会员分享，可在线阅读，更多相关《离散数学试卷A（5页珍藏版）》请在金锄头文库上搜索。
1、 本试卷共本试卷共 3 页，此页为页，此页为 A 卷第卷第 1 页页 （注：参加重修考试者请在重修标识框内打钩）中中 原原 工工 学学 院院20092010 学年学年 第第 一一 学期学期08 级计算机科学级计算机科学 专业专业 离散数学离散数学 课程期末试卷课程期末试卷题号题号一一二二三三四四五五六六七七八八九九十十总分总分一、 填空（每题 4 分，共 20 分） 1、 设 P:天下雨，Q:我骑自行车上班，将命题“只有天不下雨，我才骑自行车上班”符 号化为 。2、 在谓词逻辑中，设在北京工作，是北京人，将命题“在北京工作 :F xx :G xx的人未必都是北京人”符号化为 。3、 设图是 6
2、 个顶点的连通图，总度数是 20，则从图中删除 边后，使之成GG 为树。4、 设，是群， （其中是的幂集，为集合的对称1,2,3,4,5A ,P A P AA差，若方程 ，则 。 1,33,4,5XX 5、 设，二元关系 ，, , ,Aa b c dR,a ba cb cc d则 。 Rt二、 单项选择题（每题 4 分，共 20 分）1、 给定命题公式，该公式在全功能集中的形式为（ ） 。pqr, A B pqrpqr C Cqpr qpr2、 给定命题公式 ，则该公式的成真赋值为（ ） 。()pqrA 无 B 010,100,101,111C 010,100,101,110,111 D 全体
3、赋值3、 给定解释 I 如下：（a）个体域 ， 1,2D (b) 为 ， ，则（ ）真值为真。,F x y 1,12,11FF1,22,20FFA B ,x yF x y ,x yF x y C D ,xF x y,x yF x y 4、 以下四组数（ ）能构成简单无向图的度数列。A B 12 2 3 4 5，2 33 4 4 5，C D 1112 3，2 33 4 5 6，5、 对于下面的二元有序正则树，先根遍历的次序是（ ） 。 三、(本题 9 分) 设命题公式 A 的真值表如下，试写出命题公式 A 的主析取范式与主合取范式。P Q R A0 0 010 0 100 1 00 0 1 11
4、 1 0 011 0 101 1 001 1 10A 卷卷重修标识重修标识班级班级 姓名姓名 学号学号 装订线KIJHGFDECBA本试卷共本试卷共 3 页，此页为页，此页为 A 卷第卷第 2 页页 四、(本题 9 分) 设 ，A= 1,2,3,4,5,6,7,8,9 ,R=, ,x y xy x yA整除1、证明 R 是 A 上的偏序关系； 2、画出其偏序关系所对应的哈斯图。五、(本题 7 分) 求谓词公式 的前束范式。 (,()xyP x yyQ yR x 六、 （本题 9 分）根据哈夫曼算法求一棵树权为 2,3,5,7,9，11,13,15 的最优 2 叉树,计算它的权。 ，七、 （本题
5、 8 分）设有 5 个城市 ，任意两个城市之间铁路造价如下：（以百万为单位）12345,v v v v v 12131415232425343545,4,7,16,10,13,8,17,3,10,12,w v vw v vw v vw v vw v vw v vw v vw v vw v vw v v试求出连接 5 个城市的且造价最低的铁路网。班级班级 姓名姓名 学号学号 装订线本试卷共本试卷共 3 页，此页为页，此页为 A 卷第卷第 3 页页八、 (本题分) 设是连通平面图，且每个面的次数至少为 （） ，则Gl3l 22lmnl（其中为边数，为结点数） ，应用上述结论说明不是平面图。mn3,
6、3K九、(本题 8 分) 设 是任一群，定义为,G RG G1,Ra bGbhah存在h使得证明是上的等价关系。RG班级班级 姓名姓名 学号学号 装订线本试卷答案共本试卷答案共 2 页，此页为页，此页为 A 卷卷 第第 1 页页 中中 原原 工工 学学 院院2009 2010 学年学年 第第 一一 学期学期08 计算机科学计算机科学 专业专业 离散数学离散数学 课程期末试卷标准答案（即评分标准）课程期末试卷标准答案（即评分标准）一、1 ；QP x F xG x1,4,5 ,t Ra ba cb cc da db d二、1；三、 解 ；- 4 分 APQRPQRPQR APQRPQRPQRPRR
7、PQR - 9 分 四、证明 因为具有自反性、反对称性及传递性，所以，R 是偏序关系。- - 5 分- 9 分五、 解 (,)x y zP x yQ zR x = - 7 分 (,)x y zP x yQ zR x 六、解- 7 分树权为( )3 112 55 34 53 73 92 132 15182W T - - 9 分七、解 首先将本题用权图来描述，于是求解此问题变成为求权图中的最优支撑树问题，然 后按克鲁斯克尔算法，下图是求得的最优支撑树：-8 分A 卷卷1986754321513975321110374本试卷答案共本试卷答案共 2 页，此页为页，此页为 A 卷卷 第第 2 页页 八、
8、 证明 由已知条件可知在：（1） 12deg()ri imRl r 由于 G 是连通平图，由欧拉公式得 （2） -4 分2rnm将 （2）代入（1）得- 7 分22lmnl对于，于是3,3K 有m =10, n=522这是个矛盾，所以不是平面图。 -10 分3,3K九、 证明 设 e 是中的幺元，则（1）对于任意的，1,aGae a e 有所以， - 2 分Ra, a（2）若，由定义，存在所以，Ra, b1,hGbh a h 使得111() ,ahbh 这表明 ， - 5 分, b aR（3）若 ，则存在,a bb cR11 121122,h hbha hchb h 使得故有 ，所以 ，1 2121()chhahh , a cR因此，是等价关系。 - 8 分R
