2025年高频计算机面试题库及答案

2025年高频计算机面试题库及答案1.反转链表时，迭代法和递归法的实现步骤及时间空间复杂度差异？迭代法实现步骤：初始化三个指针prev（初始为null）、curr（头节点）、next（临时保存curr下一个节点）。循环中，先保存curr.next到next，然后将curr.next指向prev，接着prev和curr分别后移（prev=curr，curr=next），直到curr为null时结束，prev即为新头节点。时间复杂度O(n)，空间复杂度O(1)。递归法实现步骤：递归终止条件是当前节点或下一个节点为null，返回当前节点（即尾节点作为新头）。递归调用处理子问题（反转当前节点之后的部分），然后将当前节点的下一个节点的next指向当前节点（即原后继节点的next指向自己），最后将当前节点的next设为null（断开原连接）。时间复杂度O(n)，空间复杂度O(n)（递归栈深度）。差异核心在于递归隐含使用栈空间，迭代则是原地操作。2.二叉树中如何找到两个节点的最近公共祖先（LCA）？若树是二叉搜索树（BST），利用其性质：LCA的值介于两节点值之间（或等于其中一个）。从根节点开始，若当前节点值大于两节点值，递归左子树；若小于则递归右子树；否则当前节点即为LCA。若是普通二叉树，采用后序遍历：递归左右子树，若左子树找到一个节点、右子树找到另一个节点，则当前节点是LCA；若仅左子树找到，返回左子树结果；仅右子树找到则返回右子树结果；都没找到返回null。特殊情况：若其中一个节点是另一个的祖先，直接返回该祖先节点。示例代码（普通二叉树）：```javapublicTreeNodelowestCommonAncestor(TreeNoderoot,TreeNodep,TreeNodeq){if(root==null||root==p||root==q)returnroot;TreeNodeleft=lowestCommonAncestor(root.left,p,q);TreeNoderight=lowestCommonAncestor(root.right,p,q);if(left!=null&&right!=null)returnroot;returnleft!=null?left:right;}```3.堆排序的核心步骤是什么？如何优化其稳定性？核心步骤：①建堆（将数组调整为大顶堆或小顶堆，从最后一个非叶子节点开始向前遍历，执行下沉操作）；②排序（将堆顶元素与末尾元素交换，缩小堆范围，重新调整堆，重复直到堆为空）。堆排序不稳定的原因是交换堆顶与末尾元素时，可能破坏相同值元素的相对顺序。优化稳定性需额外记录元素原始位置，或在比较时优先按原始位置排序（如将元素封装为对象，包含值和索引，比较时若值相同则按索引排序），但这会增加空间复杂度（O(n)），实际应用中堆排序因不稳定性较少用于需要稳定排序的场景。4.进程与线程的本质区别是什么？为什么多线程比多进程更高效？本质区别：进程是资源分配的最小单位（拥有独立的内存空间、文件描述符等），线程是CPU调度的最小单位（共享进程资源，仅拥有独立的栈和寄存器）。多线程更高效的原因：①线程创建/销毁开销小（无需分配新内存空间，只需分配栈空间）；②线程间通信无需经过内核（共享内存直接通信，而进程间通信需通过管道、消息队列等内核机制）；③上下文切换代价低（线程切换仅需保存/恢复寄存器和栈，进程切换需保存/恢复所有资源和页表）。但需注意，多线程受限于GIL（如Python）或CPU核心数，并非绝对高效。5.虚拟内存的作用及实现机制？作用：①扩展物理内存（将部分数据存于磁盘，程序无需等待物理内存足够即可运行）；②隔离进程（每个进程拥有独立虚拟地址空间，避免地址冲突）；③提高内存利用率（通过页面置换，按需加载必要数据）。实现机制：基于页表（记录虚拟页到物理页的映射）和缺页中断。当程序访问的虚拟页未加载到物理内存时，触发缺页中断，操作系统从磁盘读取该页到内存（若内存不足则通过页面置换算法如LRU、FIFO淘汰部分页），更新页表后恢复程序执行。虚拟地址空间通常分为用户空间和内核空间（如Linux中32位系统用户空间3GB，内核空间1GB）。6.死锁的四个必要条件是什么？如何预防和避免死锁？四个必要条件：互斥（资源同一时间只能被一个进程使用）、占有且等待（进程持有资源并请求其他资源）、不可抢占（资源只能被持有者主动释放）、循环等待（进程间形成资源请求环）。预防方法：破坏必要条件。①破坏互斥：使用可共享资源（如只读文件），但多数资源本身是互斥的（如打印机），此方法适用场景有限；②破坏占有且等待：要求进程一次性申请所有所需资源（需预知所有资源，可能导致资源浪费）；③破坏不可抢占：允许系统抢占进程资源（需支持资源状态保存，如CPU资源）；④破坏循环等待：对资源编号，要求进程按递增顺序申请（避免环的形成）。避免方法：动态检测资源分配状态，使用银行家算法（模拟资源分配，确保系统处于安全状态）。但银行家算法因计算复杂度高，实际中多用于理论分析。7.TCP三次握手的具体过程？为什么不能两次或四次？过程：①客户端发送SYN=1，seq=x（初始序号）的报文，进入SYN_SENT状态；②服务器收到后发送SYN=1，ACK=1，seq=y，ack=x+1的报文，进入SYN_RCVD状态；③客户端发送ACK=1，seq=x+1，ack=y+1的报文，进入ESTABLISHED状态，服务器收到后也进入该状态。不能两次的原因：防止失效的连接请求报文段被服务器接收。若客户端发送的SYN因网络延迟滞留，客户端超时重发新SYN并建立连接，旧SYN到达时，若两次握手则服务器直接建立连接，导致客户端无此连接需求而浪费资源。三次握手让客户端确认服务器收到了自己的SYN，避免上述问题。不能四次的原因：服务器的SYN和ACK可合并发送（SYN+ACK），减少一次报文交互，提升连接建立效率。8.HTTP1.1与HTTP2.0的主要区别？如何解决队头阻塞问题？主要区别：①二进制分帧（HTTP2将报文拆分为二进制帧，多路复用，而HTTP1.1是文本格式，按请求顺序处理）；②多路复用（一个TCP连接可并发处理多个请求/响应，HTTP1.1需通过长连接（keep-alive）或多连接实现并发）；③头部压缩（HPACK算法压缩请求头，减少冗余数据，HTTP1.1每次请求需重复发送完整头部）；④服务器推送（服务器主动向客户端发送资源，如HTML引用的CSS/JS，HTTP1.1需客户端逐个请求）。HTTP1.1的队头阻塞：因请求按顺序处理，若一个请求的响应未到达，后续请求需等待。解决方式：使用CDN分散请求、并行多连接（浏览器通常限制6-8个）、雪碧图合并资源等。HTTP2通过多路复用，不同请求的帧交错传输，接收方按流标识符重组，彻底解决了应用层的队头阻塞（但TCP层仍可能因丢包导致阻塞，需结合TLS1.3等优化）。9.事务的ACID特性分别指什么？MySQL如何实现这些特性？ACID：原子性（Atomicity，事务要么全做要么全不做）、一致性（Consistency，事务执行前后数据保持合法状态）、隔离性（Isolation，事务间互不干扰）、持久性（Durability，事务提交后数据永久保存）。实现：①原子性：通过undolog（回滚日志）实现，事务执行时记录数据修改前的状态，异常时根据undolog回滚。②一致性：依赖原子性、隔离性和应用层逻辑共同保证，如约束检查（主键、外键）在事务执行中自动触发。③隔离性：通过锁（共享锁、排他锁）和MVCC（多版本并发控制，InnoDB的undo日志提供数据快照）实现，不同隔离级别（读未提交、读已提交、可重复读、串行化）对应不同的锁策略和快照可见性规则。④持久性：通过redolog（重做日志）实现，事务提交时先将redolog写入磁盘（WAL，预写日志），数据页修改延迟刷新到磁盘，崩溃时通过redolog恢复未持久化的数据。10.索引的类型有哪些？什么情况下不适合创建索引？类型：①按数据结构：B+树索引（MySQL默认，适合范围查询）、哈希索引（Redis使用，适合等值查询，不支持范围）、全文索引（针对文本内容，MySQL的FULLTEXT）；②按字段数量：单列索引、复合索引（多字段联合，遵循最左匹配原则）；③按约束：主键索引（唯一且非空）、唯一索引（值唯一，允许null）、普通索引（无约束）；④按存储方式：聚集索引（数据行与索引存储在一起，InnoDB主键为聚集索引，一个表仅有一个）、非聚集索引（索引与数据分开存储，需回表查询）。不适合索引的情况：①字段更新频繁（索引维护增加写开销）；②数据区分度低（如性别字段，仅“男/女”，索引效果差）；③表数据量小（全表扫描比索引查找更快）；④查询条件不涉及索引字段（如WHERE条件为未索引的字段）；⑤覆盖索引无法满足（非聚集索引查询需回表，若回表成本高于全表扫描则不适用）。11.synchronized和ReentrantLock的区别？如何选择？区别：①锁获取方式：synchronized是关键字，JVM隐式管理（自动释放）；ReentrantLock是类（java.util.concurrent.locks），需显式调用lock()和unlock()（通常在finally块中释放）。②锁特性：ReentrantLock支持公平锁（按等待队列顺序获取）和非公平锁（默认，提高吞吐量），synchronized仅非公平；ReentrantLock可响应中断（lockInterruptibly()）、尝试获取锁（tryLock()），synchronized无法中断等待。③条件变量：ReentrantLock通过Condition对象支持多个等待队列（如生产者-消费者模型中区分读/写等待），synchronized仅一个wait/notify队列。④性能：早期版本synchronized因重量锁性能差，JDK6后引入偏向锁、轻量级锁、自旋锁优化，两者性能接近，高竞争场景下ReentrantLock更灵活。选择：简单同步用synchronized（代码简洁）；需要公平锁、可中断、尝试锁或多条件变量时用ReentrantLock。12.JVM内存模型中各区域的作用及常见异常？JVM内存分为：①程序计数器（PC寄存器）：记录当前线程执行的字节码行号，线程私有，无OOM（OutOfMemoryError）。②Java虚拟机栈：存储栈帧（局部变量表、操作数栈、动态链接、方法出口），线程私有。若线程请求栈深度超过限制（如递归未终止），抛StackOverflowError；若动态扩展时内存不足，抛OOM。③本地方法栈：与虚拟机栈类似，服务于本地方法（如native方法），HotSpot将其与虚拟机栈合并，异常同虚拟机栈。④堆（Heap）：存放对象实例和数组，线程共享。若对象分配时内存不足，抛OOM（如“Javaheapspace”）。⑤方法区（元空间，JDK8后）：存储类信息、常量、静态变量、即时编译代码等，线程共享。若类元数据过多（如动态提供大量类），抛OOM（“Metaspace”）。⑥运行时常量池：方法区的一部分，存储编译期提供的常量和符号引用，JDK7后移至堆中，异常同堆。13.CAP定理的具体含义？分布式系统中如何权衡？CAP指一致性（Consistency，所有节点同一时间看到相同数据）、可用性（Availability，每次请求都能收到非错误响应）、分区容错性（Partitiontolerance，网络分区时系统仍能运行）。定理指出三者无法同时满足，最多满足两个。权衡策略：①CP（一致性+分区容错）：牺牲可用性，如ZooKeeper、HBase。网络分区时，为保证一致性，可能拒绝部分请求（如Master节点不可达时，集群进入不可写状态）。②AP（可用性+分区容错）：牺牲强一致性，保证最终一致性，如Redis（异步复制）、Eureka（自我保护机制）。用户可能读到旧数据，但最终会同步。③CA（一致性+可用性）：放弃分区容错，适用于单机或网络可靠环境（如传统单体应用），但分布式系统中网络分区不可避免，CA实际难以实现。实际设计需根据业务场景选择，如金融交易强调一致性（CP），电商首页推荐强调可用性（AP）。14.如何实现一个线程安全的单例模式？双重检查锁定的原理？饿汉式（线程安全）：类加载时初始化实例，无线程问题，但可能浪费资源（实例未使用时已创建）。```javapublicclassSingleton{privatestaticfinalSingletonINSTANCE=newSingleton();privateSingleton(){}publicstaticSingletongetInstance(){returnINSTANCE;}}```懒汉式（线程不安全）：延迟初始化，但多线程下可能创建多个实例。双重检查锁定（DCL，线程安全且高效）：```javapublicclassSingleton{privatevolatilestaticSingletonINSTANCE;//volatile禁止指令重排privateSingleton(){}publicstaticSingletongetInstance(){if(INSTANCE==null){//第一次检查，减少同步开销synchronized(Singleton.class){if(INSTANCE==null){//第二次检查，防止多线程同时通过第一次检查INSTANCE=newSingleton();//可能因指令重排导致其他线程获取到未初始化的实例，需volatile}}}retu