计算机科学与技术专业级第二学期离散数学试题2012年1月一、单项选择题（每小题3分，本题共15分）1. C 2. C 3. B 4. A 5. D1-若集合4的元素个数为10,则其幕集的元素个数为（）•A. 10B. 100C. 1024D. 12. 设A={a, d},伊{1,2}, R、,电、足是刀到8的二元关系，旦用二{＜Q, 2＞,＜。

】＞},他二{＜。

1＞,＜。

2＞,＜》，】＞},足={＜。

，】＞,＜/?, 2＞）,则（）是从/到8的函数.A. R［和R? B . R仁 C. R3 D. R\和足3. 设木{1,2,3,45,6,7,8}, /?是/上的整除关系，位{2, 4, 6},则集合8的最大元、最小元、上界、下界依次为（）•A. 8、2、8、2B.无、2、无、2C. 6、2、6、2D. 8、1、6、14.若完全图G中有77个结点777条边，则当（）时，图G中存在欧拉回路.A.。

为奇数B. ”为偶数C. "7为奇数D. s为偶数5.已知图G的邻接矩阵为% o o 1 T0 0 0 0 10 0 0 1 110 10 111110则。

有（）.A. 6 点，8 边B.6点，6边C. 5 点，8 边D.5点，6边二、埴空题（每小题3分，本题共15分）6. 设集合乂 = {况，那么集合/的富集是{。

腥}}.7. 若吊和％是/上的对称关系，则R\U电,R、nw R'-电，传用中对称关系有个.8. 设图G是有5个结点的连通图，结点度数总和为10,则可从G中删去1 条边后使之变成树.9. 设连通平面图G的结点数为5,边数为6,贝1|面数为 3 .10. 设个体域D = G d},则谓词公式（VA）MW A B（X））消去重词后的等值式为（乂（Q） A8（Z?））A（4 （。

）AB（/?）） .三、逻辑公式翻译（每小题6分，本题共12分）11. 将语句“今天有联欢活动，明天有文艺晚会翻译成命题公式.设户：今天有联欢活动，Q：明天有文艺晚会，（2分）PN Q.（6 分）12. 将语句“如果小王来，则小李去翻译成命题公式.设P：小王来，Q：小李去（2分）四、判断说明题(每小题7分，本题共14分)判断下列各题正误，并说明理由.13. 若偏序集<4, />的哈斯图如图一所示, 则集合4的最大元为。

极小元不存在.错误. (3分)对于集合/的任意元素x,均有<x.a>eR (或所以Q是集合/中的最大元.(5分)但按照极小元的定义，在集合/中b.c.d均是极小元. (7分)14. PA (Ji Q) V户为永假式.错误. (3分)-)PA (—1 Q) V户是由1 PA (Ji Q)与户组成的析取式，如果户的值为直，贝Ij-i PA Q) V户为直，(5分)如果户的值为假，贝f P与 f Q为直，即1 PA (f Q)为直，也即1 PA (—1 Q) VP为直，所以-I P!\ (—1 Q) VP是永直式. (7分)另种说明：-I PA (—1 Q) V户是由1 PN (J-I 6?)与户组成的析取式，只要其中一项为直，则整个公式为直. (5分)可以看到，不论户的值为直或为假，「PA (—■, Q)与户总有一个为直，所以1 PA (f 6?) V户是永直式.(7分) 或用等价演算1 PA (f Q) VST五.计算题(每小题12分，本题共36分)15. 设集合A={], 2, 3, 4), R={<x,y>\x, ye A; \x-y\=]或外尸0},试(】)写出舟的有序对表示；(2) 画出*的关系图；(3) 说明*满足自反性，不满足传递性.】5.⑴底{<】，1>,<2,2>,<3,3>,<4,4>,<】,2>,<2,1>,<2,3>,<3,2>,<3,4>,<4,3>} (3 分)(2)关系图如图二：⑶ 因为V 】,]＞,V 2,2＞,V 3,3＞,V 4,4＞均属于Q 即/的每个元素构成的有序对均在舟中，故舟在/上 是自反的.因有＜2,3＞与＜3,4＞属于但＜2.4＞不属于/?,所以在/上不是传递的.（12 分）16.设图 G=＜ E ＞,囹匕 峋，4，*，4 &｛（*，峋），（6 闭，（岭，*）,（4心），（*心）｝，（1） 画出G 的图形表示; （2） 写出其邻接矩阵； （3） 求出每个结点的度数;（3分）（2）邻接矩阵0 110 0'10 0 10（6分）0 10 0 1 0 0 1 1 0（3） deg （用二2 deg （玲）=2 deg （.）二2 deg （*）=2deg （咯）=2 （4）补图如图四（12 分）17. 求P —QNR 的合取范式与主析取范式. P- （RNQ ）户V （"Q ）=（f 户V Q ） A （n PMR ） （合取范式） Pf （"Q ）（9分）（4）画出图G 的补图的图形. 16. （1）关系图如图三:（9分）（4分）6 户V (A7\Q)=(「PA h QVQ) ) V (/?A Q\(7 分) <^>h 尸Q)V (-| 户AQ)V (/MQ) (8 分) =((i6?) A (-)/?VM)V (i PNQ'M'RNQ 、(9 分) =(「户 A"i Q何 V (-)户 A-| Q/\ 用 V (-| 户 AQ )V (舟/\Q)(10 分)<=>(n 户A"i Q 的V (-)尸 A~i Q A 的 V ((-| 户A 倒 A (-| rv 竹)V (舟 A 。

