乐学平台数据结构考题精讲：约瑟夫问题、验证表、循环小数与BFS

简介：北理工大二数据结构课程乐学在线评测平台编程题的完整C++实现合集，共29个cpp源码文件，压缩包大小仅25KB，覆盖线性表、栈与队列、树与二叉树、图、查找与排序等数据结构核心内容，适合正在修读该课程或准备期末机考的本科同学参考学习。具体题目包括约瑟夫问题、验证表、循环小数、双向约瑟夫、综教楼后的坑、一元多项式相加/相乘、括号匹配、表达式求值、树的建立与遍历、哈夫曼树、折半查找、堆排序、快速排序、关键路径、迷宫问题等，基本涵盖了乐学平台大二阶段的典型编程题目。文件按章节编号独立组织，题目与代码一一对应，便于按需打开、对照调试；整体难度递进清晰，既有基础线性表与栈队列操作，也有递归建树、图遍历与排序查找等进阶内容，可作为上机实验和期末复习的算法参考。资源目前已有2968人浏览学习，体积虽小但覆盖面广，适合用来巩固基础、查漏补缺，也能帮助理解抽象数据结构如何落地为可运行的C++代码。 大二被乐学平台这套数据结构编程题折磨过的同学，应该都记得这几个名字：约瑟夫问题、验证表、循环小数、综教楼后的坑。它们不是同一类题，但都踩中了数据结构课的经典考点——线性表的删除模拟、二叉树的合法性判断、循环节的数学建模、图的遍历搜索。这篇文章我把每道题的思路、实现、还有我当时踩过的坑全部拆开讲一遍，正在做这套题或者在做类似题目的同学，可以直接拿去参考。

先说个总体感受：这套题真正考的不是“会不会背模板”，而是你能不能把课堂上讲的性质（比如约瑟夫递推、中序序列有序性、余数判重、BFS最短步数）转化成代码。纯靠模仿书上的完整代码很难拿满分，乐学的测试用例卡得细，边界情况特别多。

1. 先看清这波题到底在考什么

1.1 乐学平台的题风与应对思路

北理工的乐学平台不是简单交作业，它本质是个在线评测系统，所以它对时间复杂度、空间复杂度、输入输出的格式要求都很严格。很多同学在本地DevCpp跑得好好的，一提交就“运行错误”或者“超时”，多半不是代码逻辑错，而是没有处理好几类细节。

这四道题我按考点拆了一下：

做题顺序上，我建议先做“循环小数”和“约瑟夫问题”，这两个题目的解题路径比较固定，写完容易验证对错。“验证表”和“综教楼后的坑”需要多花时间想清楚题目细节，尤其是题目里那些括号、输出格式的说明，漏看一个条件就会白白折腾一晚。

1.2 题量和精力的合理分配

不要试图一个晚上刷完四道题，我试过，结果就是前面两题因为粗心反复提交失败，后面两题完全没时间细想。比较合理的节奏是：约瑟夫和循环小数各花半天搞定，验证表单独留一下午，综教楼后的坑留一晚上专门调BFS。每道题都要留出至少半小时用来补边界测试用例，后面我会具体讲每个题的边界长什么样。

2. 约瑟夫问题：别一上来就写循环链表

2.1 递归公式推导：为什么答案能一行算出

约瑟夫问题的经典描述是：n个人围成一圈，从某个位置开始报数，报到m的人出圈，然后下一个人重新从1报数，问最后剩下的人是谁。很多教材给的解法是循环链表删除，这个思路最直观，但如果你只需要知道最后的幸存者编号，根本不用去模拟删除过程。

这里有一个非常关键的递推思想。假设f(n, m) 表示n个人报数m时，最后幸存者的编号（从0开始编号）。第一轮报数后，编号为(m-1) mod n的人出圈，那么剩下的人从原来的编号m mod n开始重新组成一个规模为n-1的圈子。在这个新圈子里，编号从0开始数的第f(n-1, m)个人，就是原来的幸存者。所以有：

f(1, m) = 0 f(n, m) = (f(n-1, m) + m) mod n

这个公式的巧妙之处在于，它把“删人后重新编号”的过程压缩成了一个模运算。很多同学不理解为什么最后要加上m再取模，其实它就是做了“新编号还原回旧编号”的逆运算。你可以拿n=5, m=3手推一遍，感受一下这个还原过程。

2.2 两种解法对比与代码实现

我先把两种方法的代码都放出来，再给你看它们的定位。

循环链表模拟的代码大致长这样：

