计算机基础面试题
测试开发工程师必背 | 数据结构 + 计算机网络 + 数据库
一、数据结构与算法
ArrayList 和 LinkedList 的区别？各适用于什么场景？
ArrayList 基于动态数组，底层是 Object[]，支持下标随机访问（O(1)），但插入/删除需要移动元素（最坏 O(n)）。LinkedList 基于双向链表，插入/删除只需修改前后指针（O(1)），但查询需要遍历（O(n)）。场景：频繁随机访问用 ArrayList，频繁增删用 LinkedList。队列/栈实现优先选 LinkedList。
HashMap 的底层实现原理？JDK 1.8 有什么优化？
HashMap 底层是数组 + 链表（桶），通过 hash(key) % length 确定桶位置。JDK 1.8 优化：① 链表改尾插法，避免 resize 时的死循环；② 当链表长度 > 8 且数组长度 >= 64 时，转红黑树（查询从 O(n) 优化到 O(log n)），长度 <= 6 时退化为链表。
HashMap 和 Hashtable 的区别？ConcurrentHashMap 呢？
HashMap：线程不安全，允许 null 键/值。Hashtable：线程安全（synchronized 加全局锁），不允许 null。ConcurrentHashMap：JDK 1.7 用分段锁（Segment 数组，每段一把锁），JDK 1.8 改用 CAS + synchronized，锁粒度细化到每个桶，并发性能大幅提升。
常见排序算法的时间复杂度？快速排序最坏情况是什么？
快速排序 O(n log n)（平均/最优），最坏 O(n²)（数据有序时）；归并排序 O(n log n)（稳定）；堆排序 O(n log n)；冒泡/插入排序 O(n²)；选择排序 O(n²)。面试能描述快排分治思路 + 最坏情况即可。
栈和队列的区别？应用场景？
栈是 LIFO（后进先出），队列是 FIFO（先进先出）。栈用于函数调用栈、括号匹配、表达式求值、撤销操作。队列用于任务调度、BFS 广度优先搜索、线程池任务队列、消息队列。
什么是红黑树？为什么 HashMap 用它而不是平衡二叉树？
红黑树是一种自平衡二叉查找树，通过红黑节点着色规则保持大致平衡（插入/删除操作只需 O(log n) 的旋转和重着色，比严格平衡树（如 AVL）的旋转次数少）。HashMap 使用红黑树是因为：严格平衡意味着更多的旋转操作，在频繁插入删除场景下性能开销大；红黑树的查找性能和平衡性足够满足 HashMap 的需求。
什么是堆（Heap）？有哪些应用场景？
堆是一种完全二叉树，分为最大堆（父节点大于等于子节点）和最小堆（父节点小于等于子节点）。应用：① 优先级队列（Java PriorityQueue）；② Top K 大/小问题（维护一个大小为 K 的最小堆）；③ 合并 K 个有序链表；④ 实时流数据中位数（双堆法）。
B 树和 B+ 树的区别？为什么数据库索引用 B+ 树而不是 B 树？
B 树：每个节点都存储键和数据，所有节点（包括叶子节点）都在同一层。B+ 树：只有叶子节点存储数据（完整数据或指针），非叶子节点只存储键；叶子节点之间通过双向链表连接。数据库选 B+ 树的原因：① 叶子节点链表连接，支持范围查询更快；② 非叶子节点不存数据，每个节点能容纳更多键，树层数更浅，I/O 次数更少；③ 查询效率更稳定（都查到叶子）。
布隆过滤器（Bloom Filter）是什么？有什么应用？
布隆过滤器是一种概率数据结构，使用 k 个哈希函数将元素映射到位数组的 k 个位置。用于快速判断"一个元素一定不存在或可能存在"。特点：查询极快（O(k)）、空间效率高；存在假阳性（可能误判存在），但不会假阴性。应用：Redis 缓存穿透防护、爬虫 URL 去重、黑名单校验。
什么情况下用数组，什么情况下用链表？
用数组：需要快速随机访问（O(1) 查询）、数据量固定或接近固定、不频繁增删。用链表：需要频繁在任意位置插入/删除、数据量动态变化、无法预知大小。补充：JDK ArrayList 是动态数组，在容量不足时自动扩容（1.5 倍），适合"读多写少"场景；LinkedList 是双向链表，适合"写多读少"场景。
如何判断链表有环？快慢指针的原理？
使用快慢指针（Floyd 算法）：慢指针每次走一步，快指针每次走两步。如果链表中存在环，两指针会在环内相遇（快指针追上慢指针）。时间复杂度 O(n)，空间复杂度 O(1)。进阶：进一步可以找到环的入口节点（数学推导：相遇点到入口的距离 = 头节点到入口的距离）。
什么是拓扑排序？应用场景？
拓扑排序是对有向无环图（DAG）的所有节点进行线性排序，使得对于每条有向边 (u, v)，节点 u 都在节点 v 之前。方法：Kahn 算法（维护入度为 0 的队列，依次删除）。应用：任务调度（课程表问题、Makefile 依赖构建）、项目编译顺序、任务分配。
图：有向图和无向图有什么区别？DFS 和 BFS 的区别？
有向图的边有方向，无向图的边无方向（可看作双向有向）。DFS（深度优先）：用栈/递归，优先深入，适合找路径、拓扑排序。BFS（广度优先）：用队列，层层扩展，适合找最短路径、层次遍历。
什么是哈希冲突？如何解决？
哈希冲突：不同 key 通过 hash 函数计算得到相同的桶下标。解决方法：① 链地址法（HashMap 使用，每个桶存链表/红黑树）；② 开放定址法（线性探测、二次探测）；③ 再哈希法（用多个 hash 函数依次探测）；④ 建立公共溢出区。HashMap 采用链地址法 + 红黑树优化。
一致性哈希算法是什么？解决什么问题？
一致性哈希将哈希值空间组织成一个环（2^32），每个节点映射到环上一点，数据 key 顺时针找到第一个节点存储。解决的问题：普通哈希在节点数量变化时大量数据需要重新映射（缓存雪崩）。优点：节点增减时只影响相邻节点。改进：引入虚拟节点，使数据分布更均匀（HashMap/Redis 集群/分布式缓存使用）。
二、计算机网络
TCP 三次握手和四次挥手的过程？为什么需要三次？
三次握手：① Client 发送 SYN -> ② Server 收到回 SYN+ACK -> ③ Client 回 ACK。建立连接需要双方确认彼此的发送+接收能力均正常，三次是理论最小值。四次挥手：① Client 发 FIN -> ② Server 回 ACK -> ③ Server 处理完数据发 FIN -> ④ Client 回 ACK。比握手多两步是因为 TCP 全双工，Server 收到 FIN 后先回 ACK，等应用层处理完再发自己的 FIN。
HTTP 和 HTTPS 的区别？HTTPS 的加密过程？
HTTP 明文传输（端口 80），HTTPS 是 TLS/SSL 加密传输（端口 443）。HTTPS 流程：Client 请求证书 -> Server 发送数字证书 -> Client 验证证书有效性 -> Client 用证书中的公钥加密随机对称密钥发给 Server -> Server 用私钥解密，后续通信用对称加密（性能更高）。数字证书由 CA 机构签发，防止中间人攻击。
GET 和 POST 的区别？
GET：参数拼接在 URL（?a=1&b=2），长度受限（约 2KB），可被浏览器缓存，适用于查询。POST：参数在请求体，更安全（参数不在 URL 中），长度无限制，不缓存，适用于提交数据。本质是 HTTP 方法定义，GET 也可不安全，POST 也可被缓存，区别不是绝对的。
HTTP 常见状态码？
2xx 成功：200 OK、201 Created、204 No Content。3xx 重定向：301 永久、302 临时、304 Not Modified（缓存）。4xx 客户端错误：400 参数错误、401 未认证、403 无权限、404 未找到。5xx 服务端错误：500 服务器异常、502 网关错误、503 服务不可用、504 网关超时。
TCP 和 UDP 的区别？各自适用场景？
TCP：面向连接、可靠传输（有确认、重传、流控）、首部 20 字节、速度慢。UDP：无连接、不可靠（无确认无重传）、首部 8 字节、速度快。场景：TCP 用于文件传输、HTTP/HTTPS、邮件（SMTP）；UDP 用于视频流、直播、DNS 解析、VoIP、游戏。
什么是 TCP 滑动窗口？有什么用？
滑动窗口是 TCP 的流量控制机制：发送方维护一个窗口大小，表示"不需要等待确认就能发送多少数据"。接收方通过 ACK 携带窗口大小告知发送方自己还能接收多少数据。发送方窗口滑动：已确认的数据移出窗口，新的数据进入窗口。作用：避免发送方速度过快导致接收方缓冲区溢出，提高网络利用率。
TCP 如何保证可靠传输？
① 校验和：检测数据传输错误，错误则丢弃。② 确认机制（ACK）：接收方对收到的数据进行确认。③ 超时重传：发送方在超时时间内没收到 ACK 则重发。④ 流量控制（滑动窗口）：避免发送过快。⑤ 拥塞控制：慢启动、拥塞避免、快速恢复，控制网络拥塞。
HTTP 1.0、1.1、2.0、3.0 的主要区别？
HTTP 1.0：每个请求建立一个 TCP 连接，用完即关。HTTP 1.1：支持持久连接（Connection: keep-alive），支持管道化（请求可以并行发出），支持虚拟主机（Host 头）。HTTP 2.0：多路复用（一个 TCP 连接上并行多个请求）、头部压缩（HPACK）、服务器推送、请求优先级。HTTP 3.0（QUIC）：基于 UDP，实现类似 TCP 的可靠传输，0-RTT 连接建立，彻底解决队头阻塞问题。
Cookie 和 Session 的区别？
Cookie：存储在浏览器端（客户端），数据量有限（通常 < 4KB），可以长期保存。Session：存储在服务器端，数据量无限制，安全性更高。区别：Cookie 适合存储少量不敏感数据（如偏好设置）；Session 适合存储用户登录状态等敏感数据。Session 通常通过 Cookie 中的 Session ID 来关联。
DNS 解析的过程？
① 浏览器检查自身缓存 → ② 检查操作系统缓存（hosts 文件）→ ③ 请求本地域名服务器（LDNS，通常是 ISP 提供）→ ④ LDNS 请求根域名服务器 → ⑤ LDNS 请求顶级域名服务器（.com）→ ⑥ LDNS 请求权威域名服务器 → ⑦ 获取 IP 返回给客户端，并缓存。递归查询和迭代查询结合。
ARP 协议的作用？
ARP（地址解析协议）用于根据 IP 地址获取物理地址（MAC 地址）。过程：主机在本地网络广播 ARP 请求（"谁是 IP xxx"），对应 IP 的主机回复 ARP 响应（包含自己的 MAC 地址）。 ARP 缓存表存储 IP-MAC 映射，定期更新或超时删除。
什么是 ARP 攻击？测试中如何发现？
ARP 攻击：攻击者发送伪造的 ARP 报文，将自己的 MAC 地址绑定到合法 IP 上，导致同网段其他主机的流量经过攻击者。测试发现方法：① 查看 ARP 表是否有重复 MAC 绑定不同 IP；② 使用 ARP 防火墙或 Wireshark 抓包检测异常 ARP 响应；③ 检查网络延迟是否异常增大；④ 查看交换机 MAC 地址表是否异常。
输入 URL 到页面展示，发生了什么？
① DNS 解析获取 IP；② 建立 TCP 连接（三次握手）；③ 发起 HTTP/HTTPS 请求；④ 服务器处理返回 HTML；⑤ 浏览器解析 HTML 构建 DOM 树；⑥ 解析 CSS 构建 CSSOM；⑦ 合并生成渲染树（Render Tree）；⑧ 计算布局（Layout）；⑨ 绘制（Paint）；⑩ 合成图层并显示（Composite）。涉及 CDN、DNS 缓存、浏览器缓存（强缓存/协商缓存）等优化点。
强缓存和协商缓存的区别？
强缓存：不发请求，直接从本地缓存读取。命中强缓存返回 200（from cache）。通过 Cache-Control（max-age）和 Expires 控制。协商缓存：发请求到服务器，服务器判断资源是否更新。未更新返回 304（Not Modified），从缓存读取；更新了返回新资源。通过 ETag/If-None-Match 和 Last-Modified/If-Modified-Since 控制。实际使用：静态资源（CSS/JS/图片）用强缓存 + 协商缓存配合。
WebSocket 和 HTTP 的区别？
HTTP 是请求-响应模型，服务器不能主动向客户端推送数据（除非用轮询/长轮询）。WebSocket 是持久连接协议，握手基于 HTTP（Upgrade 头），建立后全双工通信，服务器和客户端可随时互相发送消息。应用场景：实时聊天、在线游戏、股票行情推送、协同编辑。HTTP 2.0 的服务器推送在一定程度上可替代部分场景。
三、数据库 MySQL
MySQL 索引有哪些类型？索引的优缺点？
类型：主键索引（唯一非空）、唯一索引、普通索引、全文索引、复合索引。优点：大幅加速查询。缺点：占用磁盘空间，增加写操作（INSERT/UPDATE/DELETE）开销，不宜过多。索引列应选择区分度高的字段（如用户ID），避免在性别、状态这类低区分度列上建索引。
事务的四大特性（ACID）？
原子性（Atomicity）：事务是最小执行单元，要么全成功，要么全失败回滚。一致性（Consistency）：事务前后数据库状态保持一致（如转账总额不变）。隔离性（Isolation）：并发事务之间相互隔离。持久性（Durability）：提交后数据永久保存到磁盘。
MySQL 的四种隔离级别？分别解决了什么问题？
① Read Uncommitted（读未提交）：最低级别，存在脏读（读到未提交的数据）。② Read Committed（读已提交）：解决了脏读，但存在不可重复读（同一次事务两次读取结果不同）。③ Repeatable Read（可重复读，MySQL 默认）：解决了不可重复读，但标准 SQL 中存在幻读（同一事务中新出现的记录）。④ Serializable（串行化）：完全隔离，性能最差，串行执行所有事务。MySQL InnoDB 通过 MVCC + Next-Key Lock 在 RR 级别下解决了幻读问题。
什么是 MVCC？它解决了什么问题？
MVCC（多版本并发控制）是一种读写并发控制技术，通过保存数据的多个版本，使读操作不需要加锁，从而提高并发性能。每个事务看到的是某个时间点的数据快照。解决的问题：① 在 RR 隔离级别下实现可重复读，避免脏读和不可重复读；② 读操作不阻塞写操作，写操作不阻塞读操作，大幅提升并发能力。InnoDB 通过隐藏列（事务ID + 回滚指针）+ Undo 日志 + Read View 实现 MVCC。
SQL：查询每个科目成绩最高的学生姓名？
-- 写法一：子查询
SELECT s.name, sc.score
FROM student s
JOIN score sc ON s.id = sc.student_id
JOIN (
SELECT subject_id, MAX(score) as max_score
FROM score
GROUP BY subject_id
) m ON sc.subject_id = m.subject_id AND sc.score = m.max_score;
-- 写法二：窗口函数
SELECT * FROM (
SELECT s.name, sc.score,
ROW_NUMBER() OVER(PARTITION BY sc.subject_id ORDER BY sc.score DESC) as rn
FROM student s JOIN score sc ON s.id = sc.student_id
) t WHERE rn = 1;SQL：查询课程成绩排名前三的学生？
-- 写法一：窗口函数
SELECT * FROM (
SELECT s.name, sc.score,
ROW_NUMBER() OVER(PARTITION BY subject_id ORDER BY score DESC) as rn
FROM student s JOIN score sc ON s.id = sc.student_id
) t WHERE rn <= 3;
-- 写法二：相关子查询
SELECT * FROM student s
WHERE (SELECT COUNT(*) FROM score sc2
WHERE sc2.subject_id = s.subject_id AND sc2.score > s.score) < 3;MyISAM 和 InnoDB 的区别？
MyISAM：支持表级锁，不支持事务和外键，支持全文索引，适用读多写少场景，查询速度较快。InnoDB：支持行级锁（并发高），支持事务（ACID）和外键，支持 MVCC，崩溃恢复能力更强，适用写多或需要事务的场景。5.5 版本后 MySQL 默认存储引擎改为 InnoDB。
什么是数据库慢查询？如何优化？
慢查询：执行时间超过 long_query_time 阈值（默认 10s）的查询。优化方法：① EXPLAIN 分析执行计划，检查是否走索引、是否有全表扫描；② 检查 WHERE 条件字段是否有索引、索引是否失效（函数/类型转换导致索引失效）；③ 优化 SQL（避免 SELECT *、避免 OR、避免子查询过多）；④ 分表分库；⑤ 读写分离；⑥ 增加缓存层（Redis）。
什么是 SQL 注入？如何防止？
SQL 注入：攻击者在输入参数中注入恶意 SQL 语句，绕过验证或获取非法数据。防止方法：① 使用参数化查询/预编译语句（PreparedStatement），将 SQL 结构和数据分离；② 严格验证输入数据类型和格式；③ 对特殊字符转义（'、"、--、;）；④ 最小权限原则，数据库账号不要给 DBA 权限之外的过高权限；⑤ 使用 ORM 框架（Hibernate/MyBatis）自动处理转义。
内连接、左连接、右连接的区别？
内连接（INNER JOIN）：只返回两个表满足连接条件的记录。左连接（LEFT JOIN）：返回左表全部记录，右表没有匹配的字段填 NULL。右连接（RIGHT JOIN）：返回右表全部记录，左表没有匹配的字段填 NULL。全连接（FULL OUTER JOIN）：返回两个表的全部记录，不匹配的填 NULL（MySQL 不直接支持，可用 UNION 实现）。
Redis 和 MySQL 的区别？各自适用场景？
Redis 是内存数据库（支持持久化），MySQL 是磁盘关系数据库。Redis：基于内存，读写性能极高（10W+ QPS），支持 String/Hash/List/Set/ZSet 等数据结构，适用缓存、计数器、排行榜、实时消息队列、会话存储。MySQL：支持复杂 SQL 查询、事务、联表操作，适用需要持久化、关系型数据、一致性要求高的场景。通常两者配合使用：Redis 做缓存层加速访问，MySQL 做持久化存储。
数据库三大范式是什么？
第一范式（1NF）：字段不可再分，即每个字段都是原子值。第二范式（2NF）：在满足 1NF 基础上，所有非主键字段完全依赖主键（消除部分依赖，单主键时自动满足）。第三范式（3NF）：在满足 2NF 基础上，非主键字段之间不存在传递依赖（消除传递依赖）。实际工作中适度反规范化（增加冗余字段）以提升查询性能。
MySQL 执行一条 SELECT 语句的完整过程？
① 连接器：建立 TCP 连接，验证用户身份。② 查询缓存（MySQL 8.0 已移除）：检查是否有缓存结果。③ 解析器：词法分析 + 语法分析，生成解析树。④ 预处理器：检查表/列是否存在、权限等。⑤ 优化器：根据成本生成执行计划（选择索引、决定 JOIN 顺序等）。⑥ 执行器：调用存储引擎 API 执行查询。⑦ 存储引擎：InnoDB 从磁盘/Memory 读取数据。⑧ 返回结果（若命中查询缓存则直接返回）。