离散数学210试卷.docVIP

考试科目名称　　 离散数学 　　　 考试方式：开卷　　闭卷　　　　考试日期　　　年　月　日　教师　　　　　 年级　　　　　学号　　　　　　　　姓名　　　　　　　　　成绩　　　　 题号 一 二 三 四 五 六 七 八 九 十 分数 得分 1、证明实数集不可数。 得分 2、某勘探队有3名队员，有一天取得一块样品，3人判断如下： 甲：这不是铁，也不是铜；乙：这不是铁，是锡；丙：这不是锡，是铁 经过实验室鉴定后，发现其中一个人的两个判断都正确，他是专家，一个人的判断一对一错，他是普通队员，一个人判断全错，他是实习生。 请确定样品种类并判断甲乙丙的身份。 得分 3、在字母m,a,t,h,i,s,f,u,n的排列中，存在多少不含样式”math”, ”is”, “fun”的排列？ 得分 设集合A＝{a,b,c,d},A上的关系R={a,b,b,a,b,c,c,d} 给出上述关系的相邻矩阵和关系图 （2）用作图法求R的自反和对称闭包 （2）用warshall算法求出R的传递闭包（要求有过程） 得分 5、设，。 （1）计算。 （2）p1是偶置换还是奇置换？ 得分 6、考虑1×n棋盘。假设用红、兰两种颜色为棋盘的每一个方格涂色。令hn是使得没有两个被涂为红色方格相邻的涂色方法数。求出hn所满足的递推关系，然后得出hn的通式。 得分 7、写出4个元素构成集合中的所有等价关系。 得分 8、下列算法的执行步骤数随着输入N的不同而变化。请给出描述该变化的函数f，给出该函数的θ类，并证明之。 得分 9、设L为一个有补分配格，证明：对于任意的L中元素a,b,下述四个条件是等价的：