简介这份文档资料是《数据结构与算法》期中练习题的配套答案面向正在学习数据结构课程的高校学生与备考者帮助其核对解题思路、巩固核心考点。内容覆盖基本概念、线性结构、栈与队列、二叉树、算法设计及稀疏矩阵等模块包含选择题、指针操作、存储位置计算、循环队列状态填写、静态链表插入删除以及三元组顺序表转置等典型题型并给出对应解答过程。资源包内含1个doc文件大小约318KB结构紧凑便于打印或对照复习。目前已有127人学习下载适合需要系统梳理期中重点、查漏补缺的读者参考使用。1. 从一份“期中练习题答案”说起数据结构与算法到底该怎么练每年期中前后总有人翻出一份《数据结构与算法期中练习题答案.doc》想靠它把线性表、栈队列、树、图、排序、查找一口气吃下来。现实往往很骨感答案能看懂题目一换就不会王道408的题刷了不少真让你手写一个归并排序或者KMP的next数组还是卡壳。问题不在题量而在于你练的是“答案”而不是“过程”——数据结构与算法这门课考的是你能不能把抽象逻辑翻译成可运行、可验证的代码而不是背结论。这份材料真正能帮到的人有三类正在准备期中/期末、考研408数据结构的学生想用C语言或Java把链表、树、排序算法重新手写一遍的转行者以及需要快速核对答案、定位自己思路断点的自学者。它解决的不是“从零学算法”而是“把已经听过课的知识点通过题目和答案对照补上代码落地这一环”。下面我不谈空泛的学习方法直接按“知识点拆解—手写实现—对答案—避坑”的路径把这份练习题里最高频的几类题讲透让你拿到任何一份类似的.doc都能自己拆着练。2. 线性表与链表题从答案反推代码别只背结论2.1 顺序表和链表的选型先看题目在问什么期中练习题里关于线性表的第一类题通常是“在长度为n的顺序表中插入/删除一个元素平均移动多少次”。答案写的是插入 n/2、删除 (n-1)/2很多人背下来就完事。但真正要练的是为什么顺序表插入是O(n)而链表插入是O(1)因为顺序表要腾位置链表只要改指针。题目如果问“频繁插入删除选哪个”答案一定是链表如果问“频繁按位查找选哪个”答案一定是顺序表。这个判断逻辑比数字重要。我一般会让学生把这类题改写成代码用实际运行来验证。比如下面这段C语言分别用顺序表和单链表实现插入跑一遍就能直观看到移动次数的差别。#include stdio.h #include stdlib.h #define MAXSIZE 100 // 顺序表插入返回实际移动次数 int seq_insert(int arr[], int *len, int pos, int value) { if (pos 0 || pos *len || *len MAXSIZE) return -1; int moves 0; for (int i *len; i pos; i--) { // 从后往前腾位置 arr[i] arr[i - 1]; moves; } arr[pos] value; (*len); return moves; // 移动次数就是 n - pos } // 单链表节点 typedef struct Node { int data; struct Node *next; } Node; // 链表插入不需要移动只改指针 Node* list_insert(Node *head, int pos, int value) { Node *newNode (Node*)malloc(sizeof(Node)); newNode-data value; if (pos 0) { // 头插 newNode-next head; return newNode; } Node *p head; for (int i 0; i pos - 1 p; i) p p-next; if (!p) return head; // 位置越界简单返回 newNode-next p-next; p-next newNode; return head; } int main() { int arr[MAXSIZE] {1, 2, 3, 4, 5}; int len 5; int m seq_insert(arr, len, 2, 99); printf(顺序表插入移动次数: %d\n, m); // 输出 3 Node *head NULL; for (int i 5; i 1; i--) head list_insert(head, 0, i); head list_insert(head, 2, 99); printf(链表插入完成无移动\n); return 0; }这段代码的关键参数是pos和len。顺序表插入时循环从*len递减到pos1移动次数正好是*len - pos这就是答案里“平均n/2”的来源——因为pos从0到n均匀分布平均移动n/2次。链表插入的循环只负责找位置不搬数据所以移动次数为0。练习题答案如果只写“O(n)”你对照这段代码就能明白它指的是时间开销而不是移动次数。2.2 用“答案反推法”练链表操作题期中题里链表部分最爱考单链表逆置、找中间节点、判断是否有环、合并两个有序链表。答案往往只给几行伪代码比如“phead; qNULL; while(p){...}”。我的做法是先把答案盖住自己写一遍再对照答案找差异。差异通常出现在边界处理上——空链表、只有一个节点、尾节点。下面以单链表逆置为例给出可运行的完整代码并说明答案里容易省略的指针细节。// 单链表逆置三指针法 Node* reverse_list(Node *head) { Node *prev NULL; Node *curr head; while (curr ! NULL) { Node *nextTemp curr-next; // 先保存下一个节点 curr-next prev; // 当前节点指向前一个 prev curr; // prev后移 curr nextTemp; // curr后移 } return prev; // 新头节点 }逻辑说明nextTemp必须最先保存否则改完curr-next就找不到后面的节点了。参数上prev初始为NULL因为逆置后原头节点变成尾节点尾节点的next必须是NULL。练习题答案如果写“头插法”那是另一种思路新建一个空链表依次把原链表节点插到新链表头部效果一样但多用了空间。考试时两种都算对但三指针法空间O(1)更推荐。提示链表题写完一定要画图把每个指针的指向标出来比空想靠谱得多。3. 树与二叉树遍历、还原和408高频代码3.1 由遍历序列还原二叉树答案对不上怎么办期中练习题里必有一道给前序和中序求后序或者给中序和后序求前序。答案通常是一串字母但很多人自己推的时候总差一个位置。核心就一句话前序的第一个是根后序的最后一个是根中序用来分左右子树。我一般让学生用递归代码来验证手推结果而不是反复看答案。#include stdio.h #include string.h // 根据前序pre和中序in输出后序 void post_from_pre_in(char *pre, char *in, int len) { if (len 0) return; char root pre[0]; int rootIdx 0; while (in[rootIdx] ! root) rootIdx; // 在中序里找根的位置 // 左子树长度 rootIdx右子树长度 len - rootIdx - 1 post_from_pre_in(pre 1, in, rootIdx); // 递归左 post_from_pre_in(pre 1 rootIdx, in rootIdx 1, len - rootIdx - 1); // 递归右 printf(%c, root); // 后序最后访问根 } int main() { char pre[] ABDEC; char in[] DBEAC; post_from_pre_in(pre, in, strlen(pre)); printf(\n); // 输出 DEBCA return 0; }参数说明pre和in是当前子树的前序和中序起始地址len是当前子树节点数。递归左子树时前序从pre1开始中序从in开始长度是rootIdx递归右子树时前序从pre1rootIdx开始中序从inrootIdx1开始长度是len-rootIdx-1。这段代码跑出来的后序和答案对照如果不一样基本就是左右子树长度算错了。408数据结构代码必背里这个递归模板出现频率极高。3.2 二叉树的非递归遍历用栈模拟递归练习题答案里非递归遍历经常只给文字描述比如“用栈保存节点”。但真写起来中序非递归的循环条件容易写错。下面给出中序非递归的完整实现并标注关键参数。#include stdio.h #include stdlib.h typedef struct TreeNode { char data; struct TreeNode *left, *right; } TreeNode; // 中序非递归遍历 void inorder_nonrecursive(TreeNode *root) { TreeNode *stack[100]; // 简单数组模拟栈 int top -1; TreeNode *p root; while (p ! NULL || top ! -1) { while (p ! NULL) { // 一路向左入栈 stack[top] p; p p-left; } if (top ! -1) { p stack[top--]; // 出栈 printf(%c , p-data); // 访问 p p-right; // 转向右子树 } } }逻辑说明外层循环条件是p ! NULL || top ! -1缺一不可。内层while负责把左孩子全部入栈出栈后访问节点然后转向右孩子。参数top初始为-1表示空栈入栈用top出栈用top--。如果答案里写“栈空且p为空时结束”和这里的条件一致。常见错误是只写while(p)导致右子树还没处理就退出了。注意非递归遍历的栈深度最坏是O(n)练习题如果问空间复杂度别答O(1)。4. 排序算法手写归并、快排和堆排对答案不如对过程4.1 归并排序分治的边界是答案里最常省略的归并排序算法是热搜里的常客期中题一般要求写出归并过程或者补全代码。答案往往给一个merge函数但mid怎么算、临时数组开多大这些细节决定你能不能跑通。下面给出完整可运行的C语言归并排序。#include stdio.h #include stdlib.h // 合并两个有序区间 [left, mid] 和 [mid1, right] void merge(int arr[], int left, int mid, int right) { int n1 mid - left 1; int n2 right - mid; int *L (int*)malloc(n1 * sizeof(int)); int *R (int*)malloc(n2 * sizeof(int)); for (int i 0; i n1; i) L[i] arr[left i]; for (int j 0; j n2; j) R[j] arr[mid 1 j]; int i 0, j 0, k left; while (i n1 j n2) { if (L[i] R[j]) arr[k] L[i]; // 保证稳定性 else arr[k] R[j]; } while (i n1) arr[k] L[i]; while (j n2) arr[k] R[j]; free(L); free(R); } void merge_sort(int arr[], int left, int right) { if (left right) { int mid left (right - left) / 2; // 防止溢出 merge_sort(arr, left, mid); merge_sort(arr, mid 1, right); merge(arr, left, mid, right); } } int main() { int arr[] {38, 27, 43, 3, 9, 82, 10}; int n sizeof(arr) / sizeof(arr[0]); merge_sort(arr, 0, n - 1); for (int i 0; i n; i) printf(%d , arr[i]); return 0; }参数说明mid left (right - left) / 2比(leftright)/2更安全避免leftright溢出。merge里用而不是是为了保持稳定排序——相等时先取左边的。练习题答案如果只写“合并两个有序数组”你可以对照这段代码看它有没有处理剩余元素。归并排序的时间复杂度是O(n log n)空间O(n)这些在选择题里经常考。4.2 快速排序partition的三种写法与答案差异快排的partition是期中题的重灾区。答案可能给“挖坑法”“左右指针法”或“前后指针法”不同写法得到的中间序列可能不同但最终排序结果一样。下面用最经典的左右指针法实现并说明参数。// 左右指针法partition int partition(int arr[], int low, int high) { int pivot arr[low]; // 选第一个元素为基准 while (low high) { while (low high arr[high] pivot) high--; arr[low] arr[high]; while (low high arr[low] pivot) low; arr[high] arr[low]; } arr[low] pivot; return low; // 返回基准最终位置 } void quick_sort(int arr[], int low, int high) { if (low high) { int pivotPos partition(arr, low, high); quick_sort(arr, low, pivotPos - 1); quick_sort(arr, pivotPos 1, high); } }逻辑说明pivot保存基准值high从右往左找比pivot小的填到low位置low从左往右找比pivot大的填到high位置。最后lowhigh时把pivot放进去。参数low和high是当前子数组的边界。如果练习题答案用的是“取中间元素为基准”那partition里的比较和交换逻辑会变但递归框架不变。对答案时重点看基准最终位置是否正确而不是中间过程是否一模一样。提示快排最坏O(n²)练习题如果问“什么时候最坏”答“已经有序且取第一个为基准”。5. 查找与KMPnext数组手算和代码验证5.1 二分查找的边界答案里的mid到底怎么取二分查找看着简单但期中题喜欢考“查找失败时的比较次数”或者“mid取整方式”。答案可能写mid (lowhigh)/2也可能写mid low (high-low)/2两者在lowhigh不溢出时等价。下面给出标准实现并说明循环条件。int binary_search(int arr[], int n, int target) { int low 0, high n - 1; while (low high) { // 注意是 int mid low (high - low) / 2; if (arr[mid] target) return mid; else if (arr[mid] target) low mid 1; else high mid - 1; } return -1; // 查找失败 }参数说明low high对应闭区间[low, high]如果写成low high就会漏掉最后一个元素。mid用low (high-low)/2防止溢出。练习题答案如果问“查找失败时low和high的关系”答“low high”。二分查找的时间复杂度O(log n)但前提是数组有序。5.2 KMP算法next数组手算与代码生成对照KMP算法是408数据结构的高频考点期中题常要求“求模式串的next数组”。答案给的是数字序列但很多人手算和代码算不一致。下面给出next数组的生成代码下标从0开始并解释每个值的含义。#include stdio.h #include string.h // 生成next数组next[i]表示pattern[0..i-1]的最长相等前后缀长度 void get_next(char *pattern, int next[]) { int len strlen(pattern); next[0] -1; int i 0, j -1; while (i len - 1) { if (j -1 || pattern[i] pattern[j]) { i; j; next[i] j; } else { j next[j]; } } } int main() { char pattern[] ABABAA; int next[100]; get_next(pattern, next); for (int i 0; i strlen(pattern); i) { printf(%d , next[i]); } // 输出 -1 0 0 1 2 3 return 0; }逻辑说明next[0] -1是哨兵方便回退。i是当前处理的位置j是前缀长度。当pattern[i] pattern[j]时前后缀匹配长度加1next[i1] j1。否则j回退到next[j]。参数上如果教材采用下标从1开始next[1]0整体值会比这里大1。对答案时先确认教材版本严蔚敏数据结构C语言版用的是从1开始王道408通常用从0开始。手算时可以用“前缀和后缀最长公共部分”来验证代码输出。注意KMP的next数组和nextval数组不同nextval是在next基础上优化练习题如果问“nextval”需要再判断pattern[i]和pattern[next[i]]是否相等。6. 把练习题变成自己的题库三个验证习惯练到这一步你已经能把期中练习题里大部分代码题手写出来了。但我想说的是答案本身不重要重要的是你有一套验证自己思路的方法。我自己的习惯是每做完一道题不管答案对不对都写一个最小测试用例跑一遍。比如链表逆置我会构造空链表、单节点、双节点、五节点四种情况排序算法我会用随机数组和已经有序的数组各跑一次。这个习惯帮我避开了无数“看着对、跑起来错”的坑。第二个习惯是给代码加打印。递归函数不好调试就在进入和返回时打印参数。比如二叉树还原那道题打印每次递归的pre、in和len一眼就能看出左右子树长度算错没有。第三个习惯是对照多份答案。同一道题不同教材的答案可能符号不同、下标不同比如KMP的next数组严蔚敏版和王道版差1。遇到不一致时以你目标考试指定的教材为准然后用代码验证哪种写法能正确匹配。最后说一个具体技巧把《数据结构与算法期中练习题答案.doc》里的每道题改写成“输入—输出—边界”三行注释贴在代码上方。比如“输入前序ABDEC中序DBEAC输出后序DEBCA边界空树、单节点”。这样复习时不用翻文档直接看代码就能回忆题目。我当年考研前就是把408数据结构代码必背的几十道题都这么整理了一遍最后代码题基本没丢分。希望帮到你。本文还有配套的精品资源点击获取