1. 为什么我会去啃这套2017年的数据结构真题

先说清楚背景。2017年某邮电类院校的硕士研究生入学考试里，《数据结构》这门专业课的代码是802。这套卷子在网上流传的版本不少，但完整、带答案、且答案经过验证的版本极少。我手里这份是我自己一道一道做下来、又反复核对过的部分答案，覆盖了当年卷面上大部分算法设计题和综合应用题。

我为什么要花时间做这件事？原因很直接：数据结构这门课，光看书不做题等于没学。尤其是考研级别的题目，它考察的不是你背没背下来快速排序的平均时间复杂度，而是你能不能在白纸上、在没有编译器的情况下，写出一个逻辑自洽、边界处理正确的算法。这种能力，靠刷选择题是练不出来的。

这套802卷子的特点很鲜明。它不像某些学校那样大量堆砌概念填空，而是把重心压在算法设计和复杂度分析上。卷面里出现了好几道需要手写代码的题目，涉及树、图、排序、查找这些核心模块。我做完之后的感受是：题目本身不算偏，但陷阱埋得很细，稍不留神就会在边界条件上翻车。

这篇文章适合谁看？如果你正在准备数据结构相关的专业课考试，或者你虽然不考研但想检验一下自己的算法基本功，再或者你是个刚学完数据结构想找点真题练手的学生，那这份内容应该能帮到你。我会把每道有代表性的题目拆开讲，不光给答案，还会讲我为什么这么写、当时卡在哪里、以及后来复盘时发现的更优解法。

需要提前说明的是，我做的只是“部分答案”，不是全卷。有些题目因为原始回忆版信息不全，或者涉及多种等价解法，我只挑了我认为最有把握、也最有讲解价值的部分来写。另外，所有代码都是手写风格，没有依赖任何特定库，你在纸上写和在编辑器里写应该是一致的。

2. 802卷子的题型分布与我的应对策略

2.1 从回忆版还原出的卷面结构

根据我拿到的回忆版信息，2017年的802卷子大致分为三个板块：选择题、综合应用题、算法设计题。选择题部分覆盖了线性表、栈队列、串、树、图、查找、排序这些章节的基础知识点，题量不大但考得很细。综合应用题通常是给一个具体场景，让你分析数据结构的选择或者手动模拟某个算法的执行过程。算法设计题则是重头戏，要求写出完整的函数或伪代码，并给出时间复杂度和空间复杂度的分析。

我拿到卷子后的第一反应是：选择题不能丢分，因为这部分考的是硬知识，会就是会，不会就是不会，没有中间地带。综合应用题要稳，因为这类题往往有标准套路，只要平时练过类似场景，拿分不难。算法设计题是拉开差距的地方，也是我花时间最多的部分。

2.2 我给自己定的答题节奏

在模拟作答时，我给自己定了一个时间分配方案：选择题控制在30分钟以内，综合应用题40分钟，剩下的时间全部留给算法设计题。这个分配的依据是，算法设计题的分值权重最高，而且写代码需要反复检查边界条件，时间不够很容易出低级错误。

实际做下来，我发现最大的挑战不是不会做，而是“写不完”。有几道题我思路很清晰，但手写代码的速度跟不上，导致最后检查的时间被压缩。后来我调整了策略：对于特别长的算法题，先用伪代码把框架搭出来，确保逻辑完整，再回头补充细节。这样即使时间不够，至少框架分能拿到。

提示：如果你也在准备类似的考试，建议平时练习时就用白纸手写代码，不要依赖IDE的自动补全。考试时没有语法高亮，没有错误提示，全靠脑子里的“编译器”。

2.3 哪些题目值得反复琢磨

做完一遍之后，我把题目分成了三类。第一类是“一眼就会”的，比如简单的链表插入删除，这类题我只看一遍确认没有陷阱就过了。第二类是“有思路但容易写错”的，比如二叉树的非递归遍历、图的拓扑排序，这类题我反复写了三遍以上，直到能默写出正确版本。第三类是“当时没做出来”的，比如涉及复杂递归或者需要巧妙设计数据结构的题目，这类题我专门整理了错题笔记，分析卡壳的原因。

这份答案里，我重点呈现的是第二类和第三类题目。因为第一类题目对读者的参考价值有限，而第二、三类才是真正能让人学到东西的地方。

3. 树与二叉树相关题目的手写实录

3.1 一道考察二叉树非递归遍历的题目

