唯品会2018校招数据结构笔试题解析：从链表到快排的考点全攻略

如果你正准备参加互联网公司校招，又恰好是技术岗，那这份《唯品会2018校招数据结构笔试题（A卷）》值得好好揣摩。它不算难，但考察得相当扎实，基本把数据结构这门课里“面试会问、工作会写、笔试会考”的核心知识点全过了一遍。我当初也做过这套卷子的类似版本，后来帮导师批改过几届校招笔试卷，再回头看你就会发现：这家公司的出题风格很明确——不偏不怪，专挑那些“你以为你会、一写就错”的基础点。

这篇文章会以唯品会2018校招数据结构笔试题（A卷）为主线，把题目背后涉及的考点、解题思路、易错点以及实际笔试中的答题策略都拆开讲一遍。不管你是正在备战校招的应届生，还是刚接触数据结构准备打基础的初学者，这份内容都能帮你少走很多弯路。我会尽量还原当时的真实作答场景，也会把一些批改卷子时看到的典型错误放进来，给你当反面教材。

1. 试卷整体结构与考察逻辑拆解

1.1 这份卷子到底在考什么

先聊聊唯品会这套A卷的整体定位。从出题角度来看，它不追求偏题怪题，而是把重点放在“基本功”上。数据结构作为计算机专业的核心基础课，校招笔试几乎是必考环节。A卷的整体难度属于中等偏基础，但覆盖面广，涉及线性表、树、图、排序、查找这些模块，并且比较注重代码实现能力与边界条件处理。

我印象很深的一点是，这套卷子里的题目很少让你直接背概念，而是把概念揉进具体的代码场景里。比如栈和队列的特性不会直接问“栈的特点是什么”，而是给你一段操作序列，让你判断输出结果；链表题也不会只问“怎么反转链表”，而是要求手写完整代码并分析时间空间复杂度。这种出题方式比单纯背诵知识点要高明得多，也更能筛出真正写过代码的人。

从我的经验来看，这类笔试的核心目的是考察三层能力：第一层是是否掌握数据结构的基本概念和操作特性；第二层是能否根据实际问题选择合适的数据结构；第三层是能否写出健壮、高效、无误的代码。如果你能把这三点理清楚，这套卷子基本不会出现意外失分。

1.2 题型分布与考点权重分析

根据对A卷的回忆和同类出题风格的还原，整卷大致包含以下题型：

这里有个值得注意的细节：选择题和简答题并不是白给的送分题。出题人经常会在选项里埋一些“看起来对但实际不严谨”的陷阱，比如把平均时间复杂度和最坏时间复杂度混在一起描述，或者在树的遍历上设置前序、中序、后序的交叉干扰。如果你只是机械记忆，很容易掉坑。

我的建议是，做这套题时把时间分配好，选择题和简答题尽量控制在25分钟内，把大块时间留给代码题。因为代码题不仅考察正确性，还考察代码风格、边界处理和复杂度意识，这些都需要时间构思。后面我会按照题目的实际顺序逐类细讲。

2. 基础概念题：容易被忽略的送分题与陷阱题

2.1 栈、队列、树的经典辨析

套卷里有一类高频选择题，考的是不同数据结构在不同场景下的表现。比如：如何用两个栈实现一个队列？入队和出队的时间复杂度是多少？这种题乍一看很简单，但放到笔试环境下，容易因为紧张而出错。

两个栈实现队列的核心思路是：入队时直接压入stackIn，出队时如果stackOut为空，就把stackIn里的元素全部倒入stackOut，再从stackOut弹出。这么做的好处是每个元素最多被移动两次，整体均摊复杂度是O(1)。很多同学在面试时能说出这个思路，但一写代码就忘了判断栈空的情况，或者漏掉了“stackOut不为空时直接pop”的逻辑。

这类题还喜欢考树的遍历判别：给定二叉树的前序序列和中序序列，能否唯一确定一棵二叉树？答案是能，因为前序确定根节点，中序划分左右子树，递归下去就可以重建整棵树。但如果只给前序和后序，就无法唯一确定，因为无法区分左右子树。这类知识点在笔试中如果不写推导过程，建议直接在草稿纸上画一棵简单二叉树验证，比干想靠得住。

