多益网络软件开发笔试：18 道选择加 6 道简答加 1 道编程

《面试题目》

1. 选择题 18 道，主要考察数据结构（树、图、排序）、网络（哪些 IP 地址不是私有地址）以及 MySQL。
2. 简答题：把一段关于「粒子系统」的英文材料翻译成中文。
3. 哈希冲突是什么？
4. 弱引用的定义和使用场景是什么？
5. 多线程和多进程有什么区别？
6. MySQL 有哪些优缺点？
7. IP、ARP、RARP、ICMP 的定义和作用分别是什么？
8. 编程题：判断一棵树是不是平衡二叉树，要求 O(n) 时间复杂度。

《参考解析》

O(n) 判断平衡二叉树：平衡二叉树的定义是每个节点左右子树的高度差不超过 1，所以不能只看根节点，也不能对每个节点各求一次高度——那样是 O(n²)。自顶向下的重复计算来自「求高度时反复遍历同一棵子树」，改成自底向上的后序遍历即可：递归函数返回该子树的高度，同时用返回 -1 表示「这棵子树已经不平衡」。对每个节点先拿左右子树的高度，任一为 -1 就直接向上返回 -1；否则比较两者差值，超过 1 返回 -1，不超过则返回 max(左, 右) + 1。每个节点只被访问一次，时间 O(n)；递归深度等于树高，空间 O(h)，最坏（退化成链）是 O(n)，这点面试官常追问——如果树可能很深，就要改成显式栈加后序状态标记，或者用「求树高的迭代写法」避免爆栈。空树与单节点树都算平衡，边界别漏。

哈希冲突：不同 key 经过哈希函数算到同一个槽位就是冲突，理论上无法根除（鸽巢原理：key 空间通常远大于桶数量）。主流处理方式两类：链地址法（每个桶挂一条链表或红黑树，Java 的 HashMap 就是链表长度超过 8 且表长不小于 64 时转红黑树，避免极端情况下退化成 O(n)）和开放寻址法（线性探测、二次探测、双重哈希，冲突时按探测序列找下一个空位，删除要打墓碑标记，否则会截断后续探测链）。衡量指标是负载因子 元素数 / 桶数，超过阈值就扩容并重新散列，HashMap 默认 0.75。工程上还要注意两点：哈希函数要足够均匀（对 Java 的 String，hashCode 再异或上高 16 位就是为了打散低位规律）；自定义对象做 key 必须同时正确重写 hashCode 与 equals，只重写一个会导致「存进去查不出来」。

弱引用：弱引用指向的对象只被弱引用持有时，下一次 GC 就会被回收，即使内存并不紧张。Java 里的引用强度从强到弱是强引用 → SoftReference（内存不足才回收，适合做缓存）→ WeakReference（下次 GC 必回收）→ PhantomReference（无法通过它拿到对象，只在对象被回收后进引用队列，用于清理堆外资源）。典型使用场景有三个：一是做缓存的 key 或值，避免缓存把对象永久钉在内存里，WeakHashMap 就是这个思路（key 被回收后条目自动失效）；二是 ThreadLocal，ThreadLocalMap 的 Entry 用弱引用指向 ThreadLocal 本身，配合 remove() 防止线程池里线程长期存活导致 value 泄漏——注意弱引用只解决了 key 的泄漏，value 仍要手动清；三是监听器、回调注册表，避免被注册方无法释放。面试追问常见「ThreadLocal 为什么会内存泄漏」，答清「key 弱引用会被回收变成 null，但 value 仍被 Entry 强引用，线程不结束就一直挂着，所以必须 remove()」即可。

私有 IP 地址范围：判断「哪些 IP 不是私有地址」靠背下三段保留网段——A 类 10.0.0.0/8（10.0.0.0 ~ 10.255.255.255）、B 类 172.16.0.0/12（172.16.0.0 ~ 172.31.255.255）、C 类 192.168.0.0/16（192.168.0.0 ~ 192.168.255.255）。容易混进来当干扰项的是另外几类特殊地址：127.0.0.0/8 是回环地址，169.254.0.0/16 是链路本地地址（DHCP 拿不到地址时自动配置），0.0.0.0/8、224.0.0.0/4 组播、240.0.0.0/4 保留，它们都不是「私有地址」。做这类题时把 172.16 到 172.31 的第二段范围记死（很多人会误以为整个 172.x 都是私有），192.168 后面跟的第三段任意。另外要区分：私有地址是 RFC 1918 定义的、只在内部网络使用、需要 NAT 才能出公网；而回环与链路本地地址是另一种用途，答题时别混为一谈。