简介自考02331数据结构重点总结文档是面向自考计算机专业考生的核心考点整理覆盖数据构造的概论与线性表两大板块。文档从逻辑结构、存储结构、数据运算出发梳理了顺序存储、链式存储、索引存储、散列存储四种基本方法并总结了常见时间复杂度等级、算法评价准则以及线性表顺序表与链表的初始化、查找、插入、删除等基础操作重点突出、条理清晰。其中还包含顺序表地址计算、单链表头插法/尾插法建表、结点移动次数等易考易混细节便于读者对照教材加深理解。资源为单个doc文档文件总数为1压缩包大小1.62MB轻量易用适合打印后逐章背诵或与教材搭配复习。目前已有97人学习下载对准备自学考试、需要快速建立数据结构知识框架的读者而言是一份值得收藏的考前冲刺资料。1. 自考数据结构 02331这份重点总结为什么值得当备考主线数据结构是计算机专业的“分水岭”课程自考 02331 更是卡住不少考生的一科。我拆完这份《自考数据结构重点总结最终.doc》后发现它没有废话从第一章概论到第五章树覆盖了考试全部核心考点算法复杂度、线性表、栈、队列、数组、广义表、二叉树每个知识点都给出了结论和公式省去了自己翻教材重新整理的时间。对准备自考、考研 408 或想补数据结构基础的程序员来说这份文档可以直接当复习主线配合教材查缺补漏即可。文档定位是“应试导向的知识点总结”不是入门教程但足够精炼。它有两条主线一是从逻辑结构、存储结构到算法评价指标的理论骨架二是线性表、栈队列、树这几类核心结构的公式与操作细节。接下来我按考试实际出题频率把文档里的重点拆开讲顺带补上文档没明说、但做题时绕不开的坑。2. 算法复杂度与概论先把“时间换空间”的账算明白数据结构第一章常被考生跳过但复杂度分析几乎出现在每套试卷的简答题或选择题里。文档里沃思那句“算法 数据结构 程序”是必考点更要紧的是复杂度数量级排序——这是后面所有算法比较的基础。2.1 五个准则与四种存储方法选择题高频素材算法必须满足输入、输出、有穷性、确定性、可行性五个准则。这里容易混淆的是“算法”与“程序”的差别算法可以用自然语言或类 C 描述不依赖具体编程语言程序必须依赖计算机语言。这个点在判断题里反复出现值得记牢。四种存储方法各对应一种典型场景顺序存储通常借助数组适合随机访问链式存储借助指针适合频繁插入删除索引存储通过关键字查找适合静态查找表散列存储直接由关键字计算地址适合等值查找。选择题常给一个场景问“用哪种最合适”记住“随机访问选顺序、频繁增删选链式”就够用。2.2 时间复杂度递增序列按数量级背下来文档给出了完整的复杂度递增序列常数阶 O(1)、对数阶 O(log₂n)、线性阶 O(n)、线性对数阶 O(nlog₂n)、平方阶 O(n²)、立方阶 O(n³)、k 次方阶 O(nᵏ)、指数阶 O(2ⁿ)、阶乘阶 O(n!)。我备考时把这个序列画在纸上贴墙每天扫一遍。题目给的代码块先看是否有循环嵌套再看循环变量是增还是减半。一层循环且变量增量为 1 是 O(n)两层嵌套是 O(n²)循环变量每次翻倍或减半是对数阶。// 示例对数阶写法 int i 1; while (i n) { i i * 2; // 每次乘2执行次数为 log₂n }执行次数取决于 i 每次乘 2从 1 增长到超过 n 需要 log₂n 次。若把乘法改成加法复杂度就退化成 O(n)。空间复杂度的定义类似它包含算法本身占用空间、输入输出数据占用空间和运行时的临时空间考试通常只问“额外辅助空间”。3. 线性表顺序表与链表的选择本质是时间与空间的博弈第二章是数据结构真正的核心也是后续栈、队列实现的基础。文档里已经明确顺序表是随机存取结构插入删除平均要移动一半结点链表靠修改指针完成插入删除不用移动数据。这一章的考点集中在“移动次数计算”和“链表指针操作”两块。3.1 顺序表插入与删除移动次数必须手算过关顺序表中第 i 个位置插入结点的移动次数是 n-i1删除第 i 个结点的移动次数是 n-i。很多同学把这两个公式记反我提供一个记忆方法插入多了一个空位所以要多挪一个元素删除直接补位少挪一个。平均移动次数插入是 n/2删除是 (n-1)/2平均时间复杂度都是 O(n)。// 顺序表插入操作C语言 void InsertList(SeqList *L, int i, DataType x) { // L为顺序表指针i为插入位置x为待插入元素 int j; if (L-length MaxSize) { printf(表已满无法插入\n); return; } if (i 1 || i L-length 1) { printf(插入位置不合法\n); return; } for (j L-length - 1; j i - 1; j--) { L-data[j 1] L-data[j]; // 从尾部开始逐个后移 } L-data[i - 1] x; // 腾出的位置放入新元素 L-length; }循环从最后一个元素开始向后移动避免数据覆盖。位置从 1 计数对应数组下标 i-1。判断表满条件、位置合法条件和插入后长度自增这三处缺一不可。3.2 头插法与尾插法建表顺序的差异头插法每次把新结点插到头结点之后最终链表元素顺序与输入顺序相反尾插法用尾指针记录当前末尾顺序与输入一致。考试常给出输入序列问建表结果头插法的逆序特征是高频陷阱。// 尾插法建带头结点的单链表C语言 void CreateListR(LinkList *head, char input[]) { ListNode *r, *s; int i 0; head (ListNode *)malloc(sizeof(ListNode)); r head; // 尾指针初值指向头结点 while (input[i] ! \0) { s (ListNode *)malloc(sizeof(ListNode)); s-data input[i]; // 生成新结点并给数据域赋值 r-next s; // 新结点链到原表尾之后 r s; // 尾指针指向新的表尾 i; } r-next NULL; // 终端结点指针域置空 }尾指针 r 始终指向链表的最后一个结点每次新结点都链到 r 后面然后 r 前移。三个建表算法的时间复杂度均为 O(n)。如果去掉头结点第一个位置插入和删除就得单独处理这是头结点存在的最大意义——统一空表与非空表的操作。3.3 双向链表与单循环链表指针修改顺序的先后逻辑双向链表插入涉及四个指针修改顺序不能乱。文档里的前插操作顺序是先给新结点 s 的 prior 指向 p 的前驱、next 指向 p再让 p 前驱的 next 指向 s最后让 p 的 prior 指向 s。我先改 s 自身的两个指针再改链上原有指针顺序反了会丢失链信息。单循环链表判断空的条件是 head head-next指向头结点自身。如果用尾指针 rear 表示单循环链表连到 a₁ 和 an的时间都是 O(1)在做首尾插入删除时效率很高这也是“约瑟夫环”类题目优先选尾指针循环链表的原因。4. 栈与队列受限线性表的两张规则牌栈是 LIFO队列是 FIFO本质都是“受限的线性表”。自考第三章的高频考点集中在循环队列的判空判满以及后缀表达式转换。文档里对“上溢”和“下溢”的区分是基础题常客上溢是栈满再做入栈为错误状态下溢是栈空再做退栈常被用作控制转移条件。4.1 栈的顺序存储栈顶指针指向栈顶元素顺序栈用数组模拟栈顶指针 top 指向栈顶元素。入栈时先把 top 加 1再存入元素出栈时先取元素再把 top 减 1。空栈时 top 为 -1这是文档里特别标注的空栈时栈顶指针不能是 0。两个栈共享空间时栈底设在两端top1 和 top2 相向增长栈满条件为 top1 top2 - 1。4.2 循环队列的判空判满三种方案的边界条件顺序队列有“假溢出”问题——front 前移释放的空间不能再利用。循环队列通过模运算把数组首尾相连入队、出队都按 (i1) % QueueSize 推进。但这也带来一个新问题队空和队满时 front 都等于 rear必须另加判断。文档给出三种解法考试常考的是第三种“少用一个元素空间”队满条件为 (Q-rear 1) % QueueSize Q-front队空条件为 Q-rear Q-front。此时 rear 所指单元始终为空队列实际最多存 QueueSize-1 个元素。// 循环队列基本操作C语言 #define QueueSize 100 typedef struct { DataType data[QueueSize]; int front, rear; } CirQueue; // 入队 int EnQueue(CirQueue *Q, DataType x) { if ((Q-rear 1) % QueueSize Q-front) { return 0; // 队列满返回0表示失败 } Q-data[Q-rear] x; Q-rear (Q-rear 1) % QueueSize; // 循环意义下尾指针加1 return 1; } // 出队 DataType DeQueue(CirQueue *Q) { DataType temp; if (Q-rear Q-front) { return NULL; // 队列空 } temp Q-data[Q-front]; Q-front (Q-front 1) % QueueSize; // 循环意义下头指针加1 return temp; }队满判断里用取模运算把 rear 推进到数组末端时折回开头这样数组空间可以反复使用。记住一个口诀入队先判满、出队先判空、指针移动都要取模。4.3 链栈与链队列无需判满的内存动态分配链栈本质是不带头结点的单链表栈顶指针就是链表头指针。链栈结点动态分配理论上只要有内存就不会上溢所以不需要定义 StackFull 运算。链队列为方便处理在队头前附加头结点入队只改尾指针出队只改头指针。当原队列只有一个结点时出队要同时修改头尾指针删完后队列变空。还有一个高频简答题中缀表达式如何转后缀表达式。核心是操作数直接输出运算符入栈时比较优先级右括号弹出栈顶直到左括号。文档在第三章结尾简单提了这个问题考试卷上会配合栈的操作步骤来考。5. 数组、广义表与二叉树公式与性质的记忆工程第四章和第五章内容多、公式多是考卷里计算题和证明题的主阵地。文档里给出的所有地址计算公式和二叉树性质都属于“必须会背且能推导”的硬功夫。5.1 数组地址计算下界为 1 与下界为 0 的区分二维数组按行优先存储的地址公式为 LOC(aᵢⱼ) LOC(a₁₁) [(i-1)×n j-1]×d其中 n 是每行元素个数d 是单个元素所占存储单元。若数组下标从 0 开始公式简化为 i×nj。按列优先时行数和列数互换。三维数组的地址公式在文档里也有LOC(aᵢⱼₖ) LOC(a₁₁₁) [(i-1)×n×p (j-1)×p k-1]×d。做题时先确认下界是 0 还是 1这直接决定是否要减 1。我在这里翻过车——把下界为 1 的三维数组套用了二维公式结果偏差很大后来我每次做题都先圈出题目里的下标范围再写公式。5.2 对称矩阵与三角矩阵压缩一维数组下标映射对称矩阵只需存下三角或上三角矩阵元素 aᵢⱼ 与一维数组下标 k 的映射关系要记牢。下三角按行优先存时k i×(i1)/2 ji≥j。我推荐用“等差数列求和”来理解第 i 行前面共有 i 行每行元素数从 1 递增到 i前 i 行元素总数为 i×(i1)/2再加上当前行的列偏移 j。三角矩阵压缩时重复元素常量 c 存到一维数组最后一个位置其余 n×(n1)/2 个元素按规则顺序存放。这类题计算量不大关键是把 i 和 j 谁大谁小判断准。5.3 稀疏矩阵的三元组表失去随机存取功能稀疏矩阵只存非零元素用三元组 (i, j, aᵢⱼ) 记录行列位置和值这是顺序存储方案十字链表是链式存储方案。要特别注意文档里的结论稀疏矩阵压缩后“失去随机存取功能”——因为无法通过行列号直接算出存储位置必须逐个查找。5.4 二叉树四个性质n₀ n₂ 1 是证明题最爱二叉树性质 1 到性质 4 中性质 3终端结点数 n₀ 度为 2 的结点数 n₂ 1考试频率最高不但会直接考还常用来做推导题。理解方式从叶子数角度出发每增加一个分支结点叶子数不增加但度为 2 的结点数加 1 时叶子数也加 1所以叶子数总比度为 2 的结点数多 1。性质 4 的深度计算公式是 ⌊log₂n⌋ 1 或 ⌈log₂(n1)⌉。文档举例100 个结点的完全二叉树深度为 ⌊log₂100⌋ 1 6 1 7因为 2⁶ 642⁷ 128。5.5 完全二叉树编号双亲与孩子编号的推导编号从 0 开始时结点 i 的双亲编号为 ⌊(i-1)/2⌋左孩子编号为 2i1右孩子编号为 2i2。这里有个需要避开的坑文档中同时给出了编号从 1 开始和从 0 开始的两套规则考试必须看清题目给的是哪套。从 0 开始时左孩子存在条件是 2i1 n从 1 开始则是 2i ≤ n。完全二叉树适合顺序存储因为编号能直接映射到数组下标。但一般二叉树用顺序存储要补虚结点存储密度低所以通常用二叉链表。5.6 二叉链表与前中后序遍历唯一确定二叉树的条件n 个结点的二叉链表共有 2n 个指针域其中 n-1 个指向孩子n1 个为空。线索二叉树利用这些空指针域存放前驱后继指针一个结点是叶结点的充要条件是左右标志均为 1。遍历的核心是递归。前序访问根→左子树→右子树中序左子树→访问根→右子树后序左子树→右子树→访问根。确定二叉树只需“前序 中序”或“后序 中序”前序 后序不能唯一确定。解题方法是先用前序或后序确定根再用中序把左右子树切开递归进行。6. 避坑与考前强化五个高频翻车点 验证方法这份文档我前前后后拆了三遍发现内容本身没有硬伤但考生在应用阶段最容易在几个固定位置翻车。下面把常见问题按“现象 → 原因 → 解决”列出来。6.1 复杂度化简出错把 O(2n) 写成 O(2)现象学生在计算一层循环的时间复杂度时写成 O(2) 或 O(2n)。原因复杂度关注数量级系数和常数项在渐进分析中丢弃。解决算完执行次数后直接看最高阶项去掉系数。O(2n) 化简为 O(n)O(n²n) 化简为 O(n²)。做题时保留系数不化简会被判概念错误。6.2 顺序表删除移动次数与插入记混现象删除第 i 个元素写成 n-i1。原因只背了“插入公式”忽略了插入和删除的移动起点不同。解决用模拟法验证一次。插入时第 i 个位置本身空着从第 i 个到第 n 个都要后移共 n-i1 个删除时第 i 个直接移除后面 n-i 个前移。记住“删除少移一位”。6.3 循环队列判空判满方案混用现象用 Q.rear Q.front 同时判断空和满导致入队错误。原因只记住一个条件没有区分方案的适用前提。解决凡是用“少用一个元素空间”方案判满必须是 (Q.rear1) % QueueSize Q.front判空才是 Q.rear Q.front。如果看到题目有“计数器”或“标志位”再用对应的方案。6.4 数组地址计算忽略下界条件现象题目说数组下标从 0 开始仍套用减 1 的行优先公式。原因教材默认公式下界为 1但试卷常改为下界 0。解决提笔前先用笔圈出“下标从 0 开始”或“从 1 开始”。从 0 开始时行优先公式变为 i×nj不减 1。三元组里行号和列号也要对齐这个规则。6.5 广义表表头表尾理解偏差现象题目问 tail((a,b)) 的结果答成 a。原因把表尾理解成“最后一个元素”而定义是“除表头外其余元素组成的子表”。解决任何非空广义表的表尾一定是子表。所以 tail((a,b)) (b)不是 bhead((a,b)) a是原子。广义表 () 是空表不能求表头和表尾而 (()) 长度为 1表头和表尾都是空表 ()。验证自己是否掌握这份文档我用过最有效的方法是合上文档在白纸上把复杂度递增序列、顺序表插入删除移动次数公式、循环队列判空判满条件、二叉树四个性质和三类遍历顺序各写一遍然后对照原文。写不出来的地方就是漏洞。从那以后我每次考前复习数据结构都强制自己先过一遍这五类考点——我觉得这份文档最值钱的地方就是把散落在教材各章节的计算公式和边界条件汇总到了一起。文档是死的但考试用得上如果你能把上面的公式条件练到闭眼默写那这张卷子对你来说就是一场计算的重复劳动。希望帮到你。本文还有配套的精品资源点击获取 自考数据结构02331重点总结：核心考点与公式全梳理
简介自考02331数据结构重点总结文档是面向自考计算机专业考生的核心考点整理覆盖数据构造的概论与线性表两大板块。文档从逻辑结构、存储结构、数据运算出发梳理了顺序存储、链式存储、索引存储、散列存储四种基本方法并总结了常见时间复杂度等级、算法评价准则以及线性表顺序表与链表的初始化、查找、插入、删除等基础操作重点突出、条理清晰。其中还包含顺序表地址计算、单链表头插法/尾插法建表、结点移动次数等易考易混细节便于读者对照教材加深理解。资源为单个doc文档文件总数为1压缩包大小1.62MB轻量易用适合打印后逐章背诵或与教材搭配复习。目前已有97人学习下载对准备自学考试、需要快速建立数据结构知识框架的读者而言是一份值得收藏的考前冲刺资料。1. 自考数据结构 02331这份重点总结为什么值得当备考主线数据结构是计算机专业的“分水岭”课程自考 02331 更是卡住不少考生的一科。我拆完这份《自考数据结构重点总结最终.doc》后发现它没有废话从第一章概论到第五章树覆盖了考试全部核心考点算法复杂度、线性表、栈、队列、数组、广义表、二叉树每个知识点都给出了结论和公式省去了自己翻教材重新整理的时间。对准备自考、考研 408 或想补数据结构基础的程序员来说这份文档可以直接当复习主线配合教材查缺补漏即可。文档定位是“应试导向的知识点总结”不是入门教程但足够精炼。它有两条主线一是从逻辑结构、存储结构到算法评价指标的理论骨架二是线性表、栈队列、树这几类核心结构的公式与操作细节。接下来我按考试实际出题频率把文档里的重点拆开讲顺带补上文档没明说、但做题时绕不开的坑。2. 算法复杂度与概论先把“时间换空间”的账算明白数据结构第一章常被考生跳过但复杂度分析几乎出现在每套试卷的简答题或选择题里。文档里沃思那句“算法 数据结构 程序”是必考点更要紧的是复杂度数量级排序——这是后面所有算法比较的基础。2.1 五个准则与四种存储方法选择题高频素材算法必须满足输入、输出、有穷性、确定性、可行性五个准则。这里容易混淆的是“算法”与“程序”的差别算法可以用自然语言或类 C 描述不依赖具体编程语言程序必须依赖计算机语言。这个点在判断题里反复出现值得记牢。四种存储方法各对应一种典型场景顺序存储通常借助数组适合随机访问链式存储借助指针适合频繁插入删除索引存储通过关键字查找适合静态查找表散列存储直接由关键字计算地址适合等值查找。选择题常给一个场景问“用哪种最合适”记住“随机访问选顺序、频繁增删选链式”就够用。2.2 时间复杂度递增序列按数量级背下来文档给出了完整的复杂度递增序列常数阶 O(1)、对数阶 O(log₂n)、线性阶 O(n)、线性对数阶 O(nlog₂n)、平方阶 O(n²)、立方阶 O(n³)、k 次方阶 O(nᵏ)、指数阶 O(2ⁿ)、阶乘阶 O(n!)。我备考时把这个序列画在纸上贴墙每天扫一遍。题目给的代码块先看是否有循环嵌套再看循环变量是增还是减半。一层循环且变量增量为 1 是 O(n)两层嵌套是 O(n²)循环变量每次翻倍或减半是对数阶。// 示例对数阶写法 int i 1; while (i n) { i i * 2; // 每次乘2执行次数为 log₂n }执行次数取决于 i 每次乘 2从 1 增长到超过 n 需要 log₂n 次。若把乘法改成加法复杂度就退化成 O(n)。空间复杂度的定义类似它包含算法本身占用空间、输入输出数据占用空间和运行时的临时空间考试通常只问“额外辅助空间”。3. 线性表顺序表与链表的选择本质是时间与空间的博弈第二章是数据结构真正的核心也是后续栈、队列实现的基础。文档里已经明确顺序表是随机存取结构插入删除平均要移动一半结点链表靠修改指针完成插入删除不用移动数据。这一章的考点集中在“移动次数计算”和“链表指针操作”两块。3.1 顺序表插入与删除移动次数必须手算过关顺序表中第 i 个位置插入结点的移动次数是 n-i1删除第 i 个结点的移动次数是 n-i。很多同学把这两个公式记反我提供一个记忆方法插入多了一个空位所以要多挪一个元素删除直接补位少挪一个。平均移动次数插入是 n/2删除是 (n-1)/2平均时间复杂度都是 O(n)。// 顺序表插入操作C语言 void InsertList(SeqList *L, int i, DataType x) { // L为顺序表指针i为插入位置x为待插入元素 int j; if (L-length MaxSize) { printf(表已满无法插入\n); return; } if (i 1 || i L-length 1) { printf(插入位置不合法\n); return; } for (j L-length - 1; j i - 1; j--) { L-data[j 1] L-data[j]; // 从尾部开始逐个后移 } L-data[i - 1] x; // 腾出的位置放入新元素 L-length; }循环从最后一个元素开始向后移动避免数据覆盖。位置从 1 计数对应数组下标 i-1。判断表满条件、位置合法条件和插入后长度自增这三处缺一不可。3.2 头插法与尾插法建表顺序的差异头插法每次把新结点插到头结点之后最终链表元素顺序与输入顺序相反尾插法用尾指针记录当前末尾顺序与输入一致。考试常给出输入序列问建表结果头插法的逆序特征是高频陷阱。// 尾插法建带头结点的单链表C语言 void CreateListR(LinkList *head, char input[]) { ListNode *r, *s; int i 0; head (ListNode *)malloc(sizeof(ListNode)); r head; // 尾指针初值指向头结点 while (input[i] ! \0) { s (ListNode *)malloc(sizeof(ListNode)); s-data input[i]; // 生成新结点并给数据域赋值 r-next s; // 新结点链到原表尾之后 r s; // 尾指针指向新的表尾 i; } r-next NULL; // 终端结点指针域置空 }尾指针 r 始终指向链表的最后一个结点每次新结点都链到 r 后面然后 r 前移。三个建表算法的时间复杂度均为 O(n)。如果去掉头结点第一个位置插入和删除就得单独处理这是头结点存在的最大意义——统一空表与非空表的操作。3.3 双向链表与单循环链表指针修改顺序的先后逻辑双向链表插入涉及四个指针修改顺序不能乱。文档里的前插操作顺序是先给新结点 s 的 prior 指向 p 的前驱、next 指向 p再让 p 前驱的 next 指向 s最后让 p 的 prior 指向 s。我先改 s 自身的两个指针再改链上原有指针顺序反了会丢失链信息。单循环链表判断空的条件是 head head-next指向头结点自身。如果用尾指针 rear 表示单循环链表连到 a₁ 和 an的时间都是 O(1)在做首尾插入删除时效率很高这也是“约瑟夫环”类题目优先选尾指针循环链表的原因。4. 栈与队列受限线性表的两张规则牌栈是 LIFO队列是 FIFO本质都是“受限的线性表”。自考第三章的高频考点集中在循环队列的判空判满以及后缀表达式转换。文档里对“上溢”和“下溢”的区分是基础题常客上溢是栈满再做入栈为错误状态下溢是栈空再做退栈常被用作控制转移条件。4.1 栈的顺序存储栈顶指针指向栈顶元素顺序栈用数组模拟栈顶指针 top 指向栈顶元素。入栈时先把 top 加 1再存入元素出栈时先取元素再把 top 减 1。空栈时 top 为 -1这是文档里特别标注的空栈时栈顶指针不能是 0。两个栈共享空间时栈底设在两端top1 和 top2 相向增长栈满条件为 top1 top2 - 1。4.2 循环队列的判空判满三种方案的边界条件顺序队列有“假溢出”问题——front 前移释放的空间不能再利用。循环队列通过模运算把数组首尾相连入队、出队都按 (i1) % QueueSize 推进。但这也带来一个新问题队空和队满时 front 都等于 rear必须另加判断。文档给出三种解法考试常考的是第三种“少用一个元素空间”队满条件为 (Q-rear 1) % QueueSize Q-front队空条件为 Q-rear Q-front。此时 rear 所指单元始终为空队列实际最多存 QueueSize-1 个元素。// 循环队列基本操作C语言 #define QueueSize 100 typedef struct { DataType data[QueueSize]; int front, rear; } CirQueue; // 入队 int EnQueue(CirQueue *Q, DataType x) { if ((Q-rear 1) % QueueSize Q-front) { return 0; // 队列满返回0表示失败 } Q-data[Q-rear] x; Q-rear (Q-rear 1) % QueueSize; // 循环意义下尾指针加1 return 1; } // 出队 DataType DeQueue(CirQueue *Q) { DataType temp; if (Q-rear Q-front) { return NULL; // 队列空 } temp Q-data[Q-front]; Q-front (Q-front 1) % QueueSize; // 循环意义下头指针加1 return temp; }队满判断里用取模运算把 rear 推进到数组末端时折回开头这样数组空间可以反复使用。记住一个口诀入队先判满、出队先判空、指针移动都要取模。4.3 链栈与链队列无需判满的内存动态分配链栈本质是不带头结点的单链表栈顶指针就是链表头指针。链栈结点动态分配理论上只要有内存就不会上溢所以不需要定义 StackFull 运算。链队列为方便处理在队头前附加头结点入队只改尾指针出队只改头指针。当原队列只有一个结点时出队要同时修改头尾指针删完后队列变空。还有一个高频简答题中缀表达式如何转后缀表达式。核心是操作数直接输出运算符入栈时比较优先级右括号弹出栈顶直到左括号。文档在第三章结尾简单提了这个问题考试卷上会配合栈的操作步骤来考。5. 数组、广义表与二叉树公式与性质的记忆工程第四章和第五章内容多、公式多是考卷里计算题和证明题的主阵地。文档里给出的所有地址计算公式和二叉树性质都属于“必须会背且能推导”的硬功夫。5.1 数组地址计算下界为 1 与下界为 0 的区分二维数组按行优先存储的地址公式为 LOC(aᵢⱼ) LOC(a₁₁) [(i-1)×n j-1]×d其中 n 是每行元素个数d 是单个元素所占存储单元。若数组下标从 0 开始公式简化为 i×nj。按列优先时行数和列数互换。三维数组的地址公式在文档里也有LOC(aᵢⱼₖ) LOC(a₁₁₁) [(i-1)×n×p (j-1)×p k-1]×d。做题时先确认下界是 0 还是 1这直接决定是否要减 1。我在这里翻过车——把下界为 1 的三维数组套用了二维公式结果偏差很大后来我每次做题都先圈出题目里的下标范围再写公式。5.2 对称矩阵与三角矩阵压缩一维数组下标映射对称矩阵只需存下三角或上三角矩阵元素 aᵢⱼ 与一维数组下标 k 的映射关系要记牢。下三角按行优先存时k i×(i1)/2 ji≥j。我推荐用“等差数列求和”来理解第 i 行前面共有 i 行每行元素数从 1 递增到 i前 i 行元素总数为 i×(i1)/2再加上当前行的列偏移 j。三角矩阵压缩时重复元素常量 c 存到一维数组最后一个位置其余 n×(n1)/2 个元素按规则顺序存放。这类题计算量不大关键是把 i 和 j 谁大谁小判断准。5.3 稀疏矩阵的三元组表失去随机存取功能稀疏矩阵只存非零元素用三元组 (i, j, aᵢⱼ) 记录行列位置和值这是顺序存储方案十字链表是链式存储方案。要特别注意文档里的结论稀疏矩阵压缩后“失去随机存取功能”——因为无法通过行列号直接算出存储位置必须逐个查找。5.4 二叉树四个性质n₀ n₂ 1 是证明题最爱二叉树性质 1 到性质 4 中性质 3终端结点数 n₀ 度为 2 的结点数 n₂ 1考试频率最高不但会直接考还常用来做推导题。理解方式从叶子数角度出发每增加一个分支结点叶子数不增加但度为 2 的结点数加 1 时叶子数也加 1所以叶子数总比度为 2 的结点数多 1。性质 4 的深度计算公式是 ⌊log₂n⌋ 1 或 ⌈log₂(n1)⌉。文档举例100 个结点的完全二叉树深度为 ⌊log₂100⌋ 1 6 1 7因为 2⁶ 642⁷ 128。5.5 完全二叉树编号双亲与孩子编号的推导编号从 0 开始时结点 i 的双亲编号为 ⌊(i-1)/2⌋左孩子编号为 2i1右孩子编号为 2i2。这里有个需要避开的坑文档中同时给出了编号从 1 开始和从 0 开始的两套规则考试必须看清题目给的是哪套。从 0 开始时左孩子存在条件是 2i1 n从 1 开始则是 2i ≤ n。完全二叉树适合顺序存储因为编号能直接映射到数组下标。但一般二叉树用顺序存储要补虚结点存储密度低所以通常用二叉链表。5.6 二叉链表与前中后序遍历唯一确定二叉树的条件n 个结点的二叉链表共有 2n 个指针域其中 n-1 个指向孩子n1 个为空。线索二叉树利用这些空指针域存放前驱后继指针一个结点是叶结点的充要条件是左右标志均为 1。遍历的核心是递归。前序访问根→左子树→右子树中序左子树→访问根→右子树后序左子树→右子树→访问根。确定二叉树只需“前序 中序”或“后序 中序”前序 后序不能唯一确定。解题方法是先用前序或后序确定根再用中序把左右子树切开递归进行。6. 避坑与考前强化五个高频翻车点 验证方法这份文档我前前后后拆了三遍发现内容本身没有硬伤但考生在应用阶段最容易在几个固定位置翻车。下面把常见问题按“现象 → 原因 → 解决”列出来。6.1 复杂度化简出错把 O(2n) 写成 O(2)现象学生在计算一层循环的时间复杂度时写成 O(2) 或 O(2n)。原因复杂度关注数量级系数和常数项在渐进分析中丢弃。解决算完执行次数后直接看最高阶项去掉系数。O(2n) 化简为 O(n)O(n²n) 化简为 O(n²)。做题时保留系数不化简会被判概念错误。6.2 顺序表删除移动次数与插入记混现象删除第 i 个元素写成 n-i1。原因只背了“插入公式”忽略了插入和删除的移动起点不同。解决用模拟法验证一次。插入时第 i 个位置本身空着从第 i 个到第 n 个都要后移共 n-i1 个删除时第 i 个直接移除后面 n-i 个前移。记住“删除少移一位”。6.3 循环队列判空判满方案混用现象用 Q.rear Q.front 同时判断空和满导致入队错误。原因只记住一个条件没有区分方案的适用前提。解决凡是用“少用一个元素空间”方案判满必须是 (Q.rear1) % QueueSize Q.front判空才是 Q.rear Q.front。如果看到题目有“计数器”或“标志位”再用对应的方案。6.4 数组地址计算忽略下界条件现象题目说数组下标从 0 开始仍套用减 1 的行优先公式。原因教材默认公式下界为 1但试卷常改为下界 0。解决提笔前先用笔圈出“下标从 0 开始”或“从 1 开始”。从 0 开始时行优先公式变为 i×nj不减 1。三元组里行号和列号也要对齐这个规则。6.5 广义表表头表尾理解偏差现象题目问 tail((a,b)) 的结果答成 a。原因把表尾理解成“最后一个元素”而定义是“除表头外其余元素组成的子表”。解决任何非空广义表的表尾一定是子表。所以 tail((a,b)) (b)不是 bhead((a,b)) a是原子。广义表 () 是空表不能求表头和表尾而 (()) 长度为 1表头和表尾都是空表 ()。验证自己是否掌握这份文档我用过最有效的方法是合上文档在白纸上把复杂度递增序列、顺序表插入删除移动次数公式、循环队列判空判满条件、二叉树四个性质和三类遍历顺序各写一遍然后对照原文。写不出来的地方就是漏洞。从那以后我每次考前复习数据结构都强制自己先过一遍这五类考点——我觉得这份文档最值钱的地方就是把散落在教材各章节的计算公式和边界条件汇总到了一起。文档是死的但考试用得上如果你能把上面的公式条件练到闭眼默写那这张卷子对你来说就是一场计算的重复劳动。希望帮到你。本文还有配套的精品资源点击获取