2011离散数学A卷.doc

2010-2011年第二学期 《离散数学》期末考试试卷A 专业班级： 题目 一 二 三 四 五 六 七 八 分数 一、填空题（共10题，每题3分，共30分） 1. 已知，则 ， ， . 2. 命题公式，它们关系是 A B （填写“”）. 3.中根遍历图1中结点的次序为 . 4.设函数和函数，且是A上的恒等函数， 则是 射函数，是 射函数。 5.设有向图图2，则其邻接矩阵为： 6.一棵树有2个2度结点，1个3度结点，3个4度结点，其他为树叶结点，则它 有 个结点， 条边， 片树叶. 7.设有连通平面图有12个结点，22条边，则有 个面. 8.实数集上定义二元运算*为，x*y=xy-2x-2y+6,则*的单位元为 ，零元为 ，幂等元为 . 9.设有二部图如下，则其互补结点子集分别为 V1={ }, V2={ }. 10.判别命题公式的类型：是 公式. 二、选择题（共5题，每题3分,15分） 1.已知四个偏序集的哈斯图如下：其中不是格的是（）. 2. 集合上关系， 则是（ ）。 A．反自反 B．对称 C．可传递 D 自反 3. 下面关于群正确的是（） A 若为的子代数，则也是群 B 若对，若，则 C 中除单位元外还有其他的幂等元 D 中任意元素都存在有限周期 4.关于下列四个无向图的命题，正确的是（） A （a）是欧拉图，（b）是哈密顿图 B （a）是欧拉图，（c）是哈密顿图 C （b）是欧拉图，（d）是哈密顿图 D （c）是欧拉图，（d）是哈密顿图 5.设集合A上的等价关系R1和R2，则下列关系中是等价关系的是（） （A）A2-R1； （B）R1-R2； （C）r(R1-R2)；（D）R12 三、已知集合上的关系， 求出的自反、对称闭包。（10） 四、设集合A={x∣x为12的正因子}，A上的关系={()∣为整数，}，可知为偏序关系。() （1）作出上述偏序关系的哈斯图。 （2）判断偏序集为格，求2、3的最大下界，4、6上的最小上界。 （3）写出其最大元素和最小元素。 、求叶的权重分别为3,5,6,7,8,10的最优二元树，并求其权重。（） 、求下图的最小生成树及权。（5） 、试用形式证明格式证明： （分） 、符号化下面的命题，并证明其推理是正确的。（10） 每个运动员都是强壮的，每一个既强壮又聪明的人都将在事业中获得成功。张三是运动员，并且是聪明的。因此张三一定能在事业中获得成功。（个体域是人的集合） 图1 图2 A C H J I G F E D B K (d) A BA CA DA (a) (b) (d) (c) A B C D E F 2 3 4 4 5 6 7 8 10 9