莆田学院离散数学A卷.docVIP

莆田学院期末考试试卷 （A）卷 2007 —— 2008学年第 一 学期 课程名称： 离散数学 适用年级/专业： 05级数学与应用数学 试卷类别 开卷（ ）闭卷（√ ） 学历层次 本科 考试用时 120分钟 《考生注意：答案要全部抄到答题纸上，做在试卷上不给分》 一、单项选择题(每小题2分，共10分) ( )1. 命题公式的主析取范式中含极小项的个数为 ( ) A. 8 B. 3 C. 5 D. 0 ( ) 2. 已知有向图如下，那么下列命题正确的是： A. 强连通图、哈密顿图 B. 单向连通图、半哈密顿图 C. 弱连通图、哈密顿图 D. 以上都不是 ( ) 3. 已知有向图D及其邻接矩阵A和邻接矩阵的各次幂如下， ，，， 求有向图D中有多少条长度为3的通路： A. 14 B. 19 C. 31 D. 33 ( ) 4. 已知图形如下，下列对该图形的判断正确的是 A. 欧拉图、二部图 B. 欧拉图，非二部图 C. 非欧拉图，二部图 D. 非欧拉图，非二部图 ( ) 5. 设无向图G的边数为m，结点数为n，则G是树等价于　　A．G连通且m＝n＋1　　　　　　 B．G且＝1 　　C．G连通且m＝2n　　　　　　　 D．每对结点之间至少有一条通路 在点极限为的定义如下：对任意的，存在，使得对任意的，当时，总有．试在一阶逻辑中把该定义表示出来： ____________________________________________________________________________ 2. 已知关系图如下，那么该二元关系具有哪些性质：________________________。 3. 根据欧拉公式可知，在所有凸多面体中，正多面体有___________个。 4. 设函数， 定义为：，求复合函数___________________。 5. 已知带权图如下，那么该带权图的最小生成树的权为______________________。 三、计算题(共12分) 1. (6分) 设某校足球队有队员38人，篮球队有队员15人，排球队有队员20人，三队队员的总数为58人，其中有3人同时参加了三个队，试求同时参加二个队的队员共几人？ 2. (6分) 设无向简单图是正则图且是欧拉图，其顶点数为和边数满足条件： ，求和，并画出两个非同构的符合题设的图。 四、证明题 (共36分) 1.(12分) 在自然推理F系统中，证明下面推理 如果一个人怕困难，那么他就不会获得成功。每个人或者获得成功或者失败过，有些人未曾失败过，所以有些人不怕困难。(个体域为人类集合) 2.(10分) 设是实数部分非零的全体复数组成的集合，上定义的二元关系 如：， (1) 证明是上的等价关系。 (2) 在复平面上给出关系的等价类的几何意义。 3.(6分) 设是阶条边的简单平面图，已知，证明。 4.(8分) 请证明下面两个图形是否是平面图： (a) (b) 五、作图题(共12分) 1. (6分) 设A={1,2,3,4,5,6,7,8,9,10,11,12}，R为整除关系，画出偏序集A,R的哈斯图。 2. (6分) 求带权为5,5,6,7,10,15,20,30的最优二叉树，并计算权。 六、应用题(共20分) 1. (8分) 已知五支球队进行循环比赛，每两队都比赛一场，规定每场比赛的胜者得2分。负者得0分，平者得1分。已知各队所得总分各不相等，并且同时满足下面3种情况： (1) 获得冠军的队没有平过一场， (2) 获得亚军的队没有负过一场， (3) 获得第四名的队没有胜过一场。 试确定所有球队各场比赛的结果。请说明在证明中所用的数理逻辑推理中的方法和规则（至少说出两条）。 2. (6分) 1996年的诺贝尔化学奖授予对发现C60有重大贡献的三位科学家． C60是有60 个C原子组成的分子，它结构为简单多面体形状(其结构如下图)．这个多面体有60个顶点，从每个顶点都引出3条棱，各面的形状分别为五边形或六边形两种．计算C60分子中形状为五边形和六边形的面各有多少？并说明所用的方法涉及离散数学的哪些理论。 3. (6分) 在某次国际会议的预备会中，共8人参加，他们来自不同的国家，已知他们中任何两个无共同语言的人中的每一个