专升本数据结构手写模板与高频考点复习指南

简介：这是一套面向专升本考生的数据结构备考资料包，覆盖数组、链表、栈、队列、树、图、哈希表及常用排序查找算法等核心知识点，并以1800道例题与详细答案的方式帮助考生将理论转化为解题能力。资源共34个文件，以htm网页例题和doc文档答案为主，可方便地按章节浏览练习与对照解析；整个压缩包仅1.09MB，轻量易用，适合在复习阶段快速查漏补缺。已有509人学习使用。通过反复演练这些题目，考生可系统梳理数据结构考点、熟悉各类算法的时间复杂度分析，并逐步提升编程思维与实际问题求解能力，为专升本考试打下扎实基础。

1. 专升本数据结构：不是背诵课，是手写喂出来的手感

专升本数据结构这门课，考场上最常见的两种场面：一种人概念题全对，一动手写算法题就卡壳；另一种代码能写个大概，但复杂度算错、边界漏判，被扣得莫名其妙。把它当背诵课，考前抱着笔记背概念的人，上了考场才会发现真正拉分的全是手写题。

它不是玄学，也不是记忆竞赛，而是「见过、写过、写对过」的肌肉记忆。适合计算机相关专业的专升本考生，也适合已经工作、想补系统基础的人。后者日常写代码没障碍，一旦被要求白纸手写核心算法，思路不完整的毛病立刻暴露。

下面按考什么、怎么写、坑在哪、考前怎么练来拆。先把考点权重理清，再给可直接默写的模板代码，最后说清楚失分点，按这个顺序推进比盲目刷题省时间。

2. 按考纲拆考点：线性表、树、排序的权重分配与复习顺序

专升本数据结构没有全国统一的一张卷，各省各院校的考纲细节不同，但核心模块高度一致：线性表、栈与队列、树与二叉树、图、查找、排序，外加基础概念与算法分析。这门课的特点是模块边界清晰，每一章独立性很强，非常适合按优先级推进，而不是从头到尾一遍过。

从常见卷面结构和历年题型经验看，线性表与栈队列合计往往在三成左右，树与图两到三成，查找与排序约两成，剩余是概念判断题和综合大题。这个比例在不同院校变化明显，但用来排复习顺序足够。下面按这个权重把复习主线理清楚。

2.1 线性表与栈队列：占分最稳，复习回报最高

线性表在考纲里处于地基位置。顺序表的插入删除、单链表的建立与反转，是手写题的高频素材；栈与队列则更多以小题出现，例如给一组入栈序列判断某个出栈序列是否合法、计算循环队列的队满条件、把中缀表达式转成后缀表达式。这类题题型固定、答案明确，是整张卷子里最稳定的得分来源。

为什么把它放第一位：它的编程量小、错误模式固定，亲手写过三五次就能稳定得分。对比之下，树的题需要递归思维，图的题需要背流程，前期投入大、见效慢。从投入产出比看，线性表是回报最直接的模块，建议先拿下，别一上来就啃二叉树。

第一周只做线性表：手写顺序表插入、单链表头插法建表、单链表反转，每天 30 到 40 分钟。第二周转栈队列小题：判断出栈序列是否合法、计算循环队列入队出队后的下标。注意，出栈序列判断不能靠枚举，要模拟栈的 push/pop 过程。这道题型练熟了，后缀表达式和括号匹配的同源题也就一起解决了。

2.2 树与二叉树：递归模板是高分起点，别先啃图

树的考点高度集中在二叉树：先序/中序/后序/层序遍历序列、由两种遍历序列还原一棵二叉树、求深度与叶子数。图的考点集中在存储结构（邻接矩阵与邻接表的选择）、DFS/BFS 的访问过程、最小生成树与最短路径的手工模拟。树和图的深度学习关系不大，但二叉树的递归思维会直接影响后续所有代码题的发挥。

从题量看，树通常多于图。图更常考概念判断，比如生成树边数等于顶点数减一、连通分量影响 DFS 生成森林的计数；树的题则是实打实要求写序列、补全代码。所以时间分配上树占大头，图以背概念加手工模拟为主，不必投入大量代码训练。

做法分三步。第一步默写先序/中序/后序递归模板，目标是在白纸上 3 分钟内完整写出；第二步做「给树写序列」和「给中序+先序还原树」的手工题，后者考的是对遍历性质的理解，在小题里出现频率不低；第三步图只练两类手工模拟：从指定顶点出发的 DFS/BFS 访问序列，以及最小生成树的选边过程。完全二叉树和二叉排序树的性质题放在最后一周集中背，性价比比反复刷图高得多。

