离散数学2answer.doc

常熟理工学院 试题参考答案及评分标准 一、选择题（每题2分，共20分） BCCAD AABDC 二、填空题（每题2分，共20分） 1.(1)PQ (2)(┐P∨Q)∧(P∨┐Q)或（(┐P∧┐Q)∨(P∧Q)等） 2.自反，反对称，传递 3.（） 4.经过图中每边一次且仅一次 5. 上确界 6. Max Min + 可结合性 Y Y Y 可交换性 Y Y Y 存在幺元 N N N 存在零元 N N Y 7. 至少有两个元素的有补分配格 8. 小项的析取所组成 9. x | (x?A) ù (x?B) 10. 简单图中若每一对结点间都有边相连 三、判断题（每题1分，共10分）××√√× √√××√ 四、解答题（3小题，共20分） 1. （5分）在根树中，若每一个结点的出度小于或等于2，则这棵树称为2叉树。 任何一棵有序树都可以改写为对应的二叉树，方法是： ⑴除了最左边的分枝点外，删去所有从每一结点长出的分枝。在同一层次中，兄弟结点间用从左到右的有向边连接。 ⑵选定二叉树的左儿子和右儿子如下：直接处于给定结点下面的结点，作为左儿子，对于同一水平线上给定结点右邻结点，作为右儿子，以此类推。 2．（8分）各4分，步骤对，结果错，适当扣分，如果求出其一个，另一个直接写出，也不扣分。只有结果，且结果对，给一半分，只有结果，且结果错，不给分。 解：主析取范式:（┐PQR）∨（┐P┐QR）∨（PQR） 主合取范式:（┐P∨Q∨R）（┐P∨Q∨┐R）（P∨Q∨R）（P∨┐Q∨R）（┐P∨┐Q∨R） 3.（7分）这是一个求最小生成树的问题，可用多种方法，但必须有思路和过程。 解：按该图的生成树建立通讯线路能使城市间直接通讯，按最小生成树建立通讯线路能使城市间直接通讯且总造价最小。（1分） 通讯方案（最小生成树）：（5分） 最小总造价为：57（1分） 五、证明（3小题，共30分） （10分）每步约1分，没有P,T标识扣3分,没有序号扣3分。证明过程： （1）P→Q P （2）QR P （3）Q→R T(2)E （4）P→R T(1)（3）I （5）R P （6）P T（4）（5）I （7）SP P （8）S T(6)（7）I （10分）证明过程： 证明：因为R和S都是非空集A上的等价关系，所以R和S都有自反性，对称性和传递性。（1分） （1）,则,所以,所以RS是自反的。（2分） （2），则，因为R和S是对称的，所以（3分） ，从而,所以RS是对称的。 （3），则，因为R和S是传递的，所以，从而,所以RS是传递的。（3分） 由上面的三点可得RS是A上的等价关系。（1分） （6分）证明过程： 如果图G(V,E)不连通的话，它的顶点可以分为两个非空集合A,B，其中对于任意在A中的点P和任意在B中的点Q都没有PQ这条边。（3分） 取其补图，则对于任意在A中的点P和任意在B中的点Q都有PQ这条边。这样的话，对于任意两点P,Q，如果它们分别处于A,B的话，它们之间就有边相连；否则，不失一般性设它们都在A中，由于B非空，我们可以在B中任取一点R，我们知道PR和QR这两条边都是存在的，所以P,Q是连在一起的。 综上，知连通。（3分） 4．（4分）证明过程： 证明：显然，*运算封闭，且(a*b)*c=a*(b*c)=a+b+c-4,所以*满足结合律。（2分） 2是幺元，4-a是a的逆元。所以I,*是群。（2分） 试题参考答案及评分标准 2 1 课程名称： 离散数学（试卷库02卷） / 学年第 学期 制 作 人： 涂为员 2009年 6月 5 日 使用班级：