离散数学模拟试题.pdf

第 1 页 共 10 页 西安电子科技大学西安电子科技大学 期末考试试题期末考试试题 课程名称 离散数学 考试形式 闭 卷 学习中心 考试时间 90 分钟 姓 名 学 号 一 填空题一 填空题 每空 2 分 合计 20 分 1 如果有限集合 A 有 n 个元素 则 2A 2 设 P 它占据空间 Q 它有质量 R 它不断运动 S 它叫做物质 命 题 占据空间的 有质量的而且不断运动的叫做物质 的符号化 为 3 某人有三个儿子 组成集合 A S1 S2 S3 在 A 上的兄弟关系具有 性质 4 公式 SQPQP 的对偶公式 为 5 设 K N 0 K 0 1 则 K N 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 SAB EB 第 7 页 共 10 页 西安电子科技大学西安电子科技大学 期末考试答题纸期末考试答题纸 课程名称 离散数学 考试形式 闭 卷 学习中心 考试时间 90 分钟 姓 名 学 号 题号题号 一一 二二 三三 四四 总分总分 题分题分 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 三 计 算 三 计 算 每题 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 原式 RPRQPRPRQP 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 mgmgbaba 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