#include <stdio.h> #include <stdlib.h> typedef struct Node { int id; struct Node *next; } Node; Node* createList(int n) { Node *head = (Node*)malloc(sizeof(Node)); head->id = 1; head->next = NULL; Node *tail = head; for (int i = 2; i <= n; i++) { Node *p = (Node*)malloc(sizeof(Node)); p->id = i; p->next = NULL; tail->next = p; tail = p; } tail->next = head; return head; } int main() { int n, m; while (scanf("%d%d", &n, &m) != EOF) { if (n == 0) break; Node *cur = createList(n); Node *prev = NULL; while (cur->next != cur) { for (int i = 1; i < m; i++) { prev = cur; cur = cur->next; } Node *tmp = cur; prev->next = cur->next; cur = cur->next; free(tmp); } printf("%d\n", cur->id); free(cur); } return 0; }

而递推法的代码短得多：

#include <stdio.h> int main() { int n, m; while (scanf("%d%d", &n, &m) != EOF) { if (n == 0) break; int ans = 0; for (int i = 2; i <= n; i++) { ans = (ans + m) % i; } printf("%d\n", ans + 1); } return 0; }

注意输出的时候要加1，因为递推公式里的编号是从0开始的，而题目通常要求输出从1开始的编号。当时我第一次写这题，就是用链表模拟，结果n一超过10万就开始剧烈卡顿，改成递推后连n等于几百万都能秒过。但如果你遇到的输出要求是给出完整出圈序列，那么递推法就不适用了，还是得用链表模拟或者在循环链表基础上做优化。

两种方法的对比如下：

经验之谈：先读清楚题目到底要什么。看到“最后剩下的人”就立刻用递推，看到“输出出圈序列”才用链表。另外链表的题即使要用模拟，也要注意释放内存，乐学平台上内存泄漏一般不会判错，但养成良好的习惯对后面的课程设计有帮助。

3. 循环小数：模拟除法竖式比你想的要简单

3.1 循环节产生的本质：余数重复

循环小数这题，核心不是小数本身，而是“循环节”。输入一个分子a和分母b（我遇到的版本是a和b都是正整数），要求输出 a/b 的小数形式，如果小数部分循环，需要用括号标出循环节，比如 1/3 输出 1.(3)，1/6 输出 0.1(6)。

为什么会产生循环？因为除法竖式里，每次都是拿余数乘10再除以除数，得到新的商和新的余数。一旦某个余数之前出现过，那么之后的所有计算过程都会完全重复，小数就进入了循环。所以找循环节的关键就是“余数判重”：记录每个余数第一次出现的位置，当某个余数再次出现时，从它第一次出现的位置到当前位置就是循环节。

3.2 从整数部分到循环节的完整流程

我写的C程序分了三步：先算整数部分，再算小数部分，最后输出循环节。核心代码如下：

#include <stdio.h> #include <string.h> int main() { int a, b; while (scanf("%d%d", &a, &b) != EOF) { if (b == 0) continue; int integer = a / b; int rem = a % b; printf("%d.", integer); if (rem == 0) { printf("0\n"); continue; } int pos[100005]; memset(pos, -1, sizeof(pos)); int quotient[100005]; int idx = 0; int startCycle = -1; while (rem != 0) { if (pos[rem] != -1) { startCycle = pos[rem]; break; } pos[rem] = idx; rem *= 10; quotient[idx] = rem / b; rem %= b; idx++; } if (startCycle == -1) { for (int i = 0; i < idx; i++) { printf("%d", quotient[i]); } printf("\n"); } else { for (int i = 0; i < startCycle; i++) { printf("%d", quotient[i]); } printf("("); for (int i = startCycle; i < idx; i++) { printf("%d", quotient[i]); } printf(")\n"); } } return 0; }

这段代码有几个关键点。第一个是pos数组要开多大，理论上余数的取值范围是0到b-1，但题目如果给出b的最大值，就直接按最大值开。如果没有明确给边界，建议用动态内存或哈希来处理，避免数组越界。第二个是整除的情况一定单独处理，比如 6/2，输出 3.0 而不是 3. 后面什么都没有。还有一个小细节：如果整数部分本来为0，也要输出0，所以printf("%d.", integer)这个写法能保证格式正确。

我当时在这个题上栽过两次。第一次是忘了记录余数第一次出现的位置，导致循环节判断错乱；第二次是没处理“余数为0被整除”的情况，导致程序死循环。后来我每次拿到这类题，都会先想清楚“什么样的输入会让循环退出”，再开始写代码。

4. 验证表：树的题，核心是先搞懂遍历序列

4.1 “验证表”到底要验证什么