提示：树的层序遍历用队列实现，不是递归。代码补全题里出现层序时，用递归硬套，阅卷一眼就能看出概念不清。

2.3 排序与查找：专升本数据结构里性价比最高的涨分点

排序与查找的稳定题型有两类：小题考 8 种排序的复杂度与稳定性对比、折半查找的判定树与平均查找长度；大题考给一组数据写出快速排序每趟结果或某趟希尔排序的结果。这部分的优点是基本不需要写长代码，缺点是过程题要求每一步都得画对，落一趟就扣一趟的分。

很多人在这丢分，不是不会背，而是背了不会用。常见失误三条：快速排序没写全每个子区间的过程；归并排序只写合并结果不写分组过程；折半查找在区间长度为奇数或偶数时，边界判断错位。这三条都属于「考试时不慌就能避免」的问题，平时练到位就不会慌。

建议自己做一张排序对比表，把平均复杂度、最坏复杂度、稳定性、是否原地排序四列整理清楚。然后用它刷 10 组手工题：快排每组写到每个子区间只剩一个元素；折半查找每组画出每次的 mid 与收缩后的区间边界。这张表也是考前最后一天唯一值得再扫一遍的材料。

表里的占比是常见经验值，不同院校差异明显，它只用来定复习顺序，别拿来当押题依据。

3. 手写模板实战：链表反转、二叉树遍历、快排与二分的 4 段必练代码

考纲背得再熟，最终要在卷面上变成代码。专升本的数据结构笔试，编程题通常只要求写核心函数，不要求完整可编译程序，所以准备重点不是工程能力，而是短小、完整、边界正确的模板型代码。下面这四段——单链表反转、二叉树先序递归遍历、快速排序、折半查找，是值得练到肌肉记忆的底线清单。

为什么是这四段：它们分别覆盖专升本编程题最常考的三种能力——指针操作、递归、区间边界控制。练熟之后，求树的深度可以看作后序遍历的变形，折半插入排序里的查找步骤可以直接复用二分模板，栈的进出顺序题也能用链表演练时的指针直觉辅助理解。

3.1 单链表反转：先存后继再改指向，三指针顺序不能换

单链表反转是手写题常客，也是指针题的门面。它代码短，但三个指针同时工作，任何一步顺序不对都会断链或成环。考场上最常见的失败现场：先写了curr->next = prev，然后发现后继丢了，后面越写越乱，整道题的逻辑跟着崩。

// 反转单链表，返回反转后的头指针 struct Node* reverseList(struct Node* head) { struct Node *prev = NULL; // 已处理好的链表的头 struct Node *curr = head; // 当前要改指向的节点 struct Node *next = NULL; // 暂存当前节点的原后继 while (curr != NULL) { next = curr->next; // 第一步：先保存后继，防止断链 curr->next = prev; // 第二步：当前节点指向前驱 prev = curr; // 第三步：前驱指针前移 curr = next; // 第四步：当前指针后移 } return prev; // 结束时 prev 指向原链表的尾节点 }

三个关键点。第一，next必须在修改curr->next之前赋值，否则原后继丢失，循环无法继续。第二，prev初始必须是NULL，这样原链表头节点反转后才是新链表的尾节点，指向NULL是合法的链表结尾。第三，函数返回prev，不是curr，因为循环结束时curr已经走到NULL，prev才是原来的尾节点。这三处错任何一个，阅卷都能直接看出来。

笔试建议用迭代写法。递归反转代码更短，但递归出口和返回值容易写错，而且过程不透明。如果考扩展题「每 k 个节点一组反转」，本质还是三指针操作，先分组再逐组反转，组间衔接时把上一组的尾接到下一组的头。平时手写时，可以用三个节点的链表从头演算一遍，两分钟能挡住大部分指针错误。

3.2 二叉树三种递归遍历：出口、访问位置与三行顺序

二叉树的递归遍历在专升本里几乎必考：小题写遍历序列，大题写函数体或补全代码。先序、中序、后序的唯一区别是访问根节点的位置：在递归调用之前、之间还是之后。把下面先序模板吃透，另两种只是移动一行 visit。

