哈工大计算机机试回忆：集合论与图论知识点梳理

本资源是一份关于哈尔滨工业大学计算机学院历年复试题的回忆整理，主要聚焦于图论和集合论相关的知识点。提供者强调这是由王道论坛的热心会员回忆，版权归属王道论坛，未经许可禁止转载，且由于是机试回忆版，可能存在一定的错误和重复。 1. 集合论与图论部分： - 第一个问题考察了函数性质：如果函数f：X->Y，A⊆X，并且对于x∈A，有f(x)∈f(A)，则选项A（x∈A）是正确的，因为集合A中的元素映射到其自身的像集。 2. 关于图论的判断题： - 一道关于图的性质问题指出，一个有6个顶点和11条边的图，所有顶点的度数要么是3要么是4。由于总边数（6*4/2）=12，而题目只有11条边，所以该图不可能是哈密顿图，即没有通过所有顶点恰好一次的路径。选项C（不是哈密顿图）是正确的。 - G(p, q)是无向树的充要条件被列举出来，选项A（p=q+1，表示除了根节点外，每个节点正好有一个子节点）是正确条件。 3. 偏序关系与二元关系： - 二元关系在X上的数量问题，根据题目，X={1,2,3}，对于这样的集合，共有2^3=8个可能的二元关系，但选项C（512）和D（27）显然不符合。这里可能存在回忆错误，一般而言，是2^|X|，即9个不同的关系。 4. 其他题目涉及： - 自反等价关系和等价类的数量计算，因为是自反且传递的，对于集合{1,2,3}，有5个不同的等价类。 - 对于一个关于居住关系的问题，描述模糊，可能是关于6个人的相互认识情况，但具体细节未给出。 5. 数学逻辑和集合理论： - 包括整数、自然数和有理数的基数比较，以及集合运算的性质，如集合A并集与B、C的关系，以及函数性质的进一步讨论。 6. 最后，提及了一些选择题，如关于图的性质（q与p的关系）、集合运算的等价关系表达等，这些题目体现了对基础概念的考查。 总体来看，这份回忆录提供了哈工大计算机学院历年复试题中集合论和图论部分的精华知识点，对于备考的学生来说，这部分内容可以帮助复习和理解相关概念，但需注意其中可能存在回忆误差。