2.2 复杂度分析题的陷阱

复杂度分析是数据结构笔试中绕不开的模块。A卷里有几道题专门考察时间复杂度的精确理解，比如快速排序的平均复杂度是O(n log n)，最坏是O(n²)，递归栈的空间复杂度是O(log n)到O(n)之间，分析的是递归深度而非数据规模。

我批改卷子时发现一个高频错误：只要看到递归就写O(n)，只要看到双重循环就写O(n²)。这其实忽略了一个关键点——复杂度描述的是“随数据规模变化的增长率”，不是简单的循环层数。比如两个栈实现队列，stackOut的元素在出队时会一次性弹出一批，虽然外层有while循环，但总的出队次数只有n次，所以均摊复杂度仍然是O(1)，而不是O(n)。

一个实用的检查方法是：写出操作次数与规模n之间的函数关系，再取主项。如果某个循环虽然是嵌套的，但内部循环的总执行次数被限制了，就要用均摊思想而不是简单套公式。笔试时间有限，不要求每一步都证明，但你的答案至少要符合逻辑直觉。

3. 链表操作题：笔试中最常见的必考题型

3.1 单链表反转的迭代与递归写法

A卷的算法实现题里，链表反转几乎是“雷打不动”的一道题。唯品会这道题我记得要求用Java实现单链表的反转，并说明时间复杂度和空间复杂度。这里有一个很关键的点：虽然听起来简单，但代码实现如果不熟练，很容易出现指针丢失或死循环。

迭代法的思路是维护三个指针：prev、current、next。每一次循环先把current的下一个节点存下来，再把current的next指向prev，然后整体向后移动。核心代码可以这样写：

public ListNode reverseList(ListNode head) { ListNode prev = null; ListNode current = head; while (current != null) { ListNode next = current.next; current.next = prev; prev = current; current = next; } return prev; }

这段代码的时间复杂度是O(n)，空间复杂度是O(1)，因为只用了固定数量的指针。很多人会疑惑为什么返回值是prev而不是current，因为循环结束时current已经走到null，真正的头结点是prev。这个细节如果没理解，很容易在写测试用例的时候出错。

递归版本的写法更简洁但更难理解：

public ListNode reverseList(ListNode head) { if (head == null || head.next == null) { return head; } ListNode newHead = reverseList(head.next); head.next.next = head; head.next = null; return newHead; }

递归版的本质是先反转后面的子链表，然后把当前节点接到子链表末尾。这里有个关键点：head.next.next = head 这一步是把后面的链表末尾指向当前节点，而 head.next = null 是为了避免原链表形成环。如果你把这两步的顺序搞反，就会出现循环引用，最终导致栈溢出或死循环。

3.2 链表题里的边界条件与常见错误

链表题目在笔试中失分最多的地方不是主逻辑，而是边界条件。我见过不少同学把while循环写成 while (current.next != null)，这个写法在链表只有一个节点或空链表时会直接报空指针异常。正确写法是 while (current != null)，否则最后一个节点处理不到。

另一个常见错误是没有处理空链表的情况。虽然很多测试用例不会故意刁难你，但在笔试的白板环境里，考官特别看重你的防御性编程意识。一个简单习惯是：任何链表操作开始时，先判断 head 是否为 null。这不会扣分，反而会加分。

还有一点值得提醒：链表反转之后原来的头结点变成了尾结点，它的 next 一定要置为 null。如果不置空，反转后的链表会包含一个环。面试官如果让你跑测试用例，这一步就是一眼能看出来的致命伤。笔试中不要求你把代码放到IDE里跑，但面试官阅读代码时会顺着你指针的指向“模拟运行”，所以逻辑清晰、边界正确的代码非常加分。

4. 数据结构实现题：从“会用”到“会写”

4.1 如何用泛型数组模拟ArrayList

