资源描述：
《离散数学-期末考试卷-A卷.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、东莞理工学院城市学院（本科）试卷（A卷）2013-2014学年第一学期开课单位：计算机与信息科学系，考试形式：闭卷，允许带入场科目：离散数学，班级：软工本2012-1、2、3姓名：学号：题序一二三四总分得分A评卷人一、单项选择题（每小题2分，共20分）在每小题列出的四个备选项中只有一个是符合题目要求的，错选、多选或未选均无分。1.下述不是命题的是()A.做人真难啊!B.后天是阴天。C.2是偶数。D.地球是方的。2.命题公式P→(P∨Q∨R)是()A.永假的B.永真的C.可满足的D.析取范式3.命题公式﹁B→﹁A等价于()A.﹁A∨﹁BB.﹁(A∨B)C.﹁A∧
2、﹁BD.A→B4．设P：他聪明，Q：他用功，命题“他虽聪明但不用功”的符号化正确的是（ ）A．P∧QB．P∧QC．P→QD．P∨Q5．设A（x）:x是人，B（x）：x犯错误，命题“没有不犯错误的人”符号化为（ ）A．x(A(x))∧B(x)B．x(A(x)→B(x))C．x(A(x)∧B(X))D．x(A(x)∧B(x))6.设有A={a,b,c}上的关系R={,,,}，则R具有()A.自反性B.反自反性C.传递性D.反对称性7.设A={1,2,3,4,5,6},B={a,b,c,d,e}，以下哪一个关系是从A到
3、B的满射函数()A.f={<1,a>,<2,b>,<3,c>,<4,d>,<5,e>}B.f={<1,e>,<2,d>,<3,c>,<4,b>,<5,a>,<6,e>}C.f={<1,a>,<2,b>,<3,c>,<4,a>,<5,b>,<6,c>}D.f={<1,a>,<2,b>,<3,c>,<4,d>,<5,e>,<1,b>}8．设简单图G所有结点的度数之和为10，则G一定有（ ）A．3条边B．4条边C．5条边D．6条边9．下列不一定是树的是（ ）A．每对结点之间都有通路的图B．有n个结点，n-1条边的连通图C．无回路的连通图D．连通但删去一条边则
4、不连通的图10．下列各图中既是欧拉图，又是哈密顿图的是（ ）ABCD二、填空题（每空2分，共20分）请在每小题的空格中填上正确答案。错填、不填均无分。1、设A={1,2,3,4}，B={2,3,5}，则A-B=_______________，AB=________________。2、设A={(1,2),(2,4),(3,3)},B={(1,3),(2,4),(4,2)},那么dom(A∪B)=___________________,ran(A∩B)=__________________（说明：dom指R的定义域，ran指R的值域）。3、设A={1，2，3
5、，4}上关系R={(1,2),(2,4),(3,3),(1,3)}，则R的自反闭包r(R)=_____________________________________________________，对称闭包s(R)=________________________________________________________。4、设f:R→R,f(x)=x2-2,g:R→R,g(x)=x-1,那么复合函数=__________，=__________。5、设A={a,b,c}，则A的幂集P(A)=。6、设A={a,b,c}，R是A上的二元关系R={(a,b
6、),(b,c),(c,a)}，则其传递闭包为t(R)=。三、计算题（每小题8分，共48分）要求写出详细计算过程，按步给分。1、求(﹁P∨Q)→(R∧﹁Q)的主析取范式和主合取范式。2、已知集合A={1,2,3,4,5,6,8,12,18,21,24,36}，R是A上的整除关系，求R的哈斯图。3、设A={1，2，3，4}，R是A上的二元关系，R={(1,1),(1,2),(2,3),(3,2)(3,3),(4,1),(4,2),(4,3)}。（1）画出R的关系图；（2）写出R的关系矩阵；（3）说明R是否具有自反、反自反、对称、反对称、传递性质，并给出理由。4、求
7、出下图的最小生成树并计算该树的权（要求画出最小生成树的形成过程）。5、已知一算式的树(如图)，试分别写出前序周游算法、中序周游算法和后序周游算法的算式。6、画出树叶权为3,5,8,10,12,15,18,22的哈夫曼树，计算出该最优树的权，并给出哈夫曼编码。四、证明题（共12分）用命题逻辑推理方法证明下面推理的有效性：如果体育馆有球赛，青年大街交通就拥挤。在青年大街交通拥挤情况下，如果小王不提前出发，就会迟到。因此，小王没有提前出发也未迟到，则体育馆没有球赛。
