离散数学-2006`2007(2)-试卷A.pdf

密 密 第 1 页 共 4 页 西南科技大学 2006 2007 学年第 2 学期 西南科技大学 2006 2007 学年第 2 学期 离散数学 J 期末考试试卷 A 卷 学院 离散数学 J 期末考试试卷 A 卷 学院 班级班级 姓名姓名 学号学号 一 下列图能否不重复画同一条边 一笔画完 如果能 请列出顶点顺序 给 出一种画法 不能 请说明原因 6 分 1 2 二 下列图是否存在哈密尔顿回路 若存在 请列出顶点顺序 给出一条哈密 尔顿回路 若不存 在请说明原因 6 分 1 2 三 请在下图上 作出其对应的对偶图 4 分 课程代码 1 43 1 4 0 320命题单位 计算机科学与技术学院 软件教研室 课程代码 1 43 1 4 0 320命题单位 计算机科学与技术学院 软件教研室 密 密 第 2 页 共 4 页 西南科技大学 2006 2007 学年第 2 学期 西南科技大学 2006 2007 学年第 2 学期 离散数学 J 期末考试试卷 A 卷 离散数学 J 期末考试试卷 A 卷 四 无向图 G 有 2l 条边 12 个 3 度数结点 其余结点的度数均为 2 求 G 的 顶点数 n 4 分 五 画出带权 3 4 5 6 12 的最优二元树 T 并计算权值 W T 5 分 六 给出下图所示二元树的前序 中序 后序遍历结果 9 分 七 用真值表判断命题公式 P Q P R 和 P Q R 是否等值 10 分 八 设集合 A 2 5 B 2 3 9 设 R 是集合 B 上的二元关 系 求 A B r R s R t R 10 分 密 密 第 3 页 共 4 页 西南科技大学 2006 2007 学年第 2 学期 西南科技大学 2006 2007 学年第 2 学期 离散数学 J 期末考试试卷 A 卷 离散数学 J 期末考试试卷 A 卷 九 在一个班级 50 个学生中 有 26 人在第一次考试中得到优 21 人在第二 次考试中得到优 假如有 17 人两次考试都没有得到优 问有多少学生在两次 考试中都得到优 10 分 十 下图所示带权图中边的权表示城市间修建公路的预测造价 试给出一个设 计方案 即画出图 使得各城市间能有公路相通 且总造价最低 并计算出最 低总造价 6 分 十一 某单位举行舞会 有 6 名女士 用 M1 M6 表示 有 6 名男士 用 G1 G6 表示 男士女士搭配起来跳舞 但每人心目中有一张表 只愿意跟表上的人 跳舞 各自表如下 M1 G1 G2 G4 M2 G3 G5 M3 G1 G2 G4 M4 G2 G5 G6 M5 G3 G6 M6 G2 G5 G6 G1 M1 M3 M6 G2 M2 M4 M6 G3 M2 M5 G4 M1 M3 G5 M2 M6 G6 M3 M4 M5 问如何搭配 使得男女双方都有相互满意的舞伴 8 分 密 密 第 4 页 共 4 页 西南科技大学 2006 2007 学年第 2 学期 西南科技大学 2006 2007 学年第 2 学期 离散数学 J 期末考试试卷 A 卷 离散数学 J 期末考试试卷 A 卷 十二 无向树 T 中有 4 片树叶 2 个 2 度顶点 其余顶点的度数均为 4 1 求 T 中 4 度顶点的个数 2 画出符合题设条件的所有不同构的无向树 10 分 十三 有向图 G 如下所示 1 写出 G 的邻