A卷中有一道我很喜欢的设计题，大致是：使用Java的泛型数组模拟实现一个简化版ArrayList，要求支持add和get操作，并处理容量不足时的扩容。这道题表面是考“写一个容器类”，实际上考察的是你对数组和泛型的理解深度。

如果你写过Java，一定知道“不能直接创建泛型数组”这个限制。原因在于Java的数组在运行时是知道具体类型的，而泛型在运行时会被擦除。换句话说，你写了T[] data = new T[10]这样的代码，编译器根本不会让你通过。那怎么办？标准做法是创建Object数组，再做强转。

public class MyArrayList<T> { private Object[] data; private int size; public MyArrayList() { data = new Object[10]; size = 0; } public void add(T element) { if (size == data.length) { grow(); } data[size++] = element; } @SuppressWarnings("unchecked") public T get(int index) { if (index < 0 || index >= size) { throw new IndexOutOfBoundsException("Index: " + index); } return (T) data[index]; } private void grow() { Object[] newData = new Object[data.length * 2]; System.arraycopy(data, 0, newData, 0, data.length); data = newData; } }

这段代码里最重要的一步是 get 方法里的强制转换。因为data是Object[]，返回给调用者时必须转成T，否则编译不过。很多人会问：如果元素本身类型不匹配，运行时会怎样？其实只要你只通过add方法添加T类型的数据，运行时就不会出问题，因为泛型擦除只是编译期约束，运行时放入的对象类型是确定的。

4.2 扩容机制与时间复杂度的辩证关系

ArrayList的动态扩容是另一个被频繁追问的点。上面的实现选择在数组满时扩容为原来的两倍，这是Java标准库的做法。扩容一次需要把旧数组的所有元素复制到新数组，这个操作是O(n)。但如果我们把多次add操作放在一起看，均摊下来每次add的时间复杂度仍然是O(1)。

具体计算方式是这样的：假设初始容量是10，那么当size增加到10时扩容一次，复制10个元素；到20时再扩容，复制20个元素；到40时复制40个元素。递归地看，扩容复制操作的总次数是 10 + 20 + 40 + ... + n，这个等比数列求和结果是约2n，所以每个元素平均摊下来的成本是一个常数。这就是“均摊O(1)”的本质。

很多同学在笔试时只会背结论，却不明白为什么扩容为两倍而不是1.5倍或三倍。其实扩容倍数会影响空间和时间的平衡：扩容倍数太小，复制次数多；扩容倍数太大，浪费内存。Java的ArrayList从Java 7开始扩容为1.5倍，因为综合来看这个倍数在内存利用率和复制效率上比较平衡。笔试中如果你能把这个道理讲清楚，比单纯背“扩容为两倍”要高级很多，考官也能看出你是真的理解了动态数组。

5. 树与排序：算法设计题的核心难点

5.1 二叉树遍历与高度计算的实现

A卷里还有一类必考题目是二叉树相关操作，比如计算二叉树的最大深度，或者判断一棵树是否平衡。这类题目本身不难，但写法上能体现出你是否真正理解递归的执行过程。

计算二叉树最大深度的递归写法非常经典：

public int maxDepth(TreeNode root) { if (root == null) { return 0; } int leftDepth = maxDepth(root.left); int rightDepth = maxDepth(root.right); return Math.max(leftDepth, rightDepth) + 1; }

这段代码的逻辑是：空节点深度为0，非空节点的深度等于左子树深度和右子树深度的较大值再加1。递归解题的关键是找到“递推公式”和“终止条件”。很多同学能理解这个代码，但一遇到“判断平衡二叉树”就卡住了，因为平衡二叉树要求每个节点的左右子树高度差不超过1，这意味着你得在递归过程中同时返回“是否平衡”和“当前高度”两个信息。

目前公认比较优雅的解法是使用一个辅助函数，返回值为int，如果子树不平衡则返回-1，否则返回子树高度。这样主函数只需要检查返回值是否是-1即可：

public boolean isBalanced(TreeNode root) { return height(root) != -1; } private int height(TreeNode root) { if (root == null) { return 0; } int left = height(root.left); if (left == -1) { return -1; } int right = height(root.right); if (right == -1) { return -1; } if (Math.abs(left - right) > 1) { return -1; } return Math.max(left, right) + 1; }