“验证表”这题我第一次看到名字也是一头雾水，后来看了样例才明白，它给出一棵二叉树的中序序列（或者是某种遍历结果），要求判断这棵树是否是二叉搜索树，并输出对应的验证信息表。不同年份的题目描述可能不一样，我拿到的版本是：给出一棵二叉树每个节点的值，以及左右子节点关系，要求验证这棵树是否满足二叉搜索树的性质，输出每个节点对应的合法区间。

二叉搜索树的核心性质是中序遍历有序，但不止这一条：每个节点的所有左子树节点都小于当前节点，所有右子树节点都大于当前节点。如果只检查相邻两个中序节点是否递增，会遇到一个问题：样例数据可能构造出连续值相等的序列，这时候需要额外判断是否允许重复值。

我采用的思路是递归区间验证：从根节点开始，假设它允许的取值范围是(-∞, +∞)。对于某个节点值为val，它的左子树所有节点必须落在(min, val)区间内，右子树所有节点必须落在(val, max)区间内。只要在递归过程中任何一个节点值不在允许区间内，就说明不是二叉搜索树。

4.2 区间递归的边界细节

这个思路的代码量不大，但边界处理极其容易出现隐蔽错误。我这里写一个参考实现：

#include <stdio.h> #include <limits.h> int flag = 1; typedef struct TreeNode { int val; int left; int right; } TreeNode; TreeNode nodes[10005]; void dfs(int root, long long min, long long max) { if (root == -1 || !flag) return; int val = nodes[root].val; if (val <= min || val >= max) { flag = 0; return; } dfs(nodes[root].left, min, val); dfs(nodes[root].right, val, max); } int main() { int n; scanf("%d", &n); for (int i = 1; i <= n; i++) { scanf("%d%d%d", &nodes[i].val, &nodes[i].left, &nodes[i].right); } dfs(1, LLONG_MIN, LLONG_MAX); // 假设编号1是根 if (flag) printf("Valid\n"); else printf("Invalid\n"); return 0; }

这里我用long long来传区间边界，因为如果树里出现了INT_MIN，初始边界设成INT_MIN会导致判断出错——INT_MIN和INT_MIN比较要不要取等号，这是很微妙的问题。用long long把边界放大，可以避免这种纠结。另外递归深度也要注意，如果树退化成一条链，深度可能达到n，递归层数过多会导致栈溢出。这种情况可以用栈迭代替代递归，或者用中序遍历的栈实现。

我当时在这题上卡了很久，最后是手动构造了一个对称的样例才定位到问题：树的根节点不一定是编号1，乐学平台有些数据的根节点编号不是固定的。所以我加了一行查找入度为0节点的逻辑，才把所有测试点跑通。如果你遇到的题目没有明确说明根节点，这一步千万别省。

5. 综教楼后的坑：图的遍历与最短路径，别再DFS写爆炸

5.1 题目背景与地图抽象

“综教楼后的坑”这题名字听着很玄，实际上是一个网格地图问题。我拿到的版本是：给定一个n行m列的网格，有些格子有障碍物（坑），有些格子可以走，要求从起点走到终点，输出最短步数或者路径。题目描述里可能会用字符矩阵表示地图，比如S表示起点，E表示终点，#表示障碍，.表示空地。

这种题要做的第一件事就是抽象：把每个格子看成一个节点，上下左右相邻的可走格子之间连一条边，问题就变成了在无权图上求最短路径。无权图的最短路径，用BFS就可以了，第一次访问到终点时的层数就是最短步数。

我见过不少同学一上来就写DFS，理由是“深度优先看起来像在走路”。但DFS找最短路径需要把所有路径都走一遍，复杂度是O(2^(n+m))级别的，地图稍大一点就会超时或者爆栈。BFS按层扩展，每个格子最多被访问一次，复杂度是O(n*m)，稳定得多。

5.2 BFS模板与防坑记录

BFS的标准实现是用队列，配合vis数组记录每个格子是否访问过。方向数组是固定的，x和y的变化可以统一写成一个二维数组：

