离散数学考试大纲：题型与重点

"该资源是2017级离散数学考试大纲，包含了考试的题型、评分标准以及部分样题。考试分为A、B、C三套卷子，每套卷子包括判断题、填空题、计算题和证明题。其中，涉及的知识点涵盖图论、集合论、逻辑、算法等多个方面。" 详细知识点： 1. 图论概念： - 完全图：无向完全图G是n阶的，它的边数是n(n-1)/2，这在判断题中有所体现。 - 欧拉图：无向图G是欧拉图的充分必要条件是G是连通的且没有奇度顶点。 - 树的性质：在一棵树中，如果有一个度为3的节点和两个度为2的节点，那么树叶（度为1的节点）的数量可以通过解法求出，这里是5个。 2. 集合论： - 集合的关系：{b}是属于{{b}}，而不是子集。 - 等势关系：Q、N、Z之间的等势关系，即N≈Z≈Q，以及它们与自然数乘积的关系。 3. 逻辑与算法： - 主析取范式和主合取范式：计算题可能要求考生转换布尔表达式的这两种形式。 - 关系的闭包：传递闭包、对称闭包和自反闭包的计算。 - 哈夫曼编码：用于求解最佳前缀码，优化数据编码效率。 - 中国邮递员问题：计算使邮递员路线最短的路径。 - 最短路径：可能需要求解图中的最短路径问题，如Dijkstra算法或Floyd-Warshall算法。 4. 计算题示例： - A卷：包括计数问题、求关系的闭包、哈夫曼编码和中国邮递员问题。 - B卷：同样涉及哈夫曼编码，还有偏序关系的处理，如哈斯图、极大元、极小元、最大元和最小元。 - C卷：计算特定条件下的数的数量、等价关系及其矩阵，以及哈夫曼算法的应用。 5. 证明题示例： - 连通性证明：证明如果图G中任意两点的度数之和大于等于n-1，则图G是连通图。 - 双射函数：可能要求构造或证明函数的双射性质。 - N个无向简单图：可能涉及到多个无向图的性质和操作。 这份考试大纲覆盖了离散数学中的核心概念，强调了理论理解与实际应用的结合，特别是图论和集合论中的计算与证明能力，以及算法设计和分析。考生需要扎实掌握这些知识，并能灵活运用到具体问题中。