卷子里有一道题要求写出二叉树中序遍历的非递归算法。这道题本身不算难，但我在第一次写的时候犯了一个典型错误：在while循环的条件判断里，我只写了“栈不为空”，忘了加上“当前节点不为空”这个条件。结果就是，当根节点没有左孩子时，程序会直接跳过左子树的处理，导致遍历结果错误。

正确的思路是这样的：用一个栈来模拟递归调用的过程。对于中序遍历，顺序是“左-根-右”。所以我们需要先一路向左走，把沿途的节点全部压栈，直到遇到空节点。然后弹出栈顶元素访问，再转向其右孩子，重复上述过程。循环的终止条件是“栈为空且当前节点为空”。

void InOrderTraverse(BiTree T) { Stack S; InitStack(S); BiTree p = T; while (p != NULL || !IsEmpty(S)) { if (p != NULL) { Push(S, p); p = p->lchild; } else { Pop(S, p); visit(p); p = p->rchild; } } }

这段代码我后来默写了不下十遍。每次写的时候，我都会特别检查两个地方：一是while循环的条件是否完整，二是if-else分支里的指针移动是否正确。这两个地方是最容易出错的。

3.2 二叉树层次遍历的变体考法

另一道题考的是层次遍历，但不是简单的从上到下、从左到右输出，而是要求按层输出，每一层单独一行。这就需要在基本的队列实现上做一点改造。我的做法是，在每一轮循环开始前，先记录当前队列中的元素个数，这个个数就是当前层的节点数。然后只处理这么多节点，处理完就换行。

void LevelOrderByLine(BiTree T) { if (T == NULL) return; Queue Q; InitQueue(Q); EnQueue(Q, T); while (!IsEmpty(Q)) { int levelSize = QueueLength(Q); for (int i = 0; i < levelSize; i++) { DeQueue(Q, p); visit(p); if (p->lchild) EnQueue(Q, p->lchild); if (p->rchild) EnQueue(Q, p->rchild); } printf("\n"); } }

这道题的关键在于理解“层”的概念。很多同学会想用两个队列交替来处理，但那样代码更复杂，而且容易在队列切换时出错。用记录当前层节点数的方式，逻辑更清晰，代码也更简洁。

3.3 从这道题延伸出的复习方法

做完这两道树相关的题目后，我总结了一个复习方法：对于每一种树的遍历方式，都要同时掌握递归和非递归两种写法。递归写法用来理解遍历的本质，非递归写法用来应对考试中可能出现的“不准用递归”的要求。而且，非递归写法能帮你更深刻地理解栈和队列在树结构中的作用。

我还发现，很多学校的考题喜欢在层次遍历上做文章，比如求树的宽度、求某一层的节点数、判断是否是完全二叉树等等。这些变体本质上都是层次遍历的应用，只要把基础框架写熟，变体就是加几行判断的事。

4. 图论部分：拓扑排序与最短路径的实战拆解

4.1 拓扑排序的手写实现与易错点

图论部分有一道题要求对一个有向无环图进行拓扑排序，并输出排序序列。拓扑排序的经典算法是Kahn算法：先统计每个顶点的入度，把入度为0的顶点入队，然后不断出队并减少相邻顶点的入度，把新产生的入度为0的顶点入队，直到队列为空。

我在写这道题的时候，踩了一个坑：我用了邻接矩阵来存储图，但在减少入度的时候，我遍历的是整个矩阵的一行，而不是只遍历与该顶点相邻的顶点。虽然结果是对的，但时间复杂度从O(V+E)变成了O(V^2)。如果题目对时间复杂度有要求，这样写是要扣分的。

int TopologicalSort(Graph G) { int indegree[MaxVertexNum]; FindInDegree(G, indegree); Stack S; InitStack(S); for (int i = 0; i < G.vexnum; i++) { if (indegree[i] == 0) Push(S, i); } int count = 0; while (!IsEmpty(S)) { Pop(S, i); printf("%d ", i); count++; for (ArcNode *p = G.vertices[i].firstarc; p; p = p->nextarc) { int k = p->adjvex; if (--indegree[k] == 0) Push(S, k); } } if (count < G.vexnum) return -1; return 1; }

这段代码用的是邻接表，遍历相邻顶点的时间是O(E)，整体复杂度是O(V+E)。如果你在考场上用的是邻接矩阵，记得在分析复杂度时说明这一点，或者干脆改用邻接表来写。