#include <stdio.h> #include <string.h> #define MAXN 105 int n, m; char mp[MAXN][MAXN]; int vis[MAXN][MAXN]; int step[MAXN][MAXN]; int dir[4][2] = {{1,0},{-1,0},{0,1},{0,-1}}; int sx, sy, ex, ey; typedef struct { int x, y; } Point; Point queue[MAXN * MAXN]; int bfs() { int head = 0, tail = 0; queue[tail].x = sx; queue[tail].y = sy; tail++; vis[sx][sy] = 1; step[sx][sy] = 0; while (head < tail) { Point now = queue[head++]; if (now.x == ex && now.y == ey) { return step[now.x][now.y]; } for (int i = 0; i < 4; i++) { int nx = now.x + dir[i][0]; int ny = now.y + dir[i][1]; if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue; if (mp[nx][ny] == '#') continue; if (vis[nx][ny]) continue; vis[nx][ny] = 1; step[nx][ny] = step[now.x][now.y] + 1; queue[tail].x = nx; queue[tail].y = ny; tail++; } } return -1; } int main() { while (scanf("%d%d", &n, &m) != EOF) { for (int i = 0; i < n; i++) { scanf("%s", mp[i]); for (int j = 0; j < m; j++) { if (mp[i][j] == 'S') { sx = i; sy = j; } else if (mp[i][j] == 'E') { ex = i; ey = j; } } } memset(vis, 0, sizeof(vis)); memset(step, 0, sizeof(step)); int ans = bfs(); if (ans == -1) printf("No path\n"); else printf("%d\n", ans); } return 0; }

这个模板里有三个常见的坑。第一个是队首队尾指针的处理，我习惯用数组模拟队列，因为直接调用STL的queue在部分老版本的评测环境里可能会有兼容问题，而且数组模拟访问速度快。第二个是vis标记的时机：我一贯的做法是在元素入队时立刻标记，也就是节点入队就把vis[nx][ny]置1，避免同一个点被多次加入队列。如果等到出队时才标记，那么同一个点可能被多个方向的邻居同时发现，队列会膨胀，严重时导致超时或内存不够。第三个是step数组，如果题目只要求输出最短步数，用step数组记录每格步数非常直观；如果题目要求输出路径，还要另开一个数组存前驱。

6. 常见错误与调试心得：这波真的被坑过

6.1 高频报错清单与定位方法

我把自己和身边同学在乐学平台上遇到的高频报错整理成了一张表，对照这个表自查，比对着屏幕发呆有用得多：

运行错误里最阴间的就是“数组越界”。比如循环小数里，如果b最大是100000，我把pos数组开成100000，可是余数本身可能等于99999，访问pos[99999]没问题，但后面rem *= 10之后rem可能超过数组范围，这时候就需要在赋值前判断一下rem的范围。再比如验证表的树节点编号，题目如果告诉你节点编号从1到n，你开nodes[10005]没问题，但如果某组数据编号范围正好是99999，数组就爆了。我的习惯是：凡是数组大小依赖输入数据的题目，一律按照题目给的上限再多开5到10个，这是防御性编程的基本功。

6.2 边界样例与对拍技巧

我写这些题的时候，会给自己准备一组“边界全家桶”用例，每道题提交前先跑一遍：

• 约瑟夫问题：n=1, m=1；n=5, m=3；n=10, m=100（m大于n的情况）
• 循环小数：1/2（整除后余数为0）；1/3（从第一位开始循环）；1/6（循环节不在小数第一位）；0/5（分子为0）
• 验证表：空树（如果题目允许）；单节点；根只有一个左孩子；整棵树退化成链表
• 综教楼后的坑：地图只有起点和终点且相邻；终点被障碍包围；2x2最小地图

还有一个很笨但很有效的调试技巧：在关键循环里用printf打印中间变量。比如约瑟夫问题，打印每次递推的ans值；循环小数里，打印每次的余数和商；BFS里，打印每个出队点的坐标。定位完bug再把printf删掉，虽然土，但比只会加断点快得多。

如果实在找不出错，还有一个“对拍”的思路：写一个暴力做法，再写一个优化做法，用随机小数据反复跑，比较两者输出是否一致。这个技巧在考试和竞赛里很常见，我平时做乐学题也这么干，一次能省出两三个小时的排查时间。

最后说一点个人体会。数据结构这门课，理论课的公式推导和实验课的编程题往往是两回事。你在纸上能推约瑟夫递推，不代表你能处理n=0的输入；你懂BFS的原理，不代表你能避开队列内存爆炸的坑。乐学平台这几道题最锻炼人的地方，其实是“把课堂知识翻译成边界条件”的能力。建议学弟学妹们别急着提交，先花十分钟把所有可能的特殊输入列出来，跑一遍再交，通过率会大幅提升。后面如果有时间，可以把这几道题再往深延伸一下——约瑟夫问题可以改成输出出圈序列的线段树版本，循环小数可以结合大数除法处理高精度分数，综教楼后的坑可以加入多起点或传送门，练熟这些变体，期末上机就真的没什么好怕的了。

本文还有配套的精品资源，点击获取