2014年离散数学期末试题

1、.离散数学期末试题一、单项选择题（每小题3分，本题共15分）1若集合A=1，1，2，1，2，则下列表述正确的是( ) A2A B1，2AC1A D2 A正确答案：A2集合A=x|x为小于10的自然数，集合A上的关系R=|x+y=10且x, y A，则R的性质为（ ） A自反的 B对称的C传递且对称的 D反自反且传递的正确答案：B3n阶无向完全图Kn的边数及每个结点的度数分别是（ ） An(n-1)/2，n-1 Bn-1，n Cn(n-1), n-1 Dn(n-1), n正确答案：A4若完全图G中有n个结点(n2)，m条边，则当（ ）时，图G中存在欧拉回路An为奇数 Bn为偶数 Cm为奇数 Dm

2、为偶数正确答案：Aooooooabcdef3图G如图一所示，以下说法正确的是( ) A(a，b)是边割集 B a，c是点割集 Cd是点割集 D (c，d)是边割集正确答案：C5已知图G的邻接矩阵为 则G有（ ） A6点，8边 B6点，6边 C5点，8边 D5点，6边正确答案：D5下列公式成立的为( )APQ PQ BPQ PQ CP P DP(PQ) Q正确答案：C二、填空题（每小题3分，本题共15分）6设集合Aa，那么集合A的幂集是 正确答案：,a7如果R是非空集合A上的等价关系，a A，bA，R，则可推知R中至少包含 等元素正确答案：，8若A=1,2，R=|xA, yA, x+y4，则R的

3、自反闭包为 正确答案：,8设G是有20个结点，25条边的连通图，则从G中删去 条边，可以确定图G的一棵生成树正确答案：69设连通平面图G的结点数为5，边数为6，则面数为 正确答案：310设个体域D1,2，则谓词公式消去量词后的等值式为 正确答案：A(1) A(2)10(x)(P(x)R(y)S(z) 中的约束变元有 正确答案：x三、逻辑公式翻译（每小题6分，本题共12分）11将语句“他们去旅游，仅当明天天晴”翻译成命题公式正确答案：设P：他们去旅游，Q：明天天晴. PQ：他们去旅游，仅当明天天晴12将语句“如果明天下雨，则我们就在室内上体育课”翻译成命题公式正确答案：设 P：明天下雨， Q：我

4、们在室内上体育课. 则命题公式为：P Q四、判断说明题（每小题7分，本题共14分）13设集合A=1，2，B=3，4，从A到B的关系为f=，则f是A到B的函数正确答案：错误 ooooabcd图一因为A中元素1有B中两个不同的元素与之对应，故f不是A到B的函数13若偏序集的哈斯图如图一所示， 则集合A的最大元为a，极小元不存在正确答案：错误.b,c,d都是极小元.五、计算题（每小题12分，本题共36分）15设集合A=a, b, c，B=a, c，试计算（1）（AB）； （2）（B - A）； （3）（AB）B正确答案：（1）（AB）=c； （2）（B - A）=a； （3）（AB）B=, 16设G

5、=，V=v1, v2, v3, v4, v5，E=(v1,v3) , (v1,v5) , (v2,v3) , (v2,v5) , (v3,v4)，试（1）给出G的图形表示； （2）写出其邻接矩阵；（3）求出每个结点的度数； （4）画出其补图的图形oooov1v2v3v4图二v5o正确答案：（1）（2）oooov1v2v3v4图三v5o（3）v1，v2，v3，v4，v5结点的度数依次为2，2，3，1，2（4）17求（PQ）（RQ）的析取范式，合取范式正确答案：（PQ）（RQ） （PQ）（RQ） （4分） (PQ)（RQ） (PRQ)(QRQ)(PRQ)17试画一棵带权为2, 3, 3, 4, 5,的最优二叉树,并计算该最优二叉树的权ooooooooo23345510717正确答案：最优二叉树如图所示权为23+33+32+42+52=39六、证明题（本题共8分）18试证明集合等式A (BC)=(AB) (AC) 证明：设S= A (BC)，T=(AB) (AC)，若xS，则xA或xBC，即 xA或xB 且 xA或xC 也即xAB 且 xAC ， 即 xT，所以ST 反之，若xT，则xAB 且 xAC， 即xA或xB 且 xA或xC， 也即xA或xBC，即xS，所以TS 因此