=(r 尸 A"i Q的 V (-)尸 A~iQ/\ 何V (-] P A ^?An 竹 V(-)P t\ Q f\ \ R N Q\PZ QA-i 何 V (-| QA 何 V (-| PN 6?A n 竹 Vh 户 A QA 竹 V (J P\! P\N (R\ Q))=h PNr QAr v(-| 户A-I QA 何 v(-| Pt\ 6?An VJ 户AQA 竹V "ARNO\(主析取范式)(12分)说明：此题解法步骤多样，若能按正确步骤求得结果，均可给分. 六、证明题（本题共8分）18. 设连通无向图G 有14条边，3个4度顶点，4个3度顶点，其它顶点的度数均小于3,试说明 G 中可能有的顶点数.证明：可利用数列可图化及握手定理解答 顶点度数和为2x14=28,（2分） 28- （3x4+4x3）=4,则知其他顶点度数和为4,（4分）对于有限图，若无零度顶点，则除4度及3度顶点外，可能的顶点情况有：2个2度点； 】个2度点和2个】度点； 4个1度点，（6分） 即对应图的顶点数分别至少为9、10、11.（8分）2011年7月一、单项选择题（每小题3分，本题共15分）1. A 2. C 3. C1. 若集合E,⑴,⑵,{】，2}},则下列表述正确的是（）. A. {2}eA B. {1, 2}uS C. 1 位/D. 2u/2. 设G 为无向图，则下列结论成立的是（）. 无向图G 的结点的度数等于边数的两倍. 无向图G 的结点的度数等于边数.无向图G 的结点的度数之和等于边数的两倍. 无向图G 的结点的度数之和等于边数. 图G 如图一所示，以下说法正确的是（ {（。

，切}是边割集 "。

{。

G 是点割集 {⑦是点割集 （（C 动}是边割集图_ 设集合/={】},则/的富集为（）. «!}） B. {1, {!}）4. D5. BA. B. c.D. 3. A. B. C. D. oe 4. A.c. (0, 1} D. {0, (!}}5 .设/(*): x是人，3(为：x犯错误，贝愉题“没有不犯错误的人” 可符号化为().A. n (3A)(/4(A)—•-| B(x))B. -| (3 A)(/4(A) A-] 8(x))C. i (3为(/(X)A8(A))D. (V A)(^(A)A5(A))二、埴空题(侮小题3分，本题共15分)6. 命题公式的直值是-7. 若无向图「是连通的，则，的结点数，与边数&满足关系井时,r是树.8. 无向图G是欧拉图的充分必要条件是.9. 设集合/={1, 2}上的关系胡={<2,2>,<1,2>},则在舟中仅需加入一个元素<1，1>就可使新得到的关系为自反的.】0. 为fRy)V5(z))中的约束变元有.三、逻辑公式翻译(每小题6分，本题共12分)11. 将语句“雪是黑色的翻译成命题公式.设尸雪是黑色的，(2分)则命题公式为：P.(6分)12. 将语句“如果明天下雨，则我们就在室内上体育课翻译成命题公式.设P-如果明天下雨，Q：我们在室内上体育课，(2分)则命题公式为：P—Q.(6分)四、判断说明题(每小题7分，本题共14分) 判断下列各题正误，并说明理由.】3.设集合A={], 2), B={3, 4),从/到8的关系为七{<],3>, <1,4>},则，是4到8的函数.错误. (3分)因为/中元素1有6中两个不同的元素与之对应，故，不是4到8的函数. (7分)】4.设G是一个连通平面图，有5个结点9条边，则G有6个面.正确. (3分)因G是一个连通平面图，满足欧拉定理，有，诳/=2,所以/=2-(”。

)二2- (5-9) =6(7 分)五.计算题(每小题12分，本题共36分)15. 试求出—(舟AQ)的合取范式・P— (/?A<9) 5 PN (A7\Q) (6 分)o(-|⑶竹A (iPVQ)(合取范式) (12分)16. 设/4=({1},(L2), 1),伊{1,2,{2}},试计算(1) (^0 5) (2) (4U8) (3) (4n8) I.(1) (/C18) ={1} (4 分)(2) (/U8)={1,2,{】},{2},{】，2}} (8 分)(3) (/n8) -Z =0 (12 分)17. 试画一棵带权为2, 3, 3, 4, 5,的最优二叉树，并计算该最优二叉树的权. 最优二叉树如图二所示.（10 分）图二权为 2x3+3x3+3x2+4x2+5x2=39 （12 分）六、证明题（本题共8分）18. 试证明：若与5是集合4上的对称关系，则/?ns 也是集合/上的对称关系.证明：设Vx, yeZ,因为/?对称，所以若<x,y>eR,贝\\<y,X>eR. （2分）因为S 对称，所以若<X y>eS,贝\\<y,X>eS. （4分） 于是若VX y>eRC\S 贝Ijvx y>eS即旦VR（6 分）也即VR A>e /?A 5,故ROS 是对称的・（8分）中央广播电视大学2010-2011学年度第一学期■开放本科”期末考试高散数学（本）试题2011年1月一、单项选择题（每小题3分，本题共15分）1. A 2. D 3. B 4. D 5. C1. A. C.2. A. 若集合4 = {。