信息管理与信息系统专业离散数学 试卷及答案.doc

《信息管理与信息系统专业离散数学 试卷及答案.doc》由会员分享，可在线阅读，更多相关《信息管理与信息系统专业离散数学 试卷及答案.doc（5页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、一 单项选择题（将正确答案题号填在括号里，每小题2分，合计40分）1.设命题P、Q、R的真值分别为1、1、0，则复合命题P(QR)的真值为（ ）。 A 1 B 1或0 C 0 D 不确定2.下列命题中，（ ）是复合命题。A 长江与黄河都流经安徽境内。 B 美丽的黄山地处安徽。C 合肥位于长江以北。 D 合肥是包公故里。3.命题公式(PQ)R的主合取范式为（ ）。A (0,2,6) B (1,3,4,5,7)C (0,2,6) D (1,3,4,5,6)4.命题公式(PQ)R的主析取范式为（ ）。A (0,2,6) B (1,3,4,5,7)C (0,2,6) D (1,3,4,5,6)5.命题

2、公式(PQ)R的类型为（ ）。A 重言式 B 矛盾式 C 可满足式 D 不确定6.设论域为实数集，谓词公式xy(xy1)的真值为（ ）。A 1 B 1或0 C 0 D 不确定7.下列关系中（ ）不是等价关系。A 实数集上的等于关系 B 平面三角形集合上的全等关系C 幂集上的包含于关系 D 北大学生集合上住在同公寓的关系8.命题“合肥位于北京与上海之间。”的个体为（ ）。A 合肥，北京 B 北京，上海 C 上海，合肥 D 合肥，北京，上海9.设R为实数集，关系hx,yR，y2x，关系gx,yR，y3x，则复合关系h-1og-1的值为（ ）。A x,yR，y6x B x,yR，yC x,yR，y5

3、x D x,yR，y4x10.设A1,2,3，关系fAA且f,，关系gAA且g,，复合关系fog的值为（ ）。A , B ,C , D ,11.设IA为集合A上的恒等关系，则IA不是A上的（ ）关系。A 自反 B 反自反 C 对称 D 反对称12.设A1,2,3,4，则A上有（ ）个等价关系。A 216 B 212 C 15 D 不确定13.设A1,2,3,4，则A上有（ ）个自反关系。A 216 B 212 C 44 D 不确定14.具有5个结点3条边的不同构的简单无向图的个数为（ ）。A 2 B 3 C 4 D 515.设A1,2,3,4，Rx,yA，y2x，则R的前域dom(R)等于（

4、）A 1,2 B 2,4 C 1,3 D 1,2,3,416.设A1,2,3,4，关系RAA且R,，则R5的值为（ ）。A , B ,C , D ,17.设A1,2,3,4，关系RAA且R,，则R的传递闭包t(R)的值为（ ）A , B ,C , D ,18.设G是有9个结点的简单图，则图G的最大度(G)为（ ）。A (G) 9 B (G)9 C (G)9 D (G)919.以下列序列中（ ）为结点度数序列可构成简单无向图。A 1，1，2，2，3 B 1，1，2，2，2 C 0，1，3，3，3 D 1，3，4，4，520.设无向图G有12条边，有6个3度结点，其余结点度数均小于3，则G至少有（

5、 ）个结点。A 13 B 12 C 11 D 9二 填空题（每小题2分，合计30分）1.设P,Q为命题变元，则命题演算的吸收律可表示为 。2.设A,B为集合，则集合运算的德摩根律可表示为 。3.设A,B,C为命题变元，化简命题公式(ABC)(ABC) 。4.设A,B,C为集合，化简(ABC)(ABC) 。5.设P(x)：x是人，Q(x)：x犯错误，翻译命题“没有人不犯错误。”为 。6.给定论域2,3，且L(2,2)与L(3,3)的真值均为1，L(2,3)与L(3,2)的真值均为0，则yxL(x,y)的真值为 。7.命题“如果我是你，那么太阳从西边出。”的真值为 。8.设A1,2,3,4，B3,

6、4,5,6，则AB 。9.设P()为空集的幂集，则P(P() 。10.若R是A上的自反关系，反对称关系， ，则称R为A上的偏序关系。11.命题“如果我休假，我将去美丽的黄山旅游。”的否定可表述为 。12.设A1,2,3,4，给出上的一个关系R ，使R既是对称又是反对称的。13.无向连通图G是欧拉图，当且仅当G有 个奇数度数结点。14.若连通平面图G有4个结点3个面，则G有 条边。15.树T有2个2度结点，1个3度结点，3个4度结点，其余都是1度结点，则树T的叶子数为 。三 解答题(1、4小题各8分，2、3小题各7分，合计30分)1.今有a、b、c、d、e、f、g七人，其中a擅长英语，b擅长英语

7、和汉语，c擅长英语、意大利语和俄语，d擅长日语和汉语，e擅长德语和意大利语，f擅长法语、日语和俄语，g擅长法语和德语。试用图论知识描述如何安排这七人围圆桌而坐，使得每人都能与其相邻两边的人交谈。2.设集合A1,2,3，P(A)为A的幂集，偏序关系x,yP(A)，xy，画偏序集的哈斯图，并指出的最大元和极小元，其中B,1,3,1,3,A。3.翻译命题“所有的人都是要死的，苏格拉厎是人，所以苏格拉厎要死。”并证明其有效结论。4.某发电厂A要向b、c、d、e四个地点送电，已知发电厂A可以和b、c、d直接架设电线，地点e可以和b、d直接架设电线，其他由于地理原因无法直接架设电线。架设电线时不能有回路存

8、在，否则会造成浪费。找出所有电线架设方案，使从发电厂A可向b、c、d、e四个地点送电。答案一 单项选择题CAADC ACDBB BCBCA AADBD二 填空题1. P(PQ)P P(PQ)P2. (AB)AB (AB)AB3. BC4. BC5. $x(P(x)Q (x)6. 1或T7. 1或T8. 1,29. ,10. 传递11. 我休假但我不去美丽的黄山旅游。12. 13. 014. 515. 9三 解答题(1、4小题各8分，2、3小题各7分，合计30分)1.构造简单图G，其中 Va,b,c,d,e,f,g任意x,yV，边(x,y)E当且仅当x与y擅长同种语言图G中的一条Hamilton回路即为所求方案。4.构造简单图G，其中 VA,b,c,d,e任意x,yV，边(x,y)E当且仅当x与y间可直接架设电线图G中的生成树即为所求方案