简介这份自考数据结构重点总结文档面向备战02331数据结构课程的自考考生与计算机专业初学者系统梳理了该课程的核心考点与知识框架。内容围绕逻辑结构与存储结构、算法复杂度评估、线性表及其顺序与链式实现等主线展开涵盖顺序存储、链式存储、索引存储与散列存储四种基本方式并整理常见时间复杂度等级与线性表基本运算等高频考点便于对照复习与查漏补缺。资源包共1个doc文件大小约1.62MB内容为纯文档笔记适合打印或电子阅读。目前已有97人学习下载可作为自考冲刺阶段的重点速记材料帮助读者快速建立知识脉络、把握算法时空效率与可读性等评价维度提升解题与代码实现能力。1. 自考数据结构重点总结从线性表到二叉树一份能直接背的复习路线自考数据结构这门课挂的人多不是因为题难而是因为复习方向错了。很多人抱着教材从第一章啃到最后一章结果线性表还没搞明白二叉树已经忘光了。我当年第一次考就是栽在这上面后来复盘发现自考数据结构的考点其实高度集中线性表、栈和队列、二叉树、图、查找、排序这六块占了卷面八成以上剩下的边角料基本靠选择题蒙。所以这份总结不打算面面俱到而是按考点权重和出题频率来组织把每一块的核心概念、必背公式、典型题型和代码模板拆开讲清楚。适合正在备考自考、专升本或者期末突击的人也适合已经工作但想补数据结构基础的开发者。接下来的内容按「先搞懂考什么、再动手写什么、最后避开哪些坑」的顺序推进每一章都能直接拿去背或者拿去练。2. 线性表、栈和队列自考卷面上最容易拿满分的三块2.1 线性表的顺序存储和链式存储到底怎么选线性表是数据结构里最基础的结构自考里几乎每年必考。它的核心就两种实现方式顺序存储数组和链式存储链表。顺序存储用一段连续内存放数据支持随机访问按下标取值的时间复杂度是 O(1)但插入和删除要移动元素平均移动 n/2 个时间复杂度 O(n)。链式存储用节点加指针的方式插入删除只需要改指针O(1) 就能搞定但查找必须从头遍历O(n)。自考选择题特别喜欢考这个对比。比如「在长度为 n 的顺序表第 i 个位置插入元素需要移动多少个元素」——答案是 n-i1。删除第 i 个元素需要移动 n-i 个。这两个公式必须背死考场上没时间推导。链表中有一个高频考点是头结点。带头结点的链表在插入和删除第一个元素时不需要特殊处理代码更统一。自考简答题经常问「头结点的作用是什么」标准答案就是统一空表和非空表的处理简化第一个位置的插入删除操作。下面这段代码是单链表按值删除的标准写法自考代码题经常要求写这个// 删除单链表中值为 x 的第一个节点 int deleteNode(LinkList *L, int x) { LinkList p (*L)-next; // p 指向第一个实际节点 LinkList pre *L; // pre 始终指向 p 的前驱 while (p ! NULL p-data ! x) { pre p; p p-next; } if (p NULL) return 0; // 没找到 pre-next p-next; // 跳过 p free(p); // 释放内存 return 1; }这段代码的关键在于 pre 指针的维护。很多人写的时候只用一个指针结果找到目标节点后没法删除因为不知道前驱是谁。参数 L 是头指针的指针这样在空表插入时也能修改头指针本身。时间复杂度 O(n)空间 O(1)。2.2 栈和队列的判空判满条件为什么总记混栈是后进先出队列是先进先出概念谁都懂但一到循环队列的判空判满就翻车。顺序栈的判空条件是 top -1判满条件是 top maxSize-1这个好记。循环队列就麻烦了判空是 front rear判满也是 front rear冲突了。解决办法有三种一是牺牲一个存储单元判满条件变成 (rear1)%maxSize front二是加一个 size 变量记录元素个数三是加一个 tag 标记最近操作是插入还是删除。自考最常考的是第一种因为不用额外变量。循环队列的元素个数公式也要背count (rear - front maxSize) % maxSize。这个公式在选择题里出现频率极高不背的话考场上现推容易出错。栈的应用里自考最爱考的是括号匹配和表达式求值。括号匹配的思路是遇到左括号入栈遇到右括号就弹出栈顶看是否匹配最后栈空则合法。表达式求值分中缀转后缀、后缀求值两步核心还是栈的操作。这部分简答题经常要求写出算法思想不用写完整代码但步骤要写清楚。队列的应用里层次遍历是重点这个放到二叉树那章一起讲。这里先记住一点循环队列的入队操作是 rear (rear1) % maxSize出队是 front (front1) % maxSize取模运算不能忘。3. 二叉树遍历、线索化和哈夫曼编码的拿分套路3.1 三种遍历方式的递归和非递归写法二叉树是自考数据结构里分值最高的章节没有之一。遍历是基础中的基础先序、中序、后序三种递归写法必须闭着眼都能写出来。先序是根左右中序是左根右后序是左右根这个顺序不能乱。递归写法很简单但自考经常考非递归。非递归的核心是用栈模拟递归调用。以中序遍历为例思路是一路向左把节点压栈直到没有左孩子然后弹出栈顶访问再转向右孩子。代码如下// 二叉树中序遍历的非递归实现 void inOrderTraverse(BiTree T) { Stack S; InitStack(S); BiTree p T; while (p ! NULL || !isEmpty(S)) { if (p ! NULL) { Push(S, p); // 一路向左沿途入栈 p p-left; } else { Pop(S, p); // 弹出栈顶 visit(p); // 访问节点 p p-right; // 转向右子树 } } }这段代码的关键是 while 循环的条件p 不为空或者栈不为空。只写一个条件都会漏掉情况。先序的非递归更简单入栈前访问即可。后序最难需要两个栈或者一个栈加标记位自考考后序非递归的概率相对低一些但也要会。层次遍历用队列思路是根节点入队然后循环出队访问同时把左右孩子入队。这个在求二叉树宽度、按层输出等题目里经常用到。3.2 线索二叉树和哈夫曼树的自考出题规律线索二叉树是自考的常客但很多人搞不清楚线索化的规则。简单说就是把空闲的左指针指向遍历前驱空闲的右指针指向遍历后继。中序线索化最常考因为中序线索化后可以直接找到前驱和后继不需要栈。线索二叉树的节点结构要多两个标志位ltag 和 rtag。ltag0 表示 left 指向左孩子ltag1 表示 left 指向前驱。rtag 同理。自考选择题经常给一个二叉树让画中序线索二叉树或者问某个节点的前驱后继是谁。做题技巧是先写出中序遍历序列然后看每个节点的左右指针是否为空空的话就按规则连线。哈夫曼树是另一个高频考点。构造方法是每次选两个权值最小的节点合并新节点权值为两者之和重复直到只剩一个节点。哈夫曼编码就是从根到叶子路径上左 0 右 1。自考经常考计算带权路径长度 WPL公式是每个叶子节点的权值乘以路径长度再求和。这里有一个容易错的地方哈夫曼树不唯一但 WPL 是唯一的。选择题如果问「哈夫曼树是否唯一」答案是否定的。另外哈夫曼编码是前缀编码任何一个编码都不是另一个编码的前缀这个性质经常考判断题。二叉树还有一个必考公式n0 n2 1即叶子节点数等于度为 2 的节点数加 1。这个公式在选择题里出现频率极高推导过程也要会设节点总数 n n0 n1 n2边数 n - 1 n1 2*n2联立可得 n0 n2 1。4. 图、查找和排序自考最后三道大题的固定套路4.1 图的存储结构和两种遍历的代码模板图这一章自考考得相对浅但邻接矩阵和邻接表的转换、深度优先搜索和广度优先搜索的遍历序列是必考的。邻接矩阵用一个二维数组存边适合稠密图邻接表用链表存每个顶点的邻接点适合稀疏图。两者转换的选择题经常出现关键记住邻接矩阵的第 i 行非零元素个数等于顶点 i 的出度有向图或度无向图。深度优先搜索类似树的先序遍历用递归或者栈实现。广度优先搜索类似树的层次遍历用队列实现。自考经常给一个图让写出从某个顶点出发的 DFS 和 BFS 序列。做题时注意DFS 序列不唯一取决于邻接点的访问顺序但考试一般会指定按编号从小到大访问。最小生成树有两个经典算法Prim 和 Kruskal。Prim 从一个顶点开始每次选连接已选集合和未选集合的最小边Kruskal 按边权排序每次选不构成回路的最小边。自考简答题经常问两者的区别Prim 适合稠密图时间复杂度 O(n²)Kruskal 适合稀疏图时间复杂度 O(elog e)。最短路径的 Dijkstra 算法也是重点思路是每次选一个未访问的距离最小的顶点然后更新其邻接点的距离。自考一般考手动模拟过程给一个带权图让写出每一步的 dist 数组变化。4.2 查找算法二分查找的判定树和哈希冲突的解决查找这一章二分查找是重中之重。二分查找的前提是序列有序时间复杂度 O(log n)。自考经常考判定树的构造把 mid 作为根左半部分递归构造左子树右半部分递归构造右子树。判定树的深度就是最大比较次数。二分查找的代码要会写注意 mid 的计算方式mid (low high) / 2 是向下取整mid (low high 1) / 2 是向上取整。两种写法对应的判定树不同自考一般用向下取整。哈希表是另一个考点。哈希函数构造方法有除留余数法、直接定址法等自考最常考除留余数法H(key) key % pp 一般取小于表长的最大质数。冲突解决有开放定址法和链地址法。开放定址法里线性探测再散列的公式是 Hi (H(key) di) % mdi 1, 2, 3...。自考经常给一组关键字和表长让画出哈希表并计算平均查找长度。平均查找长度的计算要注意查找成功时ASL 每个元素的比较次数之和 / 元素个数查找失败时ASL 每个位置查找失败的比较次数之和 / 表长。这两个公式不一样别搞混。4.3 排序算法对比时间复杂度、稳定性和适用场景排序是自考最后一道大题的常客八种排序算法都要掌握。冒泡、插入、选择是 O(n²)快排、归并、堆排是 O(nlog n)基数排序是 O(d(nr))。稳定性方面快排、选择、堆排、希尔不稳定冒泡、插入、归并、基数稳定。自考最爱考的是快排的一趟划分过程。给一个序列让写出以第一个元素为基准的一趟快排结果。做题技巧是从右往左找比基准小的从左往右找比基准大的交换直到左右指针相遇基准归位。堆排序要会建堆和调整堆。建堆从最后一个非叶子节点开始依次向下调整。大根堆的调整规则是如果孩子节点比父节点大交换然后继续向下调整。自考经常考「给一个序列建大根堆」或者「堆排序的前两趟结果」。归并排序考得相对少但二路归并的一趟结果要会写。基数排序考得更少但基本思想要清楚按位分配和收集从低位到高位。下面这张表把八种排序的核心参数列出来考前扫一眼就能记住排序算法平均时间复杂度最坏时间复杂度空间复杂度稳定性冒泡排序O(n²)O(n²)O(1)稳定插入排序O(n²)O(n²)O(1)稳定选择排序O(n²)O(n²)O(1)不稳定快速排序O(nlog n)O(n²)O(log n)不稳定归并排序O(nlog n)O(nlog n)O(n)稳定堆排序O(nlog n)O(nlog n)O(1)不稳定希尔排序O(n^1.3)O(n²)O(1)不稳定基数排序O(d(nr))O(d(nr))O(r)稳定5. 自考数据结构避坑这五个错误每年都有人犯5.1 循环队列判满条件写反现象题目给一个循环队列front3rear7maxSize10问队列是空还是满。很多人看到 front 不等于 rear 就判断不是空然后套公式算元素个数结果算出来是 4 个但实际可能是满的。原因循环队列判空和判满都可能是 front rear如果题目没有说明牺牲一个存储单元就无法直接判断。自考题目一般会明确「采用牺牲一个存储单元的方式」这时候判满条件是 (rear1)%maxSize front。解决做题前先看题目有没有说明判满方式。如果没有说明默认牺牲一个单元。元素个数公式 (rear-frontmaxSize)%maxSize 在判满时算出来是 maxSize-1不是 maxSize这个细节要注意。5.2 二叉树遍历序列还原时搞错根节点现象给先序序列和中序序列让还原二叉树画出来的树和答案对不上。原因先序的第一个元素是根这个没错但中序里根左边的元素个数决定了左子树的规模。很多人画的时候没有严格按个数切分导致左右子树节点数对不上。解决先序第一个是根在中序里找到根的位置左边就是左子树的中序序列右边是右子树的中序序列。然后根据左子树的节点个数在先序里切出左子树的先序序列。递归这个过程。每次切分后检查左右子树节点数是否一致不一致就是切错了。5.3 哈希表平均查找长度算错分母现象哈希表查找失败的 ASL 算出来和答案差很多。原因查找失败的分母是表长不是元素个数。很多人习惯性用元素个数做分母结果偏大。解决查找成功的 ASL 分母是元素个数 n查找失败的 ASL 分母是表长 m。另外查找失败的比较次数是从每个位置出发到第一个空位置的比较次数不是到最后一个元素的次数。画哈希表的时候把空位置标出来逐个算。5.4 快排一趟划分后基准位置搞错现象快排一趟划分基准元素最后的位置写错了。原因快排的划分有多种写法有的从右往左找小有的从左往右找大交换的时机不同基准归位的位置也不同。解决记住一个标准流程low 指向第一个元素high 指向最后一个元素基准取第一个元素。先从 high 往左找比基准小的找到后放到 low 位置再从 low 往右找比基准大的找到后放到 high 位置重复直到 low high基准放到 low 位置。这个流程走一遍基准位置不会错。5.5 图的 DFS 和 BFS 序列漏掉孤立点现象图的遍历序列写出来少了一个顶点。原因如果图不是连通图从一个顶点出发只能遍历到所在连通分量。题目如果说「从顶点 V1 出发」那就只写 V1 所在分量的序列。如果说「遍历整个图」那就要对每个未访问的顶点再启动一次遍历。解决先判断图是否连通。不连通的话看题目要求是「从某点出发」还是「遍历全图」。前者只写一个分量后者要写多个分量中间用分号隔开。6. 考前一周怎么用这份总结一个可执行的复习节奏最后一章不讲新知识讲怎么把前面五章的内容在七天内塞进脑子并且考场能调出来。我当年第二次考就是靠这个节奏过的血泪经验换来的。前三天按章节过知识点。第一天线性表加栈队列第二天二叉树第三天图加查找排序。每天不要只看要动手写。线性表的插入删除代码默写一遍二叉树的三种遍历递归非递归各写一遍快排的一趟划分手动模拟三组数据。写不出来就翻回去看看完再默写直到能闭卷写出来。第四天和第五天刷真题。自考真题重复率很高尤其是选择题和简答题。把近五年的真题选择题全部做一遍错题标记出来回到对应章节重新看。简答题不用全写但要把答题要点列出来比如「头结点的作用」就写「统一空表和非空表处理简化第一个位置插入删除」两句话就够了。第六天专门攻代码题。自考代码题一般考链表操作、二叉树遍历、排序算法这三类。每类准备两个模板链表准备按值删除和头插法建表二叉树准备中序非递归和层次遍历排序准备快排一趟划分和堆调整。模板背熟考场上根据题目要求改改变量名和条件就行。第七天做两件事一是把八种排序的对比表默写一遍时间复杂度、空间复杂度、稳定性一个都不能错二是把二叉树节点公式 n0n21、循环队列元素个数公式、二分查找 mid 公式这三个高频公式再背一遍。然后早点睡考场上遇到不会的选择题先蒙一个别空着简答题能写多少写多少代码题就算写不完整也要把思路和关键步骤写上自考是按步骤给分的。最后说一个我自己的习惯考前那天晚上不再看新题只翻自己整理的错题本和公式表。看新题容易慌看熟悉的错题能稳住心态。希望帮到你。本文还有配套的精品资源点击获取