201220132离散数学期末试卷.doc

诚信应考 考出水平 考出风格 浙江大学城市学院 2012 — 2013 学年第 二 学期期末考试试卷 《 离散数学 》 开课单位： 计算分院 ；考试形式：闭卷；考试时间：_2013_年_7_月_3_日； 所需时间： 120 分钟 题序 一 二 三 四 总 分 得分 评卷人 得分 一．单项选择题 (本大题共10题，每题2分，共20分。选择题答案请填到下面表格的相应栏中) 题号 1 2 3 4 5 6 7 8 9 10 答案 1．下面（ ）命题公式是重言式。 A． ； B． ； C． ； D．。 2．设A={{1，2，3}，{4，5}，{6，7，8}}，下列各式中（ ）是错的。 A．； B．{6，7，8}A； C．{{4，5}}A； D．{1，2，3}A 。 3．设L(x)：x是演员，J(x)：x是老师，A(x , y)：x钦佩y，命题“所有演员都钦佩某些老师”符号化为（ ）。 A．； B． ； C．； D． 。 4．设A={a, b, c, d }，则A上的二元关系有（ ）个。 A． 4 ； B． 16 ； C． ； D． 。 5．下列选项中，不属于关系性质名称的为 ( ) 。 A． 自反性 B． 反传递性 C． 反自反性 D． 反对称性 6．n个结点的无向完全图的边数为（ ）。 A．； B．； C．； D．。 7．对于集合A={x∣0x10}，下列哪种运算是封闭的（ ）。 A．+； B．—； C．∣x—y∣； D．×。 8．设S={0，1}，*为普通乘法，则 S , * 是（ ）。 A． 半群，但不是独异点； B．只是独异点，但不是群； C．群； D．以上都不对。 9．图 相对于完全图的补图为（ ）。 10．下列各图中，是欧拉图的为 ( )。 得分 二．填空题(本大题共20空，每空1分，共20分。) 1．公式的主析取范式为 。 2．若P，Q，为二命题，当且仅当 时真值为0 。 3．集合A={a,{b}}的幂集P(A) = 。 4．设，请在下列每对集合中填入适当的符号（）： （1） A , (2) A。 5．集合S={a, b, c, d}上的二元运算*如右侧运算表所示， * a b c a b c a b c b b c c c b 那么，代数系统S, *中的幺元是 。 有逆元的元素为 　　　 　 。是否有等幂元 　　　 ；是否满足交换性 　　　 　（填“是”或“否”）满足交换性。 6．设图G = V ，E 中有5个结点，各结点的度数分别为0，2，2，3，3，则G中有 　 条边。 7．有向图 中有没有平行边 。从v1到v4长度为3的通路有 条。 8．设树G有e条边，v个节点，那么e与v满足关系式 e= 。 9．图G是欧拉图的充要条件是 。 10．设图G = V，E ，的邻接矩阵，则A属于 （填“有向图”或“无向图”）。的入度= ，的度数= ，从到的长度为2的路有 条。 11. 给定集合A={1,2,3,4,5}，在集合A上定义两种关系：R={1,3,3,4,2,2}, S={4,2,2,5,3,1,1,3}，则，。 得分 三．计算题(本大题共6题，每题5分，共30分。) 1．求命题公式(P∨(Q∧R))((P∧Q∧R)的主析取范式和主合取范式。 设集合, A上的一个划分。试求由导出的上的等价关