简介数据结构是专升本计算机类考试的重点科目《数据结构1800例题与答案》复习资料包正是为备考专升本的考生及需要系统复习数据结构基础的学习者准备。包里共34个文件约1.09MB以23个htm格式的例题页面和11个doc格式的试题、答案解析文档为主覆盖数组、链表、栈、队列、二叉树、堆、图、散列表、排序与查找等核心考点既有分章节专项练习也有完整试卷与参考答案文件按知识点分离编排便于按需查阅和反复训练。目前已有508人学习下载。通过逐题演练可帮助读者熟悉各类题型的解题套路巩固时间复杂度分析与算法设计能力并借助答案文档理解关键步骤建议结合编程实践将理论转化为应对考试和实际问题的竞争力。例题与答案解析一一对应特别适合考前冲刺阶段查漏补缺快速提升实战水平。1. 专升本数据结构到底在考什么先认清范围再下手每年6到9月是专升本备考的第一批焦虑期。刚报完名的人打开严蔚敏的《数据结构》C语言版或者翻到王道408的目录看到红黑树、B树、最小生成树一堆名词当场就想换专业。但实际上专升本的《数据结构》考纲范围比考研窄得多线性表、栈、队列、串、树、图、查找、排序重点在基础结构的理解和简单算法设计。这篇文章就是把这块内容按“考什么、怎么学、怎么避坑”拆成能照着执行的动作。适合正在备考专升本、手里有真题但不知道从哪下手或者C语言基础一般、担心代码题写不出来的人。先别急着刷题先弄清楚你和考研的人学的不是同一本书。2. 用C语言过一遍核心结构顺序表、链表、栈队列、树和图专升本的《数据结构》判断题和填空题里70%的分数来自这几个基础结构。代码题则集中在“线性表的插入删除”“二叉树的遍历”这两个方向。教材建议直接用严蔚敏的C语言版虽然它的代码风格偏老但考纲基本按它的章节走。王道408可以用但它是按考研难度编的复习时只取基础题部分别把红黑树、B树当重点。2.1 顺序表与单链表插入删除的两种写法都要会顺序表考插入、删除、查找链表考建表、插入、删除。先看顺序表的核心操作#include stdio.h #define MAXSIZE 100 // 在顺序表第 pos 个位置插入 valpos 从 1 开始 int insertElem(int arr[], int* length, int pos, int val) { if (*length MAXSIZE) { return 0; // 表满 } if (pos 1 || pos *length 1) { return 0; // 位置非法 } // 从最后一个元素开始往后移 for (int i *length; i pos; i--) { arr[i] arr[i - 1]; } arr[pos - 1] val; (*length); return 1; } int main() { int arr[MAXSIZE] {3, 5, 7}; int len 3; if (insertElem(arr, len, 2, 9)) { for (int i 0; i len; i) { printf(%d , arr[i]); } } return 0; }这段代码的逻辑要点移动元素必须从后往前如果从前往后会覆盖后一个元素pos 的合法范围是 1 到 length1不允许跳着插。参数里数组和长度必须分开传长度用指针才能在函数内修改。考试时经常把“是否越界”和“是否满”写成两个 if漏掉任何一个都会扣分。单链表的插入比顺序表麻烦在指针操作。默认带头结点头结点不存数据这样插入删除不用特判首结点#include stdio.h #include stdlib.h typedef struct Node { int data; struct Node* next; } Node; // 初始化带头结点的空链表 Node* initList() { Node* head (Node*)malloc(sizeof(Node)); head-next NULL; return head; } // 在第 pos 个位置插入 valpos 从 1 开始 int insertNode(Node* head, int pos, int val) { Node* p head; for (int i 1; i pos p ! NULL; i) { p p-next; // 找到第 pos-1 个结点 } if (p NULL) { return 0; // 位置超出链表长度 } Node* newNode (Node*)malloc(sizeof(Node)); newNode-data val; newNode-next p-next; p-next newNode; return 1; }链表的插入关键在“先连后断”先让新结点指向后继再让前驱指向新结点顺序反了就会丢链。考试手写链表代码时最容易错的是循环退出条件用for (int i 1; i pos p ! NULL; i)而不是i pos因为 p 从 head 开始移动 pos-1 次正好落在目标位置的前驱上。如果题目要求不带头结点那插入在头部时要单独修改 head 指针这是两种套路建议平时把带头结点的版本练熟考场遇到不带头结点时再改。2.2 栈和队列top 和 rear 的边界条件栈的代码题通常以“括号匹配”和“表达式求值”的形式出现但底层就考一个入栈出栈。队列考循环队列的判空判满这两者的边界条件是填空题的常客。#define MAXSIZE 100 typedef struct { int data[MAXSIZE]; int top; // 栈顶指针初始为 -1 } SqStack; void push(SqStack* s, int val) { if (s-top MAXSIZE - 1) { return; // 栈满 } s-data[(s-top)] val; } int pop(SqStack* s, int* val) { if (s-top -1) { return 0; // 栈空 } *val s-data[(s-top)--]; return 1; }这里 top 指向栈顶元素所以入栈是先 再赋值出栈是先取值再 --。很多第一次写的人会把(s-top)写成s-top结果是先赋值再移动指针栈顶数据被覆盖。判断栈空的条件是 top -1栈满的条件是 top MAXSIZE-1这两个值要背下来。队列用循环队列实现核心是牺牲一个存储单元来区分队空和队满typedef struct { int data[MAXSIZE]; int front; // 队头指针指向队头元素 int rear; // 队尾指针指向队尾元素的下一位置 } SqQueue; // 入队 int enQueue(SqQueue* q, int val) { if ((q-rear 1) % MAXSIZE q-front) { return 0; // 队满 } q-data[q-rear] val; q-rear (q-rear 1) % MAXSIZE; return 1; } // 出队 int deQueue(SqQueue* q, int* val) { if (q-front q-rear) { return 0; // 队空 } *val q-data[q-front]; q-front (q-front 1) % MAXSIZE; return 1; }循环队列的判满条件(rear1) % MAXSIZE front这意味队满时数组中实际还有一个空位判空条件 front rear。这两个公式是专升本常客选择题和填空题直接考。计算队列长度时用(rear - front MAXSIZE) % MAXSIZE不要直接用 rear-front负数情况会算错。2.3 二叉树递归遍历是后面一切算法的基础二叉树的遍历是《数据结构》里最值得花时间的部分。前序、中序、后序的递归写法要背到条件反射因为层序要用队列非递归要用栈这些高级写法都是从递归推出思路的。typedef struct BiTNode { char data; struct BiTNode* lchild; struct BiTNode* rchild; } BiTNode; // 前序遍历根 - 左 - 右 void preOrder(BiTNode* root) { if (root NULL) { return; } printf(%c , root-data); preOrder(root-lchild); preOrder(root-rchild); } // 中序遍历左 - 根 - 右 void inOrder(BiTNode* root) { if (root NULL) { return; } inOrder(root-lchild); printf(%c , root-data); inOrder(root-rchild); } // 后序遍历左 - 右 - 根 void postOrder(BiTNode* root) { if (root NULL) { return; } postOrder(root-lchild); postOrder(root-rchild); printf(%c , root-data); }递归遍历的三个函数只有 printf 的位置不同但它决定了遍历结果。记忆口诀“根左右、左根右、左右根”在考试时有用但更关键的是理解递归栈每次调用都会把自己压入系统栈返回时再弹出。数据结构期末考试里经常给一棵树让你写出三种遍历序列只要递归写熟这种题就是原样输出。还有一种常考题是“已知中序和前序还原二叉树”做法是取前序的第一个元素作为根再到中序里找它的位置左边是左子树、右边是右子树递归继续拆。这个套路要专门练几遍因为填空和简答都会考。2.4 图邻接矩阵与 DFS/BFS 的模板图的考查以概念为主代码题考 DFS 和 BFS 的编写。掌握邻接矩阵的写法最简单因为矩阵就是二维数组复习成本最低。#define MAXVEX 100 int graph[MAXVEX][MAXVEX]; // 邻接矩阵 int visited[MAXVEX]; // 访问标记数组 // 深度优先遍历v 为起点编号 void DFS(int v, int n) { visited[v] 1; printf(访问顶点 %d\n, v); for (int i 0; i n; i) { if (graph[v][i] 1 visited[i] 0) { DFS(i, n); // 递归访问未访问的邻接点 } } } // 深度优先遍历入口处理非连通图 void DFSTraverse(int n) { for (int i 0; i n; i) { visited[i] 0; } for (int i 0; i n; i) { if (visited[i] 0) { DFS(i, n); } } }DFS 的思路跟二叉树的前序遍历一模一样先访问当前结点再递归访问邻居。区别只在二叉树的邻居固定是两个图的邻居数量不确定所以用 for 循环扫描整行。考试如果让写 BFS就把递归换成队列起点入队出队时把它所有未访问的邻居入队重复到队空。非连通图必须在外层再套一个循环否则只能遍历一个连通分量这个考点在简答题里出现过多次。3. 排序与查找复杂度表直接背代码模板照着写排序和查找是专升本《数据结构》里分数最集中的两章不仅选择题常考算法设计题也偏好考“把某序列用快速排序第一趟的结果写出来”。这一章没有太多玄学核心是把一张表背熟再练熟两个手写模板。3.1 八大排序的复杂度表排序算法平均时间复杂度最坏时间复杂度空间复杂度稳定性直接插入O(n²)O(n²)O(1)稳定冒泡排序O(n²)O(n²)O(1)稳定简单选择O(n²)O(n²)O(1)不稳定希尔排序O(n^1.3)O(n²)O(1)不稳定快速排序O(nlogn)O(n²)O(logn)不稳定堆排序O(nlogn)O(nlogn)O(1)不稳定归并排序O(nlogn)O(nlogn)O(n)稳定基数排序O(d(nr))O(d(nr))O(r)稳定背这张表有个投机方法所有“交换类”排序里只有冒泡和直接插入稳定快速排序最坏情况退化成 O(n²)原因是在基本有序的序列上每次选的基准都接近最大值或最小值归并排序是唯一一个最坏情况还能保持 O(nlogn) 且稳定的排序。希尔排序的平均复杂度是 O(n^1.3)这是经验值不是推导值考试不会追问为什么。3.2 快排和归并的手写模板快速排序是专升本代码题的最高频考点统考和校考都爱考“手写一趟划分”或者“完整快排”。用填坑法写最简单也最不容易丢分// 快速排序对 arr[low] 到 arr[high] 排序 void quickSort(int arr[], int low, int high) { if (low high) { return; } int pivot arr[low]; // 取第一个元素为基准 int i low, j high; while (i j) { // 从右往左找第一个比 pivot 小的数 while (i j arr[j] pivot) { j--; } // 填到左边坑里 arr[i] arr[j]; // 从左往右找第一个比 pivot 大的数 while (i j arr[i] pivot) { i; } // 填到右边坑里 arr[j] arr[i]; } arr[i] pivot; // 基准归位 quickSort(arr, low, i - 1); // 递归排左边 quickSort(arr, i 1, high); // 递归排右边 }这段代码的得分点有三处边界判断low high两个内层 while 一定要加i j防止越界比较符号是和而不是和否则相等的元素会无限交换。考试如果只让写“一趟划分的结果”就只写 while 循环里的部分返回 i 的值不需要递归调用。归并排序的代码考查频率略低但一旦考到就是简答题或代码题重点是把 merge 函数写对// 归并两个有序区间 arr[left..mid] 和 arr[mid1..right] void merge(int arr[], int temp[], int left, int mid, int right) { int i left, j mid 1, k left; while (i mid j right) { if (arr[i] arr[j]) { temp[k] arr[i]; } else { temp[k] arr[j]; } } while (i mid) temp[k] arr[i]; // 左边剩余 while (j right) temp[k] arr[j]; // 右边剩余 for (int t left; t right; t) { arr[t] temp[t]; // 写回原数组 } } // 归并排序入口 void mergeSort(int arr[], int temp[], int left, int right) { if (left right) { return; } int mid (left right) / 2; mergeSort(arr, temp, left, mid); mergeSort(arr, temp, mid 1, right); merge(arr, temp, left, mid, right); }归并排序必须开一个临时数组空间复杂度是 O(n)。如果考试只让写思路就答“分治分成两半分别排序再合并两个有序序列”。很多学校的期末复习题喜欢把归并排序和快排放在同一道题里对比让说明为什么归并稳定而快排不稳定答案是快排的交换是跳跃式的可能把相等元素的相对顺序打乱。3.3 二分查找与哈希表查找一章的两个大头二分查找的代码本身很简单但考试偏爱考边界条件和比较次数// 在有序数组 arr 中查找 key找到返回下标否则返回 -1 int binarySearch(int arr[], int n, int key) { int low 0, high n - 1; while (low high) { int mid (low high) / 2; if (arr[mid] key) { return mid; } else if (arr[mid] key) { low mid 1; } else { high mid - 1; } } return -1; }二分查找的易错点是low high写成low high以及mid (low high) / 2在极端情况下可能越界。专升本考题不会考 mid 溢出这种工程问题但“查找失败的比较次数”是简答题热点。一个长度为 n 的有序表二分查找失败时的比较次数等于判定树的深度即 log2(n1) 向上取整。哈希表在专升本里主要考构造和冲突处理。常见做法是除留余数法H(key) key % pp 取小于表长的最大质数冲突处理常考线性探测和链地址法。手写哈希表的查找代码性价比不高因为代码长且不太可能考把“线性探测遇到冲突就往后找空位”的过程写清楚就够。期末复习时重点关注“给定一组关键字画出哈希表并计算平均查找长度”这类题。4. 把真题刷出效果题型得分策略与三步答题法很多人的复习顺序是先把教材从头看到尾再开始刷题结果看完第三章就把第一章忘了。更有效的做法是先拿一套真题把题型分布列出来再按分值决定投入时间。数据结构这门课的知识点归纳必须自己整理一遍只看别人总结的表格记不住。4.1 题型分布与得分策略不同学校的专升本考卷差异较大但大体分四类选择题、填空题、简答题、算法设计题。常见分值分布如下题型常见题量主要考查内容目标得分率选择题10-20题概念、复杂度、排序结果、结构性质90%填空题5-10空栈顶指针变化、循环队列长度、二叉树节点数90%简答题3-5题图的遍历序列、排序过程、哈希表构造75%算法设计题2-3题线性表操作、二叉树遍历、查找60%选择题和填空题拼的是背功靠刷题就能稳定提分简答题拼的是过程书写只写答案不写步骤会扣一半分算法设计题拼的是模板熟练度线性表和二叉树的两个模板写熟就能拿下一道题的绝大部分分数。如果你的目标院校真题偏难把选择题和填空题的得分率拉满比钻研偏题更划算。4.2 算法设计题的三步答题法算法设计题最容易翻车的地方不是不会写而是“看一眼觉得会下手全是语法错”。我建议按三步走先在草稿纸上画图推演再写主框架最后补边界。以“删除顺序表中所有值为 x 的元素”为例先画一个带重复元素的数组手动模拟用两个指针i和j扫一遍元素不等于x就保留等于x就跳过j指向要覆盖的位置i指向遍历位置。画完流程后写代码// 删除顺序表中所有值为 x 的元素返回新长度 int removeX(int arr[], int len, int x) { int j 0; // j 指向保留位置 for (int i 0; i len; i) { if (arr[i] ! x) { arr[j] arr[i]; } } return j; }这段代码的思路叫“双指针原地覆盖”时间复杂度 O(n)空间复杂度 O(1)。考试时不要用遍历加“每删一个就整体左移”的写法因为它是 O(n²)虽然结果对但可能被扣复杂度分。写完主体后检查边界len 为 0 时循环不执行返回 0数组中全是 x 时返回 0没有 x 时返回原长度。这三个情况画图验证一遍代码题基本就稳了。树相关的算法设计题大多围绕遍历做文章比如“统计二叉树叶子结点个数”int countLeaf(BiTNode* root) { if (root NULL) { return 0; } if (root-lchild NULL root-rchild NULL) { return 1; } return countLeaf(root-lchild) countLeaf(root-rchild); }这个题的套路是“递归出口 递归分解”。递归出口写两件事空节点返回0叶子节点返回1其余情况交给递归去算左右子树的和。专升本的算法设计题不要求写出可编译的完整程序但函数头要写对返回值类型要明确你写的每个参数都会被当成评分点。4.3 错题本怎么做才有用错题本不是抄题是记录“卡住的那个判断”。比如你做错一道“已知中序和后序求前序”的题不要抄整棵树只记录后序的最后一个元素是根在中序里找到根的位置后右侧全是右子树。这类一句话的经验考前过一遍比翻十套卷子有用。另一个容易被忽略的是教材版本差异。严蔚敏C语言版的代码风格和《数据结构与算法》常见教材不同比如她习惯用SqList L传引用而校考答案可能要求用指针。建议在错题本上单独留一页记录“自己学校的答案风格”是否带头结点、栈顶指针初始值是0还是-1、表长是单独变量还是结构体字段。这些细节决定代码题的最终得分。5. 避坑专升本数据结构最常见的五个翻车现场这个科目坑不少有些坑是方向性错误有些是细节性失误。每一条都是真实考生反复踩过的按“现象、原因、解决”写清楚你复习的时候主动绕开。5.1 用Java刷题考场却要写C语言现象复习全程用Java写代码题觉得Java的API方便到了考场上看到“用C语言写出单链表的插入操作”憋了半天写不出一个带struct的完整函数。原因专升本的《数据结构》教材和考纲多数以严蔚敏C语言版为参考代码题标准答案也用C写。Java的ArrayList、LinkedList是封装好的容器长期用它会让你失去手写底层结构的能力。解决从复习第一天就用C语言练习尤其是链表和二叉树部分把malloc、free、struct的写法练熟。如果你C语言基础薄弱至少要把教材上线性表和二叉树的所有代码自己敲一遍再合上书默写。5.2 指针没学明白就冲二叉树现象二叉树章节的代码看得懂一自己写就报错仔细一看是root-lchild写成了root.lchild或者递归函数里对空指针解引用。原因二叉树是“指针的指针”每个节点本身是个结构体左右子树又是结构体指针。C语言的指针如果只是“知道概念”而没有亲手调试过到这里大概率翻车。解决先回到C语言的指针章节把“指针变量存地址”“箭头访问结构体成员”“Node* p和Node p的区别”这三个点用代码验证一遍。不要在没搞懂指针的情况下去背二叉树的遍历代码那属于死记硬背题型一换就失效。5.3 只背代码不画图现象排序算法倒背如流但考试让写“快速排序第一趟的结果”时写出来的序列和答案完全对不上还觉得自己没背错。原因排序过程是动态的背代码只能记住“取基准、交替比较”这几个字而一次具体的划分涉及多个指针的同时变化不用笔画一遍根本推不出正确结果。解决每学一个算法先在草稿纸上画一个长度为6-8的乱序数组手动模拟整个排序过程再对照代码看每一步对应哪个变量变化。二叉树、图、哈希表同理画图是数据结构复习里的核心动作不能省。5.4 复杂度分析全凭感觉现象问直接插入排序的最好情况回答“不知道反正很快”问快速排序最坏情况回答“O(nlogn)”被扣分。原因复杂度分析有严格定义却被当成“背结论”。没理解“基本操作次数”和“问题规模”之间的关系导致题目换个说法就答错。解决把复杂度表从头推一遍直接插入最好情况是序列基本有序每趟只比较一次总比较次数O(n)快速排序最坏情况是每次基准都取到极值递归深度变成n每层比较O(n)乘积变成O(n²)。这样推过一遍之后乱序、正序、逆序下的复杂度就不用死记了。5.5 真题只刷一遍就丢现象真题刷了一遍对答案的时候觉得自己都会了过两周再做原题选择题还是错代码题还是卡住。原因第一遍刷题时是“看着答案做题”大脑记住了题目本身没有记住解题路径。两周后记忆消退剩下的还是原来的空白。解决每套真题刷三遍。第一遍限时做做完立即对答案第二遍隔三天只做错题和蒙对的题第三遍隔一周把大题在空白纸上完整写一遍重点看过程书写是否规范。三遍之后这套卷子才算真正吸收。6. 最后二十天把会做的题稳定拿分冲刺阶段的目标不是学会新东西而是保证会的全对。按下面这个节奏安排最后三周第一周过线性表、栈、队列把顺序表和链表代码默写一遍第二周过树和图递归遍历、DFS、BFS各写两遍第三周过排序和查找快排模板和二分查找模板交替默写再刷一遍错题本。每天用半小时做“快筛训练”拿一张白纸默写一棵树的三种遍历序列或手动推一遍快速排序。这类训练的验证方式是“合上书把自己当成考试从零开始写”不要边看答案边写那叫抄不叫练。冲刺期如果发现某个知识点总是记不住果断放弃它把时间和精力转到必得分题型上。比如红黑树的旋转过程专升本考的概率极低已经掌握基础的优先保住快排和二叉树的分数。算法设计题的稳定拿分方法是把下面三句话刻在脑子里线性表题先想双指针树题先想递归出口查找题先想指针移动方向。这三句话能覆盖专升本题库里的绝大多数大题。还有一个小技巧容易被忽略考试时先写函数签名和核心逻辑再补细节。阅卷是按点给分int返回值、参数列表、主循环写对了即使逻辑有小瑕疵也能拿到大部分分数。我当年复习时最吃亏的一件事是花了大把时间钻研图的最短路径算法推导结果正式考试只考了一道“给出DFS遍历序列”的简单题。后来才想明白专升本数据结构是过关型考试不是选拔型考试把基础题做到全对分数一定在前列。希望这些经验和踩过的坑能帮你少走这段弯路照着上面的节奏执行这门课能稳定拿到高分。希望帮到你。本文还有配套的精品资源点击获取 专升本数据结构C语言核心考点：顺序表、链表与排序算法
简介数据结构是专升本计算机类考试的重点科目《数据结构1800例题与答案》复习资料包正是为备考专升本的考生及需要系统复习数据结构基础的学习者准备。包里共34个文件约1.09MB以23个htm格式的例题页面和11个doc格式的试题、答案解析文档为主覆盖数组、链表、栈、队列、二叉树、堆、图、散列表、排序与查找等核心考点既有分章节专项练习也有完整试卷与参考答案文件按知识点分离编排便于按需查阅和反复训练。目前已有508人学习下载。通过逐题演练可帮助读者熟悉各类题型的解题套路巩固时间复杂度分析与算法设计能力并借助答案文档理解关键步骤建议结合编程实践将理论转化为应对考试和实际问题的竞争力。例题与答案解析一一对应特别适合考前冲刺阶段查漏补缺快速提升实战水平。1. 专升本数据结构到底在考什么先认清范围再下手每年6到9月是专升本备考的第一批焦虑期。刚报完名的人打开严蔚敏的《数据结构》C语言版或者翻到王道408的目录看到红黑树、B树、最小生成树一堆名词当场就想换专业。但实际上专升本的《数据结构》考纲范围比考研窄得多线性表、栈、队列、串、树、图、查找、排序重点在基础结构的理解和简单算法设计。这篇文章就是把这块内容按“考什么、怎么学、怎么避坑”拆成能照着执行的动作。适合正在备考专升本、手里有真题但不知道从哪下手或者C语言基础一般、担心代码题写不出来的人。先别急着刷题先弄清楚你和考研的人学的不是同一本书。2. 用C语言过一遍核心结构顺序表、链表、栈队列、树和图专升本的《数据结构》判断题和填空题里70%的分数来自这几个基础结构。代码题则集中在“线性表的插入删除”“二叉树的遍历”这两个方向。教材建议直接用严蔚敏的C语言版虽然它的代码风格偏老但考纲基本按它的章节走。王道408可以用但它是按考研难度编的复习时只取基础题部分别把红黑树、B树当重点。2.1 顺序表与单链表插入删除的两种写法都要会顺序表考插入、删除、查找链表考建表、插入、删除。先看顺序表的核心操作#include stdio.h #define MAXSIZE 100 // 在顺序表第 pos 个位置插入 valpos 从 1 开始 int insertElem(int arr[], int* length, int pos, int val) { if (*length MAXSIZE) { return 0; // 表满 } if (pos 1 || pos *length 1) { return 0; // 位置非法 } // 从最后一个元素开始往后移 for (int i *length; i pos; i--) { arr[i] arr[i - 1]; } arr[pos - 1] val; (*length); return 1; } int main() { int arr[MAXSIZE] {3, 5, 7}; int len 3; if (insertElem(arr, len, 2, 9)) { for (int i 0; i len; i) { printf(%d , arr[i]); } } return 0; }这段代码的逻辑要点移动元素必须从后往前如果从前往后会覆盖后一个元素pos 的合法范围是 1 到 length1不允许跳着插。参数里数组和长度必须分开传长度用指针才能在函数内修改。考试时经常把“是否越界”和“是否满”写成两个 if漏掉任何一个都会扣分。单链表的插入比顺序表麻烦在指针操作。默认带头结点头结点不存数据这样插入删除不用特判首结点#include stdio.h #include stdlib.h typedef struct Node { int data; struct Node* next; } Node; // 初始化带头结点的空链表 Node* initList() { Node* head (Node*)malloc(sizeof(Node)); head-next NULL; return head; } // 在第 pos 个位置插入 valpos 从 1 开始 int insertNode(Node* head, int pos, int val) { Node* p head; for (int i 1; i pos p ! NULL; i) { p p-next; // 找到第 pos-1 个结点 } if (p NULL) { return 0; // 位置超出链表长度 } Node* newNode (Node*)malloc(sizeof(Node)); newNode-data val; newNode-next p-next; p-next newNode; return 1; }链表的插入关键在“先连后断”先让新结点指向后继再让前驱指向新结点顺序反了就会丢链。考试手写链表代码时最容易错的是循环退出条件用for (int i 1; i pos p ! NULL; i)而不是i pos因为 p 从 head 开始移动 pos-1 次正好落在目标位置的前驱上。如果题目要求不带头结点那插入在头部时要单独修改 head 指针这是两种套路建议平时把带头结点的版本练熟考场遇到不带头结点时再改。2.2 栈和队列top 和 rear 的边界条件栈的代码题通常以“括号匹配”和“表达式求值”的形式出现但底层就考一个入栈出栈。队列考循环队列的判空判满这两者的边界条件是填空题的常客。#define MAXSIZE 100 typedef struct { int data[MAXSIZE]; int top; // 栈顶指针初始为 -1 } SqStack; void push(SqStack* s, int val) { if (s-top MAXSIZE - 1) { return; // 栈满 } s-data[(s-top)] val; } int pop(SqStack* s, int* val) { if (s-top -1) { return 0; // 栈空 } *val s-data[(s-top)--]; return 1; }这里 top 指向栈顶元素所以入栈是先 再赋值出栈是先取值再 --。很多第一次写的人会把(s-top)写成s-top结果是先赋值再移动指针栈顶数据被覆盖。判断栈空的条件是 top -1栈满的条件是 top MAXSIZE-1这两个值要背下来。队列用循环队列实现核心是牺牲一个存储单元来区分队空和队满typedef struct { int data[MAXSIZE]; int front; // 队头指针指向队头元素 int rear; // 队尾指针指向队尾元素的下一位置 } SqQueue; // 入队 int enQueue(SqQueue* q, int val) { if ((q-rear 1) % MAXSIZE q-front) { return 0; // 队满 } q-data[q-rear] val; q-rear (q-rear 1) % MAXSIZE; return 1; } // 出队 int deQueue(SqQueue* q, int* val) { if (q-front q-rear) { return 0; // 队空 } *val q-data[q-front]; q-front (q-front 1) % MAXSIZE; return 1; }循环队列的判满条件(rear1) % MAXSIZE front这意味队满时数组中实际还有一个空位判空条件 front rear。这两个公式是专升本常客选择题和填空题直接考。计算队列长度时用(rear - front MAXSIZE) % MAXSIZE不要直接用 rear-front负数情况会算错。2.3 二叉树递归遍历是后面一切算法的基础二叉树的遍历是《数据结构》里最值得花时间的部分。前序、中序、后序的递归写法要背到条件反射因为层序要用队列非递归要用栈这些高级写法都是从递归推出思路的。typedef struct BiTNode { char data; struct BiTNode* lchild; struct BiTNode* rchild; } BiTNode; // 前序遍历根 - 左 - 右 void preOrder(BiTNode* root) { if (root NULL) { return; } printf(%c , root-data); preOrder(root-lchild); preOrder(root-rchild); } // 中序遍历左 - 根 - 右 void inOrder(BiTNode* root) { if (root NULL) { return; } inOrder(root-lchild); printf(%c , root-data); inOrder(root-rchild); } // 后序遍历左 - 右 - 根 void postOrder(BiTNode* root) { if (root NULL) { return; } postOrder(root-lchild); postOrder(root-rchild); printf(%c , root-data); }递归遍历的三个函数只有 printf 的位置不同但它决定了遍历结果。记忆口诀“根左右、左根右、左右根”在考试时有用但更关键的是理解递归栈每次调用都会把自己压入系统栈返回时再弹出。数据结构期末考试里经常给一棵树让你写出三种遍历序列只要递归写熟这种题就是原样输出。还有一种常考题是“已知中序和前序还原二叉树”做法是取前序的第一个元素作为根再到中序里找它的位置左边是左子树、右边是右子树递归继续拆。这个套路要专门练几遍因为填空和简答都会考。2.4 图邻接矩阵与 DFS/BFS 的模板图的考查以概念为主代码题考 DFS 和 BFS 的编写。掌握邻接矩阵的写法最简单因为矩阵就是二维数组复习成本最低。#define MAXVEX 100 int graph[MAXVEX][MAXVEX]; // 邻接矩阵 int visited[MAXVEX]; // 访问标记数组 // 深度优先遍历v 为起点编号 void DFS(int v, int n) { visited[v] 1; printf(访问顶点 %d\n, v); for (int i 0; i n; i) { if (graph[v][i] 1 visited[i] 0) { DFS(i, n); // 递归访问未访问的邻接点 } } } // 深度优先遍历入口处理非连通图 void DFSTraverse(int n) { for (int i 0; i n; i) { visited[i] 0; } for (int i 0; i n; i) { if (visited[i] 0) { DFS(i, n); } } }DFS 的思路跟二叉树的前序遍历一模一样先访问当前结点再递归访问邻居。区别只在二叉树的邻居固定是两个图的邻居数量不确定所以用 for 循环扫描整行。考试如果让写 BFS就把递归换成队列起点入队出队时把它所有未访问的邻居入队重复到队空。非连通图必须在外层再套一个循环否则只能遍历一个连通分量这个考点在简答题里出现过多次。3. 排序与查找复杂度表直接背代码模板照着写排序和查找是专升本《数据结构》里分数最集中的两章不仅选择题常考算法设计题也偏好考“把某序列用快速排序第一趟的结果写出来”。这一章没有太多玄学核心是把一张表背熟再练熟两个手写模板。3.1 八大排序的复杂度表排序算法平均时间复杂度最坏时间复杂度空间复杂度稳定性直接插入O(n²)O(n²)O(1)稳定冒泡排序O(n²)O(n²)O(1)稳定简单选择O(n²)O(n²)O(1)不稳定希尔排序O(n^1.3)O(n²)O(1)不稳定快速排序O(nlogn)O(n²)O(logn)不稳定堆排序O(nlogn)O(nlogn)O(1)不稳定归并排序O(nlogn)O(nlogn)O(n)稳定基数排序O(d(nr))O(d(nr))O(r)稳定背这张表有个投机方法所有“交换类”排序里只有冒泡和直接插入稳定快速排序最坏情况退化成 O(n²)原因是在基本有序的序列上每次选的基准都接近最大值或最小值归并排序是唯一一个最坏情况还能保持 O(nlogn) 且稳定的排序。希尔排序的平均复杂度是 O(n^1.3)这是经验值不是推导值考试不会追问为什么。3.2 快排和归并的手写模板快速排序是专升本代码题的最高频考点统考和校考都爱考“手写一趟划分”或者“完整快排”。用填坑法写最简单也最不容易丢分// 快速排序对 arr[low] 到 arr[high] 排序 void quickSort(int arr[], int low, int high) { if (low high) { return; } int pivot arr[low]; // 取第一个元素为基准 int i low, j high; while (i j) { // 从右往左找第一个比 pivot 小的数 while (i j arr[j] pivot) { j--; } // 填到左边坑里 arr[i] arr[j]; // 从左往右找第一个比 pivot 大的数 while (i j arr[i] pivot) { i; } // 填到右边坑里 arr[j] arr[i]; } arr[i] pivot; // 基准归位 quickSort(arr, low, i - 1); // 递归排左边 quickSort(arr, i 1, high); // 递归排右边 }这段代码的得分点有三处边界判断low high两个内层 while 一定要加i j防止越界比较符号是和而不是和否则相等的元素会无限交换。考试如果只让写“一趟划分的结果”就只写 while 循环里的部分返回 i 的值不需要递归调用。归并排序的代码考查频率略低但一旦考到就是简答题或代码题重点是把 merge 函数写对// 归并两个有序区间 arr[left..mid] 和 arr[mid1..right] void merge(int arr[], int temp[], int left, int mid, int right) { int i left, j mid 1, k left; while (i mid j right) { if (arr[i] arr[j]) { temp[k] arr[i]; } else { temp[k] arr[j]; } } while (i mid) temp[k] arr[i]; // 左边剩余 while (j right) temp[k] arr[j]; // 右边剩余 for (int t left; t right; t) { arr[t] temp[t]; // 写回原数组 } } // 归并排序入口 void mergeSort(int arr[], int temp[], int left, int right) { if (left right) { return; } int mid (left right) / 2; mergeSort(arr, temp, left, mid); mergeSort(arr, temp, mid 1, right); merge(arr, temp, left, mid, right); }归并排序必须开一个临时数组空间复杂度是 O(n)。如果考试只让写思路就答“分治分成两半分别排序再合并两个有序序列”。很多学校的期末复习题喜欢把归并排序和快排放在同一道题里对比让说明为什么归并稳定而快排不稳定答案是快排的交换是跳跃式的可能把相等元素的相对顺序打乱。3.3 二分查找与哈希表查找一章的两个大头二分查找的代码本身很简单但考试偏爱考边界条件和比较次数// 在有序数组 arr 中查找 key找到返回下标否则返回 -1 int binarySearch(int arr[], int n, int key) { int low 0, high n - 1; while (low high) { int mid (low high) / 2; if (arr[mid] key) { return mid; } else if (arr[mid] key) { low mid 1; } else { high mid - 1; } } return -1; }二分查找的易错点是low high写成low high以及mid (low high) / 2在极端情况下可能越界。专升本考题不会考 mid 溢出这种工程问题但“查找失败的比较次数”是简答题热点。一个长度为 n 的有序表二分查找失败时的比较次数等于判定树的深度即 log2(n1) 向上取整。哈希表在专升本里主要考构造和冲突处理。常见做法是除留余数法H(key) key % pp 取小于表长的最大质数冲突处理常考线性探测和链地址法。手写哈希表的查找代码性价比不高因为代码长且不太可能考把“线性探测遇到冲突就往后找空位”的过程写清楚就够。期末复习时重点关注“给定一组关键字画出哈希表并计算平均查找长度”这类题。4. 把真题刷出效果题型得分策略与三步答题法很多人的复习顺序是先把教材从头看到尾再开始刷题结果看完第三章就把第一章忘了。更有效的做法是先拿一套真题把题型分布列出来再按分值决定投入时间。数据结构这门课的知识点归纳必须自己整理一遍只看别人总结的表格记不住。4.1 题型分布与得分策略不同学校的专升本考卷差异较大但大体分四类选择题、填空题、简答题、算法设计题。常见分值分布如下题型常见题量主要考查内容目标得分率选择题10-20题概念、复杂度、排序结果、结构性质90%填空题5-10空栈顶指针变化、循环队列长度、二叉树节点数90%简答题3-5题图的遍历序列、排序过程、哈希表构造75%算法设计题2-3题线性表操作、二叉树遍历、查找60%选择题和填空题拼的是背功靠刷题就能稳定提分简答题拼的是过程书写只写答案不写步骤会扣一半分算法设计题拼的是模板熟练度线性表和二叉树的两个模板写熟就能拿下一道题的绝大部分分数。如果你的目标院校真题偏难把选择题和填空题的得分率拉满比钻研偏题更划算。4.2 算法设计题的三步答题法算法设计题最容易翻车的地方不是不会写而是“看一眼觉得会下手全是语法错”。我建议按三步走先在草稿纸上画图推演再写主框架最后补边界。以“删除顺序表中所有值为 x 的元素”为例先画一个带重复元素的数组手动模拟用两个指针i和j扫一遍元素不等于x就保留等于x就跳过j指向要覆盖的位置i指向遍历位置。画完流程后写代码// 删除顺序表中所有值为 x 的元素返回新长度 int removeX(int arr[], int len, int x) { int j 0; // j 指向保留位置 for (int i 0; i len; i) { if (arr[i] ! x) { arr[j] arr[i]; } } return j; }这段代码的思路叫“双指针原地覆盖”时间复杂度 O(n)空间复杂度 O(1)。考试时不要用遍历加“每删一个就整体左移”的写法因为它是 O(n²)虽然结果对但可能被扣复杂度分。写完主体后检查边界len 为 0 时循环不执行返回 0数组中全是 x 时返回 0没有 x 时返回原长度。这三个情况画图验证一遍代码题基本就稳了。树相关的算法设计题大多围绕遍历做文章比如“统计二叉树叶子结点个数”int countLeaf(BiTNode* root) { if (root NULL) { return 0; } if (root-lchild NULL root-rchild NULL) { return 1; } return countLeaf(root-lchild) countLeaf(root-rchild); }这个题的套路是“递归出口 递归分解”。递归出口写两件事空节点返回0叶子节点返回1其余情况交给递归去算左右子树的和。专升本的算法设计题不要求写出可编译的完整程序但函数头要写对返回值类型要明确你写的每个参数都会被当成评分点。4.3 错题本怎么做才有用错题本不是抄题是记录“卡住的那个判断”。比如你做错一道“已知中序和后序求前序”的题不要抄整棵树只记录后序的最后一个元素是根在中序里找到根的位置后右侧全是右子树。这类一句话的经验考前过一遍比翻十套卷子有用。另一个容易被忽略的是教材版本差异。严蔚敏C语言版的代码风格和《数据结构与算法》常见教材不同比如她习惯用SqList L传引用而校考答案可能要求用指针。建议在错题本上单独留一页记录“自己学校的答案风格”是否带头结点、栈顶指针初始值是0还是-1、表长是单独变量还是结构体字段。这些细节决定代码题的最终得分。5. 避坑专升本数据结构最常见的五个翻车现场这个科目坑不少有些坑是方向性错误有些是细节性失误。每一条都是真实考生反复踩过的按“现象、原因、解决”写清楚你复习的时候主动绕开。5.1 用Java刷题考场却要写C语言现象复习全程用Java写代码题觉得Java的API方便到了考场上看到“用C语言写出单链表的插入操作”憋了半天写不出一个带struct的完整函数。原因专升本的《数据结构》教材和考纲多数以严蔚敏C语言版为参考代码题标准答案也用C写。Java的ArrayList、LinkedList是封装好的容器长期用它会让你失去手写底层结构的能力。解决从复习第一天就用C语言练习尤其是链表和二叉树部分把malloc、free、struct的写法练熟。如果你C语言基础薄弱至少要把教材上线性表和二叉树的所有代码自己敲一遍再合上书默写。5.2 指针没学明白就冲二叉树现象二叉树章节的代码看得懂一自己写就报错仔细一看是root-lchild写成了root.lchild或者递归函数里对空指针解引用。原因二叉树是“指针的指针”每个节点本身是个结构体左右子树又是结构体指针。C语言的指针如果只是“知道概念”而没有亲手调试过到这里大概率翻车。解决先回到C语言的指针章节把“指针变量存地址”“箭头访问结构体成员”“Node* p和Node p的区别”这三个点用代码验证一遍。不要在没搞懂指针的情况下去背二叉树的遍历代码那属于死记硬背题型一换就失效。5.3 只背代码不画图现象排序算法倒背如流但考试让写“快速排序第一趟的结果”时写出来的序列和答案完全对不上还觉得自己没背错。原因排序过程是动态的背代码只能记住“取基准、交替比较”这几个字而一次具体的划分涉及多个指针的同时变化不用笔画一遍根本推不出正确结果。解决每学一个算法先在草稿纸上画一个长度为6-8的乱序数组手动模拟整个排序过程再对照代码看每一步对应哪个变量变化。二叉树、图、哈希表同理画图是数据结构复习里的核心动作不能省。5.4 复杂度分析全凭感觉现象问直接插入排序的最好情况回答“不知道反正很快”问快速排序最坏情况回答“O(nlogn)”被扣分。原因复杂度分析有严格定义却被当成“背结论”。没理解“基本操作次数”和“问题规模”之间的关系导致题目换个说法就答错。解决把复杂度表从头推一遍直接插入最好情况是序列基本有序每趟只比较一次总比较次数O(n)快速排序最坏情况是每次基准都取到极值递归深度变成n每层比较O(n)乘积变成O(n²)。这样推过一遍之后乱序、正序、逆序下的复杂度就不用死记了。5.5 真题只刷一遍就丢现象真题刷了一遍对答案的时候觉得自己都会了过两周再做原题选择题还是错代码题还是卡住。原因第一遍刷题时是“看着答案做题”大脑记住了题目本身没有记住解题路径。两周后记忆消退剩下的还是原来的空白。解决每套真题刷三遍。第一遍限时做做完立即对答案第二遍隔三天只做错题和蒙对的题第三遍隔一周把大题在空白纸上完整写一遍重点看过程书写是否规范。三遍之后这套卷子才算真正吸收。6. 最后二十天把会做的题稳定拿分冲刺阶段的目标不是学会新东西而是保证会的全对。按下面这个节奏安排最后三周第一周过线性表、栈、队列把顺序表和链表代码默写一遍第二周过树和图递归遍历、DFS、BFS各写两遍第三周过排序和查找快排模板和二分查找模板交替默写再刷一遍错题本。每天用半小时做“快筛训练”拿一张白纸默写一棵树的三种遍历序列或手动推一遍快速排序。这类训练的验证方式是“合上书把自己当成考试从零开始写”不要边看答案边写那叫抄不叫练。冲刺期如果发现某个知识点总是记不住果断放弃它把时间和精力转到必得分题型上。比如红黑树的旋转过程专升本考的概率极低已经掌握基础的优先保住快排和二叉树的分数。算法设计题的稳定拿分方法是把下面三句话刻在脑子里线性表题先想双指针树题先想递归出口查找题先想指针移动方向。这三句话能覆盖专升本题库里的绝大多数大题。还有一个小技巧容易被忽略考试时先写函数签名和核心逻辑再补细节。阅卷是按点给分int返回值、参数列表、主循环写对了即使逻辑有小瑕疵也能拿到大部分分数。我当年复习时最吃亏的一件事是花了大把时间钻研图的最短路径算法推导结果正式考试只考了一道“给出DFS遍历序列”的简单题。后来才想明白专升本数据结构是过关型考试不是选拔型考试把基础题做到全对分数一定在前列。希望这些经验和踩过的坑能帮你少走这段弯路照着上面的节奏执行这门课能稳定拿到高分。希望帮到你。本文还有配套的精品资源点击获取