简介这份自考数据结构重点总结文档面向备战02331数据结构课程的自考考生及计算机专业初学者帮助梳理逻辑结构、存储结构、算法分析等核心考点。文档以沃思“算法数据结构程序”为切入点系统整理线性表、栈、队列、数组、树、图等结构的定义与运算并归纳顺序存储、链式存储、索引存储、散列存储四种方式的适用场景与差异。资源包共1个doc文件大小约1.62MB内容涵盖时间复杂度与空间复杂度的常见量级、算法五大准则、顺序表插入删除的平均移动次数推导以及单链表头插法、尾插法建表等典型代码实现适合对照教材逐章复习与考前速记。目前已有97人学习下载可作为自考冲刺阶段的知识点清单与查漏补缺参考。1. 自考 02331 数据结构重点总结一份能直接背的复习文档长什么样如果你正在准备自考 02331 数据结构大概率经历过这种局面教材翻了三遍线性表、栈、队列、二叉树的概念都眼熟但一做真题就卡在“顺序表插入平均移动多少个结点”“循环队列怎么判满”这种细节上。这份《自考 02331 数据结构重点总结最终修订》就是冲着这个痛点来的——它不是教材的替代品而是一份把考点压缩到极致的复习文档覆盖概论、线性表、栈和队列、多维数组和广义表、树和二叉树五大章节每一章都按“概念定义 公式 算法描述 复杂度结论”的结构整理。适合两类人一是离考试还有两三周、需要快速过一遍核心考点的自考生二是已经学过一遍、想拿一份浓缩版查漏补缺的从业者。它解决的不是“理解数据结构”的问题而是“在有限时间内把该记的公式和结论记准”的问题。2. 概论与复杂度文档里最容易拿分也最容易记混的部分2.1 逻辑结构与存储结构的四象限划分文档第一章把数据结构拆成三个层面逻辑结构、存储结构、数据运算。这个划分本身就是考点。逻辑结构回答的是“数据元素之间是什么关系”分线性线性表、栈、队列、串和非线性数组、广义表、树、图两类存储结构回答的是“这些关系在内存里怎么放”分顺序存储、链式存储、索引存储、散列存储四种。很多人在做题时把这两个层面混在一起比如看到“栈”就以为是存储结构其实栈是逻辑结构层面的概念它可以用顺序存储实现顺序栈也可以用链式存储实现链栈。文档里有一个容易被忽略的细节顺序存储通常借助数组描述链式存储借助指针描述索引存储的关键是索引表散列存储的核心是“根据关键字直接计算存储地址”。这四个存储方法在选择题里经常以“以下哪种存储方式不需要额外空间”或“哪种存储方式失去随机存取特性”的形式出现。我的建议是把这四种存储方法和它们各自的典型代表结构做成一张对照表考前反复看。2.2 时间复杂度排序与算法五准则文档明确列出了常见时间复杂度的递增顺序O(1) O(log₂n) O(n) O(nlog₂n) O(n²) O(n³) … O(n^k) O(2^n) O(n!)。这个排序几乎每年都会以某种形式出现在选择题里要么是直接排序要么是给几个算法让你比较优劣。需要注意的是文档特别强调了“算法与程序的区别”程序必须依赖具体编程语言而算法可以用自然语言、数学语言或约定符号描述。这个点在简答题里出现过很多人只记得“算法有五个准则”却忘了“算法不等于程序”这个结论。算法五个准则——输入、输出、有穷性、确定性、可行性——文档写得很清楚但考试里容易设坑的地方是“输入”这一条算法可以有零个或多个输入但必须有一个或多个输出。也就是说“零输入”是允许的“零输出”是不允许的。这个细节在判断题里反复出现。2.3 空间复杂度的构成文档把空间复杂度 S(n) 拆成三部分算法本身占用的空间、输入输出数据占用的空间、运行过程中临时占用的空间。考试里通常只关注第三部分也就是辅助空间。比如问“冒泡排序的空间复杂度是多少”答案是 O(1)因为只需要一个临时变量做交换不需要额外的辅助数组。而归并排序需要 O(n) 的辅助数组所以空间复杂度是 O(n)。这个区分在选择题里很常见。提示文档里“算法求解问题的输入量称为问题的规模用正整数 n 表示”这句话是理解复杂度的前提。做题时先确认 n 代表什么再判断复杂度。3. 线性表顺序表与链表的公式、算法和选型边界3.1 顺序表的地址计算与插入删除代价文档给出了顺序表中结点 ai 的存储地址公式LOC(ai) LOC(a1) (i-1) × c其中 c 是每个结点占用的存储单元数。这个公式是顺序表“随机存取”特性的数学基础——只要知道起始地址和下标就能直接算出任意元素的地址不需要从头遍历。这也是顺序表最大的优势。但优势的反面是代价。文档明确写了在顺序表上插入一个结点平均要移动一半结点n/2时间复杂度 O(n)删除一个结点平均要移动约一半结点(n-1)/2时间复杂度也是 O(n)。具体来说在第 i 个位置插入时需要移动 n-i1 个结点删除第 i 个结点时需要移动 n-i 个结点。这两个公式建议直接背下来考试里经常出计算题比如“在长度为 n 的顺序表第 i 个位置插入一个元素需要移动多少个元素”。3.2 单链表的头插法与尾插法文档给出了单链表建表的两种方法。头插法的核心是四步生成新结点、填入数据、新结点 next 指向 head、head 指向新结点。代码逻辑如下// 头插法建表 p (ListNode *)malloc(sizeof(ListNode)); // 生成新结点 p-data ch; // 将读入的数据放入新结点的数据域 p-next head; // 新结点的 next 指向原头结点 head p; // head 指向新结点头插法的时间复杂度是 O(n)但它有一个特点读入数据的顺序和链表中结点的顺序是相反的。比如依次读入 a、b、c头插法建出来的链表是 c→b→a。这个特性在考试里会以“头插法建立的链表输出顺序与输入顺序的关系”形式出现。尾插法需要维护一个尾指针 rear每次把新结点接到 rear 后面然后更新 rear。文档还给出了带头结点的尾插法版本头结点的作用是统一空表和非空表的处理同时让第一个位置的操作和其他位置一致。这个“头结点”的概念在链表相关的题目里反复出现必须理解清楚。3.3 单链表的查找、插入与删除按序号查找的算法逻辑是从头结点开始扫描用 j 记录当前结点的序号当 j 等于目标序号 i 时返回当前结点。时间复杂度 O(n)。按值查找更直接从第一个结点开始逐个比较 data 域找到就返回指针找不到返回 NULL。时间复杂度也是 O(n)。插入操作的关键是找到第 i-1 个结点然后执行四步生成新结点、填入数据、新结点 next 指向第 i 个结点、第 i-1 个结点的 next 指向新结点。删除操作类似找到第 i-1 个结点让它的 next 指向第 i1 个结点然后 free 掉第 i 个结点。文档特别强调链表上的插入和删除不需要移动结点只需要修改指针这是链表相对于顺序表的核心优势。3.4 循环链表与双向链表的关键差异单循环链表把终端结点的 next 从 NULL 改为指向头结点。判断空链表的条件变成了 head head-next。文档还提到了仅设尾指针的单循环链表用尾指针 rear 表示时查找开始结点 a1 和终端结点 an 的时间都是 O(1)因为 rear-next 就是 a1rear 本身就是 an。这个特性使得在实际中多采用尾指针表示单循环链表。双向链表的每个结点多了一个 prior 指针域指向前驱结点。文档给出了前插和删除的算法核心区别是双向链表的插入和删除必须同时修改两个方向上的指针。比如前插操作需要修改四根指针新结点的 prior 和 next、原结点的 prior 的 next、原结点的 prior。时间复杂度都是 O(1)但指针操作的数量比单链表多一倍写代码时容易漏掉某一根指针导致断链。3.5 顺序表与链表的选型判断文档给出了一个简洁的选型原则时间性能上经常查找用顺序表经常插入删除用链表空间性能上数据量大小事先知道的用顺序表数据量变化大的用链表。存储密度方面顺序表的存储密度是 1链表小于 1。这个选型逻辑在简答题里经常出现建议按“时间性能 空间性能 存储密度”三个维度来组织答案。注意文档里“数据的运算是定义在逻辑结构上的而运算的具体实现是在存储结构上进行的”这句话是理解线性表各种操作的前提。逻辑结构决定有哪些操作存储结构决定这些操作怎么实现、代价多大。4. 栈和队列LIFO 与 FIFO 的判空判满、循环队列与链式实现4.1 顺序栈的栈顶指针与上下溢文档明确了一个容易记错的细节空栈时栈顶指针不能是 0只能是 -1。这是因为栈顶指针指向的是栈顶元素的位置而不是栈顶元素的下一个位置。进栈时先加 1 再存元素退栈时先取元素再减 1。S-top StackSize-1 表示栈满此时再做进栈运算会产生“上溢”S-top 0 表示空栈此时再做退栈运算会产生“下溢”。文档特别指出下溢是正常现象常用作程序控制转移的条件。这个结论在判断题里出现过。两个栈共享同一存储空间时栈底分别设在数组两端栈顶向中间延伸。当 Top1 Top2-1 时栈满。这个共享栈的设计思路在考试里以“两个栈共享空间判断栈满的条件是什么”的形式出现。4.2 循环队列的三种判满方案循环队列是这一章的核心考点。文档指出了问题的根源入队时尾指针追赶头指针出队时头指针追赶尾指针导致队空和队满时头尾指针都相等。所以不能简单用 Q.front Q.rear 来判断队列是空还是满。文档给出了三种解决方案一是另设一个标志位二是设置一个计数器记录元素总数三是少用一个元素空间约定入队前测试尾指针在循环意义下加 1 后是否等于头指针如果相等就认为队列满。第三种方案最常用判满条件是 (Q.rear1) % QueueSize Q.front判空条件仍然是 Q.rear Q.front。循环队列的入队和出队操作都涉及“循环意义下的加 1”文档给出了两种写法一种是 if 判断一种是模运算。模运算写法更简洁Q.rear (Q.rear1) % QueueSize。这个写法在代码题里经常出现建议直接记住。4.3 链队列的头结点与出队边界链队列是在表头删除、表尾插入的单链表。文档建议在队头结点之前附加一个头结点队头指针指向此结点。这样做的好处和单链表的头结点一样统一空队列和非空队列的处理。链队列的出队操作有一个容易翻车的边界当队列长度大于 1 时只需要修改头结点指针尾指针不变但当队列长度等于 1 时删去此结点后队列变空不仅要修改头结点指针还要修改尾指针让 Q.rear Q.front。这个边界条件在代码题里经常被忽略导致队列变空后尾指针变成野指针。4.4 栈与队列的应用场景对比文档提到栈的一个重要应用是实现递归因为递归函数的调用和返回天然符合后进先出的顺序。队列则常用于需要按顺序处理的场景比如操作系统的任务调度、打印队列等。文档还提到用计算机处理算术表达式时需要将中缀表达式转换成后缀表达式这个转换过程就用到了栈。这个应用在考试里以“中缀表达式转后缀表达式”的题目出现需要掌握转换规则。提示栈顶指针指向栈顶元素队尾指针指向队尾元素的下一个位置。这两个“指向”的差异是很多判断题的陷阱来源。5. 多维数组、广义表与二叉树压缩存储公式和遍历还原5.1 行优先与列优先的地址计算文档给出了二维数组按行优先和按列优先存储的地址计算公式。以行优先为例下界为 1 时LOC(aij) LOC(a11) [(i-1)×n j-1] × d下界为 0 时公式变为 [i×n j]。列优先的公式是 LOC(aij) LOC(a11) [(j-1)×m i-1] × d。文档特别指出Pascal 和 C 语言按行优先存储Fortran 按列优先存储。这个语言差异在选择题里出现过。三维数组的公式更复杂一些但逻辑是一样的先算前面有多少个完整的“面”再算当前面里有多少个完整的“行”最后加上当前行的偏移量。建议把二维的公式记牢三维的可以现场推导。5.2 对称矩阵与三角矩阵的压缩存储对称矩阵只需要存储上三角或下三角元素让对称的元素共享一个存储空间。文档给出了 aij 和 sa[k] 之间的对应关系当 i ≥ j 时k i×(i1)/2 j当 i j 时k j×(j1)/2 i。地址计算公式是 LOC(aij) LOC(sa[0]) [I×(I1)/2 J] × d其中 I max(i,j)J min(i,j)。三角矩阵的压缩存储稍微不同上三角矩阵中当 i ≤ j 时 k i×(2n-i1)/2 j - i当 i j 时 k n×(n1)/2也就是常数 c 存放在数组的最后一个位置。下三角矩阵中当 i ≥ j 时 k i×(i1)/2 j当 i j 时 k n×(n1)/2。文档特别强调三角矩阵的压缩存储结构是随机存取结构。这个结论在判断题里出现过。5.3 稀疏矩阵的三元组表与十字链表稀疏矩阵的非零元素分布没有规律所以存储非零元素的同时还必须存储它所在的行和列用三元组 (i, j, aij) 来确定。文档指出稀疏矩阵的压缩存储会失去随机存取功能因为要查找某个元素必须遍历三元组表或十字链表。这个“失去随机存取”的结论是考试里的高频考点。5.4 广义表的表头、表尾与深度广义表是线性表的推广元素可以是原子也可以是子表。文档给出了两个基本运算取表头 head(Ls) 和取表尾 tail(Ls)。关键结论是任何一个非空广义表的表头可以是原子也可以是子表但表尾必定是子表。比如 head(a, b) atail(a, b) (b)。文档还特别提醒广义表 () 和 (()) 不同前者是长度为 0 的空表不能做求表头和表尾的运算后者是长度为 1 的由空表作元素的广义表分解得到的表头和表尾都是空表 ()。广义表的深度是指展开后所含括号的层数。文档指出广义表是一种多层次的线性结构实际上是一种树形结构。这个“多层次”的特性在选择题里以“广义表的深度”或“广义表的长度”的形式出现。5.5 二叉树的五条性质与完全二叉树编号文档列出了二叉树的五条性质。性质 1第 i 层最多有 2^(i-1) 个结点。性质 2深度为 k 的二叉树最多有 2^k - 1 个结点。性质 3终端结点数 n0 度为 2 的结点数 n2 1。性质 4具有 n 个结点的完全二叉树的深度为 ⌊log₂n⌋ 1。性质 5 是关于完全二叉树编号的如果从 0 开始编号结点 i 的双亲编号是 ⌊(i-1)/2⌋左孩子编号是 2i1右孩子编号是 2i2。这五条性质里性质 3 和性质 4 是计算题的高频考点。性质 3 的证明逻辑是设结点总数为 n则 n n0 n1 n2设边数为 e则 e n - 1 n1 2n2联立两式可得 n0 n2 1。这个推导过程建议自己走一遍比死记结论更可靠。5.6 遍历序列还原二叉树文档指出一棵二叉树的前序和中序遍历序列或中序和后序遍历序列可以唯一确定一棵二叉树。具体方法是先根据前序或后序遍历序列确定根结点然后在中序遍历序列中找到根结点的位置左边是左子树的中序序列右边是右子树的中序序列再根据左子树和右子树的结点数量在前序或后序序列中划分出对应的子序列递归还原。这个还原过程在考试里以“给定前序和中序序列画出二叉树”或“给定中序和后序序列写出前序序列”的形式出现。我的经验是先找根再分左右然后递归处理每一棵子树。画图时把每一步的根结点标出来不容易出错。5.7 线索二叉树的空指针利用n 个结点的二叉链表有 2n 个指针域其中 n-1 个用来指示左右孩子剩下的 n1 个是空指针。线索二叉树就是利用这 n1 个空指针域存放指向结点在某种遍历次序下的前驱和后继结点的指针。文档给出了线索链表的结点结构增加 ltag 和 rtag 两个标志域用来区分指针域是指向孩子还是指向前驱/后继线索。文档还给出了一个结论线索二叉树中一个结点是叶结点的充要条件是左、右标志均是 1。这个结论在判断题里出现过。线索化的过程本质上是在遍历过程中把空指针改成线索所以线索二叉树的中序遍历不需要递归也不需要栈可以直接沿着线索走。注意文档里“二叉树与度数为 2 的有序树不同”这个点容易被忽略。在有序树中只有一个孩子时不区分左右但在二叉树中即使只有一个孩子也有左右之分。这个差异在选择题里以“二叉树和度为 2 的有序树的区别是什么”的形式出现。6. 把这份文档用出最大价值我的三轮复习法和公式速查表这份文档最大的价值在于“浓缩”但浓缩的东西如果不经过主动加工很容易变成“看的时候都懂做题的时候都想不起来”。我自己的做法是把这份文档过三轮每一轮的目标不同。第一轮是“扫盲式通读”目标是确认每个概念都能用自己的话解释一遍。具体做法是打开文档逐章阅读遇到公式就手抄一遍遇到算法描述就在纸上画出执行过程。比如看到顺序表的插入算法就在纸上画一个长度为 5 的数组模拟在第 3 个位置插入一个元素的过程数一数移动了几个结点。这一轮不追求记住追求的是“理解每个结论是怎么来的”。第二轮是“公式默写”目标是把文档里所有公式和复杂度结论默写出来。我整理了一张速查表按章节排列章节核心公式/结论常见考法概论时间复杂度排序O(1) O(log₂n) O(n) O(nlog₂n) O(n²) O(2^n) O(n!)选择题排序线性表顺序表插入移动 n-i1 个删除移动 n-i 个计算题线性表单链表插入/删除时间复杂度 O(n)双向链表 O(1)选择题栈和队列循环队列判满(rear1)%QueueSize front判断题/代码题栈和队列空栈条件top -1判断题多维数组行优先地址LOC(aij) LOC(a11) [(i-1)×n j-1]×d计算题对称矩阵k i×(i1)/2 ji ≥ j计算题二叉树n0 n2 1计算题二叉树完全二叉树深度⌊log₂n⌋ 1计算题二叉树编号 i 的左孩子 2i1右孩子 2i2双亲 ⌊(i-1)/2⌋选择题这张表我考前一周每天默写一遍默不出来的用红笔标记第二天重点看。三轮下来公式基本就刻在脑子里了。第三轮是“真题验证”目标是检验前两轮的成果。具体做法是找近五年的自考 02331 真题按章节分类每做一道题就回到文档里找对应的知识点确认自己用的是文档里的结论而不是凭感觉。做错的题在文档对应位置做标记考前只看标记过的内容。还有一个容易被忽略的点文档里有些结论是以“注意”或“特别指出”的形式出现的比如“下溢是正常现象”“三角矩阵的压缩存储是随机存取结构”“广义表的表尾必定是子表”。这些“注意”往往是判断题的命题点因为出题人知道考生容易忽略这些细节。我的习惯是把文档里所有“注意”“特别”“必须”标记的句子单独抄在一张纸上考前集中看。从那以后我每次拿到一份浓缩版复习资料都会先做一件事把里面的公式和结论单独抽出来做成速查表然后按“理解→默写→验证”三轮走一遍。这份自考数据结构重点总结的文档结构清晰、考点覆盖完整按这个方法用比自己从头翻教材至少省一半时间。希望帮到你。本文还有配套的精品资源点击获取