清华大学2001年计算机考研真题：并查集、图论与归并排序

"清华大学2001年计算机专业考研真题1" 这是一份来自清华大学2001年的计算机专业研究生入学考试试卷，主要考察数据结构与程序设计相关的知识。试题分为五个部分，涵盖并查集操作、图论问题、非递归归并排序的时间复杂度分析、AVL树的基本属性以及散列表的冲突处理。 一、并查集 并查集是一种用于处理不相交集合的操作数据结构，主要操作包括查找和合并。题目给出了一个并查集的操作序列，要求根据不同的策略（路径压缩、按高度合并或按大小合并）实现并查集的合并操作，并给出结果。路径压缩策略是将所有经过的节点直接链接到根节点，而按高度和大小合并则是根据两个子树的高度或节点数量来决定合并后的新根节点。 二、图论问题 这是一个旅行商问题的变种，需要在4个地点之间通过6座桥恰好走过每座桥一次并返回原地。问题探讨了这类问题的解的存在条件，并要求设计一个算法来找到满足条件的回路。旅行商问题通常与图的遍历和回路检测相关，可以使用深度优先搜索或广度优先搜索等方法来解决。 三、非递归归并排序 归并排序通常使用递归实现，但题目要求非递归的方法。分析在不同输入情况下的运行时间，即数据比较次数和移动次数。当数据完全有序或逆序时，非递归归并排序的时间复杂度会有优化，而在随机输入情况下则接近于常规的O(n log n)。 四、AVL树问题 AVL树是一种自平衡二叉搜索树，确保每个节点的左右子树高度差不超过1。问题询问了节点高度数据成员的存储需求，以及具有8位高度计数器的AVL树的最大和最小层数。在AVL树中，每个节点需要额外存储一个表示高度的字段，而高度计数器的位数限制了树的最大深度和最小元素数量。 五、散列表 散列表是一种通过哈希函数实现快速查找的数据结构。题目使用线性探查法处理冲突，并给出了特定的哈希函数（取余运算）。需要分析各个关键码可能产生的冲突情况，线性探查会在冲突发生时寻找下一个空位置，直至找到合适的位置插入元素。 这些题目综合了数据结构和算法的核心概念，反映了对计算机科学基础理论的深入理解和应用能力的要求。