哈工大 2007 年 秋季学期
集合论与图论 试题A 题号 分数 一 二 三 四 总分 班号 姓名 本试卷满分90分
(06级计算机、信息安全专业、实验学院)
一、判断对错(本题满分10分,每小题各1分) ( 正确画“√”,错误画“×”)
1.对每个集合A,{A}?2A。 (×) 2.对集合P,Q,若P?Q?Q,P?Q??,则P??。 (√) 3.设f:X?Y,A?X,若f(x)?f(A),则x?A。 (×) 4.设f:X?Y,B?Y,则有f(f?1(B))?B。 (×)
5.若R是集合X上的等价关系,则R2也是集合X上的等价关系。 (√) 6.若f:X?Y且f是满射,则只要X是可数的,那么Y至多可数的。(√) 7.设G是有10个顶点的无向图,对于G中任意两个不邻接的顶点u和v, 均有degu?degv?9,则G是哈密顿图。 (×) 8.设A?(aij)是p个顶点的无向图G的邻接矩阵,则对于G的顶点vi, 有degvi??aij成立。 (√)
j?1p9.设G是一个(p,q)图,若q?p?1,则?(G)?[2p/q]。 (×) 10.图G和G1同构当且仅当G和G1的顶点和边分别存在一一对应关系。(×)
第 1 页 （共 6 页）
试 题： 班号： 姓名：
二.填空(本题40分,每空各2分)
1.设S?{?,{?}},则2S? {?,{?},{{?}},{?,{?}}} 。
2.设A,B是任意集合,若A\\B?B,则A与B关系为 A?B?? 。 3.设X?{a,b,c},Y?{0,1},Z?{2,3};f:X?Y,f(a)?f(b)?0,f(c)?1, g:Y?Z,g(0)?2,g(1)?3,则g?f(a)，g?f(c)分别为 2,3 。
4.设X和Y是集合且X?m,Y?n,若m?n,则从X到Y的单射的 个数为 Cnmm! 。
5.设X?{1,2,?,n},B?{1,2},则从X到Y的满射的个数为 2n?2 。 6.设X?{1,2,3,4},R?{(1,2),(2,2),(3,4)},S?{(2,3),(3,1),(4,2)},则 R?(S?R)? {(1,4),(2,4),(3,2)} 。
?12345??12345??12345?7.设?1???32514??,?2???43215??,则?1?2???23541?? 。
??????8.设X?{a,b,c,d},R?{(a,b),(b,c),(c,a)},则
R??{(a,a),(b,b),(c,c),(a,b),(a,c),(b,c),(b,a),(c,a),(c,b)} 。 9.设X为集合且X?n,则X上不同的自反或对称的二元关系的个数 为 2n2?n?2n2?n2?2n2?n2 。
10.设X?{a,b,c,d},A?{{a,b},{c},{d}}是X的一个划分,则由A确定的
X上的等价关系为 {(a,a),(b,b),(a,b),(b,a),(c,c),(d,d)} 。 11.S?{1,2,?,10},在偏序关系“整除”下的极大元为 6,7,8,9,10 。 12.给出一个初等函数f(x),使得它是从(0,1)到实数集合R的一一对应,
这个函数为 ctg?x或-ctg?x或tg(?x??/2) 。 13.设G是(p,p)连通图,则G的生成树的个数至多为 p 。
第 2 页