本文系统梳理了研究生招生考试《计算机学科基础》科目中的数据结构部分的核心知识点。首先介绍了线性表的顺序表示和链式表示，比较了它们在插入和删除操作上的时间复杂度。接着，详细讨论了栈和队列的概念、存储结构及其应用，包括中缀表达式转后缀表达式的调度场算法。随后，文章介绍了数组的特殊矩阵压缩方法和稀疏矩阵的存储方式。
在树的部分，文章讲解了二叉树的遍历方法、线索二叉树、多叉树的转换与遍历、霍夫曼树的构造与编码，以及并查集的实现与路径压缩技术。图的部分涵盖了图的基本概念、存储结构、遍历算法、最短路径算法、最小生成树算法、拓扑排序和关键路径方法。
最后，文章深入探讨了各种排序算法，包括插入排序、冒泡排序、快速排序、选择排序、堆排序、归并排序、基数排序和计数排序，分析了它们的时间复杂度、空间复杂度和稳定性。通过本文的学习，读者可以全面掌握数据结构的基本理论和应用技巧，为研究生招生考试奠定坚实的基础。
（摘要由 OpenAI GPT 4o 生成）
本篇文章系统梳理了研究生招生考试《计算机学科基础》科目中操作系统部分的核心知识点。首先介绍了操作系统概念和RISC-V环境下的系统调用机制，分析了硬件异常处理和用户态与内核态的切换流程。接着，阐述了操作系统引导过程，以及微内核和宏内核模型的差异与适用场景。随后，详细讨论了进程和线程的概念，进程调度算法、线程同步与互斥、信号量及死锁预防与检测的原理，并通过银行家算法等典型案例说明死锁避免方法。内存管理部分重点介绍了分页与分段、虚拟内存、页面置换算法以及工作集等概念。文件系统方面，则围绕文件结构、目录管理、磁盘空间分配策略等内容展开。最后讲解了I/O系统及磁盘调度算法，为研究生招生考试《计算机学科基础》科目中的操作系统部分提供了全面、系统的复习思路。
（摘要由 OpenAI o1-preview 生成）
本文系统梳理了计算机组成与体系结构的核心内容，重点涵盖了计算机的基础概念、数据表示与运算、存储系统与层次结构、指令系统与CPU基本功能、流水线与多处理器系统，以及总线与I/O系统。通过详细阐述寄存器、ALU、控制单元和中断机制的工作原理，以及 Cache、DMA、TLB 等关键技术的实现方式，本文为读者提供了完善的理论框架和复习思路，帮助在研究生招生考试《计算机学科基础》中高效掌握计算机组成部分的要点与难点。
（摘要由 OpenAI o1-preview 生成）
本文系统梳理了研究生招生考试《计算机学科基础》科目中计算机网络部分的主要知识点。首先介绍了计算机网络的概念、体系结构及其交换技术，并对OSI七层模型与TCP/IP四层模型进行对比。随后阐述了物理层的相关概念，如码元、比特率、带宽及Nyquist与Shannon定理；接着详述了数据链路层，包括封装成帧、差错控制、流量控制与可靠传输，以及介质访问控制（含CSMA/CD、CSMA/CA、令牌传递等）。在网络层部分，介绍了IPv4/IPv6的首部字段、ARP、DHCP、ICMP、路由算法及NAT等核心机制；在传输层，重点分析了UDP与TCP，包括连接建立与释放、流量控制和拥塞控制。最后，在应用层讲解了DNS、FTP、HTTP、电子邮件等典型协议的原理和工作流程，为研究生招生考试《计算机学科基础》科目中的计算机网络部分提供了全面、系统的复习思路。
（摘要由 OpenAI o1-preview 生成）
《编译原理》课程主要内容：{% post_link lexical-analysis %}、语法分析（{% post_link syntactic-analysis-top-down %}、{% post_link syntactic-analysis-bottom-up %}）、抽象语法、{% post_link semantic-analysis %}、{% post_link activition-record %}、{% post_link intermediate-representation %}、基本块和轨迹（包含在 {% post_link intermediate-representation %} 之内、处理 IR 之后）、{% post_link instruction-selection %}、{% post_link liveness-analysis %}、寄存器分配、垃圾回收、面向对象语言、循环优化。部分章节有比较完整的笔记（详见链接），全部章节内容的概要在下面的 A4 cheat paper 中：
本文简要介绍了指令选择问题中的两种主要方法：
通过对比这两种方法，可以在编译过程中更好地进行目标代码生成。
（摘要由 OpenAI o1-preview 生成）
本文介绍了编译原理中的活跃变量分析，详细阐述了其在寄存器分配和死代码删除等方面的应用。通过构建控制流图（CFG）进行数据流分析，定义了变量的活跃性，并介绍了相关术语如前驱节点、后继节点、定义和使用。文章探讨了活跃变量分析的可判定性问题，并提出了一种保守的近似算法，分析了其时间复杂度和最小不动点的概念。此外，还区分了静态活跃性与动态活跃性，强调了静态活跃性作为一种保守估计的重要性。
（摘要由 OpenAI o1-preview 生成）
AST -> IR1 -> IR2 -> ... -> IRk -> asm
IR 是一种抽象的机器语言、旨在表达目标机器的操作而不涉及过多与指令集有关的细节。相比于直接生成目标架构的汇编语言代码，将源代码首先转为 IR 能够有效地提高编译器的模块化以及可移植性（考虑需要将高级语言转为不同目标架构的汇编语言）。
冯诺依曼架构中的编译器需要将所有的 CODE 转换为汇编指令，并为 DATA 分配空间。活动记录是通过编译器实现的，使得程序在运行时，存储或传递：函数或过程的局部变量、返回地址、参数等信息的数据结构，一般是栈帧。
符合语法的程序不一定有有意义或是程序员期望的语义。
狭义上的语义分析是编译器前端的最后一部分，手段是对 AST 做一些分析和变换，目的是确定程序的某些静态属性，例如变量的声明与作用域、变量与表达式的类型、函数调用是否符合定义等等。最后，语义分析将把 AST 转换为某种中间表示（IR）。