计算机考研基础题库核心考点解析

常见问题精选与深度解析

计算机考研基础题库涵盖了计算机科学的核心知识点，是考生备考过程中不可或缺的学习资料。本栏目精选了考生们普遍关心的5个基础题，并提供了详尽的解答思路。这些问题不仅覆盖了数据结构、操作系统、计算机网络等关键领域，还深入分析了解题方法和易错点，帮助考生构建扎实的知识体系。

问题1：什么是快速排序算法？其时间复杂度是多少？

快速排序是一种高效的排序算法，采用分治策略实现。其基本思想是：选择一个基准元素，将数组划分为两个子数组，使得左侧所有元素都不大于基准，右侧所有元素都不小于基准，然后递归地对这两个子数组进行快速排序。快速排序的平均时间复杂度为O(nlogn)，但在最坏情况下（如已排序数组选择第一个或最后一个元素为基准）会退化到O(n2)。实际应用中可通过随机选择基准或三数取中等策略来优化性能。

快速排序的空间复杂度主要取决于递归调用栈的深度，平均为O(logn)，最坏为O(n)。其稳定性较差，因为相等的元素可能在划分过程中改变相对位置。尽管如此，快速排序因其常数因子小、缓存友好等特性，在实际应用中往往比其他O(nlogn)算法更快。掌握快速排序的关键在于理解其划分过程和递归实现，同时要能分析不同基准选择策略对性能的影响。

问题2：操作系统中的进程与线程有什么区别？

进程和线程是操作系统中的两个核心概念，它们在资源管理和执行模型上有显著区别。进程是资源分配的基本单位，拥有独立的地址空间和系统资源（如内存、文件描述符等），而线程是CPU调度的基本单位，共享所属进程的资源，自身不拥有资源。从资源占用角度看，创建进程需要复制父进程资源，开销较大；创建线程则只需分配栈空间，效率高得多。

在并发执行方面，进程间通信需要通过IPC机制，效率较低；线程间可以直接读写共享内存，通信更便捷但需注意同步问题。从系统开销看，进程切换涉及地址空间切换，开销显著大于线程切换。多线程编程能充分利用多核CPU，提高程序性能，但不当的线程管理可能导致死锁、竞争条件等问题。理解这两者的区别对于设计并发程序和优化系统性能至关重要。

问题3：TCP协议的三次握手过程是怎样的？为什么不能省略第二步？

TCP的三次握手过程是建立可靠连接的机制，确保通信双方都准备好数据传输。第一次握手：客户端发送SYN报文段，包含初始序列号seq=x，请求建立连接；第二次握手：服务器收到后回复SYN+ACK报文段，ack=x+1，seq=y，表示同意连接；第三次握手：客户端收到后发送ACK报文段，ack=y+1，完成连接建立。整个过程确保了双方都知晓对方的存在，且初始序列号不重复。

如果省略第二步，可能导致连接建立失败。设想客户端发送SYN=x后立即断网，服务器收到后回复SYN+ACK，但该报文可能丢失。若客户端超时重发SYN=x，服务器会误以为是新的连接请求而建立重复连接。三次握手通过等待服务器的明确确认，避免了这种"已失效连接请求重传"的问题。这种机制虽然多了一个RTT，但牺牲少量时间换取了连接的可靠性，是网络协议设计的典型权衡案例。