2019年4月全国自考离散数学试题及答案解析.docx

离散数学是计算机科学中的基础学科，主要研究离散而非连续的数据结构和数学概念。这份2019年4月全国自考离散数学试题涵盖了多个核心知识点，包括图论、命题逻辑、集合论和代数结构。 1. **图论**： - **度数列**：无向图中，每条边连接两个顶点，所以度数列的总和应为偶数。选项B和C满足这一条件；A和D中度数和为奇数，因此排除。 - **简单图**：简单图没有自环（即顶点不能与自身相连）和重边。选项A中有自环（如"ab, eb"），B中的E2未给出具体边，C和D中无自环或重边。 - **欧拉图**：欧拉图是从任意顶点出发都能通过所有边恰好一次返回起点的图。图C符合此条件，因为它没有奇数度的顶点；而A、B、D都有至少一个奇数度的顶点。 2. **命题逻辑**： - **命题公式等价**：题目中涉及命题逻辑的蕴含和量词。例如第4题，公式P→(Q→R)等价于¬P∨(Q→R)，经过逻辑等价变换可以得到正确答案。 3. **集合论与代数结构**： - **循环群与阿贝尔群**：循环群一定是阿贝尔群，但阿贝尔群不一定是循环群。题目中第6题的陈述是正确的。 - **函数复合**：函数复合运算"。"满足结合律，即(f•g)•h=f•(g•h)。第11题的陈述是正确的。 - **图的生成树**：生成树是连通图的一个子图，包含所有顶点且没有环。对于(n,m)图，生成树有n个结点，这是正确的，对应第13题。 4. **填空题**： - **边数与顶点度数关系**：在无向图中，边数等于所有顶点度数之和的一半。 - **非平凡无向完全图成为欧拉图**：非平凡无向完全图Kn是欧拉图当n为偶数。 - **1度顶点数量**：根据握手定理，3度顶点数乘以3加上2度顶点数乘以2等于边数，解得1度顶点数。 - **关系的性质**：r(R)表示关系R的基数，s(R)表示关系R的势，t(R)表示关系R的元数。 - **小项与合取、析取**：任意两个不同小项的合取为假，全体小项的析取式为所有可能真值组合的析取。 - **形式化表达**：(1)存在唯一偶素数可以用"∃!x(P(x) ∧ Q(x))"表示，(2)至多有一个偶素数可以用"∀x(¬P(x) ∨ ¬Q(x))"表示。 - **无向连通图的不同构**：5个节点4条边的连通图的不同构可以通过构造和分析得出。 - **m元树和完全m叉树**：m元树的根有m个子节点，完全m叉树每个层的节点数达到最大。 - **代数系统(N，+)**：单位元是0，只有非零整数有逆元。 - **平面图的面数**：欧拉公式V - E + F = 2可以用来计算平面图的面数。 5. **问答题**： - **奇数顶点的连通性**：在图中，如果有两个奇数度的顶点，由握手定理，它们必须通过一条路径相连。 - **面的面度**：六结点十二边的连通平面简单图，面度之和等于边数的两倍。每个面的面度为3可保证总和为24。 - **朋友围桌问题**：应用图论中的染色理论，如果每个人的朋友都在自己周围，可以构造一个无环的圈，证明可行性。 - **格的判断**：(z,≤)是否构成格取决于它是否满足格的两个性质：半序集和上、下确界的存在性。 - **函数的满射与单射**：满射意味着对于所有目标值都有源值映射到它，但不是单射意味着存在不同的源值映射到同一个目标值。 6. **计算题**： - **前缀码设计**：基于概率分配，设计前缀码使得平均码长最小。 - **命题公式转换**：将给定的命题公式转换为主合取范式（CNF）和主析取范式（DNF），涉及逻辑等价变换和化简。 这些知识点是离散数学的核心内容，理解和掌握它们对于深入学习计算机科学至关重要。通过解答这些问题，考生可以检验自己对这些概念的理解程度，并进一步巩固相关知识。