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

2025年高频计算机面试试题及答案1.算法题：给定两个字符串s和t，判断t是否是s的字母异位词（字母相同但排列不同），要求时间复杂度O(n)，空间复杂度O(1)。解答：字母异位词的本质是字符出现次数完全相同。可创建长度为26的数组（对应a-z）统计s中各字符频率，再遍历t减少对应频率，若最终数组全为0则是异位词。需处理长度不等的情况（直接返回false）。示例：s="anagram",t="nagaram"→是；s="rat",t="car"→否。2.数据结构题：用双向链表和哈希表实现LRU缓存，要求get和put操作均为O(1)时间复杂度。解答：LRU（最近最少使用）缓存需维护“最近使用”顺序，双向链表保存键值对，头部为最近使用，尾部为最久未使用。哈希表存储键到链表节点的映射。get操作时，若存在则将节点移到头部；put操作时，若键存在则更新值并移到头部，若不存在则创建新节点插入头部，若容量已满则删除尾部节点并从哈希表中移除。关键点：双向链表需处理前驱后继指针，哈希表快速定位节点，容量满时的淘汰逻辑。3.二叉树题：给定二叉树的前序遍历和中序遍历结果，重建该二叉树。解答：前序遍历首元素是根节点，在中序遍历中找到根的位置，左侧为左子树节点，右侧为右子树节点。递归构建左右子树。例如前序[3,9,20,15,7]，中序[9,3,15,20,7]，根为3，左子树中序[9]对应前序[9]，右子树中序[15,20,7]对应前序[20,15,7]，递归得到左子树9，右子树根20，其左15、右7。需处理边界条件（空树、无效输入）。4.动态规划题：求最长递增子序列（LIS）的长度。解答：动态规划解法中，dp[i]表示以nums[i]结尾的最长递增子序列长度。初始时每个dp[i]=1（自身为一个序列）。遍历每个元素i，对每个j<i，若nums[j]<nums[i]，则dp[i]=max(dp[i],dp[j]+1)。最终结果为dp数组最大值。优化解法用贪心+二分：维护一个数组tail，tail[i]表示长度为i+1的递增子序列的最小末尾元素。遍历nums，对每个数x，用二分查找在tail中找到第一个≥x的位置，替换为x，最终tail长度即为LIS长度。5.字符串题：实现正则表达式匹配，支持'.'（匹配任意单个字符）和''（匹配零个或多个前面的那一个元素）。解答：动态规划解法，dp[i][j]表示s的前i个字符与p的前j个字符是否匹配。状态转移：若p[j-1]是''，则有两种情况：匹配0次（dp[i][j-2]）或匹配多次（需s[i-1]与p[j-2]匹配且dp[i-1][j]为真）；若p[j-1]是'.'或与s[i-1]相同，则dp[i][j]=dp[i-1][j-1]。初始条件：dp[0][0]=true（空匹配空），处理p中''可能匹配0次的情况（如a可匹配空）。6.操作系统：进程与线程的区别及应用场景。解答：进程是资源分配的最小单位，线程是调度执行的最小单位。进程拥有独立的地址空间、文件描述符等资源，线程共享进程资源（如内存、文件句柄），仅拥有自己的栈、寄存器、线程ID。进程间通信（IPC）需通过管道、消息队列、共享内存等，线程间通信可直接访问共享变量（需考虑同步）。进程切换开销大（需切换页表、寄存器等），线程切换仅需保存/恢复少量寄存器。应用场景：需隔离资源（如容器、多任务）用进程；需高效并发（如Web服务器处理请求）用线程。7.操作系统：死锁的必要条件及解决策略。解答：死锁四条件：互斥（资源同一时间只能被一个进程占用）、占有并等待（进程已占资源，等待其他资源）、不可抢占（资源不可被强制剥夺）、循环等待（进程间形成资源等待环）。解决策略：预防（破坏四条件之一，如资源一次性分配破坏占有并等待；资源有序分配破坏循环等待）；避免（银行家算法，动态检查分配后是否安全）；检测（通过资源分配图检测环）；解除（终止部分进程或抢占资源）。8.操作系统：虚拟内存的作用及实现机制。解答：虚拟内存将物理内存与外存结合，为进程提供更大的逻辑地址空间。作用：允许程序使用比物理内存更大的地址空间；实现内存共享（多个进程共享同一物理页）；隔离进程地址空间（防止进程间地址越界）。实现机制：分页（将虚拟地址空间划分为固定大小的页，物理内存划分为页框，通过页表映射虚拟页到物理页框）；缺页中断（访问的页不在内存时，触发中断，从外存调入页，可能置换其他页）；页面置换算法（如LRU、FIFO、OPT，决定换出哪些页）。9.操作系统：IO多路复用中select、poll、epoll的区别。解答：select用位掩码表示文件描述符（FD）集合，限制最大FD数量（如1024），每次调用需将FD集合从用户态拷贝到内核态，内核遍历所有FD检查就绪状态。poll用链表存储FD，无最大数量限制，但仍需用户态到内核态拷贝，遍历检查。epoll通过epoll_create创建内核事件表，epoll_ctl添加/删除FD，epoll_wait等待就绪事件。epoll使用事件驱动（回调函数），仅通知就绪FD，无需遍历所有FD，且通过mmap减少用户态与内核态的拷贝。epoll支持LT（水平触发，默认）和ET（边缘触发，仅就绪时通知一次），适合高并发场景（如百万连接的服务器）。10.计算机网络：TCP三次握手与四次挥手的过程及原因。解答：三次握手：①客户端发送SYN=1，seq=x（连接请求）；②服务器回复SYN=1,ACK=1，seq=y，ack=x+1（确认请求并发送自己的连接请求）；③客户端发送ACK=1，seq=x+1，ack=y+1（确认服务器的连接请求）。目的是同步双方的序列号和确认号，防止已失效的连接请求报文段突然到达服务器导致错误。四次挥手：①客户端发送FIN=1，seq=u（关闭连接请求）；②服务器回复ACK=1，seq=v，ack=u+1（确认收到关闭请求，此时服务器可能仍有数据发送）；③服务器发送FIN=1,ACK=1，seq=w，ack=u+1（服务器数据发送完毕，请求关闭）；④客户端回复ACK=1，seq=u+1，ack=w+1（确认服务器关闭请求）。客户端需等待2MSL（最大报文段生存时间）再关闭，确保最后一次ACK到达服务器，避免服务器重发FIN导致连接未正确关闭。11.计算机网络：HTTP1.1、HTTP2、HTTP3的主要区别。解答：HTTP1.1支持长连接（Connection:keep-alive）、管道化（但请求需按顺序响应，队头阻塞）、分块传输编码。HTTP2使用二进制帧（Frame）传输，多路复用（一个TCP连接可并发多个请求，解决队头阻塞），头部压缩（HPACK算法），服务器推送（主动向客户端发送资源）。HTTP3基于QUIC协议（UDP之上），解决TCP的队头阻塞（单个流的丢包不影响其他流），支持0-RTT连接建立（首次握手后缓存密钥，后续连接无需重新握手），改进拥塞控制和加密（TLS1.3）。12.计算机网络：HTTPS的加密过程。解答：HTTPS=HTTP+TLS/SSL。加密过程：①客户端发送支持的TLS版本、加密算法列表等（ClientHello）；②服务器选择算法，发送证书（含公钥）（ServerHello）；③客户端验证证书（通过CA机构），提供随机数（预主密钥），用服务器公钥加密后发送（ClientKeyExchange）；④双方用预主密钥+随机数提供会话密钥（对称加密密钥）；⑤后续通信通过会话密钥进行AES等对称加密。关键点：非对称加密（RSA或ECC）用于传输会话密钥，对称加密用于数据传输，证书防止中间人攻击。13.数据库：MySQL索引的类型及B+树索引的优势。解答：索引类型：主键索引（唯一标识行，自动创建）、唯一索引（约束列值唯一）、普通索引（加速查询）、联合索引（多列组合）、全文索引（针对文本内容）。B+树索引优势：内部节点存储索引键，叶子节点存储数据指针（InnoDB中是行记录），所有叶子节点通过指针连接，支持范围查询（顺序遍历叶子节点）；相比B树，B+树层级更少（相同数据量下，内部节点不存数据），更适合磁盘存储（减少IO次数）；叶子节点数据有序，支持二分查找和范围扫描。14.数据库：事务的ACID特性及实现机制。解答：ACID：原子性（Atomicity，事务要么全做要么全不做）、一致性（Consistency，事务前后数据处于合法状态）、隔离性（Isolation，事务间互不干扰）、持久性（Durability，提交后数据永久保存）。实现：原子性通过undolog（记录事务修改前的数据，回滚时恢复）；持久性通过redolog（记录事务修改后的数据，崩溃时重放）；隔离性通过锁（共享锁、排他锁）和MVCC（多版本并发控制，InnoDB的undo日志提供数据版本）；一致性由原子性、隔离性、持久性共同保证，并依赖应用层的业务逻辑。15.数据库：MySQL的四种事务隔离级别及对应的问题。解答：读未提交（ReadUncommitted）：允许读取未提交的修改，存在脏读（读取到回滚的数据）。读已提交（ReadCommitted，RC）：只能读取已提交的数据，解决脏读，但存在不可重复读（同一事务两次查询结果不同）。可重复读（RepeatableRead，RR，InnoDB默认）：保证同一事务多次查询结果一致，解决不可重复读，但存在幻读（查询范围新增/删除行，导致结果集变化）。可串行化（Serializable）：事务串行执行，解决所有问题，但并发性能低。InnoDB通过MVCC在RR级别下解决幻读（快照读），但当前读（加锁读）仍可能出现幻读，需通过间隙锁（GapLock）防止。16.数据库：Redis的常用数据结构及应用场景。解答：字符串（String）：缓存单个值（如用户信息JSON）、计数器（INCR命令）、分布式锁（SETkeyvalueNXPX）。哈希（Hash）：存储对象属性（如用户的name、age，对应hsetuser:1name"Alice"）。列表（List）：消息队列（LPUSH/RPOP）、最新动态（保留最近100条记录）。集合（Set）：去重数据（如用户标签）、交集/并集/差集（共同好友）。有序集合（ZSet）：排行榜（分数排序，如游戏积分）、时间序列（时间戳作为分数）。位图（BitMap）：统计活跃用户（按位标记登录状态）。HyperLogLog：估算基数（如UV统计）。17.数据库：缓存穿透、击穿、雪崩的区别及解决方案。解答：穿透：查询不存在的键（如id=-1），缓存不命中，请求直达数据库，压垮DB。解决：缓存空值（设置短过期时间）、布隆过滤器（预存所有可能的键，快速判断是否存在）。击穿：热点键过期，大量请求同时查询该键，缓存不命中，DB压力骤增。解决：互斥锁（查询缓存前加锁，仅一个线程查询DB并更新缓存）、永不过期（逻辑过期，异步更新）。雪崩：大量缓存同时过期，请求集中到DB。解决：过期时间分散（添加随机值）、多级缓存（本地缓存+分布式缓存）、限流降级（保护DB）。18.前端开发：Vue3响应式原理（与Vue2的区别）。解答：Vue3用Proxy替代Vue2的Object.defineProperty实现响应式。Proxy可监听对象的所有操作（属性增删、数组索引修改等），而Object.defineProperty只能监听已有属性的get/set，无法检测数组长度变化和属性新增。Vue3的响应式系统由reactive（处理对象）、ref（处理基本类型和对象）、effect（副作用函数）、track（依赖收集）、trigger（触发更新）组成。当访问响应式对象属性时，track收集当前activeEffect；当修改属性时，trigger触发所有依赖的effect重新执行。Vue3还支持组合式API（setup函数），更灵活的逻辑复用。19.前端开发：虚拟DOM（VDOM）的原理及diff算法。解答：虚拟DOM是真实DOM的JS对象表示（如{tag:'div',props:{class:'box'},children:[]}）。渲染时，将VDOM转换为真实DOM插入页面。当状态变化时，提供新的VDOM，与旧VDOM进行diff，仅更新变化的部分。diff算法遵循深度优先、同层比较原则：①比较根节点，若类型不同则替换整个子树；②类型相同则比较props（仅更新变化的属性）；③比较子节点，使用双指针遍历（旧前、旧后、新前、新后），通过key（唯一标识）复用节点，减少DOM操作。Vue的diff算法还优化了静态节点（跳过比较）和最长递增子序列（最小化移动操作）。20.前端开发：JavaScript事件循环（EventLoop）的执行机制。解答：JS是单线程，通过事件循环处理异步任务。执行栈先执行同步代码，遇到微任务（Promise.then、MutationObserver）加入微任务队列，遇到宏任务（setTimeout、setInterval、HTTP请求）加入宏任务队列。同步代码执行完毕后，依次执行微任务队列中的所有任务（清空队列），然后执行宏任务队列中的一个任务（浏览器可能渲染页面），重复此过程。注意：async/await本质是Promise的语法糖，await后面的代码相当于.then()，属于微任务。Node.js的事件循环分阶段（timers、I/Ocallbacks、idle/prepare、poll、check、closecallbacks），微任务在阶段切换时执行（如poll阶段结束后执行微任务）。21.分布式系统：CAP定理的含义及工程中的权衡。解答：CAP定理指分布式系统中，一致性（Consistency，所有节点同时看到相同数据）、可用性（Availability，每次请求都能得到非错误响应）、分区容错性（PartitionTolerance，网络分区时系统仍能运行）三者不可兼得，最多满足两个。工程中通常优先保证CP或AP：CP（如ZooKeeper、etcd）在分区时牺牲可用性，确保数据一致；AP（如RedisCluster、Cassandra）在分区时牺牲一致性（最终一致），保证可用。例如电商的购物车系统可能选AP（允许短暂不一致，最终同步），银行转账系统选CP（必须强一致）。22.分布式系统：一致性哈希的原理及解决的问题。解答：一致性哈希将哈希空间（如0~2^32-1）构成环，节点通过哈希值映射到环上。数据键哈希后顺时针找到最近的节点存储。当节点增加/删除时，仅影响环上相邻的少量数据，避免传统哈希（节点数变化时大量数据迁移）。解决的问题：分布式缓存的动态扩容/缩容时，数据迁移量小，提高系统可用性。例如，4个缓存节点A/B/C/D分布在环上，新增节点E，仅E与前一个节点之间的数据需要迁移。为解决节点分布不均（哈希倾斜），引入虚拟节点（每个物理节点映射多个虚拟节点到环上，均匀分布）。23.分布式系统：分布式锁的实现方式（Redis与ZooKeeper对比）。解答：Redis通过SETkeyvalueNXPXtimeout原子操作实现锁（NX保证只有一个客户端能设置成功，PX设置过期时间防死锁）。需处理锁过期但业务未完成的问题（可通过看门狗线程自动续期）。释放锁时需检查value是否匹配（防止误删其他客户端的锁，用Lua脚本保证原子性：ifredis.call('get',KEYS[1])==ARGV[1]thenreturnredis.call('del',KEYS[1])end）。ZooKeeper通过创建临时顺序节点实现锁：客户端在锁路径下创建临时顺序节点，若自己是最小节点则获得锁，否则监听前一个节点的删除事件（事件通知后重新检查）。优点：ZooKeeper支持公平锁（按创建顺序获取）、自动失效（会话过期则删除节点，无需设置超时）；缺点：性能低于Redis（每次锁操作涉及多次网络交互）。24.分布式系统：负载均衡的常见算法及适用场景。解答：轮询（RoundRobin）：按顺序分配请求，适合各节点性能相近的场景。加权轮询（WeightedRoundRobin）：根据节点性能分配权重（如高配置节点权重高），适合节点性能差异大的场景。最少连接（LeastConnections）：分配请求到当前连接数最少的节点，适合长连接场景（如数据库访问）。加权最少连接（WeightedLeastConnections）：连接数除以权重，选择值最小的节点，平衡性能与连接数。IP哈希（IPHash）：根据客户端IP哈希确定节点，保证同一客户端始终访问同一节点（适合需要会话保持的场景，如购物车）。一致性哈希（ConsistentHash）：如前面所述，适合分布式缓存的负载均衡。25.分布式系统：微服务中熔断与限流的区别及实现方式。解答：熔断（CircuitBreaker）：当被调用服务出错率超过阈值（如50%），打开断路器，直接拒绝后续请求（快速失败），避免级联故障。一段时间后进入半开状态，允许部分请求通过，若成功则关闭断路器，否则重新打开。实现如Hystrix、Resilience4J。限流（RateLimiting）：限制单位时间内的请求量，保护服务不被过量请求压垮。算法有固定窗口（统计固定时间窗口内的请求数）、滑动窗口（细分窗口，更精确）、漏桶（固定速率处理请求，溢出的请求丢弃）、令牌桶（以固定速率提供令牌，有令牌才能处理请求）。例如，API网关用令牌桶限制每个客户端每秒最多100次请求。26.后端开发：JVM内存模型及垃圾回收（GC）的主要区域。解答：JVM内存分堆（Heap，存储对象实例，线程共享，分年轻代、老年代）、方法区（存储类信息、常量、静态变量，JDK8后为元空间，使用本地内存）、虚拟机栈（存储栈帧，每个方法调用对应一个栈帧，含局部变量表、操作数栈等，线程私有）、本地方法栈（为本地方法服务）、程序计数器（记录当前线程执行的字节码行号，线程私有）。GC主要回收堆内存。年轻代（Eden区+两个Survivor区）：新对象在此分配，MinorGC回收，采用复制算法（存活对象复制到Surv