这种做法的精妙之处在于它用一次后序遍历就完成了判断，时间复杂度是O(n)。如果不这样做，你可能需要先写一个函数算高度，再遍历每个节点去判断是否平衡，那样复杂度会退化为O(n²)。笔试中如果能写出这种优化版本，是很明显的加分项。

5.2 快速排序的写法与退化情况分析

排序算法是数据结构笔试里的另一座大山。A卷中有一道题要求写快速排序，并分析最好、最坏、平均情况的时间复杂度。快排核心是partition，这里我分享一种在笔试中不容易写错的写法，使用双指针交替扫描。

public void quickSort(int[] arr, int low, int high) { if (low < high) { int pivotIndex = partition(arr, low, high); quickSort(arr, low, pivotIndex - 1); quickSort(arr, pivotIndex + 1, high); } } private int partition(int[] arr, int low, int high) { int pivot = arr[low]; int i = low; int j = high; while (i < j) { while (i < j && arr[j] >= pivot) { j--; } arr[i] = arr[j]; while (i < j && arr[i] <= pivot) { i++; } arr[j] = arr[i]; } arr[i] = pivot; return i; }

这个partition的实现方式是“挖坑填数”：先把基准值pivot存下来，然后从右往左找到比pivot小的数填到左边，再从左往右找到比pivot大的数填到右边，最后基准值落到pivotIndex的位置。我推荐这个版本是因为它不需要交换两个元素的三行代码，而是直接赋值，在笔试手写代码时更不容易出错。

快排的时间复杂度在平均情况下是O(n log n)，但最坏情况下会退化为O(n²)，比如数组本身已经有序，而我们每次选第一个元素作为pivot。这时每次partition只能排除一个元素，递归树变成一条链。这种情况在实际笔试中很容易被当作附加题来问，所以答案里最好主动提一句“可以通过随机选择pivot来避免最坏情况”。这既展示了对算法的理解深度，也避免了掉进出题人挖的坑里。

6. 综合应用题：给数组和标记位置求区间乘积

6.1 一道典型的“简单题复杂化”题目

A卷里有一道综合应用题我记得比较清楚：给定一个整数数组，以及两个位置标记 i 和 j，要求计算从 arr[i] 到 arr[j] 之间所有元素的乘积并要求写出手写函数。这道题表面上很直接，但它的坑在于你如果只写一个for循环暴力相乘，虽然正确，却可能拿不到满分。因为出题人想要你分析在不同调用频率下，如何优化性能。

先看暴力解法的实现：

public long rangeProduct(int[] arr, int left, int right) { long result = 1; for (int k = left; k <= right; k++) { result *= arr[k]; } return result; }

这段代码的时间复杂度是O(n)，单次查询没有问题。但如果让你处理大量查询，比如q个不同区间的乘积，总复杂度就是O(n*q)。当n和q都达到10⁵级别时，这个复杂度就撑不住了。笔试题目里通常不会直接告诉你“要处理多次查询”，但作为候选人对“复杂度”的敏感度是面试官考察的核心。

6.2 前缀乘积的优化思路

更优秀的做法是“前缀乘积数组”。预处理时计算pre[i]表示前i个元素的乘积（pre[0]通常设置为1），那么区间[left, right]的乘积就等于 pre[right + 1] / pre[left]。

long[] pre; public void initPrefixProduct(int[] arr) { int n = arr.length; pre = new long[n + 1]; pre[0] = 1; for (int i = 0; i < n; i++) { pre[i + 1] = pre[i] * arr[i]; } } public long rangeProduct(int left, int right) { if (left > right || pre == null) { throw new IllegalArgumentException("Invalid range"); } return pre[right + 1] / pre[left]; }

算法题里有个别名也可以用在“数组的连续区间和”问题上，用前缀和数组，原理一模一样。从O(n)的单次查询变成O(1)的查询，一旦预处理完成，后续无论查询多少次都极其高效。这正是数据结构和算法学习的价值所在：同样的需求，换个数据结构存状态，性能量级完全不同。