4.2 最短路径算法的选择逻辑

另一道题给了一个带权有向图，要求求某个源点到其他所有顶点的最短路径。这道题没有明确说用Dijkstra还是Floyd，但从“单源”这个关键词可以判断，应该用Dijkstra算法。Dijkstra的核心思想是贪心：每次从未确定的顶点中选出距离源点最近的那个，然后用它去更新其他顶点的距离。

我在写Dijkstra的时候，最容易出错的地方是“松弛操作”的条件判断。正确的写法是：如果通过当前顶点u到达顶点v的距离比已知的dist[v]更小，就更新dist[v]。这个“更小”的比较不能漏，否则会把已经确定的最短路径覆盖掉。

void Dijkstra(Graph G, int v0, int dist[], int path[]) { int visited[MaxVertexNum] = {0}; for (int i = 0; i < G.vexnum; i++) { dist[i] = G.edges[v0][i]; if (dist[i] < INF) path[i] = v0; else path[i] = -1; } visited[v0] = 1; dist[v0] = 0; for (int i = 1; i < G.vexnum; i++) { int min = INF, u = -1; for (int j = 0; j < G.vexnum; j++) { if (!visited[j] && dist[j] < min) { min = dist[j]; u = j; } } if (u == -1) break; visited[u] = 1; for (int w = 0; w < G.vexnum; w++) { if (!visited[w] && dist[u] + G.edges[u][w] < dist[w]) { dist[w] = dist[u] + G.edges[u][w]; path[w] = u; } } } }

这道题我后来复盘时发现，如果题目要求输出具体路径而不只是距离，那就需要额外维护一个path数组来记录前驱节点。很多同学在考试时只写了dist数组，结果路径输出部分拿不到分。

4.3 图论题目的通用检查清单

做完图论部分的题目后，我给自己列了一个检查清单，每次写完代码都对照检查一遍：

• 图的存储结构是邻接矩阵还是邻接表？这决定了遍历相邻顶点的方式。
• 顶点编号是从0开始还是从1开始？边界条件要对应调整。
• 是否有孤立顶点？入度为0的顶点是否全部处理了？
• 如果图不连通，算法是否能正确处理？
• 时间复杂度的分析是否与代码实现一致？

这个清单帮我避免了好几次低级错误。尤其是顶点编号的问题，我在模拟时因为没注意这个，导致数组越界，整道题几乎白写。

5. 排序与查找：那些看似简单却暗藏杀机的题目

5.1 快速排序的划分过程手写模拟

有一道题要求写出快速排序一趟划分的结果。这种题看起来简单，但实际做的时候很容易在指针移动的细节上出错。快速排序的划分有多种实现方式，我习惯用的是“挖坑填数”法：选取一个基准值，通常取第一个元素，然后从右往左找比基准小的数填到左边的坑里，再从左往右找比基准大的数填到右边的坑里，直到左右指针相遇。

我在模拟这道题的时候，第一次把指针移动的顺序搞反了，导致划分结果完全错误。后来我总结了一个口诀：“右找小，左找大，填坑交替，相遇即止。”这个口诀帮我记住了指针移动的方向和填坑的顺序。

注意：不同的教材对快速排序划分的实现细节可能不同，有的先移动右指针，有的先移动左指针。考试时一定要看清题目要求或者根据上下文判断，不要想当然。

5.2 堆排序的建堆与调整

堆排序的题目通常要求写出初始建堆的过程，或者写出某一次调整后的堆状态。我在做这类题时，最大的感受是：一定要画图。光在脑子里想很容易乱，尤其是节点数多的时候。我通常会把完全二叉树画出来，然后按照从最后一个非叶子节点开始、从右到左、从下到上的顺序逐个调整。

建堆的时间复杂度是O(n)，这个结论很多同学知道，但未必理解为什么不是O(n log n)。原因在于，大部分节点都在底层，它们需要调整的高度很小，所以总的调整次数是线性的。这个推导过程如果能在答题时简要说明，会给阅卷老师留下好印象。

5.3 查找部分的一道综合题

查找部分有一道题结合了二叉排序树和平衡二叉树的知识点，要求判断给定的插入序列是否会破坏平衡，如果破坏了，属于哪种旋转类型。这道题考察的是对LL、RR、LR、RL四种旋转类型的识别能力。

