408 考试核心考点深度解析与备考指南

计算机学科专业基础综合（简称 408）是计算机考研的重要科目，涵盖数据结构、计算机组成原理、操作系统和计算机网络四门核心课程。考生在备考过程中常会遇到一些难点和易混淆知识点，本站整理了部分高频问题，结合 408 教材内容进行详细解答，帮助考生理清思路，突破学习瓶颈。以下内容从考生实际疑问出发，提供系统化、场景化的解答思路，助力高效备考。

常见问题解答

1. 数据结构中，快速排序和归并排序的平均时间复杂度为什么都是 O(nlogn)，但实际应用场景有何区别？

快速排序和归并排序都是常见的排序算法，它们在理论分析上都具有 O(nlogn) 的平均时间复杂度，但实际应用中存在显著差异。快速排序通过分治策略将大问题分解为小问题，其核心在于选择合适的基准点（pivot），理想情况下每次划分都能将数据均匀分成两部分，从而实现 logn 层递归。然而，快速排序的最坏情况出现在数据已接近有序或基准点选择不当时，此时时间复杂度会退化到 O(n2)。归并排序则不同，它始终以对数级别进行分割，并通过额外空间合并有序子序列，因此无论输入数据状态如何，其时间复杂度始终稳定在 O(nlogn)。但在空间复杂度上，快速排序是原地排序（O(1) 额外空间），而归并排序需要 O(n) 的辅助数组，对于内存有限的场景快速排序更具优势。实际应用中，若数据规模不大或内存充足，快速排序因常数项较小通常更快；但数据量巨大或稳定性要求高时，归并排序的可靠性更受青睐。例如，在数据库排序中，归并排序常用于外部排序，因为它能处理磁盘上的大文件。

2. 计算机组成原理中，Cache 的替换算法有哪些，LRU 与 FIFO 的核心区别是什么？

Cache 替换算法是计算机组成原理中的重点，常见的有随机替换（Random Replacement）、先进先出（FIFO）和最近最少使用（LRU）三种。随机替换通过随机选择失效块替换，实现简单但命中率不稳定；FIFO 则根据块进入 Cache 的时间决定替换，适用于对时间局部性敏感的场景；而 LRU 通过追踪块的使用频率，优先淘汰最久未被访问的块，其命中率通常最高。LRU 与 FIFO 的核心区别在于替换依据：FIFO 仅关注进入时间，不考虑实际访问频率，可能将近期频繁使用的块误判为“最老”；LRU 则通过硬件或软件实现（如使用栈或计数器）来记录每个块的使用情况，确保淘汰真正冷门的块。例如，在 CPU 密集型应用中，LRU 能显著减少缺页中断次数，而 FIFO 在某些特定数据访问模式（如循环访问）下可能表现更差。实际设计中，LRU 虽然实现复杂，但性能优势使其成为主流选择，现代 CPU Cache 多采用改进的 LRU 或其变种（如伪 LRU）。

3. 操作系统中，进程与线程的区别是什么？为什么多线程编程在并发控制中更复杂？

进程与线程是操作系统中的基本概念，它们的主要区别体现在资源拥有、独立性、通信方式等方面。进程是资源分配的基本单位，拥有独立的地址空间、内存、文件描述符等，进程间通信（IPC）需要通过管道、信号量等机制实现，开销较大；线程则是 CPU 调度的基本单位，共享所属进程的地址空间和资源，线程间通信更直接高效，但需注意同步问题。多线程编程在并发控制中更复杂，共享资源的访问需要加锁（如互斥锁、读写锁），否则易引发数据竞争；死锁（如哲学家就餐问题）是线程同步的典型难题，需要合理设计资源分配顺序或使用超时机制。线程的调度策略（如时间片轮转）直接影响性能，不当的优先级设置可能导致饥饿。例如，在图形界面程序中，若未正确处理线程同步，主界面可能被耗时任务阻塞。因此，多线程编程要求开发者具备严谨的并发思维，常用工具如 Java 的 CountDownLatch 或 Python 的 asyncio 都是为了简化并发控制设计。