清华计算机研究生考试：数据结构与计算机原理题目精编

本资源是一份2018年清华大学计算机系研究生考试初试笔试试题，主要涵盖数据结构和计算机原理两个部分。以下是部分内容的详细解析： 数据结构部分： 1. 判断题： - (1) 提供的时间复杂度分析是关于分治法（T(n)=a * T(n/2) + O(1)），这是递归划分问题的一般形式，当a=1时，对应于二分查找，时间复杂度为O(log n)，因此这个表述是正确的。 - (2) 基于CBA（可能是Cache Block Algorithm，但没有明确说明）的算法，其时间复杂度至少是线性的，即Ω(n)，题目表述可能不严谨，因为没有给出具体上下界。 - (3) 基数排序利用了整数的位数进行排序，底层排序算法确实可以保持元素间的相对顺序，所以是稳定的。 - (4) 完全二叉堆的插入操作平均时间复杂度为O(1)，因为插入操作通常涉及调整堆结构，而调整操作的次数与堆的高度相关，平均情况下为常数。 - (5) 伸展树（也叫AVL树或Splay Tree）的插入操作，由于平衡操作的局部性，分摊时间复杂度可以达到O(log n)。 - (6) 对于散列表，双平方探测在长度为4k+3的素数数组上，如果设计得当，理论上能访问所有元素，但这里没有给出具体概率，只说一定能访问，需要更详细的信息来判断。 - (7) next算法，如果没有优化，确实可能具有O(n)的时间复杂度，但没有进一步说明如何达到这个复杂度。 - (8) Fib查找法利用黄金分割比例，无论前后轴点如何选择，常数因子可能相同，但具体数值取决于实际实现。 - (9) PFC（最优前缀编码）是无损压缩的一种方法，交换不同深度节点位置会破坏编码的唯一性，即性质被破坏。 - (10) 折半查找通常优于顺序查找，因为它在有序序列中搜索效率更高。 2. 选择题： - (1) 就地算法（原地操作，不额外分配空间）的空间复杂度是O(1)。 - (2) 后缀表达式的猜测问题考察的是理解表达式结构的能力，题目未提供具体内容，无法给出答案。 - (3) 非法表达式的求解值，需要具体表达式才能计算，这里未给出。 - (4) 7阶B-树根节点在内存中，对于2017规模的B-树，访问次数与树的高度有关，需要知道B-树的具体细节，这里无法确定。 - (5) 散列表的懒惰删除是指在查找失败时才会删除，已存入1000个元素，最多懒惰删除的桶单元数量取决于哈希冲突的数量，题目未给出哈希函数，所以不能确定。 - (6) 二叉树按递增或递减顺序插入，当n=2^k-1时，两者生成的平衡二叉树相等，这表明二叉树的高度固定，是充要条件。 - (7) 左式堆（一种优先队列）的最右侧链长度为k，但堆中的元素数量不一定是最少的2^k，也不一定最多，因为堆顶元素不一定在链的末端。 - (8) gs[0]=1的概率，没有给出gs的定义和上下文，无法计算。 计算机原理部分： 1. 判断题： - (1) 提升CPU主频确实可以提高程序执行速度，这是提高性能的一个常见方式。 - (2) RAID6可以在坏掉两个磁盘的情况下仍能工作，但并不意味着可以正常运行所有任务，需要备份数据恢复。 以上知识点展示了数据结构和计算机原理部分的部分核心概念和题目类型，考生需要掌握这些理论和算法，并根据题目描述灵活应用。考试强调设计高效算法，特别是O(n)复杂度的解决方案，这对于理解和解决实际问题至关重要。