简介这份资源是西南大学网络与继续教育学院2020年春季数据结构课程编号0012A卷考试的参考答案文档面向选修该课程、需要核对大作业解题思路的网教学生与自学者。压缩包内仅1个docx文件约35KB内容按试题顺序给出完整解答。参考答案覆盖单链表改造为单向循环链表的算法设计与复杂度分析、由先序与中序序列还原二叉树并求后序序列、用权集合构造哈夫曼树并计算带权路径长度、依据Prim算法构造最小生成树以及哈希表线性探测法建表与平均查找长度ASL计算等核心考点每题均附推导过程与结果。目前已有55人学习浏览适合备考冲刺阶段对照自查、梳理算法步骤与巩固数据结构基础。1. 西南大学2020年春季数据结构考试一份真题卷能挖出多少复习盲区每年春季学期总有一批同学在数据结构这门课上栽跟头。不是因为题目有多偏而是因为复习方向跑偏了——把大量时间花在背诵概念上结果考试一上来就是画图、写算法、算时间复杂度。西南大学2020年春季的这份数据结构课程考试卷恰好是一份典型的“重实操、轻背诵”的样本。它覆盖了线性表、树与二叉树、图、排序、查找这几个核心模块题型包括选择、填空、简答、算法设计。如果你正在准备数据结构期末复习或者考研408的图与数组部分这份卷子的价值不在于“对答案”而在于帮你定位哪些知识点你以为会了其实一写就错。这篇文章面向正在备考数据结构的学生和需要快速梳理知识框架的自学者把这份卷子背后的考点拆开给出可复现的复习路径和代码验证方法。2. 从卷面结构反推考点分布哪些章节在考试里权重最高2.1 题型与分值分布还原虽然无法逐字还原原卷但根据2020年前后西南大学数据结构课程的常见命题风格以及热搜词中“数据结构期末复习”“考研数据结构”“数据结构408 图和数组”的高频出现可以推断这份卷子的结构大致如下题型题量单题分值总分主要覆盖章节选择题10220线性表、栈与队列、树、图、排序填空题5210时间复杂度、存储结构、遍历序列简答题4520树的性质、图的存储、排序过程算法设计题31030链表操作、二叉树遍历、图的最短路径综合应用题21020哈希表、最小生成树或拓扑排序这个分布透露一个信号算法设计题和综合应用题占了半壁江山。也就是说光背定义没用必须能手写代码或伪代码。很多同学在复习时把精力放在选择题上结果大题写不出来这是最常见的翻车方式。2.2 各章节的复习优先级排序根据卷面权重和热搜词中“数据结构排序算法”“数据结构 双端队列”“数据结构c语言版”的热度我一般会建议按以下优先级分配复习时间第一优先级树与二叉树。几乎每年必考且容易出算法设计题。重点包括二叉树的三种遍历递归与非递归、线索二叉树、哈夫曼树构造、二叉排序树的插入与删除。第二优先级图。408和图数组的热搜说明这是很多人的薄弱点。重点包括邻接矩阵与邻接表的转换、DFS与BFS遍历、最小生成树Prim和Kruskal、最短路径Dijkstra和Floyd、拓扑排序。第三优先级排序。快速排序、归并排序、堆排序的过程和复杂度分析是高频考点。希尔排序和基数排序偶尔出现但分值不高。第四优先级线性表、栈与队列。选择题和填空题为主算法题可能涉及链表操作。双端队列是近年新增的热点需要理解其插入删除的四种组合。第五优先级查找。二叉排序树、平衡二叉树、B树、哈希表。哈希表的冲突处理和查找长度计算是简答题常客。提示如果你的复习时间只剩两周优先把树和图的算法设计题手写三遍以上排序算法能默写过程即可。3. 手写代码验证核心考点从链表到图的完整复现3.1 单链表反转与双端队列的代码实现链表操作是算法设计题的基础。卷子里如果出现链表题大概率是反转、合并、找中间节点这三类。下面用C语言写一个带头结点的单链表反转这是最常考的版本#include stdio.h #include stdlib.h typedef struct Node { int data; struct Node *next; } Node; // 头插法反转链表 Node* reverseList(Node *head) { if (head NULL || head-next NULL) { return head; } Node *prev NULL; Node *curr head-next; // 从头结点后的第一个节点开始 while (curr ! NULL) { Node *nextTemp curr-next; // 暂存下一个节点 curr-next prev; // 当前节点指向前一个 prev curr; // prev后移 curr nextTemp; // curr后移 } head-next prev; // 头结点指向新的第一个节点 return head; } // 打印链表 void printList(Node *head) { Node *p head-next; while (p ! NULL) { printf(%d , p-data); p p-next; } printf(\n); } int main() { Node *head (Node*)malloc(sizeof(Node)); head-next NULL; // 头插法建立链表 1-2-3-4-5 for (int i 5; i 1; i--) { Node *newNode (Node*)malloc(sizeof(Node)); newNode-data i; newNode-next head-next; head-next newNode; } printf(反转前: ); printList(head); head reverseList(head); printf(反转后: ); printList(head); return 0; }这段代码的关键在于三个指针的移动顺序先存下一个节点再反转当前指针最后移动prev和curr。参数说明head是带头结点的链表头函数返回反转后的头结点。时间复杂度O(n)空间复杂度O(1)。考试时如果要求写伪代码把while循环里的三行写清楚就能拿大部分分。双端队列的考点通常出现在选择题或填空题里问的是“输入受限”和“输出受限”两种情况下哪些输出序列是合法的。我一般会教学生用模拟法画一个队列两端标上L和R然后按题目给的插入删除顺序手动走一遍。比如输入序列1,2,3,4输出受限的双端队列能否得到4,2,3,1手动模拟发现不行因为4要先出必须从同一端进出但2和3的顺序会被打乱。3.2 二叉树非递归遍历的三种写法二叉树遍历是算法设计题的重灾区。递归写法太简单考试往往要求非递归。下面用C语言写中序非递归遍历这是最常考的一种#include stdio.h #include stdlib.h typedef struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; } TreeNode; // 中序非递归遍历 void inorderTraversal(TreeNode *root) { TreeNode *stack[100]; // 简单数组模拟栈 int top -1; TreeNode *curr root; while (curr ! NULL || top ! -1) { // 一路向左把左孩子全部入栈 while (curr ! NULL) { stack[top] curr; curr curr-left; } // 弹出栈顶访问然后转向右孩子 curr stack[top--]; printf(%d , curr-val); curr curr-right; } } // 创建节点 TreeNode* createNode(int val) { TreeNode *node (TreeNode*)malloc(sizeof(TreeNode)); node-val val; node-left NULL; node-right NULL; return node; } int main() { // 构造一棵简单的树 // 1 // / \ // 2 3 // / \ // 4 5 TreeNode *root createNode(1); root-left createNode(2); root-right createNode(3); root-left-left createNode(4); root-left-right createNode(5); printf(中序遍历: ); inorderTraversal(root); printf(\n); return 0; }逻辑说明中序遍历的顺序是左-根-右。非递归的核心是用栈模拟递归调用。先把所有左孩子入栈直到没有左孩子然后弹出栈顶访问再转向右孩子。参数说明stack数组模拟栈top指向栈顶元素下标初始为-1。时间复杂度O(n)空间复杂度O(n)。前序和后序的非递归写法类似后序稍微复杂一点需要记录上一个访问的节点。考试时如果要求写后序非递归可以用双栈法先按根-右-左的顺序入栈再反转输出。或者用一个栈加一个lastVisited指针。我一般建议学生至少掌握中序和前序的非递归后序如果时间不够可以放弃。3.3 图的最短路径Dijkstra算法手写模板图论部分是很多人的噩梦尤其是Dijkstra算法。下面用C语言写一个邻接矩阵版本的Dijkstra这是考试最可能要求的写法#include stdio.h #include limits.h #define V 6 // 顶点数 #define INF 9999 // 找到距离最小的未访问顶点 int minDistance(int dist[], int visited[]) { int min INF, minIndex; for (int v 0; v V; v) { if (visited[v] 0 dist[v] min) { min dist[v]; minIndex v; } } return minIndex; } // Dijkstra算法 void dijkstra(int graph[V][V], int src) { int dist[V]; // 存储从源点到各点的最短距离 int visited[V]; // 标记是否已确定最短路径 // 初始化 for (int i 0; i V; i) { dist[i] INF; visited[i] 0; } dist[src] 0; // 循环V-1次 for (int count 0; count V - 1; count) { int u minDistance(dist, visited); visited[u] 1; // 更新邻接顶点的距离 for (int v 0; v V; v) { if (!visited[v] graph[u][v] ! INF dist[u] ! INF dist[u] graph[u][v] dist[v]) { dist[v] dist[u] graph[u][v]; } } } // 输出结果 printf(从顶点%d到各点的最短距离:\n, src); for (int i 0; i V; i) { printf(到%d: %d\n, i, dist[i]); } } int main() { int graph[V][V] { {0, 2, INF, 1, INF, INF}, {2, 0, 3, 2, INF, INF}, {INF, 3, 0, INF, 1, 5}, {1, 2, INF, 0, 4, INF}, {INF, INF, 1, 4, 0, 3}, {INF, INF, 5, INF, 3, 0} }; dijkstra(graph, 0); return 0; }逻辑说明Dijkstra的核心是贪心策略。每次从未访问的顶点中选一个距离源点最近的标记为已访问然后用它去更新邻居的距离。参数说明graph是邻接矩阵INF表示不可达src是源点编号。时间复杂度O(V^2)如果用优先队列可以优化到O(E log V)但考试手写通常要求邻接矩阵版本。考试时容易出错的地方初始化时dist[src]要设为0其他设为INF更新条件里要判断graph[u][v] ! INF否则会溢出。我见过太多人忘记这个判断导致结果全错。4. 排序算法的手动模拟与复杂度速查4.1 快速排序一趟划分的三种写法快速排序是排序章节的绝对重点。考试通常要求写出某一趟划分后的结果或者手写划分函数。下面用C语言写一个经典的Hoare划分#include stdio.h // 一趟快速排序划分 int partition(int arr[], int low, int high) { int pivot arr[low]; // 选第一个元素为基准 while (low high) { // 从右往左找第一个小于pivot的元素 while (low high arr[high] pivot) { high--; } arr[low] arr[high]; // 放到左边 // 从左往右找第一个大于pivot的元素 while (low high arr[low] pivot) { low; } arr[high] arr[low]; // 放到右边 } arr[low] pivot; // 基准归位 return low; } void quickSort(int arr[], int low, int high) { if (low high) { int pivotPos partition(arr, low, high); quickSort(arr, low, pivotPos - 1); quickSort(arr, pivotPos 1, high); } } int main() { int arr[] {49, 38, 65, 97, 76, 13, 27, 49}; int n sizeof(arr) / sizeof(arr[0]); quickSort(arr, 0, n - 1); printf(排序结果: ); for (int i 0; i n; i) { printf(%d , arr[i]); } printf(\n); return 0; }逻辑说明Hoare划分用双指针从两端向中间扫描右边找小于基准的左边找大于基准的交换后继续。参数说明low和high是当前划分区间的下标。时间复杂度平均O(n log n)最坏O(n^2)当数组已经有序且选第一个元素为基准时。空间复杂度O(log n)递归栈。考试时如果要求写“挖坑法”思路类似只是把交换改成赋值。我一般建议学生掌握一种写法即可但要知道不同写法的区别。比如有的教材用“基准归位”法有的用“交换法”结果是一样的。4.2 各排序算法复杂度与稳定性对比表考试选择题和填空题经常考复杂度和稳定性。下面这张表建议直接背下来排序算法平均时间复杂度最坏时间复杂度空间复杂度稳定性直接插入O(n^2)O(n^2)O(1)稳定希尔排序O(n^1.3)O(n^2)O(1)不稳定冒泡排序O(n^2)O(n^2)O(1)稳定快速排序O(n log n)O(n^2)O(log n)不稳定简单选择O(n^2)O(n^2)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(r)稳定这张表里最容易记混的是希尔排序的时间复杂度不同教材写法不同考试一般写O(n^1.3)即可。稳定性的判断口诀不稳定的有“快希选堆”——快速、希尔、选择、堆排序。其他都是稳定的。注意归并排序的空间复杂度是O(n)不是O(1)。很多同学在填空题里写错。5. 避坑与排查考场上最容易丢分的五个细节5.1 时间复杂度算错嵌套循环不一定乘起来现象看到两层循环就写O(n^2)结果错了。原因内层循环的边界可能依赖外层变量比如for(i0;in;i) for(ji;jn;j)实际执行次数是n(n1)/2复杂度还是O(n^2)但如果是for(i1;in;i*2)这种复杂度是O(log n)。解决逐层分析执行次数用求和公式算不要凭感觉。5.2 二叉树遍历序列还原时搞混前序和中序现象给出前序和中序要求画树结果画反了。原因前序的第一个是根中序的根在中间后序的根在最后。记混了顺序就会全错。解决记住口诀“前序根在前中序根在中后序根在后”。画树时先找根再分左右子树递归处理。5.3 图的邻接表遍历时忘记标记已访问现象DFS或BFS写出来死循环。原因图中存在环访问过的节点没有标记导致重复入栈或入队。解决在访问节点时立即标记visited不要等到出栈或出队才标记。BFS尤其要注意入队时就标记否则同一个节点可能被多次入队。5.4 哈希表查找长度计算时搞混成功和失败现象ASL成功和ASL失败算反了。原因成功查找是每个元素查找次数的平均值失败查找是每个空位置查找次数的平均值。解决成功ASL分母是元素个数失败ASL分母是哈希表长度或模数。画表时把每个位置的探测次数标出来再分别计算。5.5 算法设计题只写思路不写代码现象题目要求“写出算法”只写了文字描述扣分严重。原因考试评分标准里代码占大头思路分很少。解决即使不确定语法也要把循环、条件、指针操作写出来。伪代码也可以但结构要完整。我一般建议学生至少写出函数头和核心循环。6. 用真题反推复习计划一个可复用的两周冲刺模板如果你手里有一份真题卷不管是西南大学2020年这份还是其他学校的都可以用下面这个模板来反推复习计划。核心思路是先做一遍卷子标记出所有写错的题然后按章节归类最后针对薄弱章节集中突破。第一周按章节刷题。周一线性表栈队列周二树与二叉树周三图周四排序周五查找周六哈希综合周日休息。每天先看教材对应章节然后做课后题最后手写一道算法设计题。第二周模拟考试查漏补缺。周一做第一套真题周二分析错题周三做第二套周四分析周五把错题涉及的知识点重新写一遍代码周六再快速过一遍复杂度表和稳定性表周日调整状态。这个模板的关键在于“手写代码”。很多同学复习时只看不写考场上提笔就忘。我自己的血泪经验是二叉树非递归遍历至少手写五遍Dijkstra至少手写三遍快速排序划分至少手写三遍。写多了形成肌肉记忆考场上不用想就能写出来。还有一个技巧把常考的算法做成卡片正面写题目要求背面写代码框架。每天抽十分钟随机抽一张在纸上默写。这个方法比反复看书有效得多。最后说一个我自己的习惯每次复习完一个章节我会合上书用白纸画一张思维导图把核心概念、算法步骤、复杂度、易错点全部写出来。画不出来的地方就是没掌握的立刻回去翻书。这个习惯帮我省了很多后悔药。希望帮到你。本文还有配套的精品资源点击获取