离散数学模拟试题一

1、第 1 页 （共 10 页） 西安电子科技大学西安电子科技大学 期末考试试题期末考试试题 课程名称：_离散数学 考试形式： 闭 卷 学习中心：_ 考试时间： 90 分钟 姓 名：_ 学 号： 一 填空题一 填空题（每空 2 分，合计 20 分） 1.如果有限集合 A 有 n 个元素，则|2A|= 。 2.设 P：它占据空间，Q：它有质量，R：它不断运动，S：它叫做物质。命 题“占据空间的，有质量的而且不断运动的叫做物质”的符号化 为 。 3.某人有三个儿子，组成集合 A=S1,S2,S3，在 A 上的兄弟关系具有 性质。 4.公式)()(SQPQP的对偶公式 为 。 5. 设 KN= 0 ，K

2、(0,1)= ，则 KN(0,1)= 。 6.设,cbaX =，X 上的关系 R 的关系矩阵是 = 111 011 101 R M，则 = RR M o 。 7.若BAf:是函数， 则当 f是BA 的 ，ABf c : 是 f 的逆函数。 8.若连通平面图 =+,R的自 同构映射。 第 6 页 （共 10 页） 2. 用CP规 则 证 明)(CBA，CFE)(， )(SABEB 。 第 7 页 （共 10 页） 西安电子科技大学西安电子科技大学 期末考试答题纸期末考试答题纸 课程名称：_离散数学 考试形式： 闭 卷 学习中心：_ 考试时间： 90 分钟 姓 名：_ 学 号： 题号题号 一一 二

3、二 三三 四四 总分总分 题分题分 20 20 40 20 得分得分 一 填空题一 填空题（每空 2 分，合计 20 分） 1 2n 2 RQPS 3 反 自 反 性、对称 性、传递 性 4 ()(SQPQP 5 6 111 111 111 7 双射 8 2=+rev 9 )()(RQPRQP； 001000 MM 二 选 择二 选 择（每题 2 分，合计 20 分，在正确答案上划） 1 A C D 2 A B C 3 A C D 4 A B D 5 A B C 6 A C D 第 8 页 （共 10 页） 7 A B C 8 A C D 9 A B C 10 A B D 三 计 算（三 计

4、算（每题 8 分 合计 40 分） 1 3，4，5：上界：1，3；上确界：3；下界：无；下确界：无； 1，2，3：上界：1；上确界：1；下界：4；下确界：4。 2. 3. 用 Kruskal 算法，选一条权最小的边，逐一选取剩余的边中与已知边未 构成回路且权数最小的边 ),( 21 vv ， 每次选出的边记入T,其权加入T的成本。 T 的边 T 的成本 ),( 21 vv 2 ),( 83 vv 2+2 ),( 74 vv 2+2+2 ),( 65 vv 2+2+2+2 ),( 76 vv 2+2+2+2+3 ),( 41 vv 2+2+2+2+3+3 4. 原式)()()()(RPRQPRP

5、RQP )()(RPRQP。 5. 第 9 页 （共 10 页） = 0001 1011 1100 0100 A ， = 0100 1201 1012 1011 2 A ， = 1011 2123 1301 1201 3 A ， = 1201 3513 3134 2123 4 A，由 3 v到 1 v长度为 4 的有向路径的条数为 3 条。 四 证明题四 证明题（每题 10 分 合计 20 分） 1. g是 上 的 同 态 映 射)2( 111 bam+=， Rbam+=)2( 222 )()()2()2( 2)()()2)()()22()( 212211 21212121221121 mgm

6、gbaba bbaabbaagbabagmmg +=+= +=+=+=+ g是上的满射Rbam+=)2( ，Rbam=2 使 mbababagmg=+=22)()2()(所以 g 是上的 满射。 g是上的单射)2( 111 bam+= ，Rbam+=)2( 222 ， 且 21 mm 则2)(,2)( 222111 bamgbamg=， 如 果 )()( 21 mgmg= 则 21212121 ,02)()(bbaabbaa=必有 这 与 21 mm 矛盾。 故 )()( 21 mgmg。 由，知 g 是从到的自同 构映射。 第 10 页 （共 10 页） 2. （1） B P(附加前提) （2） )(SAB P (3) SA T(1)(2)I (4) A T(3)I (5) CBA P