2018年清华数据结构与计算机原理回忆版：核心知识点总结

本资源是一份关于2018年清华大学计算机专业912课程的复习资料，主要涵盖了数据结构和计算机原理两部分的内容。以下是详细知识点解析： **数据结构部分：** 1. 时间复杂度分析： - 题目1中的第一点强调了分治法（T(n)=a+T(n/2)+O(1)）的时间复杂度通常是O(logn)，无论常数a大小如何。 - 第二点提到了CBA算法对所有n规模数组的下界时间复杂度是Ω(nlogn)，表示至少需要这么多时间。 - 第四点说明在输入随机的情况下，完全二叉堆的插入平均时间是常数，即O(1)。 - 第六点提到散列表使用双平方探测法，对于长度为4k+3的素数表，能访问所有元素。 - 第七点提到未改进的next算法即使在最坏情况下，时间复杂度也为O(n)。 - 第八点涉及斐波那契查找，指出前后黄金分割点作为轴点会使得常数相同。 - 第九点PFC（最优前缀编码）互换不同深度节点会影响编码特性。 2. 选择题： - 空间复杂度问题考察的是算法存储需求，可能选项A表示常数空间，其余选项待选。 - 后缀表达式问题暗示了需要根据表达式的结构进行猜测，类似于前一年的题目。 - 非法表达式求解值的问题，可能涉及错误处理或特殊值计算。 - 关于B-树的问题，需要考虑根节点、树的大小及内存限制，选项ABCD代表不同次数访问。 - 懒惰删除的桶单元数量与散列函数、负载因子等有关，具体数量受已存元素影响。 - 平衡二叉树的问题，涉及递增和递减顺序插入后的性质，k值与平衡条件相关。 - 左式堆的元素数量与最右侧链长度的关系，可能是满二叉树性质的体现。 - gs[0]=1的概率可能涉及哈希函数或特定分布情况。 **计算机原理部分：** 1. 计算机系统基本概念： - 提供了提高CPU主频可以改善程序运行速度的基本认识，这是硬件层面的影响。 - RAID6技术在磁盘损坏情况下仍能保持一定的可用性，即使丢失两个磁盘也能恢复数据。 2. C语言基础： - i的赋值语句没有提供完整信息，但可能涉及变量初始化、指针操作等基本语法或概念。 总结，这份文档是针对2018年清华大学计算机912课程的回忆版，内容包括数据结构中的时间复杂度分析、选择题以及两个具体的算法设计（单峰向量和最大和区间），还有计算机原理部分的基础概念和判断题。学习者可以通过这些题目复习和巩固相关理论知识，并熟悉常见算法的实现和分析方法。