西电的数据结构上机放在整个课程体系里说大不大说小不小。大是因为它直接决定你期末总评能不能往上拉一截小是因为考来考去就是那几类题线性表、链表、树、图、排序、查找翻来覆去。但每年照样有人因为环境不熟、输入输出处理不当、递归超时这类问题翻车。这篇文章就是我根据自己的备考经历和帮同学复盘时总结出来的完整复习路线围绕考点范围、代码模板、编译环境、调试技巧、考前安排五个方面展开争取让你花最少的时间把该拿的分稳稳拿下。1. 西电上机到底考什么先摸着题型的底1.1 上机形式的真实情况西电数据结构上机不同学期、不同老师可能略有差别但总体模式很统一在规定时间内通常是两到三小时用C语言在指定环境下完成两到四道编程题现场编译运行提交代码或直接由老师在终端里查看运行结果。题目不会像ACM竞赛那样绕弯子基本就是课内知识点的直接应用甚至有一半题目能在课本习题和实验指导书上找到原型。教材以严蔚敏《数据结构C语言版》为主这一点直接决定了出题风格——偏重基础逻辑和算法本身的实现而不是偏重STL封装或C高级特性。所以复习时如果只看思路不动手敲代码上机时大概率会卡在很基础的语法错误上。另外虽然课程名是数据结构但上机时对算法复杂度是有隐性要求的比如单链表的逆置就要求你写O(n)的双指针迭代而不是每次先遍历求长度再交换。1.2 考点优先级排序与复习策略我给自己的复习排了一个优先级实际用下来效率不错你可以直接参考优先级考点模块典型题型复习价值高线性表与链表顺序表插入删除、链表反转、合并有序链表、约瑟夫环必考且最容易拿分高二叉树操作递归遍历、层次遍历、求深度、镜像翻转高频出现递归必须要顺高排序算法快排、堆排、冒泡、直接插入、希尔、归并考察频率极高复杂度要背中图的基本算法DFS、BFS、邻接矩阵/邻接表转换、Dijkstra出题概率不低模板要滚瓜烂熟中栈与队列括号匹配、表达式求值、循环队列和链表树结合出题中查找与哈希顺序/折半查找、哈希表构造、冲突处理概念题上机化难度不大低串与数组KMP、矩阵压缩存储出题少时间紧可跳过策略上我建议先把自己最熟的部分练到闭眼能写再花时间啃薄弱环节。比如链表反转这个题你如果能在五分钟内无错写完考场上就相当于送分题反之如果你还在想指针到底怎么指就要多投入时间。上机考试和笔试最大的区别是它不给思考的缓冲平时练到条件反射的程度考场上才能真正发挥。2. 线性表与链表拿分最稳也最易翻车的模块2.1 顺序表的基本操作插删查要写利索顺序表这部分很多同学觉得很简单结果上机时反而在细节上出错。比如插入操作中插入位置的判断删除操作中元素的移动方向。我习惯用一段标准模板来解决#include stdio.h #include stdlib.h #define MAXSIZE 100 typedef struct { int data[MAXSIZE]; int length; } SeqList; int insert(SeqList *L, int pos, int e) { if (L-length MAXSIZE) return 0; // 表满 if (pos 1 || pos L-length 1) return 0; // 位置非法 for (int i L-length; i pos; i--) { L-data[i] L-data[i - 1]; } L-data[pos - 1] e; L-length; return 1; } int deleteElem(SeqList *L, int pos, int *e) { if (pos 1 || pos L-length) return 0; *e L-data[pos - 1]; for (int i pos; i L-length; i) { L-data[i - 1] L-data[i]; } L-length--; return 1; }这里最容易错的地方是两个循环的边界。插入时循环是i pos因为你要把pos位置及其后面的所有元素后移一格删除时循环是i L-length因为要把pos位置后面的元素前移。我在第一次练的时候就因为把循环边界写反导致数据错乱后来干脆把这两段模板背熟考场上直接默写几乎不出错。2.2 链表高频题反转、合并、约瑟夫环链表部分最常考的就是单链表反转。迭代版的三指针法是标准解法我备考时先写了递归版觉得代码更短但上机时一紧张容易绕晕后来果断用迭代版。typedef struct Node { int data; struct Node *next; } Node; Node* reverseList(Node *head) { Node *prev NULL, *cur head; while (cur ! NULL) { Node *next cur-next; // 先保存下一个节点 cur-next prev; // 指向前一个节点 prev cur; // prev 前进一步 cur next; // cur 前进一步 } return prev; // 新的头结点 }合并两个有序链表也值得专门练一下因为这道题既能考察对链表操作的熟悉程度也能考察边界情况的处理。我一般用一个哨兵头节点减少特判Node* mergeTwoLists(Node *l1, Node *l2) { Node dummy; dummy.next NULL; Node *tail dummy; while (l1 l2) { if (l1-data l2-data) { tail-next l1; l1 l1-next; } else { tail-next l2; l2 l2-next; } tail tail-next; } tail-next l1 ? l1 : l2; return dummy.next; }哨兵节点的思路就是从链表头开始不用单独处理第一个节点这种特判代码会短很多也更容易想清楚。约瑟夫环这个经典题也大概率出现过用循环链表模拟一下就行但要注意节点的释放顺序避免内存泄漏。2.3 链表题的三个常见坑我帮同学复盘时发现链表的坑集中在三个方面。第一是头指针被修改。很多同学在反转或删除时直接动了head结果后面还想用原始链表就丢了。解决办法是传入时用局部指针接收返回值或者所有操作都在局部变量上进行最后再赋给head。第二是空指针解引用。没有判断cur-next NULL就访问cur-next-data直接段错误。上机环境对段错误一般不会给太详细的提示所以写循环时要条件反射性地检查指针。第三是内存管理。严蔚敏教材本身就强调C语言封装上机题也会要求你自主分配节点。千万记得free掉不需要的节点否则虽然不影响运行但老师可能会看代码质量扣分。3. 树和图递归功底直接决定上限3.1 二叉树递归遍历必须写到条件反射西电上机对二叉树的考察频率相当高最常见的就是递归遍历、层次遍历、求深度、交换左右子树这四件事。递归遍历本身不难但你必须做到不假思索地写出来因为后续几乎所有树题都是在这三个遍历的基础上变形的。typedef struct BiTNode { int data; struct BiTNode *lchild, *rchild; } BiTNode; void preOrder(BiTNode *T) { if (T NULL) return; printf(%d , T-data); preOrder(T-lchild); preOrder(T-rchild); } void inOrder(BiTNode *T) { if (T NULL) return; inOrder(T-lchild); printf(%d , T-data); inOrder(T-rchild); } void postOrder(BiTNode *T) { if (T NULL) return; postOrder(T-lchild); postOrder(T-rchild); printf(%d , T-data); }非递归遍历上机时出现的概率更高因为老师可能专门出一道不用递归实现先序/中序遍历来考察栈的掌握情况。先序遍历的非递归实现最简单先访问根节点再把右孩子入栈、左孩子入栈因为栈是后进先出要保证左孩子先被访问就得后入栈。3.2 层次遍历与二叉树的输出格式层次遍历需要队列我在上机时喜欢用数组模拟队列既省去链表队列的麻烦代码也更直观。void levelOrder(BiTNode *root) { if (root NULL) return; BiTNode *queue[100]; int front 0, rear 0; queue[rear] root; while (front rear) { BiTNode *cur queue[front]; printf(%d , cur-data); if (cur-lchild) queue[rear] cur-lchild; if (cur-rchild) queue[rear] cur-rchild; } }上机时有个细节很多人忽视输出格式。题目要求每行输出几个节点、是否需要把空节点也打印成#或者null这类要求往往在题目描述里写得很细。我当年就遇到过一道按满二叉树补空的层次遍历题要求空节点输出为#结果我没仔细读题直接漏掉空节点判断第一遍运行结果和样例对不上浪费了十几分钟排查。3.3 图的DFS与BFS邻接矩阵版本最稳妥图的题在西电上机中出现频率不算最高但一旦出了分值往往不小。最稳妥的方案是用邻接矩阵存储比邻接表好写很多也不会因为指针问题出错。DFS和BFS的模板如下#define N 100 int graph[N][N]; int visited[N]; void dfs(int v, int n) { visited[v] 1; printf(%d , v); for (int i 1; i n; i) { if (graph[v][i] !visited[i]) { dfs(i, n); } } } void bfs(int start, int n) { int queue[N]; int front 0, rear 0; visited[start] 1; queue[rear] start; while (front rear) { int v queue[front]; printf(%d , v); for (int i 1; i n; i) { if (graph[v][i] !visited[i]) { visited[i] 1; queue[rear] i; } } } }Dijkstra算法如果考到建议直接背一个最简的邻接矩阵版模板。核心就三步找当前未访问节点中距离最小的标记访问用它更新所有邻居的最短距离。次数多了自然就记住了。注意考试时如果你看到图题先判断数据规模如果是几十个节点的稠密图邻接矩阵完全够用。4. 排序查找与哈希复杂度表背熟才能不丢基础分4.1 八种排序的复杂度对照表排序算法这部分上机题可能会让你完整实现某一种排序也可能会在一道综合题中要求先排序再查找。笔试和上机的一个显著区别是上机更看重实现是否无错但排序的复杂度判断仍然是老师考察的重点甚至会在题目描述里直接问该排序算法在最好情况下的时间复杂度是多少。排序算法平均时间复杂度最坏时间复杂度空间复杂度稳定性直接插入O(n²)O(n²)O(1)稳定希尔排序O(n^1.3)O(n²)O(1)不稳定冒泡排序O(n²)O(n²)O(1)稳定快速排序O(n log n)O(n²)O(log n)不稳定简单选择O(n²)O(n²)O(1)不稳定堆排序O(n log n)O(n log n)O(1)不稳定归并排序O(n log n)O(n log n)O(n)稳定基数排序O(d(nr))O(d(nr))O(nr)稳定这张表我备考时自己默写了好几遍上机前再扫一眼确保不会在简单概念题上丢分。4.2 快排和堆排必须能手写快排是西电上机的高频题目基本每年都有考到的概率。这里给的实现是经典Lomuto分区法代码短不容易出错void quickSort(int arr[], int left, int right) { if (left right) return; int pivot arr[right]; int i left - 1; for (int j left; j right; j) { if (arr[j] pivot) { i; int tmp arr[i]; arr[i] arr[j]; arr[j] tmp; } } arr[right] arr[i 1]; arr[i 1] pivot; quickSort(arr, left, i); quickSort(arr, i 2, right); }堆排序的重点是向下调整函数。我当时自己写的时候总把下标的(i-1)/2和2*i1搞混后来发现只要画一个数组下标对应的二叉树就清楚了建议你也别硬记直接在草稿纸上画棵完全二叉树辅助推。void heapify(int arr[], int n, int i) { int largest i; int left 2 * i 1; int right 2 * i 2; if (left n arr[left] arr[largest]) largest left; if (right n arr[right] arr[largest]) largest right; if (largest ! i) { int tmp arr[i]; arr[i] arr[largest]; arr[largest] tmp; heapify(arr, n, largest); } } void heapSort(int arr[], int n) { for (int i n / 2 - 1; i 0; i--) heapify(arr, n, i); for (int i n - 1; i 0; i--) { int tmp arr[0]; arr[0] arr[i]; arr[i] tmp; heapify(arr, i, 0); } }4.3 折半查找与哈希冲突处理折半查找上机题一般会给一个有序数组和一个目标值让你输出查找过程的下标变化或者直接返回找到的位置。这个算法本身不难但循环条件low high很容易被写错。如果你写的是low high那么当low high且该位置正好是目标值时就会漏查。所以记牢这个边界条件。哈希表是另一个高频考点。最常见的构造方法是除留余数法H(key) key % p其中p是表长或一个不大于表长的质数。冲突处理方法常考两个线性探测再散列和链地址法。线性探测的代码很短核心就是在表里循环找空位int hashInsert(int table[], int size, int key) { int h key % size; int pos h; for (int i 0; i size; i) { pos (h i) % size; if (table[pos] -1) { // -1表示空位 table[pos] key; return pos; } } return -1; // 表满 }写哈希表的题时注意题目对冲突次数的要求。有时候它要求你输出每个关键字经过了几次探测才插入成功那就要在循环里加一个计数器每次pos变化时加1。这个细节只有写代码时才会暴露看概念是看不出来的。5. 上机环境的门道从编译到调试的实操经验5.1 编译器与工程配置西电的数据结构上机不同校区、不同机房配置可能不同。我了解到的常见情况分别是Windows环境下的Dev-C或Visual Studio以及Linux环境下的GCC。无论哪个都要提前确认好两件事。第一代码文件用什么后缀名。.c还是.cpp影响很大因为有些老师如果你交了.cpp会用C编译器编译那代码里的malloc和强制转换就有可能因为规范要求不同而出问题。我当年就吃过这个亏明明是纯C代码因为文件名写成了.cpp结果提交后编译多了一堆warning虽然最后程序能跑但心里总是没底。第二是否允许使用scanf和printf。数据结构上机题基本都用这两个函数因为它们简单直观。不要用cin/cout因为有些版本的编译开关没开流输入输出可能不兼容。纯C语言环境下最稳的组合就是scanf/printf加malloc/free。5.2 输入输出格式那些不被明说的规则上机题输入输出格式是翻车重灾区。我总结出最常见的三种情况。第一种是多组数据直到EOF。题目会写输入包含多组测试用例每组输入一个整数n那么你的程序就得写成while (scanf(%d, n) ! EOF)不能只处理一组数据。我在模拟练习时就因为只写了一次scanf导致第二组数据直接没有进入处理流程整个程序的输出和样例完全对不上当时折腾了很久才反应过来。第二种是每行输出的末尾空格。有些题目对输出格式要求很严格多余的空格会被认为是格式错误。最简单的处理方式是设一个标记变量int first 1; for (int i 0; i n; i) { if (!first) printf( ); else first 0; printf(%d, arr[i]); } printf(\n);这样就能保证行内元素之间只有一个空格且行尾没有多余空格。这个方法虽小但能省掉很多调试时间。第三种是输入里包含字符。有些链表的题会以1 2 3 4 0这样以0结尾的方式输入而有些树的题会要求用-1表示空节点。这类题目的输入长度不固定所以你必须先判断结束条件再决定是否读入下一个数。最笨但最实用的办法是先把全部数据当成一个数组读进来再从头构建树或链表虽然多占了点内存但逻辑上更稳妥不容易因为边读边构建而出错。5.3 排查段错误的有效方法上机时遇到段错误是最让人崩溃的因为报错信息提示很弱只会显示Segmentation fault或直接闪退。我吃过几次亏后总结出一套排查流程。首先在代码开头把所有数组长度加上足够余量。比如题目说节点数不超过20开数组时直接开到105避免因为下标越界而段错误。这是最简单粗暴也最有效的方法尤其在西电的考场上没有人会要求你把内存空间算到精确。其次使用printf插桩法定位。在关键循环和函数入口处临时插入printf(here 1\n)之类的标记看程序最后输出到哪个位置就说明出错在哪附近。虽然看起来原始但在考场上比不会用gdb的尴尬好上一万倍。如果你会用gdb还是建议提前练一练break、next、print这六个命令考场上遇到复杂问题能明显提升排查效率。最后特别检查所有涉及cur-next的地方。链表题的段错误十有八九是空指针解引用所以写代码时凡是访问了指针的成员变量都要有这个指针有没有可能为NULL的意识。6. 考前一周的冲刺安排模拟、总结、心态6.1 一周复习节奏表最后一周千万不要再去啃新算法了收益太低。我的做法是把重点放在默写模板和环境模拟上。下面是一份可参照的节奏表时间内容安排目标第1天手写线性表、链表全部模板无错写出链表反转、合并、约瑟夫环第2天手写二叉树遍历、层次遍历、求深度递归不犹豫层次遍历独立完成第3天手写快排、堆排、折半查找边界条件不出错第4天手写哈希表、线性探测、DFS/BFS能处理输入多组数据直到EOF第5天模拟整套上机题限时2小时提前暴露环境和不熟悉的地方第6天复盘错题整理自己的易错点清单知道自己的薄弱环节第7天只看模板和自己的易错点不动手敲保持手感心态放松模拟的时候有个技巧尽量完全还原考场条件。比如考试如果是在Linux终端下用gcc编译那你模拟时就不要在Visual Studio里敲代码因为两者的编译警告、内存出错表现完全不同。提前适应环境能减少很多考场上不必要的紧张感。6.2 最后三个晚上做什么我把最后三个晚上定为只做三件事默写模板、看易错笔记、早睡。默写模板指的是在不看任何资料的情况下把链表反转、快排、层次遍历、DFS、线性探测哈希这几个核心代码完整写在纸上。写不出来的地方就是你第二天必须再看一眼的地方。这个方法看起来很笨但对形成肌肉记忆非常有效考场上你会发现自己写代码的速度比平时快不少。易错笔记不需要记得多花哨就是自己在模拟练习中踩过的坑。我当年的笔记上大概有这么几条插入删除的循环边界、输出行尾空格、EOF循环开头、数组开大一个数量级、输入字符要加getchar或scanf( %c)等。考前快速过一遍比再刷十几道题有用得多。关于心态就一条建议上机时如果某道题卡了二十分钟还没有思路果断先跳到下一题。西电的数据结构上机题通常分值分布比较均匀一道题卡太久导致后面的题没时间写整体损失很大。把能拿的分都拿到就已经比大多数同学表现好了。我个人的体会是西电数据结构上机并没有想象中那么可怕它很有自己的规律。只要把基础模板练到肌肉记忆再把环境细节摸透考场上稳稳发挥不成问题。最后再分享一个小技巧考前一天把电脑的输入法切到英文模式避免考试时因为中文输入弹出提示框干扰你敲代码。这个细节看似微不足道但确实有人在紧张关头被它打断过思路。
西电数据结构上机全攻略：考点模板与调试技巧
西电的数据结构上机放在整个课程体系里说大不大说小不小。大是因为它直接决定你期末总评能不能往上拉一截小是因为考来考去就是那几类题线性表、链表、树、图、排序、查找翻来覆去。但每年照样有人因为环境不熟、输入输出处理不当、递归超时这类问题翻车。这篇文章就是我根据自己的备考经历和帮同学复盘时总结出来的完整复习路线围绕考点范围、代码模板、编译环境、调试技巧、考前安排五个方面展开争取让你花最少的时间把该拿的分稳稳拿下。1. 西电上机到底考什么先摸着题型的底1.1 上机形式的真实情况西电数据结构上机不同学期、不同老师可能略有差别但总体模式很统一在规定时间内通常是两到三小时用C语言在指定环境下完成两到四道编程题现场编译运行提交代码或直接由老师在终端里查看运行结果。题目不会像ACM竞赛那样绕弯子基本就是课内知识点的直接应用甚至有一半题目能在课本习题和实验指导书上找到原型。教材以严蔚敏《数据结构C语言版》为主这一点直接决定了出题风格——偏重基础逻辑和算法本身的实现而不是偏重STL封装或C高级特性。所以复习时如果只看思路不动手敲代码上机时大概率会卡在很基础的语法错误上。另外虽然课程名是数据结构但上机时对算法复杂度是有隐性要求的比如单链表的逆置就要求你写O(n)的双指针迭代而不是每次先遍历求长度再交换。1.2 考点优先级排序与复习策略我给自己的复习排了一个优先级实际用下来效率不错你可以直接参考优先级考点模块典型题型复习价值高线性表与链表顺序表插入删除、链表反转、合并有序链表、约瑟夫环必考且最容易拿分高二叉树操作递归遍历、层次遍历、求深度、镜像翻转高频出现递归必须要顺高排序算法快排、堆排、冒泡、直接插入、希尔、归并考察频率极高复杂度要背中图的基本算法DFS、BFS、邻接矩阵/邻接表转换、Dijkstra出题概率不低模板要滚瓜烂熟中栈与队列括号匹配、表达式求值、循环队列和链表树结合出题中查找与哈希顺序/折半查找、哈希表构造、冲突处理概念题上机化难度不大低串与数组KMP、矩阵压缩存储出题少时间紧可跳过策略上我建议先把自己最熟的部分练到闭眼能写再花时间啃薄弱环节。比如链表反转这个题你如果能在五分钟内无错写完考场上就相当于送分题反之如果你还在想指针到底怎么指就要多投入时间。上机考试和笔试最大的区别是它不给思考的缓冲平时练到条件反射的程度考场上才能真正发挥。2. 线性表与链表拿分最稳也最易翻车的模块2.1 顺序表的基本操作插删查要写利索顺序表这部分很多同学觉得很简单结果上机时反而在细节上出错。比如插入操作中插入位置的判断删除操作中元素的移动方向。我习惯用一段标准模板来解决#include stdio.h #include stdlib.h #define MAXSIZE 100 typedef struct { int data[MAXSIZE]; int length; } SeqList; int insert(SeqList *L, int pos, int e) { if (L-length MAXSIZE) return 0; // 表满 if (pos 1 || pos L-length 1) return 0; // 位置非法 for (int i L-length; i pos; i--) { L-data[i] L-data[i - 1]; } L-data[pos - 1] e; L-length; return 1; } int deleteElem(SeqList *L, int pos, int *e) { if (pos 1 || pos L-length) return 0; *e L-data[pos - 1]; for (int i pos; i L-length; i) { L-data[i - 1] L-data[i]; } L-length--; return 1; }这里最容易错的地方是两个循环的边界。插入时循环是i pos因为你要把pos位置及其后面的所有元素后移一格删除时循环是i L-length因为要把pos位置后面的元素前移。我在第一次练的时候就因为把循环边界写反导致数据错乱后来干脆把这两段模板背熟考场上直接默写几乎不出错。2.2 链表高频题反转、合并、约瑟夫环链表部分最常考的就是单链表反转。迭代版的三指针法是标准解法我备考时先写了递归版觉得代码更短但上机时一紧张容易绕晕后来果断用迭代版。typedef struct Node { int data; struct Node *next; } Node; Node* reverseList(Node *head) { Node *prev NULL, *cur head; while (cur ! NULL) { Node *next cur-next; // 先保存下一个节点 cur-next prev; // 指向前一个节点 prev cur; // prev 前进一步 cur next; // cur 前进一步 } return prev; // 新的头结点 }合并两个有序链表也值得专门练一下因为这道题既能考察对链表操作的熟悉程度也能考察边界情况的处理。我一般用一个哨兵头节点减少特判Node* mergeTwoLists(Node *l1, Node *l2) { Node dummy; dummy.next NULL; Node *tail dummy; while (l1 l2) { if (l1-data l2-data) { tail-next l1; l1 l1-next; } else { tail-next l2; l2 l2-next; } tail tail-next; } tail-next l1 ? l1 : l2; return dummy.next; }哨兵节点的思路就是从链表头开始不用单独处理第一个节点这种特判代码会短很多也更容易想清楚。约瑟夫环这个经典题也大概率出现过用循环链表模拟一下就行但要注意节点的释放顺序避免内存泄漏。2.3 链表题的三个常见坑我帮同学复盘时发现链表的坑集中在三个方面。第一是头指针被修改。很多同学在反转或删除时直接动了head结果后面还想用原始链表就丢了。解决办法是传入时用局部指针接收返回值或者所有操作都在局部变量上进行最后再赋给head。第二是空指针解引用。没有判断cur-next NULL就访问cur-next-data直接段错误。上机环境对段错误一般不会给太详细的提示所以写循环时要条件反射性地检查指针。第三是内存管理。严蔚敏教材本身就强调C语言封装上机题也会要求你自主分配节点。千万记得free掉不需要的节点否则虽然不影响运行但老师可能会看代码质量扣分。3. 树和图递归功底直接决定上限3.1 二叉树递归遍历必须写到条件反射西电上机对二叉树的考察频率相当高最常见的就是递归遍历、层次遍历、求深度、交换左右子树这四件事。递归遍历本身不难但你必须做到不假思索地写出来因为后续几乎所有树题都是在这三个遍历的基础上变形的。typedef struct BiTNode { int data; struct BiTNode *lchild, *rchild; } BiTNode; void preOrder(BiTNode *T) { if (T NULL) return; printf(%d , T-data); preOrder(T-lchild); preOrder(T-rchild); } void inOrder(BiTNode *T) { if (T NULL) return; inOrder(T-lchild); printf(%d , T-data); inOrder(T-rchild); } void postOrder(BiTNode *T) { if (T NULL) return; postOrder(T-lchild); postOrder(T-rchild); printf(%d , T-data); }非递归遍历上机时出现的概率更高因为老师可能专门出一道不用递归实现先序/中序遍历来考察栈的掌握情况。先序遍历的非递归实现最简单先访问根节点再把右孩子入栈、左孩子入栈因为栈是后进先出要保证左孩子先被访问就得后入栈。3.2 层次遍历与二叉树的输出格式层次遍历需要队列我在上机时喜欢用数组模拟队列既省去链表队列的麻烦代码也更直观。void levelOrder(BiTNode *root) { if (root NULL) return; BiTNode *queue[100]; int front 0, rear 0; queue[rear] root; while (front rear) { BiTNode *cur queue[front]; printf(%d , cur-data); if (cur-lchild) queue[rear] cur-lchild; if (cur-rchild) queue[rear] cur-rchild; } }上机时有个细节很多人忽视输出格式。题目要求每行输出几个节点、是否需要把空节点也打印成#或者null这类要求往往在题目描述里写得很细。我当年就遇到过一道按满二叉树补空的层次遍历题要求空节点输出为#结果我没仔细读题直接漏掉空节点判断第一遍运行结果和样例对不上浪费了十几分钟排查。3.3 图的DFS与BFS邻接矩阵版本最稳妥图的题在西电上机中出现频率不算最高但一旦出了分值往往不小。最稳妥的方案是用邻接矩阵存储比邻接表好写很多也不会因为指针问题出错。DFS和BFS的模板如下#define N 100 int graph[N][N]; int visited[N]; void dfs(int v, int n) { visited[v] 1; printf(%d , v); for (int i 1; i n; i) { if (graph[v][i] !visited[i]) { dfs(i, n); } } } void bfs(int start, int n) { int queue[N]; int front 0, rear 0; visited[start] 1; queue[rear] start; while (front rear) { int v queue[front]; printf(%d , v); for (int i 1; i n; i) { if (graph[v][i] !visited[i]) { visited[i] 1; queue[rear] i; } } } }Dijkstra算法如果考到建议直接背一个最简的邻接矩阵版模板。核心就三步找当前未访问节点中距离最小的标记访问用它更新所有邻居的最短距离。次数多了自然就记住了。注意考试时如果你看到图题先判断数据规模如果是几十个节点的稠密图邻接矩阵完全够用。4. 排序查找与哈希复杂度表背熟才能不丢基础分4.1 八种排序的复杂度对照表排序算法这部分上机题可能会让你完整实现某一种排序也可能会在一道综合题中要求先排序再查找。笔试和上机的一个显著区别是上机更看重实现是否无错但排序的复杂度判断仍然是老师考察的重点甚至会在题目描述里直接问该排序算法在最好情况下的时间复杂度是多少。排序算法平均时间复杂度最坏时间复杂度空间复杂度稳定性直接插入O(n²)O(n²)O(1)稳定希尔排序O(n^1.3)O(n²)O(1)不稳定冒泡排序O(n²)O(n²)O(1)稳定快速排序O(n log n)O(n²)O(log n)不稳定简单选择O(n²)O(n²)O(1)不稳定堆排序O(n log n)O(n log n)O(1)不稳定归并排序O(n log n)O(n log n)O(n)稳定基数排序O(d(nr))O(d(nr))O(nr)稳定这张表我备考时自己默写了好几遍上机前再扫一眼确保不会在简单概念题上丢分。4.2 快排和堆排必须能手写快排是西电上机的高频题目基本每年都有考到的概率。这里给的实现是经典Lomuto分区法代码短不容易出错void quickSort(int arr[], int left, int right) { if (left right) return; int pivot arr[right]; int i left - 1; for (int j left; j right; j) { if (arr[j] pivot) { i; int tmp arr[i]; arr[i] arr[j]; arr[j] tmp; } } arr[right] arr[i 1]; arr[i 1] pivot; quickSort(arr, left, i); quickSort(arr, i 2, right); }堆排序的重点是向下调整函数。我当时自己写的时候总把下标的(i-1)/2和2*i1搞混后来发现只要画一个数组下标对应的二叉树就清楚了建议你也别硬记直接在草稿纸上画棵完全二叉树辅助推。void heapify(int arr[], int n, int i) { int largest i; int left 2 * i 1; int right 2 * i 2; if (left n arr[left] arr[largest]) largest left; if (right n arr[right] arr[largest]) largest right; if (largest ! i) { int tmp arr[i]; arr[i] arr[largest]; arr[largest] tmp; heapify(arr, n, largest); } } void heapSort(int arr[], int n) { for (int i n / 2 - 1; i 0; i--) heapify(arr, n, i); for (int i n - 1; i 0; i--) { int tmp arr[0]; arr[0] arr[i]; arr[i] tmp; heapify(arr, i, 0); } }4.3 折半查找与哈希冲突处理折半查找上机题一般会给一个有序数组和一个目标值让你输出查找过程的下标变化或者直接返回找到的位置。这个算法本身不难但循环条件low high很容易被写错。如果你写的是low high那么当low high且该位置正好是目标值时就会漏查。所以记牢这个边界条件。哈希表是另一个高频考点。最常见的构造方法是除留余数法H(key) key % p其中p是表长或一个不大于表长的质数。冲突处理方法常考两个线性探测再散列和链地址法。线性探测的代码很短核心就是在表里循环找空位int hashInsert(int table[], int size, int key) { int h key % size; int pos h; for (int i 0; i size; i) { pos (h i) % size; if (table[pos] -1) { // -1表示空位 table[pos] key; return pos; } } return -1; // 表满 }写哈希表的题时注意题目对冲突次数的要求。有时候它要求你输出每个关键字经过了几次探测才插入成功那就要在循环里加一个计数器每次pos变化时加1。这个细节只有写代码时才会暴露看概念是看不出来的。5. 上机环境的门道从编译到调试的实操经验5.1 编译器与工程配置西电的数据结构上机不同校区、不同机房配置可能不同。我了解到的常见情况分别是Windows环境下的Dev-C或Visual Studio以及Linux环境下的GCC。无论哪个都要提前确认好两件事。第一代码文件用什么后缀名。.c还是.cpp影响很大因为有些老师如果你交了.cpp会用C编译器编译那代码里的malloc和强制转换就有可能因为规范要求不同而出问题。我当年就吃过这个亏明明是纯C代码因为文件名写成了.cpp结果提交后编译多了一堆warning虽然最后程序能跑但心里总是没底。第二是否允许使用scanf和printf。数据结构上机题基本都用这两个函数因为它们简单直观。不要用cin/cout因为有些版本的编译开关没开流输入输出可能不兼容。纯C语言环境下最稳的组合就是scanf/printf加malloc/free。5.2 输入输出格式那些不被明说的规则上机题输入输出格式是翻车重灾区。我总结出最常见的三种情况。第一种是多组数据直到EOF。题目会写输入包含多组测试用例每组输入一个整数n那么你的程序就得写成while (scanf(%d, n) ! EOF)不能只处理一组数据。我在模拟练习时就因为只写了一次scanf导致第二组数据直接没有进入处理流程整个程序的输出和样例完全对不上当时折腾了很久才反应过来。第二种是每行输出的末尾空格。有些题目对输出格式要求很严格多余的空格会被认为是格式错误。最简单的处理方式是设一个标记变量int first 1; for (int i 0; i n; i) { if (!first) printf( ); else first 0; printf(%d, arr[i]); } printf(\n);这样就能保证行内元素之间只有一个空格且行尾没有多余空格。这个方法虽小但能省掉很多调试时间。第三种是输入里包含字符。有些链表的题会以1 2 3 4 0这样以0结尾的方式输入而有些树的题会要求用-1表示空节点。这类题目的输入长度不固定所以你必须先判断结束条件再决定是否读入下一个数。最笨但最实用的办法是先把全部数据当成一个数组读进来再从头构建树或链表虽然多占了点内存但逻辑上更稳妥不容易因为边读边构建而出错。5.3 排查段错误的有效方法上机时遇到段错误是最让人崩溃的因为报错信息提示很弱只会显示Segmentation fault或直接闪退。我吃过几次亏后总结出一套排查流程。首先在代码开头把所有数组长度加上足够余量。比如题目说节点数不超过20开数组时直接开到105避免因为下标越界而段错误。这是最简单粗暴也最有效的方法尤其在西电的考场上没有人会要求你把内存空间算到精确。其次使用printf插桩法定位。在关键循环和函数入口处临时插入printf(here 1\n)之类的标记看程序最后输出到哪个位置就说明出错在哪附近。虽然看起来原始但在考场上比不会用gdb的尴尬好上一万倍。如果你会用gdb还是建议提前练一练break、next、print这六个命令考场上遇到复杂问题能明显提升排查效率。最后特别检查所有涉及cur-next的地方。链表题的段错误十有八九是空指针解引用所以写代码时凡是访问了指针的成员变量都要有这个指针有没有可能为NULL的意识。6. 考前一周的冲刺安排模拟、总结、心态6.1 一周复习节奏表最后一周千万不要再去啃新算法了收益太低。我的做法是把重点放在默写模板和环境模拟上。下面是一份可参照的节奏表时间内容安排目标第1天手写线性表、链表全部模板无错写出链表反转、合并、约瑟夫环第2天手写二叉树遍历、层次遍历、求深度递归不犹豫层次遍历独立完成第3天手写快排、堆排、折半查找边界条件不出错第4天手写哈希表、线性探测、DFS/BFS能处理输入多组数据直到EOF第5天模拟整套上机题限时2小时提前暴露环境和不熟悉的地方第6天复盘错题整理自己的易错点清单知道自己的薄弱环节第7天只看模板和自己的易错点不动手敲保持手感心态放松模拟的时候有个技巧尽量完全还原考场条件。比如考试如果是在Linux终端下用gcc编译那你模拟时就不要在Visual Studio里敲代码因为两者的编译警告、内存出错表现完全不同。提前适应环境能减少很多考场上不必要的紧张感。6.2 最后三个晚上做什么我把最后三个晚上定为只做三件事默写模板、看易错笔记、早睡。默写模板指的是在不看任何资料的情况下把链表反转、快排、层次遍历、DFS、线性探测哈希这几个核心代码完整写在纸上。写不出来的地方就是你第二天必须再看一眼的地方。这个方法看起来很笨但对形成肌肉记忆非常有效考场上你会发现自己写代码的速度比平时快不少。易错笔记不需要记得多花哨就是自己在模拟练习中踩过的坑。我当年的笔记上大概有这么几条插入删除的循环边界、输出行尾空格、EOF循环开头、数组开大一个数量级、输入字符要加getchar或scanf( %c)等。考前快速过一遍比再刷十几道题有用得多。关于心态就一条建议上机时如果某道题卡了二十分钟还没有思路果断先跳到下一题。西电的数据结构上机题通常分值分布比较均匀一道题卡太久导致后面的题没时间写整体损失很大。把能拿的分都拿到就已经比大多数同学表现好了。我个人的体会是西电数据结构上机并没有想象中那么可怕它很有自己的规律。只要把基础模板练到肌肉记忆再把环境细节摸透考场上稳稳发挥不成问题。最后再分享一个小技巧考前一天把电脑的输入法切到英文模式避免考试时因为中文输入弹出提示框干扰你敲代码。这个细节看似微不足道但确实有人在紧张关头被它打断过思路。
