2012～2013学年第一学期__离散数学__A卷_(2).docx

上海第二工业大学（试卷编号：）20122013学年第一学期离散数学A卷姓名：学号：班级：成绩：一、判断题（每小题2分，本题共10分） 1、若，则。( 错 )2、设和是集合上的等价关系，则是A上的等价关系( 对 )3、若函数，则若与的复合是双射，则函数是双射。( 错 )4、在有界格中，必有最大元和最小元。( 对 )5、存在13个结点，并且每个结点的度均为3的图。( 错 )二、填空题(每空2分，本题30分)1、设集合，则=_空，a_，=_(a,a),(b,a),(a,b),(b,b_。2、若，则上共有_11_个不同的自反关系。3、假设，和是上的关系，则=_(0,0),(1,1)_；=_(2,2),(3,3)；关系的自反闭包是：_(0,0),(1,1),(2,2),(3,3),(0,2),(1,3)_；关系的对称闭包是：_(1,3),(3,1),(2,0),(0,2)_。4、命题：“小李喜欢跳舞”，命题：“小李不喜欢唱歌”，则复合命题表示：_小李不喜欢跳舞且不喜欢唱歌_。5、设集合，则有_16_个序偶，到有_256_个关系，其中有_24_个是双射函数。6、简单图各结点的度总和为12，则此图共有_6_条边。7、已知集合,是集合的幂集上的包含关系，则偏序集是一个格，则集合和集合的最小上界是_1，2,3,4,5,8_，最大下界是_1_。8、与是常元命题，则命题的真值是_1_。（填0或1）三、选择题(每空3分，本题15分)1、是整数集，则关系是集合上的( A )A 等价关系 B 对称关系 C偏序关系 D传递关系2、给定函数，则下列结论中正确的是：( B )A 是上的双射函数 B 是上入射函数，但不是满射函数C是上既非入射也非满射函数D 是上的满射函数，但不是入射函数3、下列命题中，真值是真的命题是：( C )A有最大元的格是有界格；B有界格一定是有限格；C格一定是偏序集；D 偏序集一定是格。4、一个有12个顶点的完全图共有( B )边。A 65条 B 66条 C 67条 D 68条5、简单图有6个结点，其中4个点的度均为3，其余2个点的度为2，则该图的补图的边数是：( C )。A 5 B 6 C 7 D 8四解答题（本题32分）1、(8分)设集合，上的关系的关系矩阵则(1)写出关系，结果用序偶表示；(2) 求出关系的定义域和值域；(3) 求出关系的逆关系；(4) 求关系的自反闭包和对称闭包。(1)R=(a,c),(b,a),(b,c),(d,a),(dd)(2)定义域：a,b,d值域：a,c,d（3） （c,a）,(a,b),(c,b),(d,d)(4)(a,a),(b,b),(c,c),(a,c),(b,a),(b,c),(d,a),(dd)自反闭包对称闭包：（a,c）,(c,a),(b,a),(a,b),(d,a),(a,d),(d,d)2、(6分)设集合，是上的整除关系，(1) 画出偏序集的次序图；(2) 判断偏序集是不是格？并说明理由。(1) 32 16 128 64 2 3 1(2)不是格！32和12没有最大元3、(3分)列出公式的真值表。PQPPQPQ00110010110111100101111000014、(9分)1、利用Kruskal算法求出下列带权图的最小生成树，并写出最小生成树的权。2、判断该图是不是欧拉图？3、判断该图是不是汉密尔顿图？(1)(2)不是（3）是汉密尔顿图5、(6分)写出下列有向图的邻接矩阵，并写出所有点的出度与入度矩阵U1U2U3U4U5U100010U210011U301001U401000U500010每一个点的入度于出度点数出度入度U111U232U320U413U512五证明题(本题共13分)1、(6分)证明PQPQ