// 先序遍历二叉树：根左右 void preOrder(struct Node* root) { if (root == NULL) return; // 递归出口：空树直接返回 visit(root); // 访问根节点 preOrder(root->left); // 递归遍历左子树 preOrder(root->right); // 递归遍历右子树 }

逻辑就是「根左右」。visit(root)移到两个递归调用之间是「左根右」的中序，移到两个调用之后是「左右根」的后序。递归出口必须写在函数体最前面，作用是让空指针直接返回；不写出口，递归永不终止，会栈溢出。这种错误笔试不运行代码，只能靠平时养成的检查习惯发现。

注意：先判空再访问。把visit(root)放在判空之前，空树时会访问空指针，卷面上看不出来，但阅卷人会按逻辑错误扣分。

从这段模板可以直接扩展出两个高频变体。求二叉树深度，就是后序遍历框架返回max(左深度, 右深度) + 1：左右子树先递归算深度，空节点深度记为 0，非空节点深度是两者较大值加一。求叶子数，把「访问根节点」改成「左右孩子都为空时计数加一」。这类变体题出现频率不低，但本质都回到同一棵递归模板上。非递归遍历用栈模拟，专升本要求通常停在读代码层面，能看懂「先入栈、出栈访问、转右子树」的次序即可。

3.3 快速排序与折半查找：两段代码，边界全是分

快排和二分是理解型考点里的两个钉子户。快排的partition写法很多，笔试推荐挖坑填数版，它比双指针交换版容易从零写完整，也不容易出现左右指针交错后基准放错的情况。

// 挖坑填数法：把区间划分为左小右大，返回基准最终位置 int partition(int a[], int low, int high) { int pivot = a[low]; // 挖出区间第一个元素作基准 while (low < high) { while (low < high && a[high] >= pivot) high--; // 从右向左找小于基准的 a[low] = a[high]; // 填到左边的坑 while (low < high && a[low] <= pivot) low++; // 从左向右找大于基准的 a[high] = a[low]; // 填到右边的坑 } a[low] = pivot; // 基准归位 return low; // 基准位置，左右子区间以此分隔 } void quickSort(int a[], int low, int high) { if (low >= high) return; // 区间无效或只剩一个元素 int pos = partition(a, low, high); quickSort(a, low, pos - 1); // 左半边 [low, pos-1] quickSort(a, pos + 1, high); // 右半边 [pos+1, high] }

两个细节必须记牢。第一，内层两个while的比较符号是>=和<=，等值元素也会被移动，这是为了规避区间内大量相同元素时指针卡死的问题；写成>或<，全相等的数组会死循环。第二，递归区间是闭区间，pos已归位，所以左半边到pos-1、右半边从pos+1开始，不能让基准重复参与划分。快速排序考过程题时，每一趟递归都要画，只画最外层的考生通常拿不到满分。

// 在有序数组 a 中查找 key，找到返回下标，找不到返回 -1 int binarySearch(int a[], int n, int key) { int low = 0, high = n - 1; // 闭区间 [0, n-1] while (low <= high) { // 注意：<= 不是 < int mid = low + (high - low) / 2; if (a[mid] == key) return mid; else if (a[mid] < key) low = mid + 1; else high = mid - 1; } return -1; }

循环条件是low <= high。写成low < high时，区间缩到只剩一个元素就提前退出，目标正好在这个元素时会误判为查找失败。mid用low + (high - low) / 2计算，避免大数组下(low + high)越界。这两个写法单独看都不难，但考场上手忙脚乱时最容易写错，所以把它俩跟「闭区间同步收缩」绑在一起记忆：只要坚持闭区间，条件就是<=，收缩就是mid ± 1。

4. 高频翻车点排查：5 个让数据结构白丢分的低级失误

这一章写辅导和模拟批改里反复见到的失分点。它们的共同特征是：会的人照样错，属于非智力失分。知识都懂，卷面却拿不到分，最可惜。把这几个坑提前排掉，比多刷三套模拟卷更实在。每条按现象、原因、解决三步写，可以对照自查。

4.1 递归出口漏写，程序还没运行就已经栈溢出

现象：手写二叉树的遍历、深度计算这类递归函数，主体写得很顺，但函数里缺了判空返回的那一行。代码看着逻辑完整，实际一运行就不停压栈，直到内存耗尽。

原因：递归函数没有终止条件，调用链无法返回。笔试不运行代码，这种错误最隐蔽，阅卷只能靠人工找，一旦被发现就是整段函数分预扣。

