2016离散复习练习题

08365f7161ef82547e2ed753111e60dd pdf 1 四 四 一 判断题一 判断题 每题 1 分 共 10 分 1 在命运题逻辑中 任何命题公式的主合取范式都是存在的 并且是惟一的 2 011 是公式的成真赋值 rqp 3 yGyxFxyyGxxF 4 xxGxxFxGxFx 5 三种重要的二元关系是等价关系 偏序关系和函数关系 它们的共同特点是都具 有自反性 6 设 F R 都是二元关系 则 F R 1 F 1 R 1 7 设 n 是任意一个正整数 则一定存在阶是 n 的群 8 布尔代数是有界格 也是分配格 9 无向完全图 n 2 一定是哈密顿图 n K 10 阶数至少是 2 树的每一条边都是桥 因而它的 边连通度是 1 二 空题二 空题 每小题 分 共 分 1 谓词公式x P x y tQ t z R x y t 中量词的辖域是 2 设 F x x 是人 H x y x 与 y 一样高 在一阶逻辑中 命题 人都不一样高 的符号化形式为 3 从公式分类角度来看 它为 式 qpqp 4 设 R 则 R 的对称闭包是 5 设 A B 是集合 BABABA那么 2 4 3 6 是模 6 加群 则它的生成元是 24 6 Z 7 整数加群是循环群 其生成元是 和 8 设是偏序集 如果 则称是 偏序 格 A A 08365f7161ef82547e2ed753111e60dd pdf 2 9 一棵二叉树先序遍历得 ABDECF 中序遍历得 DBEACF 则后序遍历的结果是 10 r 5 当 s 时 完全二部图才可能存在完美匹配 sr K 三 计算题三 计算题 1 4 题每题 8 分 5 6 题每题 10 分 共 52 分 1 R1 R2 求 1 R1 1 2 R1 R2 3 R22 4 t R1 传递闭包 2 设 G G 上的运算是矩 01 10 01 10 10 01 10 01 dcba 阵乘法 已知 G 构成群 1 指出个元素的阶 2 找出 G 的全部子群 3 在同构的意义下 G 是 4 阶循环群还是 Klein 四元群 3 1 在一棵有 2 个 2 度顶点 4 个 3 度顶点 其余顶点都是树叶的无向树中应该有 几片树叶 2 画出两棵非同构的满足上述条件的无向树 4 设为一个偏序集 其中 A 1 2 3 4 6 9 24 54 R 是 A 上的整除 关系 1 画出的哈斯图 2 求 A 的极大元和极小元 3 求 B 4 6 的上确界和下确界 5 求公式的主和取范式 化成 M1M2M3的形式 rqp 画一棵带权为 2 2 2 3 3 4 5 8 的最优二叉树 T 并计算它的权 W T 四 四 证明题 每小题 6 分 共 18 分 1 前提 srqrqp 结论 sqp 2 定理定理 子群判别法 1 设 H 是群的非空子集 则 HG 当且仅当 1 a b H a b H 08365f7161ef82547e2ed753111e60dd pdf 3 2 a H a 1 H 利用上述定理证明 设 H 是群的非空有限子集 若 H 关于 封闭 则 H 是 G 的子群 3 用数学归纳法证明 n 阶无向树 T 有 n 1 边 五 一 选择题 每小题一 选择题 每小题 2 2 分 共分 共 2020 分 请将答案填在下面的表格内 分 请将答案填在下面的表格内 1 从集合分类的角度看 命题公式可分为 A 永真式 矛盾式 B 永真式 可满足式 矛盾式 C 可满足式 矛盾式 D 永真式 可满足式 2 设 B 不含有 x 等值于 BxAx A B C D BxxA BxAx BxxA BxAx 3 设 S T M 是集合 下列结论正确的是 A 如果 S T S M 则 T M B 如果 S T 则 S T C D SSS TSTS 4 设 R 是集合 A 上的偏序关系 则 R 不一定是 A 自反的 B 对称的 C 反对称的 D 传递的 5 设 R 为实数集 定义 R 上 4 个二元运算 不满足结合律的是 A f1 x y x y B f2 x y x y C f3 x y xy D f4 x y max x y 6 设是一个格 则它不满足 A 交换律 B 结合律 C 吸收律 D 消去律 7 设 A 1 2 则群的单位元和零元是 AP A 与 A B A 与 C 1 与 D 1 与 A 8 下列编码是前缀码的是 A 1 11 101 B 1 001 0011 C 1 01 001 000 D 0 00 000 9 下图中既是欧拉图又是哈密顿图的是 08365f7161ef82547e2ed753111e60dd pdf 4 A B C D 9 K 10 K 3 2 K 3 3 K 10 下图所示的二叉树中序遍历的结果是 a a b b c c d de e A abcde B edcba C bdeca D badce 二 填空题 每题二 填空题 每题 3 3 分 共分 共 2424 分 分 1 含 3 个命题变项的命题公式的主合取范式为 76430 MMMMM 则它的主析取范式为 的形势表示成mm 2 模 4 加群 则 3 是 阶元 33 3 的逆元是 4 Z 3 设 V 其中 是普通加法 令 1 x x 2 x x 3 x x 5 Zx 4 x 2x 其中有 个自同构 4 设是集合 A 1 2 3 4 5 6 上的一个置换 则把它表 645132 654321 示成不相交的轮换的积是 4 已知 n 阶无向简单图 G 有 m 条边 则 G 的补图有 条边 5 一个有向图是强连通强连通的充分必要条件是 7 已知 n 阶无向图 G 中有 m 条边 各顶点的度数均为 3 又已知 2n 3 m 则 m 8 在下图中从 A 点开始 用普里姆算法构造最小生成树 加入生成树的第三条边 是 A B C D E 1 2 3 4 5 6 78 三 计算题 每题三 计算题 每题 9 9 分 共分 共 3636 分 分 08365f7161ef82547e2ed753111e60dd pdf 5 1 已知命题公式 pqqp 1 构造真值表 2 求主析取范式 要求通过等值演算推出 2 R1 R2 求 1 求 21 RR 1 1 R 12 RR 设为一个偏序集 其中 A 1 2 3 4 6 9 12 24 R 是 A 上的整除关系 1 画 R 出的哈斯图 2 求 A 的极大元和极小元 3 求 B 4 6 的上确界和下确界 画一棵带权为 1 1 1 3 3 5 8 的最优二叉树 T 并计算它的权 W T 四 证明题 共四 证明题 共 2020 分 分 1 7 分 前提 rpqsqp 结论 sr 2 7 分 A 0 0 0 1 1 0 1 3 2 2 2 3 3 1 R a b c d A 且 a b c d 1 证明 R 是 A 上的等价关系 2 给出 R 确定的对 A 的划分 分类 3 6 分 设是群 G xyyxGyGxxS 且对于 证明 S 是 G 的子群 六 六 一 选择题 一 选择题 每小题 2 分 共 20 分 1 一个命题公式或一阶逻辑公式的 是不惟一的 A 主析取范式 B 主合取范式 C 前束范式 D 对偶式 2 下列四个公式正确的是 xxBxxAxBxAx xxBxxAxBxAx xxBxxAxBxAx xBxAxxxBxxA 得分阅卷人 08365f7161ef82547e2ed753111e60dd pdf 6 A B C D 3 设集合 A a b c d e 偏序关系 R 的哈斯图下图所示 则元素的关系不正 确的是 a b c d e f g A B C D dc ea ca ed 4 已知 A B 是集合 A 15 B 10 A B 20 则 A B A 10 B 5 C 20 D 13 5 X a b c d e Y 1 2 3 4 f 从 X 到 Y 的映射 其中 f a 2 f b 4 f c 1 f d 3 f e 4 则 f 是 A 双射 B 满射 C 单射 D 不是单射也不是满射 6 设 A B C 是三个非空集合 则 是正确的 A B CBCABA CBCABA C D CBCABA CBCABA 7 在下图所示的哈斯图中的偏序集不是格的是 8 下图中 是欧拉图 A B C D 9 关于无向树的描述 不正确的是 A 无向树是连通图 没有回路 每个边都是桥 08365f7161ef82547e2ed753111e60dd pdf 7 B 无向树是连通图 边数比顶点数少 任意两个顶点的路径是惟一的 C 无向树是连通图 没有回路 每个顶点都是割点 D 无向树是连通图 没有回路 每条边都是割边 10 关于含有 n 片树叶的最优二叉树描述 不正确的是 A 含有 n 片树叶的最优二叉树每个分支点都有两个孩子 B 含有 n 片树叶的最优二叉树分支点的个数是 n 1 C W T 等于个分支点的权重 构造最优二叉树时产生 之和 D 在权重一定的前提下 含有 n 片树叶的最优二叉树是惟一的 二 计算题 二 计算题 每小题 10 分 共 40 分 1 1 求的主析取范式 prqp 2 根据主析取范式直接写出主合取范式 3 根据主析取范式直接写出真值表 2 设集合 A a b c d A 上的关系 R 求 1 画出 R 的关系图 2 求出 R 的传递闭包 tr R 3 tr R 中再添加一些元素后得 D R 若使 D R 是等价关系 则 tr R 中再添 哪些元素后得 D R 3 1 下图的最下生成树 2 求该图的点连通度和边连通度 3 求 A 到 B 的最短路径的长度 A B 4 10 分 对于下有向图 1 写出度序列和出度序列 2 写出邻接矩阵 A 第一行元素之和的含义是什么 3 求 据此说明从 A 到 A 的长度为 4 的回路用多少 4 A 08365f7161ef82547e2ed753111e60dd pdf 8 A B C D 三 证明题 1 设 A 是正整数集合 在上定义