但这里有个极其重要的前提——数组元素不能有零。万一数组里有零，前缀乘积会出现除以0或者结果全部变成0的尴尬情况。对于包含零的数组，需要分段处理或者记录零的位置。笔试中如果你能在答案里主动指出这个边界问题，并且给出“如果有零需要分段记录或者记录零下标”的解决方案，面试官对你的评价会明显高于只写正确答案的人。

6.3 区间乘积题目的易错点

我再总结一下这道题最容易丢分的几个细节，都是实际批改中见过的：

• 忘记处理区间左边界的“开闭”问题。题目要求包含 arr[i] 到 arr[j]，所以循环里应该是 k <= right，而不是 k < right。
• 用int存乘积。题目如果没提醒你数组元素的范围，多个大数相乘很容易溢出，应该用long甚至BigInteger。笔试中写long是更稳妥的选择。
• 边界条件left和right超出数组范围时没有校验。虽然测试用例可能不会覆盖，但考察的就是你的细心程度。

这道题的本质是“空间换时间”，用O(n)的空间把查询降到O(1)。类似思路在笔试中经常出现，比如二维矩阵的子矩阵和用二维前缀和，都是同一个套路。如果你能把前缀思想吃透，遇到同类题基本可以秒杀。

7. 应试经验与复习建议

7.1 笔试答题的节奏与优先级

结合这套A卷的特点，我建议你按这个节奏来答题：先快速扫一遍所有题目，把会做的题先做完，特别是选择题和简答题，因为这部分用时短、正确率高，能建立信心。然后单独攻克代码题，优先选择你最有把握、逻辑最清晰的题，不要在一道题上死磕超过20分钟。

在答题过程中，一定要先写伪代码或者画图梳理思路，再动笔写正式代码。我见过太多同学拿到链表题就直接写代码，写到一半发现指针指错了，把卷面涂得乱七八糟，给考官的印象也很差。合理的做法是先在草稿纸上画出链表反转的指针变化过程，标注好每一步哪个指针指向哪里，再对照图写代码，准确率高很多。

时间分配上，如果笔试总时长是90分钟，我建议选择题和简答题控制在30分钟以内，代码题每道控制在15到20分钟。最后留出10分钟全面检查，重点复查复杂度分析是否正确、边界条件是否覆盖、变量名是否有低级拼写错误。

7.2 校招数据结构复习的优先级排序

我在帮别人做校招辅导时，经常被问到“数据结构科目范围太广，到底应该优先复习什么”。结合唯品会2018校招数据结构笔试题（A卷）的出题风格，我的建议是按优先级从高到低排列：

第一梯队：链表（反转、合并、删除倒数第N个节点）、二叉树（遍历、深度、最近公共祖先）、栈与队列（互相实现、单调栈）。这三个模块是笔试最高频考点，而且代码量适中，很适合考察基本功。

第二梯队：排序算法（快排、归并、堆排序，以及它们的复杂度）、动态规划的经典模型（最长公共子序列、背包问题）、字符串操作（KMP的思想、字符串匹配）。

第三梯队：图的基本算法（BFS、DFS、最短路径）、并查集、前缀树、红黑树等进阶题。这些知识点在笔试中出现的频率相对低一些，但一旦出现，分值往往很大。

我的个人体会是：复习数据结构最重要的是“手写代码”，不是“看代码”。你可以把每道经典题的解题思路和模板代码整理成笔记，然后合上笔记在白纸上独立写一遍，写完之后对比标准答案，找出遗漏的边界条件和理解偏差。这个过程有点像是运动员练肌肉记忆，笔试现场时间紧张，只有形成条件反射才能在有限时间内写出高质量代码。

最后再分享一个小技巧：笔试时如果遇到复杂度分析的题目，不要只写一个答案，哪怕时间不够，也把你推导的关键过程写上。很多面试官在阅卷时更看重你的思考过程，而不是最终的结论。即使最终答案有一点偏差，但你的推导逻辑合理，也会拿到大部分过程分。这一点，在像唯品会这样注重基础功的公司笔试中，尤其重要。