离散数学考试卷.doc

《离散数学考试卷.doc》由会员分享，可在线阅读，更多相关《离散数学考试卷.doc（5页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、20102011学年第二学期计算机学院离散数学期末试卷（A卷）年级 专业 班级 学号 姓名 注：考试时间共100分钟，试卷总分100分题号一二三四五六总分签名得分一得 分一、 填空题（本大题共10小题，每小题3分，共30分） 1. 设命题公式，则使G成真指派分别是 。2公式 中,的辖域是 ，x自由出现 次 。3. 设 集合,则=_。 。4. Q为有理数集，运算+是普通加法，则群Q，+上， ， 。5. 把置换表成轮换的乘积是 ，表成对换的乘积是 。6. A=1,2,3,4, R=, _ ， 。 7欧拉图共有 个奇点，无向完全图共有 条边。8. X=a,b,c,d,e, X上的等价关系R=,Ix

2、,则 bR=_ _,X/R=_.9偏序关系具有的性质是 、 、 。10有甲乙丙三个人猜测ABC三个球队中的冠军.各人的猜测如下:甲: 冠军不是A,也不是B；乙: 冠军不是A,而是C；丙: 冠军不是C,而是A。已知其中有一个人说的完全正确.一个人说的都不对,而另外一人恰有一半说对了.据此推算,冠军应该是 。二得 分二、 选择题（每小题2分，共20分，请将所选答案填入下表中。）题号12345678910答案1. 以下语句中_是命题.A. 禁止酒后驾车! B. . C. 三亚是海南的省会. D. 0是偶数吗?2. 命题公式是_.A. 重言式 B. 矛盾式 C. 非重言式的可满足式 D. 析取范式3A

3、= 1,2,3,， 则R是A上的 .A. 等价关系 B. 偏序关系 C. 反自反关系 D. 对称关系4. 设表示“是运动员”，表示“会跳水”则“并非所有的运动员都会跳水。”可翻译成_.A. B. C. D. 5. 设，则关于如下_定义的*运算不能构成半群。A. B. C. D. 6. 一个5阶简单平面图，最多有_边数。 A. 6 B. 7 C.8 D. 97. 有12个顶点、3棵树的森林共有 条边。A. 6 B. 7 C.8 D. 98. 设集合，A上的二元关系不具备 性质。A. 传递性 B.反对称性 C.对称性 D.自反性9. 设F=-1，0，1，运算是普通乘法，则 。A. 是独异点但不是群

4、 B. 是群但不是阿贝尔群 C. 是阿贝尔群并且是循环群 D. 是阿贝尔群但不是循环群10. 设集合，则 。A. B.C. D. 三得 分三、 判断题（错的打“”，对的打“”；每小题1分，共10分）1. 若有向图G是单向连通的，则必是强连通的。 （ ）2.命题公式不是重言式。 （ ） 3. 循环群一定是交换群。 （ ）4. 群中一定没有零元。 （ ） 5. 一个关系是对称的就一定不是反对称的。 （ ）6f，g 是A上的函数，若是双射，则g一定是双射。 （ ）7 无向图G是哈密顿图，则G一定是欧拉图。 （ ） 8关系的复合满足结合律。 （ ）9A的等价关系与A的划分一一对应。 （ ）10一个有5

5、个结点，4条边的无向连通图是树。 （ ）四得 分四、(每小题6分,共12分)1求公式的主析取范式和主合取范式。2一棵树具有3个2度结点，2个3度结点，2个4度结点，其余为叶。试求其共有多少个结点？多少片叶？ 五得 分五（每小题10分，共20分）1、(10分)已知偏序集X,R,其中X=a,b,c,d,e, Y=d,e, R的关系矩阵为求：(1).用集合的列举法写出R；(2).画出R的哈斯图； (3).找出X的极大元、极小元、最大 元、最小元； (4).找出Y的上界、下界、最小上界、最大下界。2已知有向图G=,其中v=a,b,c,d，E=,，,(1).求出G中顶点的入度序列；(2).写出G的邻接矩阵；(3).求出图中所有长度等于2的路的条数。六得 分六、证明题（8分，）构造下面推理的证明： 前提： 结论：