南昌大学本科离散试卷及答案1

第 1 页 共 7 页 南昌大学南昌大学 2007 2008 学年第一学期期末考试试卷学年第一学期期末考试试卷 试卷编号 试卷编号 A 卷卷 课程编号 课程编号 课程名称 课程名称 离散数学离散数学 考试形式 考试形式 闭卷闭卷 适用班级 适用班级 姓名 姓名 学号 学号 班级 班级 学院 学院 专业 专业 考试日期 考试日期 题号题号一一二二三三四四五五六六七七八八九九十十总分总分 题分题分2080 100 累分人累分人 签签名名 得分得分 考生注意事项 1 本试卷共 5 页 请查看试卷中是否有缺页或破损 如有立即举手报告以便更 换 2 考试结束后 考生不得将试卷 答题纸和草稿纸带出考场 一 填空题 每题 4 分 共 20 分 得分得分评阅人评阅人 1 使得公式 p q r 成真的赋值是 使得公式 p q r 成假的赋值是 2 设个体域为 D 1 2 3 试消去公式 x P x y Q y 中 量词的等价式 3 4 个元素的集合共有 个不同的划分 并给出三个划分块的划分 4 设 A 1 2 求 A P A 5 无向树 T 有 8 片树叶 2 个 3 度分枝点 其余的分枝点都是 4 度结 点 问 T 有个 4 度分枝点 第 2 页 共 7 页 二 综合题 每小题 10 分 共 80 分 1 有向图 G 如图所示 写出 G 的邻接矩阵 2 求 G 中长度为 3 的路的总数 其中有多少条回路 3 求 G 的可达性矩阵 2 用等价演算证明 p q r p q r 3 求命题公式 p q p q 的主析取范式 并求命题公式的成真赋值 得分得分评阅评阅 人人 第 3 页 共 7 页 4 将下列命题符号化 并讨论它们的真值 1 有些实数是有理数 2 每个自然数都有比它大的自然数 5 证明 x F x G x x G x R x x R x x F x 第 4 页 共 7 页 6 设 A 1 2 3 4 A 上二元关系 R 定义为 R 1 2 2 1 2 3 3 4 求 R 的自反闭包 对称闭包和传递闭包 7 下面的 0 1 串集合 哪些是前缀码 做出前缀码对应的二叉树 1 01 10 11 000 111 2 01 11 000 0010 0011 第 5 页 共 7 页 8 某单位按编制有 7 个工作空缺 p1 p2 p7 有 10 个申请者 a1 a2 a10 它们能胜任的工作集合依次是 p1 p5 p6 p2 p6 p7 p3 p4 p1 p5 p6 p7 p3 p2 p3 p1 p3 p1 p5 如果规定每个申请者最多只能安排一 个工作 试给出一种方案使分配到工作的申请者最多 离散数学离散数学 A 卷答案卷答案 一填空题 1 成真的赋值是 000 001 010 011 101 110 111 成假的赋值是 100 2 x P x y Q y P 1 P 2 P 3 Q 1 Q 2 Q 3 3 1 2 3 4 1 3 2 4 1 4 2 3 2 3 1 4 2 4 1 3 3 4 1 2 1 1 1 4 6 3 1 15 种 1 4 C 2 4 C 2 4 2 1 C 4 1 1 1 1 2 1 1 2 2 2 1 2 2 2 1 2 5 T 有 2 个 4 度分枝点 二 综合题 1 解 MR 44 0000 1010 0001 0110 第 6 页 共 7 页 2 A2 A 3 44 0000 0001 0110 1011 44 0000 0110 1011 0111 长度为 3 的路有 8 条 其中回路 3 条 3 C3 A 0 A 1 A 2 A 3 P 44 1000 1221 1132 1233 1000 1111 1111 1111 2 p q r p q r 条件等价式 p q r 结合律 p q r 德 摩根律 p q r 3 p q p q p q p q p q 主析取范式 0 2 3 使得命题公式 p q p q 成真的赋值是 00 10 11 4 1 解 设 R x x 是实数 Q x x 是有理数 有些实数是有理数 符号化为 x R x Q x 它的真值为 真 2 设 N x x 是自然数 G x y x 比 y 大 每个自然数都有比它大的自然数 符号化为 x N x y N y G y x 它的真值为 真 5证明 x R x P R c US x G x R x P G c R c US G c T 拒取式 x F x G x P F c G c US F c T 析取三段论 x F x UG 6 r R 1 2 2 1 2 3 3 4 1 1 2 2 3 3 4 4 s R 1 2 2 1 2 3 3 4 3 2 4 3 R2 R R 1 1 1 3 2 2 2 4 R3 R2R 1 2 1 4 2 1 2 3 R4 R2R 1 1 1 3 2 2 2 4 R2 t R R R2 R3 R4 1 1 1 2 1 3 1 4 2 1 2 2 2 3 2 4 3 4 第 7 页 共 7 页 7解 01 10 11 000 111 不是 因 为 11 是111 的前缀 01 11 000 0010 0011 是前缀 码 8 解 按