离散数学-2006`2007(2)-试卷B参考答案及评分细则.pdf

密 第 1 页 共 6 页 参考答案及评分细则参考答案及评分细则 西南科技大学 2006 2007 学年第 2 学期西南科技大学 2006 2007 学年第 2 学期 离散数学 J离散数学 J 期末考试试卷 B 卷 一 解 图 1 能画出 比如 v1 v2 v3 v4 v7 v8 v3 v7 v6 v2 v5 v6 v1 v5 3 分 图 2 不能一笔画出 1 分 因为图 1 中奇度数顶点数为 4 2 分 二 解 图 1 存在哈密尔顿回路 比如 v1 v2 v3 v4 v5 v6 v7 v8 v1 3 分 图 2 不存在哈密尔顿回路 1 分 因为 取 V v2 v6 则连通分 支数 w G V 3 V 2 因而该图不是哈密尔顿图 2 分 三 4 分 四 解 由握手定理知 图 G 中所有顶点度数之和为边数的两倍 2 分 图 G 中所有顶点度数之和为 2 3 3 4 4 5 38 1 分 因此 G 中共有 19 条边 1 分 课程代码课程代码 1 4 3 1 4 0 320命题单位 计算机科学与技术学院 命题单位 计算机科学与技术学院 软件教研室软件教研室 密 第 2 页 共 6 页 参考答案及评分细则参考答案及评分细则 西南科技大学 2006 2007 学年第 2 学期西南科技大学 2006 2007 学年第 2 学期 离散数学 J离散数学 J 期末考试试卷 B 卷 五 解 最优二元树参考如下图 4 分 W T 1 4 2 4 5 3 3 3 3 3 6 2 7 2 71 1 分 六 解 前序遍历 P PQ P Q R 3 分 中序遍历 P P Q P Q R 3 分 后序遍历 P P Q P Q R 3 分 七 解 列公式 Q P P 和 P Q P 的真值表如下 真值表共 8 分 每 项 2 分 P Q Q P P P Q P 0 0 0 0 0 1 0 0 1 0 0 0 1 1 0 0 因为真值表的最后两列完全相同 所以公式 Q P P 和 P Q P 等值 2 分 密 第 3 页 共 6 页 参考答案及评分细则参考答案及评分细则 西南科技大学 2006 2007 学年第 2 学期西南科技大学 2006 2007 学年第 2 学期 离散数学 J离散数学 J 期末考试试卷 B 卷 八 解 A B 4 分 r R a 分 s R a 分 t R 2 分 九 解 设参加英语学习小组用集合A1表示 参加数学学习小组用集合A2表示 则 12 50 1733AA 3 分 121212 2621 3314AAAAAA 5 分 所以 有 14 个学生既参加了英语学习小组又参加了数学学习小组 2 分 若画出文氏图给 5 分 十 解 要设计一个方案使各城市间能够通讯且总造价最小 即求该图的最小生 成树 如下图 4 分 密 第 4 页 共 6 页 参考答案及评分细则参考答案及评分细则 西南科技大学 2006 2007 学年第 2 学期西南科技大学 2006 2007 学年第 2 学期 离散数学 J离散数学 J 期末考试试卷 B 卷 最小生成树的权值即为最小总造价 1 2 3 5 7 18 2 分 十一 证明 平面图 G 有k个连通分支 每个连通分支都是连通平面图 图 G 的 每个连通分支都满足欧拉公式 1 分 设 G 的第i个连通分支有 i n个顶点 i m条边 i r个面 则有 2 iii nmr 2 分 111 2 kkk iii iii nmrk 1 分 而 1 k i i nn 1 k i i mm 1 1 k i i rrk 2 分 故 12nmrkk 1 分 因此 1nmrk 1 分 十二 解 1 设该树的树叶个数为x 根据树的性质和握手定理有 2分 3 2 1 3 x 1 2 3 x 1 1 x 3 所以 T中有7个结点 2分 2 符合题设条件的无向树有以下三种 密 第 5 页 共 6 页 参考答案及评分细则参考答案及评分细则 西南科技大学 2006 2007 学年第 2 学期西南科技大学 2006 2007 学年第 2 学期 离散数学 J离散数学 J 期末考试试卷 B 卷 每个 2 分 十三 解 1 将G中结点按v1 v2 v3 v4 v5排序 则G的邻接矩阵为 01010 00001 01010 00001 10100 A 4分 2 为了求G中长度为4的路径数目 计算 4 A 4 04040 00004 04040 00004 40400 A 2 分 所以长度为 4 的路径数为 32 1 分 长度为 4 的回路数为 0 1 分 3 可达性矩阵为 密 第 6 页 共 6 页 参考答案及评分细则参考答案及评分细则 西南科技大学 2006 2007 学年第 2 学期西南科技大学 2006 200