企业官网建设流程全解析

简介：这份文档资料是《数据结构与算法》期中练习题的配套答案，面向正在学习数据结构课程的高校学生与备考者，帮助其核对解题思路、巩固核心考点。内容覆盖基本概念、线性结构、栈与队列、二叉树、算法设计及稀疏矩阵等模块，包含选择题、指针操作、存储位置计算、循环队列状态填写、静态链表插入删除以及三元组顺序表转置等典型题型，并给出对应解答过程。资源包内含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递减到pos+1，移动次数正好是*len - pos，这就是答案里“平均n/2”的来源——因为pos从0到n均匀分布，平均移动n/2次。链表插入的循环只负责找位置，不搬数据，所以移动次数为0。练习题答案如果只写“O(n)”，你对照这段代码就能明白它指的是时间开销，而不是移动次数。

2.2 用“答案反推法”练链表操作题

期中题里链表部分最爱考：单链表逆置、找中间节点、判断是否有环、合并两个有序链表。答案往往只给几行伪代码，比如“p=head; q=NULL; 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是当前子树节点数。递归左子树时，前序从pre+1开始，中序从in开始，长度是rootIdx；递归右子树时，前序从pre+1+rootIdx开始，中序从in+rootIdx+1开始，长度是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] 和 [mid+1, 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比(left+right)/2更安全，避免left+right溢出。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位置。最后low==high时把pivot放进去。参数low和high是当前子数组的边界。如果练习题答案用的是“取中间元素为基准”，那partition里的比较和交换逻辑会变，但递归框架不变。对答案时重点看基准最终位置是否正确，而不是中间过程是否一模一样。

提示：快排最坏O(n²)，练习题如果问“什么时候最坏”，答“已经有序且取第一个为基准”。

5. 查找与KMP：next数组手算和代码验证

5.1 二分查找的边界，答案里的mid到底怎么取

二分查找看着简单，但期中题喜欢考“查找失败时的比较次数”或者“mid取整方式”。答案可能写mid = (low+high)/2，也可能写mid = low + (high-low)/2，两者在low+high不溢出时等价。下面给出标准实现，并说明循环条件。

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]时，前后缀匹配长度加1，next[i+1] = j+1。否则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数据结构代码必背的几十道题都这么整理了一遍，最后代码题基本没丢分。希望帮到你。

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