我的做法是：先按照插入顺序构建二叉排序树，然后从插入点往上找第一个不平衡的节点，判断新插入的节点是在这个不平衡节点的左子树的左边还是右边，从而确定旋转类型。这个判断过程需要细心，因为有时候插入一个节点会导致多个祖先节点不平衡，但只需要调整最小的那棵不平衡子树。

这张表是我考前反复默写的，考试时直接套用，省去了现场推导的时间。

6. 算法设计题的通用解题框架与我的踩坑记录

6.1 从题目描述到代码实现的翻译过程

算法设计题最大的难点在于，题目往往只给一个场景描述，你需要自己判断该用什么数据结构、该设计什么样的算法。我的经验是，先不要急着写代码，而是用自然语言把解题思路写出来，然后再翻译成代码。

比如有一道题描述的是“在一个无序数组中找出第k小的元素”。看到“第k小”，我第一反应是排序后取第k个，但这样时间复杂度是O(n log n)。如果题目对时间复杂度有更高要求，就需要用快速选择算法，平均时间复杂度是O(n)。这个判断过程就是“翻译”的关键：先理解需求，再选择工具。

6.2 我在边界条件上翻过的车

我在做算法设计题时，翻车最多的地方就是边界条件。举几个真实的例子：

• 数组为空或只有一个元素时，循环是否还能正确执行？
• 链表操作时，头节点是否需要特殊处理？
• 递归的终止条件是否覆盖了所有情况？
• 整数除法时，是否考虑了除数为0的情况？

有一次我写一个二分查找的变体，题目要求找第一个大于等于目标值的元素位置。我写完之后检查了一遍，觉得没问题。后来模拟运行了一个测试用例：数组是[1,2,3,4,5]，目标值是6。我的代码返回了数组长度，这是对的。但如果目标值是0呢？我的代码返回了0，也是对的。但如果数组是空的呢？我的代码直接访问了数组元素，崩溃了。这就是典型的边界条件遗漏。

6.3 时间复杂度分析的答题模板

算法设计题通常要求分析时间复杂度。我的答题模板是这样的：先说明算法的基本操作是什么，然后分析基本操作的执行次数与问题规模n的关系，最后给出大O表示法。如果空间复杂度也需要分析，就额外说明额外使用的存储空间与n的关系。

这个模板看起来简单，但能保证你不漏点。有些同学只写一个“O(n log n)”就完事了，没有推导过程，阅卷老师可能会扣分。尤其是当你的代码实现和复杂度分析不一致时，老师一眼就能看出来。

7. 做完这套卷子后我总结的复习方法论

7.1 手写代码不能停

做完这套802卷子后，我最大的体会是：手写代码的能力需要持续训练。我在复习初期过于依赖IDE，觉得只要思路对就行。但实际考试时，没有自动补全、没有语法检查，一个分号漏了、一个括号没配对，都可能导致整道题失分。后来我强迫自己每天至少手写两道算法题，坚持了一个月，明显感觉手速和准确率都上来了。

7.2 错题本比刷题量更重要

我一开始也追求刷题数量，觉得做得越多越好。但后来发现，做过的题如果不复盘，下次遇到类似的还是会错。于是我建了一个错题本，每道错题都记录三个东西：当时的错误思路、正确的思路、以及这道题考察的核心知识点。这个错题本在考前一周帮我快速回顾了所有薄弱环节，效果比重新刷一遍题好得多。

7.3 复杂度分析要形成条件反射

数据结构考试里，复杂度分析几乎是必考内容。我的建议是，每写一个算法，都下意识地分析一下它的时间和空间复杂度。久而久之，你会形成条件反射，看到循环就能估算出大致的时间复杂度。这种能力不仅对考试有用，对以后的实际开发也有帮助。

7.4 模拟考试环境

最后一点，也是我觉得最重要的一点：一定要模拟考试环境。找一个安静的教室，拿一张白纸，限定时间，完整地做一套卷子。这种模拟能帮你适应考试的压力和节奏，也能暴露你在时间分配上的问题。我第一次模拟时，因为在一道难题上卡了太久，导致后面两道简单的题没时间写，教训很深刻。

这套2017年的802卷子，我前后做了三遍。第一遍是摸底，第二遍是精做，第三遍是查漏补缺。每一遍都有新的收获。如果你也在准备数据结构相关的考试，我建议你不要只盯着答案看，而是自己先动手做一遍，再对照答案找差距。这个过程虽然痛苦，但提升是最快的。