资源描述：
《2014年离散数学期末试题1009.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、离散数学期末试题一、单项选择题（每小题3分，本题共15分）1．若集合A={1，{1}，{2}，{1，2}}，则下列表述正确的是()．A．{2}ÎAB．{1，2}ÌAC．1ÏAD．2ÌA正确答案：A2．集合A={x
2、x为小于10的自然数}，集合A上的关系R={
3、x+y=10且x,yA}，则R的性质为（）．A．自反的B．对称的C．传递且对称的D．反自反且传递的正确答案：B3．n阶无向完全图Kn的边数及每个结点的度数分别是（）．A．n(n-1)/2，n-1B．n-1，nC．n(n-1),n-1D．n(n-1),n正确答案：A4．若完全图G中有n个结点(n≥2)，m条边，则当（）时，图G
4、中存在欧拉回路．A．n为奇数B．n为偶数C．m为奇数D．m为偶数正确答案：Aooooooabcdef3．图G如图一所示，以下说法正确的是()．A．{(a，b)}是边割集B．{a，c}是点割集C．{d}是点割集D．{(c，d)}是边割集正确答案：C5．已知图G的邻接矩阵为则G有（）．A．6点，8边B．6点，6边C．5点，8边D．5点，6边正确答案：D5．下列公式成立的为()．A．ØP∧ØQÛØP∨ØQB．P®ØQÛP®QC．PÞPD．ØP∧(P∨Q)ÞØQ正确答案：C二、填空题（每小题3分，本题共15分）6．设集合A＝{a}，那么集合A的幂集是．正确答案：{Æ,{a}}7．如果R是非空集合A
5、上的等价关系，aÎA，bÎA，ÎR，则可推知R中至少包含等元素．正确答案：，，，8．若A={1,2}，R={
6、xÎA,yÎA,x+y<4}，则R的自反闭包为．正确答案：{<1,1>,<2,2>,<1,2>,<2,1>}8．设G＝是有20个结点，25条边的连通图，则从G中删去条边，可以确定图G的一棵生成树．正确答案：69．设连通平面图G的结点数为5，边数为6，则面数为．正确答案：310．设个体域D＝{1,2}，则谓词公式消去量词后的等值式为．正确答案：A(1)ÙA(2)10．("x)(P(x)→R(y)∨S(z))中的约束
7、变元有．正确答案：x三、逻辑公式翻译（每小题6分，本题共12分）11．将语句“他们去旅游，仅当明天天晴．”翻译成命题公式．正确答案：设P：他们去旅游，Q：明天天晴.P→Q：他们去旅游，仅当明天天晴．12．将语句“如果明天下雨，则我们就在室内上体育课．”翻译成命题公式．正确答案：设P：明天下雨，Q：我们在室内上体育课.则命题公式为：P®Q．四、判断说明题（每小题7分，本题共14分）13．设集合A={1，2}，B={3，4}，从A到B的关系为f={<1,3>，<1,4>}，则f是A到B的函数．正确答案：错误．ooooabcd图一因为A中元素1有B中两个不同的元素与之对应，故f不是A到B的函数．
8、13．若偏序集的哈斯图如图一所示，则集合A的最大元为a，极小元不存在．正确答案：错误.b,c,d都是极小元.五、计算题（每小题12分，本题共36分）15．设集合A={a,{b},c}，B={{a},c}，试计算（1）（A∩B）；（2）（B-A）；（3）（A∩B）×B．正确答案：（1）（A∩B）={c}；（2）（B-A）={{a}}；（3）（A∩B）×B={,}16．设G=，V={v1,v2,v3,v4,v5}，E={(v1,v3),(v1,v5),(v2,v3),(v2,v5),(v3,v4)}，试（1）给出G的图形表示；（2）写出其邻接矩阵；（
9、3）求出每个结点的度数；（4）画出其补图的图形．oooov1v2v3v4图二v5o正确答案：（1）（2）oooov1v2v3v4图三v5o（3）v1，v2，v3，v4，v5结点的度数依次为2，2，3，1，2．（4）17．求（P∨Q）→（R∨Q）的析取范式，合取范式．正确答案：（P∨Q）→（R∨Q）ÛØ（P∨Q）∨（R∨Q）（4分）Û(ØP∧ØQ)∨（R∨Q）Û(ØP∨R∨Q)∧(ØQ∨R∨Q)Û(ØP∨R∨Q)17．试画一棵带权为2,3,3,4,5,的最优二叉树,并计算该最优二叉树的权．ooooooooo23345510717正确答案：最优二叉树如图所示．权为2´3+3´3+3´2+4´2
10、+5´2=39六、证明题（本题共8分）18．试证明集合等式AÈ(BÇC)=(AÈB)Ç(AÈC)．证明：设S=AÈ(BÇC)，T=(AÈB)Ç(AÈC)，若x∈S，则x∈A或x∈BÇC，即x∈A或x∈B且x∈A或x∈C．也即x∈AÈB且x∈AÈC，即x∈T，所以SÍT．反之，若x∈T，则x∈AÈB且x∈AÈC，即x∈A或x∈B且x∈A或x∈C，也即x∈A或x∈BÇC，即x∈S，所以TÍS．因此T=S．18．试证明：┐（A
