电大离散数学14-17试题.pdf

试卷代号:1009 座位号C口 中央广播电视大学2013一2014学年度第一学期“开放本科“期未考试(半开卷) 离散数学(本)试题 2014年1月 !题号|一|二|三|四|五|六|总分| |分数IIIIIIII l得分|评卷人| III一、单项选择题每小题3分，本题共15分 1.若集合A=a，b，c，则下列表述正确的是(). A.aAB.aCA C.0AD.a，b，cA 2.设A =1,2,B=1，2，3，4，时，A到B的关系R=(x，YlxA，y B，x+1=y，则 R=(). A., B., c., D., 3.元向图G的边数为12，贝tl图G的结点的度数之和是(). A.24 C.6 B.12 D.18 4.设连通平面图G有U个结点，e条边，r个面，则(). A.v十e-r=2 C.v+e-r=4 B.r+v-e=2 D.v+e-r=-4 5.设个体域D是整数集合，则命题Vx3y(x o y=y)的真值是(). A.不确定B.F CTn以上说法都不是 65 得分|评卷人 二、填空题每小题3分，本题共15分 6.设集合A=l，2，3，B=3， 4，时，c=5,6,7，则AUB一C等于 7.设A=I，2，B=怡，b，C=3，4，时，从A到B的函数f吉，从B 到C的函数g=，则Ran(gOf)等于 8.若图G=，其中V=a ,b,c,d ,E =(a，的，(a ，d)，(b，c)，(b，d)，则该图中的 割边为 9.设G是欧拉图，则G的奇数度数的结点数为一一一一一个. 10.设个体 域D=2，4，6，A(x)为“x是偶数“，则谓词 公式(Vx)A(x)的真值 为 |得分|评卷人| III 三、逻辑公式翻译每小题6分，本题共12分 11.将语句“我学英语，并且学法语“翻译成命题公式. 12.将语句“除非小王来，否则小李不去“翻译成命题公式. |得分|评卷人| III 四、判断说明题每小题7分，本题共14分 判断下列各题正误，并说明理由. 13.空集白的事集也是空集. 14.(丑 x)(P(x)Q(y)AR(z中的约束变元为y. |得分|评卷人| III 五、计算题每小题12分，本题共36分 15.设集合A=l,2, 3,R =,5=,试 计算z (l)R 5;(2)R-1;(3)r(R). 66 16.图G=，其中V=怡，b，c，d,E=(a,b),(a,c),(a,d),(b,c),(c，d)，对应 边的权值依次为6、5、2、3及8，试E (1)画出G的图形s (2)写出G的邻接矩阵z (3)求出G权最小的生成树及其权值. 17.试画一棵带权为1，2，3，3 ，4的最优二叉树，并计算该最优二叉树的权. |得分|评卷人| III 六、证明题本题共8分 18.试证明:PQP(PAQ). 67 试卷代号:1009 中央广播电视大学2013一2014学年度第一学期“开放本科“期末考试半开卷) 离散数学(本)试题答案及评分标准 (供参考 2014年1月 一、单项选择题每小题3分，本题共15分) l.B2.D3.A4.B5. C 二、填空题每小题3分，本题共15分 6.1,2 ,3,4 7. 3,4 8. (h,c) 9.0 10.真(或T，或1) 三、逻辑公式翻译每小题6分，本题共12分 1 1.设P:我学英语，也我学法语. 则命题公式为:PIQ. 12.设P:小王来，Q:小李去. 则命题公式为:QP. 或-，P-，Q 四、判断说明题每小题7分，本题共14分 13.错误. 空集的事集为臼. 14.错误. (丑x)(P(x)Q(y)八R(x中的约束变元为x. 五、计算题每小题12分，本题共36分 15.(1)R S=,; 68 (2分 (6分) (2分) (6分 3分 (7分 (3分 (7分 (4分 (2)R- 1= , I (3)r(R)=, (8分) (12分 16.(l)G的图形表示如团一所示z d8c 吨，由.、-句 3 田、 aJ E G6b (3分 图一 (2)邻接矩阵z b111 1010 1101 1010 (6分 (3)图二中的粗线与结点表示的是最小生成树z d8c -、-二 2-3 图 .、气 dE aUAU (10分) 权值为10 17.最优二叉树如图三所示z (1 2分 13 (10分 2图三 (二叉树树叶权值顺序不同，参照给分 权为1X3十2X3+3X2+3X2+4X2=29(12分) 69 六、证明题本题共8分 18.证明z (l)PQ (2)P (3)Q (4)PAQ (5)P(P AQ) 另证E 设P(P八Q)为 F， 则P为T，PAQ为F. 所以P为T，Q为F， 从而P-Q也为F. 所以PQ=争P(P八Q). P P(附加前提 T(l)(2)l T(2)(3)l CP规则 (l分 (3分 (5分 (7分 (8分 (l分 (3分 (5分 (7分 (8分 说明:1.因证明过程中，公式引用的次序可以不同，一般引用前提正确得1分，利用两个公 式得出有效结论得1或2分，最后得出结论得2或1分. 2.可以用真值表验证. 70 试卷代号:1009座位号CD 国家开放大学(中央广播电视大学)2014年春季学期“开放本科“期末考试 离散数学(本)试题半开卷) 2014年7月 |题号|一|二|三|四|五|六|总分| l分数IIIIIIII |得分|评卷人| 择题(每小题3分，本题共15分) III 1.若集合A =怡，b，c，d，则下列表述正确的是(). A.aAR任A C.a,b,cC AD.a,b,c,dA 2.设A=2,B = 3,4,5，A到B的关系R=怡，y!x A，yB，x=y十1，则R=(). A.0B., C.D., 3.无向图G是个棵树，边数为12，则G的结点数是(). A.12B.24 C.llD.13 4.下 面的推理正确的是( A.(1)(丑x)(A(x)B(x前提引人 (2)A(y)B(y)ES(1). B.0)( 3x)A(x)职工)前提引人 (2)A(y)B(y)US(1 ) . c.(1)(Vx)A(x)B(x) 前提引人 (2)A(y)B(y)US(l) . D.(1)(V x)(A (x )B (x 前提引人 (2)A(y)B(x)ES(). 52 5.设A(x):x是人，B(x):x是学生，则命题“不是所有人都是学生“可符号化为(). A.-,(3x)(A(x)八B(x B.-,(“Ix )(A(x)B(x c.-,(3x)(A(x)八-，B(x D. (Vx)(A(x)1B(x |得分|评卷人| III 二、填空题每小题3分，本题共15分) 6.设集合A=l,2, 3, B = 3,4,5,C=2，3 ，4，5，则BU(A-C)等 于 7.设A=I,2，B=怡，剖，C=3，4，从A到B的函数j=，从B到 C的函数g=，则Dom(gOJ)等于 8.两个图同构的必要条件是 9.设G是连通平面图，v，e，r分别表示G的结点数，边数和面数，则v，e和r满足的关系 式 10.设 个体域D=l，2，3，则谓词公式(“Ix)A(x)消去量词后的等值式 为 三、逻辑公式翻译(每小题6分，本题共12分 11.将语句“3大于2或1加1等于2“翻译成命题公式. 12.将语句“如果明天下雪，我们就去旅游“翻译成命题公式. |得分|评卷人| III 四、判断说明题每小题7分，本题共14分 判断下列各题正误，并说明理由. 13.若图G中存在汉密尔路，则图G是一个汉密尔顿图. 14.无向图G是树当且仅当元向图G是连通图. 53 |得分|评卷人| III 五、计算题每小题12分，本题共36分 15.设A=l,2,3,4,5,R=IxA，yA且x-y=3;i,s = IxA， yEA且x+y=3，试求R，S，RS，R寸，r(剖，s(R). 16.设有如图一所示的有向图G=， 图一 数 条 径 路 的 句U 为 度 长 的 U 到 U 中 G 求 A幻ill-u 懈 4301 接2100 附 320O G= 出A 求知 试已 咱i句L (3)求G中VI的长度为3的回路条数. 17.求(PVQ)R的析取范式与主合取范式. |得分|评卷人| III 六、证明题本题共8分) 18.设A，B，C均为任意集合，试证明:A一(BUC)=(A-B)-C. 54 试卷代号:1009 国家开放大学(中央广播电视大学)2014年春季学期“开放本科“期未考试 离散数学(本)试题答案及评分标准(半开卷) (供参考) 2014年7月 一、单项选择题(每小题3分，本题共15分 I.e2.A3. D4.A5. B 二、填空题(每小题3分，本题共15分) 6.l.3.4.5 7.1.2或A 8.结点数相等;边数相等;度数相同的结点数相等 9.v-e+r=2 10.A(l)八A(2) 八A(3) 三、逻辑公式翻译(每小题6分，本题共12分) 11.设P:3大于2.Q:l加1等于2. 则命题公式为:PVQ. 12.设p.明天下雪.Q:我们就去旅游. 则命题公式为:PQ. 四、判断说明题(每小题7分，本题共14分 13.错误. 反例:如图二中存在汉密尔路，但图G不是一个汉密尔顿图. o0 图二 (或:按定义有:若图G中存在汉密尔回路，则图G是一个汉密尔顿图.) 说明:举出符合条件的反例均给分. (2分) (6分) (2分 (6分) (3分) (7分) 55 14.错误. 反例:如图三为连通图，但不是树. / 图三 或z按定义有:无向图G是树当且仅当元向图G是元回路的连通图.) 说明:举出符合条件的反例均给分. 五、计算题每小题12分，本题共36分) 15.R=, S=, RS=, R- 1=, r(S)=, , s(R)=, . 说明:对于每一个求解项，如果基本求出了解，可以给对应1分. 1110 1010 16.G的邻接矩阵为:A= 0001 o010 (3分) (7分 (2分) (4分 (6分) (8分) (10分) (12分) (4分) (2分) (5分) (7分) (9分) (2)由A 3 中a u可知，G中VI到叭的长度为3的路径有2条;(8分) (3)由A 3 中all可知，G中VI的长度为3的回路有3条;(1 2分) 说明:如果没有求出矩阵乘积，而通过列举找出正确的路与回路数，也给相应分数. 17.(PVQ)R 。-，(PVQ)VR 。(-，P八-，Q)VR析取范式 (-，PVR)A(-,QVR) 。(-，PVR)V (Q A-，Q)八(-，QVR) 56 。(-，PVR)V(Q1-，Q)八(-，QVR)V(P八-，P) 。(-，PVRVQ)八(-，PVR V-，Q)八(-，QVR VP)1(-,Q VR V-,P) 。(PV-,Q VR)八(-，PVQVR)八(-，PV-，QVR)主合取范式 六、证明题(本题共8分 18.证明: 设S= A一，V=Vj巧，V3，叫，V5 , E = ( Vj川2) , (Vj , V3 ) , (V, Vs ) , (屿，V3), (V2，V4)，(V2，V5)(町，V4), ( V3 , Vs ) , (V4 ,V5 ) ，试; (1)画出G的图形表示; (2)写出其邻接矩阵; (3)求出每个结点的度数; . (4)画出图G的补图的图形. 17.求P(Q八R)的合取范式与主合取范式. 六、证明题本题共8分 18.对任意集合A，B和C，若有C手，则有:ACB的充分必要条件是CXACCXB. 82 试卷代号:1009 国家开放大学(中央广播电视大学)2014年秋季学期“开放本科“期末考试 离散数学(本)试题答案及评分标准(半开卷) (供参考) 一、单项选择题(每小题3分，本题共15分) l.D 2.D 3. A 二、填空题每小题3分，本题共15分 6.27 7.偶数 8.6 9. 7 10. (P(1)八P(2)V (Q(1) VQ(2) 三、逻辑公式翻译每小题6分，本题共12分 4.C 11.设P:小张可以完成这项工作，Q:小李可以完成这项工作. 则命题公式为:P八Q. 12.设P:a是偶数，Q:能被2整除. 则命题公式为:p.-Q. 四、判断说明题每小题7分，本题共14分) 5. B 2015年1月 (2分 (6分) (2分) (6分 13.正确(3分) 例:设A=叫，B=忡，a(5分 则有AB且ACB.(7分) 说明:举出符合条件的例均给分. 14.错误(3分) 完全图Ks是有5个结点10条边，因3X5-6 , , , , , , , 83 , , , , , , ,. (3分 (2)R中的每个有序对的第一个元素都可以整除第二个元素，即R为整除关系.每个数可 以整除自身，则关系R是自反的; 由R的元素可看出，若z手y，当存在R，就有f!:R，则说明关系R是反 对称的; 由R的元素可看出，若存在ER，R，就有仨R，则说明关系R 是传递的. 84 所以A上的整除关系R为偏序关系. (说明:只要指出了R的自反性、反对称、传递性，即可给分) (3)关系R的哈斯图如图一所示: 24 36 3 2 图一 (4)集合B的最大元素12、极大元素12、上确界为12 16. (1)