解决：把「递归函数第一行必须是出口」变成肌肉记忆。写完递归立刻检查三件事：出口在不在入口处、出口条件是否覆盖空指针、每次递归调用是否真缩小了问题规模。这三个问题对遍历、深度、快排都适用，检查习惯养成后，几乎不可能再丢这种分。

4.2 复杂度算错：一看到双重循环就写 O(n²)

现象：给一段for(i=0;i<n;i++) for(j=i;j<n;j++)代码问时间复杂度，想都不想写 O(n²)。选择题里如果同时给出 O(n²) 和精确的 n(n+1)/2 两个选项，就选错了。

原因：看到嵌套循环就默认相乘，没有按内层循环实际执行次数求和。数量级上没错，但选择题常考精确次数，或者内外层变量有关联的累加模式，这时候乘出来的答案就是错的。

解决：内层循环次数随外层变化时用求和而不是相乘。考试时间紧，至少做到先判断数量级的习惯：只有最内层语句的执行次数决定复杂度，常数系数不必纠结。但要能算精确和式，才能应对选项级别不同的题目，这个用等差数列求和就能覆盖大部分情况。

4.3 链表反转丢失后继：写代码的顺序，就是指针的顺序

现象：手写单链表反转的中间步骤，发现curr走到第二个节点后，后面的节点全丢了。答题纸上箭头画得挺多，但代码里找不到保存原后继的那一行。

原因：修改curr->next之前没有先用临时变量保存原后继。三指针模板里最常见的顺序错误，先赋值再保存等于把后续所有节点全部丢掉，而且这种错在纸面上不容易当场发现。

解决：把四行顺序固定成「保存后继、改指向、前驱前移、当前后移」，每次写完用三个节点的链表演算一遍，确认走到第几个节点时链条仍然完整。考前默写模板时把这句话写在该题旁边，考场上不会忘。链表的指针题本质是顺序题，代码顺序对了，逻辑就对了。

4.4 折半查找条件写成 <：死循环与漏判二选一

现象：函数写完整了，循环条件写成low < high。目标不在数组中时可能死循环，目标正好在最后一个位置时直接返回 -1，两种结果都是大扣分。

原因：对闭区间[low, high]的收缩逻辑理解不深。low <= high保证区间至少还有一个元素时循环继续，写成<等于提前一轮退出，端点元素的判断被跳过。

解决：把「循环条件 + 收缩步进」绑定记忆。low = mid + 1、high = mid - 1和low <= high是一套，区间每次都在真正缩小，不会出现low卡在原地的死循环。考前做五组手工模拟，每次把收缩后的区间写出来，条件自然就背住了。

4.5 概念题说大白话：意思是那个意思，分却不是那个分

现象：问「什么是稳定排序」，回答「排序之后，两个一样的数的位置不会变」。意思对，但「一样的数」表述不严谨，应该是关键字相同的记录，在排序前后的相对次序保持不变。阅卷按点给分时，缺了「相对次序」这个限定就扣分。

原因：概念题用口语表达，术语不准。专升本阅卷对概念题按要点给分，口语化答案经常踩不到得分点，答得辛苦但分不高。

解决：每个核心概念备一句术语模板。排序稳定性、二叉树性质、图的连通性、哈希冲突处理这四类是高频概念题，各背一句标准表述，比背十句零散笔记管用。回答时先写术语句，再补一句自己的解释，两分的小题也能拿扎实。

5. 把「看懂」变成「稳定写对」：考前两周的白纸复现法

考前最后两周，停止无止境刷题，换成白纸复现。具体做法：列出 8 段核心模板，每天抽 2 段，合上笔记在白纸上默写，写完后打开标准模板逐行对照。对照只标记三类差异：漏了哪一行、哪行顺序换了、哪个返回值不对。把差异写在模板旁边，第二天复现前先看一遍再写第二遍，直到连续两天零差异。

白纸复现的意义在于，把「认识」转成「回忆」。考场上能写出来的，只有你不看答案也完整写对过的东西。前三天复现往往惨不忍睹，反转丢 next、快排符号写成>，全是第四章说的坑；第五天开始多数模板可以一遍写对，进考场时心态完全不同。最后一周再做两套完整模拟卷，只掐时间不查答案，做完统一对，重点看手写题的过程分丢在哪。

专升本数据结构后期拼的不是智商，是稳定输出。模板练到像写自己名字一样自然，坑逐个排查过一遍，这门课就很难丢大分。希望帮到你。

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