简介这份文档面向备考软考中级软件设计师的考生尤其适合需要系统梳理考点、突破难点公式与易错点的复习阶段使用。内容围绕数据结构与算法主线展开涵盖邻接矩阵在无向图、有向图中的度与出入度计算顺序、链式、散列、索引四种存储结构的适用场景二叉排序树、哈夫曼树与平衡二叉树的构造及带权路径长度计算以及二分查找、分块查找的实现要点与平均查找长度分析排序部分逐一对比直接插入、简单选择、冒泡、希尔、快速、堆、归并、基数排序的适用条件并附时间复杂度、辅助空间与稳定性对照表。资源包共1个docx文件约3.37MB以文字笔记与例题解析为主便于打印或平板批注。目前已有382人学习适合作为冲刺阶段查漏补缺的随身考点手册。1. 软件设计师考点笔记到底是一份什么资料从“邻接矩阵求度”说起如果你翻过软件设计师中级的真题大概见过这种题给一个无向图的邻接矩阵问某个顶点的度是多少。很多人第一反应是画图画完还数错。其实有个特别朴素的规律——无向图邻接矩阵第 i 行元素之和就是顶点 i 的度有向图第 i 行之和是出度第 j 列之和是入度。就这么一句话能省掉考场上的大量草稿纸。这份《软件设计师中级——考点笔记精华版》干的就是这件事把软考中级里那些“看起来要背很多、其实有规律可循”的知识点压缩成能直接用的结论和公式。它覆盖数据结构、查找排序、树与图、表达式记法、符号数编码、指令寻址这几大块属于典型的“考前冲刺型”资料而不是从零讲起的教材。搞懂它是什么、适合谁、和教材有什么区别比急着背结论更重要。2. 为什么这些考点值得单独整理软考中级的“规律型知识”占了多大比重软考中级的知识点有个特点概念多、公式多但真正需要“理解到能推导”的并不多大部分是“知道规律就能秒答”。这类知识如果按教材顺序一页页读效率很低但如果有人把规律抽出来、配上例题复习速度会快很多。这份笔记的价值就在这个“抽规律”的动作上。2.1 存储结构的选择题顺序、链式、散列、索引各自管什么存储结构这块考试最爱考的是“什么场景选什么结构”。顺序存储用一组地址连续的单元依次存放元素好处是支持随机访问查第几个元素一步到位所以频繁查询时用它缺点是插入删除要挪一大片。链式存储用任意存储单元存放元素单元可以连续也可以不连续靠指针串起来插入删除只改指针所以频繁增删改时用它代价是不能随机访问找第 n 个得从头走。散列存储是把元素的存储位置和关键码之间建立确定对应关系通俗说就是键值对——给一个 key通过散列函数直接算出位置查找接近 O(1)。索引存储则是另建一张索引表索引是单独的物理结构记录某列或若干列的值以及指向真实数据页的指针清单数据库里用得最多。打个比方顺序存储像电影院的连座找第 5 排第 3 座直接走过去链式存储像散落在各处的寄存柜每个柜子贴一张纸条告诉你下一个柜子在哪散列存储像快递柜报取件码直接开对应格子索引存储像图书馆的目录卡片先查卡片再按编号找书架。四种结构没有绝对优劣只有“当前操作以查为主还是以改为准”的区别。2.2 链表家族单链表、循环链表、双链表的分工单链表每个节点一个指针域只能单向走循环链表把尾节点的指针指回头节点形成一个环适合需要循环遍历的场景双链表每个节点两个指针域前后都能走。因为双链表多一个指针域灵活度优于单链表但空间开支也更大——这就是典型的“用空间换操作便利”。考试里常考的比较点就三个能不能反向遍历、插入删除时要不要找前驱、空间开销谁大。单链表删除一个节点必须知道它的前驱双链表不用因为节点自己存了前驱指针。记住这个差异选择题基本不会翻车。2.3 树结构的三条主线二叉排序树、哈夫曼树、平衡二叉树二叉排序树的定义有三条左子树非空则左子树所有节点值小于根右子树非空则右子树所有节点值大于等于根左右子树本身也分别是二叉排序树。它最实用的性质是中序遍历能得到一个递增序列。还有一个容易忽略的结论——关键字最大的节点可以有左子树但一定没有右子树因为再往右就违反定义了。哈夫曼树又叫最优二叉树定义是带权路径长度 WPL 最短的树构造特点是权值越大的叶子越靠近根。它的经典应用是变长编码频率高的字符用短码频率低的用长码整体编码长度最短。笔记里给了一道“face”编码的例题思路是先按频率构造哈夫曼树再左 0 右 1 赋值从根走到叶子经过的 0/1 序列就是编码。这里有个细节哈夫曼树的左节点未必要比右节点小但做题时通常写成左小右大方便统一。平衡二叉树AVL 树的性质是它是一棵空树或者左右两棵子树高度差的绝对值不超过 1并且左右子树也都是平衡二叉树。注意 AVL 树和 AVL 算法是两回事名字像但不是同一个东西。满二叉树则是除最后一层外每一层节点都有两个子节点或者说每个节点要么有两个子节点、要么没有子节点。2.4 查找方法二分查找和分块查找的适用边界二分查找折半查找的适用情况是“不经常变动而查找频繁的有序列表”。优点是比较次数少、查找速度快、平均性能好缺点有两个要求待查表有序插入删除困难。算法过程很直白假设升序排列取中间位置关键字和目标比较相等则成功中间值大于目标就查前半段小于就查后半段重复到找到或子表为空。分块查找适合节点动态变化的情况。做法是把大线性表分成若干块块内节点可以任意存放但块与块之间必须有序——第 i 块所有节点的关键码都要小于第 i1 块的所有关键码。再建一个索引表把每块最大关键码按块顺序存进辅助数组。查找时先在索引表里定位块索引表有序可以顺序查也可以折半查再在块内顺序查。它的速度比纯顺序查找快得多但不如折半查找。提示二分查找的“有序”是硬门槛数据经常增删的场景硬上二分维护有序的成本可能比查找省下的还高。3. 排序算法怎么记才不混一张表背后的判断逻辑排序是这份笔记里信息密度最高的部分八种排序方法、三列时间复杂度、一列辅助空间、一列稳定性死记很容易串行。真正要抓的是“为什么这个算法是这个复杂度”理解了原因表自然就记住了。3.1 八种排序的一句话本质直接插入排序每一趟把一个待排序记录按关键字大小插到已排好序的队列合适位置像斗地主摸牌后往手里插。简单选择排序每趟从待排序记录里挑出关键字最小的放到已排序序列末尾。冒泡排序两两比较相邻关键字不满足次序就交换直到整表有序。希尔排序按步长 gap 分组每组做直接插入排序gap 逐渐缩小到 1 时整体有序。快速排序一趟把数据分成两部分分割点左边都比它小、右边都比它大再对两部分递归用的是分治策略。堆排序利用堆的定义——n 个元素的序列满足 ki≤k2i 且 ki≤k2i1小顶堆或 ki≥k2i 且 ki≥k2i1大顶堆。归并排序把序列看成 n 个长度 1 的有序表相邻两两归并成 n/2 个长度 2 的表反复归并直到长度为 n。基数排序不比较关键字大小按各位的值做若干趟“分配”和“收集”比如按个位分到 0~9 十个桶再依次取出。3.2 复杂度与稳定性哪些结论必须背哪些可以推必须背的结论集中在三处。第一平均 O(n log n) 的有四个快速排序、堆排序、归并排序加上希尔排序的 O(n^1.3) 属于单独一档。第二最坏情况会退化的只有快速排序最坏 O(n²)原因是每次分割点都取到极值堆排序和归并排序最坏也稳定在 O(n log n)。第三稳定的有四个直接插入、冒泡、归并、基数不稳定的是简单选择、希尔、快速、堆。辅助空间也好推插入、选择、冒泡、堆都是原地交换O(1)快速排序递归需要栈空间平均 O(log n)归并需要额外数组O(n)基数排序需要桶O(rd)。排序方法最好平均最坏辅助空间稳定性直接插入O(n)O(n²)O(n²)O(1)稳定简单选择O(n²)O(n²)O(n²)O(1)不稳定冒泡O(n)O(n²)O(n²)O(1)稳定希尔不存在O(n^1.3)不存在O(1)不稳定快速O(n log n)O(n log n)O(n²)O(log n)不稳定堆O(n log n)O(n log n)O(n log n)O(1)不稳定归并O(n log n)O(n log n)O(n log n)O(n)稳定基数O(d(nrd))O(d(nrd))O(d(nrd))O(rd)稳定希尔排序那两格写“不存在”是因为它的最好和最坏情况依赖增量序列的选取没有统一结论考试遇到就按“不存在”处理别自己脑补。3.3 堆的判断题为什么答案往往不是看起来最整齐的那个笔记里给了一道堆判断题四个选项里选 B。判断方法不是看数字大小排列而是把序列按完全二叉树的下标关系摆开第 i 个元素的左右孩子是 2i 和 2i1然后逐对检查父节点是否都小于等于或都大于等于孩子。选项 B 是 (10,18,15,20,50,80,30,60)摆成树后每个父节点都不大于孩子符合小顶堆。其他选项总有一对父子关系反着来。这类题的血泪经验是别用眼睛扫一定按 2i、2i1 的下标关系逐层核对扫一眼很容易被“大致递增”的错觉骗过去。3.4 归并路数与趟数的换算归并路数公式是 k ⌈log_k m⌉ 的反向使用笔记里写成“归并路数 |log_k m|其中 m 为元素个数k 为多路归并趟数”。例题是 27 个元素只做三趟多路归并问归并路数。代入就是 log 以 3 为底、27 为真数等于 3选 B。这个公式的直觉是每趟归并把有序段数量缩小 k 倍从 m 段缩到 1 段需要 log_k m 趟。4. 表达式与编码前缀、后缀、原码补码这些“规则题”怎么一次记牢这部分是软考里典型的“规则明确、但容易在细节上翻车”的题型。规则本身不难难的是符号位、扫描方向、栈顶和次顶的顺序这些细节错一步结果就全错。4.1 三种表达式记法扫描方向和出栈顺序是唯一考点中缀表达式就是我们平时写的 ab-c。前缀表达式波兰式从右至左扫描遇到数字压栈遇到运算符弹出栈顶两个数用“栈顶元素 op 次顶元素”计算结果入栈重复到最左端。后缀表达式逆波兰式从左至右扫描遇到数字压栈遇到运算符弹出栈顶两个数用“次顶元素 op 栈顶元素”计算结果入栈重复到最右端。两个方向、两种操作数顺序正好相反这是最容易混的点。笔记里的例子前缀“- × 3 4 5 6”从右往左压入 6、5、4、3遇到 弹出 3 和 4 算 347后缀“3 4 5 × 6 -”从左往右压入 3、4遇到 弹出 4 和 3 算 347。两边结果都是 29但中间的操作数顺序必须严格按规则来。用一段伪代码把后缀求值的逻辑固定下来考场上在草稿纸上按这个流程走就不会乱def eval_rpn(tokens): stack [] for t in tokens: # 从左到右扫描 if t not in -*/: stack.append(int(t)) # 数字直接入栈 else: b stack.pop() # 先弹出的是栈顶作为右操作数 a stack.pop() # 后弹出的是次顶作为左操作数 if t : stack.append(a b) elif t -: stack.append(a - b) elif t *: stack.append(a * b) else: stack.append(a // b) return stack[0] # 最后剩下的就是结果关键注释在两行 pop 上后缀表达式里先弹出的是右操作数前缀表达式反过来。参数 tokens 是按空格切分后的记号列表运算符只处理四则运算除法按题目要求取整。4.2 原码、反码、补码、移码符号位动不动是关键正数的原码、反码、补码都等于自身二进制数。负数的原码是符号位为 1、后面跟自身二进制反码是符号位不动、其余各位取反补码是反码加 1移码增码不论正负把补码的符号位取反即可。应用场景要记牢计算机里最适合做数字加减运算的是补码因为补码把减法统一成加法符号位直接参与运算最适合表示浮点数阶码的是移码因为移码保持了大小顺序方便比较。机器字长为 n 时各码制的表示范围有个记忆技巧设 A2^(n-1)B1-2^(-(n-1))则原码和反码的定点整数范围是 [-(A-1), A-1]定点小数是 [-B, B]补码和移码的定点整数范围是 [-A, A-1]定点小数是 [-1, B]。补码比原码多表示一个负数这是它范围不对称的原因。4.3 指令寻址方式操作数到底在哪立即寻址操作数直接包含在指令中取操作数最快因为不用再访存。直接寻址操作数的地址写在指令里。寄存器寻址操作数就在寄存器中。寄存器间接寻址操作数的地址在寄存器中还要再按这个地址访存一次。四种方式的区别就是“操作数或它的地址到底藏在指令、内存还是寄存器里”按这个层次记比背定义快。5. 常见误区这几组概念最容易在考场上搞混5.1 邻接矩阵的行和列无向图与有向图的度算反了易混点是无向图和有向图的度计算。为什么混两者都用邻接矩阵但无向图第 i 行之和是度有向图第 i 行之和是出度、第 j 列之和才是入度。怎么区分先看题目说的是无向还是有向无向图矩阵对称行和列一样有向图不对称行管出、列管入笔记里顶点 3 的出度 5、入度 16 就是按行和列分别算的。5.2 平衡二叉树与 AVL 算法名字像但不是一回事易混点是 AVL 树和 AVL 算法。为什么混都叫 AVL。怎么区分平衡二叉树AVL 树是一种数据结构性质是左右子树高度差绝对值不超过 1AVL 算法是另一回事考试里问树的性质就按高度差判断别往算法上联想。5.3 哈夫曼树的左右大小规则不是硬性的易混点是哈夫曼树左节点是否必须比右节点小。为什么混教材例题大多画成左小右大。怎么区分定义上并没有这个要求左小右大只是做题时的习惯写法方便统一左 0 右 1 赋值。考试如果给了固定树形按给定树形走别自己重排。5.4 希尔排序的复杂度最好最坏为什么写“不存在”易混点是以为希尔排序也有固定的最好最坏复杂度。为什么混其他七种都有明确三列。怎么区分希尔排序的性能依赖增量序列的选择不同序列结果不同所以笔记里最好和最坏两格写“不存在”平均按 O(n^1.3) 记。5.5 前缀和后缀的操作数顺序栈顶和次顶正好相反易混点是两种表达式弹出操作数后的计算顺序。为什么混都是弹两个数做运算。怎么区分后缀是“次顶 op 栈顶”前缀是“栈顶 op 次顶”配合扫描方向一起记——后缀从左往右、前缀从右往左方向反了顺序也反。6. 什么时候用这份笔记、什么时候别用一个复习节奏上的判断这份笔记最适合的场景很明确你已经过了一遍教材或网课知识点有印象但不成体系需要一份东西把公式、结论、易错点串起来在考前两到四周做集中回顾。它的写法是结论优先、例题佐证拿来对着真题查漏补缺效率很高——比如做完一套卷子错在堆的判断就翻到堆那一节把 2i、2i1 的核对方法再走一遍错在补码范围就把 A 和 B 的记忆技巧默写一次。不适合的场景同样明确。如果你完全没接触过数据结构和计算机组成直接啃这份笔记会很难受因为它是“压缩包”解压需要前置知识。另一个不适合的场景是把它当唯一复习材料笔记覆盖的是高频考点和规律但软考中级还有软件工程、数据库设计、面向对象这些板块光靠这一份不够。场景适合用不适合用考前 2~4 周集中回顾是—做完真题后定位薄弱点是—零基础第一次学数据结构—是先看教材当唯一复习资料—是需配合其他板块资料背复杂度表和稳定性结论是—有个习惯值得养成每次做错一道规则题不要只记正确答案而是把“我混在哪一步”写下来——是扫描方向记反了还是行和列搞混了还是把“不存在”当成了某个具体值。这些混淆点积累到五六个你会发现错的其实是同一类思维惯性。我自己复习这类规则题时踩过的坑是总觉得自己“看懂了”一合上笔记就说不清前缀和后缀的操作数顺序。后来强制自己每道错题都手写一遍栈的弹出过程写满三遍之后才真正稳住。从那以后我每次遇到“看起来会了”的规则题都强制走一遍手推流程不再靠眼睛扫。希望这份笔记的整理思路能帮你在复习时少走几段弯路。本文还有配套的精品资源点击获取 
长河君 · 2026/10/28 7:20:47 · 阅读 1.2k 软件设计师考点笔记：数据结构与算法核心规律速记
简介这份文档面向备考软考中级软件设计师的考生尤其适合需要系统梳理考点、突破难点公式与易错点的复习阶段使用。内容围绕数据结构与算法主线展开涵盖邻接矩阵在无向图、有向图中的度与出入度计算顺序、链式、散列、索引四种存储结构的适用场景二叉排序树、哈夫曼树与平衡二叉树的构造及带权路径长度计算以及二分查找、分块查找的实现要点与平均查找长度分析排序部分逐一对比直接插入、简单选择、冒泡、希尔、快速、堆、归并、基数排序的适用条件并附时间复杂度、辅助空间与稳定性对照表。资源包共1个docx文件约3.37MB以文字笔记与例题解析为主便于打印或平板批注。目前已有382人学习适合作为冲刺阶段查漏补缺的随身考点手册。1. 软件设计师考点笔记到底是一份什么资料从“邻接矩阵求度”说起如果你翻过软件设计师中级的真题大概见过这种题给一个无向图的邻接矩阵问某个顶点的度是多少。很多人第一反应是画图画完还数错。其实有个特别朴素的规律——无向图邻接矩阵第 i 行元素之和就是顶点 i 的度有向图第 i 行之和是出度第 j 列之和是入度。就这么一句话能省掉考场上的大量草稿纸。这份《软件设计师中级——考点笔记精华版》干的就是这件事把软考中级里那些“看起来要背很多、其实有规律可循”的知识点压缩成能直接用的结论和公式。它覆盖数据结构、查找排序、树与图、表达式记法、符号数编码、指令寻址这几大块属于典型的“考前冲刺型”资料而不是从零讲起的教材。搞懂它是什么、适合谁、和教材有什么区别比急着背结论更重要。2. 为什么这些考点值得单独整理软考中级的“规律型知识”占了多大比重软考中级的知识点有个特点概念多、公式多但真正需要“理解到能推导”的并不多大部分是“知道规律就能秒答”。这类知识如果按教材顺序一页页读效率很低但如果有人把规律抽出来、配上例题复习速度会快很多。这份笔记的价值就在这个“抽规律”的动作上。2.1 存储结构的选择题顺序、链式、散列、索引各自管什么存储结构这块考试最爱考的是“什么场景选什么结构”。顺序存储用一组地址连续的单元依次存放元素好处是支持随机访问查第几个元素一步到位所以频繁查询时用它缺点是插入删除要挪一大片。链式存储用任意存储单元存放元素单元可以连续也可以不连续靠指针串起来插入删除只改指针所以频繁增删改时用它代价是不能随机访问找第 n 个得从头走。散列存储是把元素的存储位置和关键码之间建立确定对应关系通俗说就是键值对——给一个 key通过散列函数直接算出位置查找接近 O(1)。索引存储则是另建一张索引表索引是单独的物理结构记录某列或若干列的值以及指向真实数据页的指针清单数据库里用得最多。打个比方顺序存储像电影院的连座找第 5 排第 3 座直接走过去链式存储像散落在各处的寄存柜每个柜子贴一张纸条告诉你下一个柜子在哪散列存储像快递柜报取件码直接开对应格子索引存储像图书馆的目录卡片先查卡片再按编号找书架。四种结构没有绝对优劣只有“当前操作以查为主还是以改为准”的区别。2.2 链表家族单链表、循环链表、双链表的分工单链表每个节点一个指针域只能单向走循环链表把尾节点的指针指回头节点形成一个环适合需要循环遍历的场景双链表每个节点两个指针域前后都能走。因为双链表多一个指针域灵活度优于单链表但空间开支也更大——这就是典型的“用空间换操作便利”。考试里常考的比较点就三个能不能反向遍历、插入删除时要不要找前驱、空间开销谁大。单链表删除一个节点必须知道它的前驱双链表不用因为节点自己存了前驱指针。记住这个差异选择题基本不会翻车。2.3 树结构的三条主线二叉排序树、哈夫曼树、平衡二叉树二叉排序树的定义有三条左子树非空则左子树所有节点值小于根右子树非空则右子树所有节点值大于等于根左右子树本身也分别是二叉排序树。它最实用的性质是中序遍历能得到一个递增序列。还有一个容易忽略的结论——关键字最大的节点可以有左子树但一定没有右子树因为再往右就违反定义了。哈夫曼树又叫最优二叉树定义是带权路径长度 WPL 最短的树构造特点是权值越大的叶子越靠近根。它的经典应用是变长编码频率高的字符用短码频率低的用长码整体编码长度最短。笔记里给了一道“face”编码的例题思路是先按频率构造哈夫曼树再左 0 右 1 赋值从根走到叶子经过的 0/1 序列就是编码。这里有个细节哈夫曼树的左节点未必要比右节点小但做题时通常写成左小右大方便统一。平衡二叉树AVL 树的性质是它是一棵空树或者左右两棵子树高度差的绝对值不超过 1并且左右子树也都是平衡二叉树。注意 AVL 树和 AVL 算法是两回事名字像但不是同一个东西。满二叉树则是除最后一层外每一层节点都有两个子节点或者说每个节点要么有两个子节点、要么没有子节点。2.4 查找方法二分查找和分块查找的适用边界二分查找折半查找的适用情况是“不经常变动而查找频繁的有序列表”。优点是比较次数少、查找速度快、平均性能好缺点有两个要求待查表有序插入删除困难。算法过程很直白假设升序排列取中间位置关键字和目标比较相等则成功中间值大于目标就查前半段小于就查后半段重复到找到或子表为空。分块查找适合节点动态变化的情况。做法是把大线性表分成若干块块内节点可以任意存放但块与块之间必须有序——第 i 块所有节点的关键码都要小于第 i1 块的所有关键码。再建一个索引表把每块最大关键码按块顺序存进辅助数组。查找时先在索引表里定位块索引表有序可以顺序查也可以折半查再在块内顺序查。它的速度比纯顺序查找快得多但不如折半查找。提示二分查找的“有序”是硬门槛数据经常增删的场景硬上二分维护有序的成本可能比查找省下的还高。3. 排序算法怎么记才不混一张表背后的判断逻辑排序是这份笔记里信息密度最高的部分八种排序方法、三列时间复杂度、一列辅助空间、一列稳定性死记很容易串行。真正要抓的是“为什么这个算法是这个复杂度”理解了原因表自然就记住了。3.1 八种排序的一句话本质直接插入排序每一趟把一个待排序记录按关键字大小插到已排好序的队列合适位置像斗地主摸牌后往手里插。简单选择排序每趟从待排序记录里挑出关键字最小的放到已排序序列末尾。冒泡排序两两比较相邻关键字不满足次序就交换直到整表有序。希尔排序按步长 gap 分组每组做直接插入排序gap 逐渐缩小到 1 时整体有序。快速排序一趟把数据分成两部分分割点左边都比它小、右边都比它大再对两部分递归用的是分治策略。堆排序利用堆的定义——n 个元素的序列满足 ki≤k2i 且 ki≤k2i1小顶堆或 ki≥k2i 且 ki≥k2i1大顶堆。归并排序把序列看成 n 个长度 1 的有序表相邻两两归并成 n/2 个长度 2 的表反复归并直到长度为 n。基数排序不比较关键字大小按各位的值做若干趟“分配”和“收集”比如按个位分到 0~9 十个桶再依次取出。3.2 复杂度与稳定性哪些结论必须背哪些可以推必须背的结论集中在三处。第一平均 O(n log n) 的有四个快速排序、堆排序、归并排序加上希尔排序的 O(n^1.3) 属于单独一档。第二最坏情况会退化的只有快速排序最坏 O(n²)原因是每次分割点都取到极值堆排序和归并排序最坏也稳定在 O(n log n)。第三稳定的有四个直接插入、冒泡、归并、基数不稳定的是简单选择、希尔、快速、堆。辅助空间也好推插入、选择、冒泡、堆都是原地交换O(1)快速排序递归需要栈空间平均 O(log n)归并需要额外数组O(n)基数排序需要桶O(rd)。排序方法最好平均最坏辅助空间稳定性直接插入O(n)O(n²)O(n²)O(1)稳定简单选择O(n²)O(n²)O(n²)O(1)不稳定冒泡O(n)O(n²)O(n²)O(1)稳定希尔不存在O(n^1.3)不存在O(1)不稳定快速O(n log n)O(n log n)O(n²)O(log n)不稳定堆O(n log n)O(n log n)O(n log n)O(1)不稳定归并O(n log n)O(n log n)O(n log n)O(n)稳定基数O(d(nrd))O(d(nrd))O(d(nrd))O(rd)稳定希尔排序那两格写“不存在”是因为它的最好和最坏情况依赖增量序列的选取没有统一结论考试遇到就按“不存在”处理别自己脑补。3.3 堆的判断题为什么答案往往不是看起来最整齐的那个笔记里给了一道堆判断题四个选项里选 B。判断方法不是看数字大小排列而是把序列按完全二叉树的下标关系摆开第 i 个元素的左右孩子是 2i 和 2i1然后逐对检查父节点是否都小于等于或都大于等于孩子。选项 B 是 (10,18,15,20,50,80,30,60)摆成树后每个父节点都不大于孩子符合小顶堆。其他选项总有一对父子关系反着来。这类题的血泪经验是别用眼睛扫一定按 2i、2i1 的下标关系逐层核对扫一眼很容易被“大致递增”的错觉骗过去。3.4 归并路数与趟数的换算归并路数公式是 k ⌈log_k m⌉ 的反向使用笔记里写成“归并路数 |log_k m|其中 m 为元素个数k 为多路归并趟数”。例题是 27 个元素只做三趟多路归并问归并路数。代入就是 log 以 3 为底、27 为真数等于 3选 B。这个公式的直觉是每趟归并把有序段数量缩小 k 倍从 m 段缩到 1 段需要 log_k m 趟。4. 表达式与编码前缀、后缀、原码补码这些“规则题”怎么一次记牢这部分是软考里典型的“规则明确、但容易在细节上翻车”的题型。规则本身不难难的是符号位、扫描方向、栈顶和次顶的顺序这些细节错一步结果就全错。4.1 三种表达式记法扫描方向和出栈顺序是唯一考点中缀表达式就是我们平时写的 ab-c。前缀表达式波兰式从右至左扫描遇到数字压栈遇到运算符弹出栈顶两个数用“栈顶元素 op 次顶元素”计算结果入栈重复到最左端。后缀表达式逆波兰式从左至右扫描遇到数字压栈遇到运算符弹出栈顶两个数用“次顶元素 op 栈顶元素”计算结果入栈重复到最右端。两个方向、两种操作数顺序正好相反这是最容易混的点。笔记里的例子前缀“- × 3 4 5 6”从右往左压入 6、5、4、3遇到 弹出 3 和 4 算 347后缀“3 4 5 × 6 -”从左往右压入 3、4遇到 弹出 4 和 3 算 347。两边结果都是 29但中间的操作数顺序必须严格按规则来。用一段伪代码把后缀求值的逻辑固定下来考场上在草稿纸上按这个流程走就不会乱def eval_rpn(tokens): stack [] for t in tokens: # 从左到右扫描 if t not in -*/: stack.append(int(t)) # 数字直接入栈 else: b stack.pop() # 先弹出的是栈顶作为右操作数 a stack.pop() # 后弹出的是次顶作为左操作数 if t : stack.append(a b) elif t -: stack.append(a - b) elif t *: stack.append(a * b) else: stack.append(a // b) return stack[0] # 最后剩下的就是结果关键注释在两行 pop 上后缀表达式里先弹出的是右操作数前缀表达式反过来。参数 tokens 是按空格切分后的记号列表运算符只处理四则运算除法按题目要求取整。4.2 原码、反码、补码、移码符号位动不动是关键正数的原码、反码、补码都等于自身二进制数。负数的原码是符号位为 1、后面跟自身二进制反码是符号位不动、其余各位取反补码是反码加 1移码增码不论正负把补码的符号位取反即可。应用场景要记牢计算机里最适合做数字加减运算的是补码因为补码把减法统一成加法符号位直接参与运算最适合表示浮点数阶码的是移码因为移码保持了大小顺序方便比较。机器字长为 n 时各码制的表示范围有个记忆技巧设 A2^(n-1)B1-2^(-(n-1))则原码和反码的定点整数范围是 [-(A-1), A-1]定点小数是 [-B, B]补码和移码的定点整数范围是 [-A, A-1]定点小数是 [-1, B]。补码比原码多表示一个负数这是它范围不对称的原因。4.3 指令寻址方式操作数到底在哪立即寻址操作数直接包含在指令中取操作数最快因为不用再访存。直接寻址操作数的地址写在指令里。寄存器寻址操作数就在寄存器中。寄存器间接寻址操作数的地址在寄存器中还要再按这个地址访存一次。四种方式的区别就是“操作数或它的地址到底藏在指令、内存还是寄存器里”按这个层次记比背定义快。5. 常见误区这几组概念最容易在考场上搞混5.1 邻接矩阵的行和列无向图与有向图的度算反了易混点是无向图和有向图的度计算。为什么混两者都用邻接矩阵但无向图第 i 行之和是度有向图第 i 行之和是出度、第 j 列之和才是入度。怎么区分先看题目说的是无向还是有向无向图矩阵对称行和列一样有向图不对称行管出、列管入笔记里顶点 3 的出度 5、入度 16 就是按行和列分别算的。5.2 平衡二叉树与 AVL 算法名字像但不是一回事易混点是 AVL 树和 AVL 算法。为什么混都叫 AVL。怎么区分平衡二叉树AVL 树是一种数据结构性质是左右子树高度差绝对值不超过 1AVL 算法是另一回事考试里问树的性质就按高度差判断别往算法上联想。5.3 哈夫曼树的左右大小规则不是硬性的易混点是哈夫曼树左节点是否必须比右节点小。为什么混教材例题大多画成左小右大。怎么区分定义上并没有这个要求左小右大只是做题时的习惯写法方便统一左 0 右 1 赋值。考试如果给了固定树形按给定树形走别自己重排。5.4 希尔排序的复杂度最好最坏为什么写“不存在”易混点是以为希尔排序也有固定的最好最坏复杂度。为什么混其他七种都有明确三列。怎么区分希尔排序的性能依赖增量序列的选择不同序列结果不同所以笔记里最好和最坏两格写“不存在”平均按 O(n^1.3) 记。5.5 前缀和后缀的操作数顺序栈顶和次顶正好相反易混点是两种表达式弹出操作数后的计算顺序。为什么混都是弹两个数做运算。怎么区分后缀是“次顶 op 栈顶”前缀是“栈顶 op 次顶”配合扫描方向一起记——后缀从左往右、前缀从右往左方向反了顺序也反。6. 什么时候用这份笔记、什么时候别用一个复习节奏上的判断这份笔记最适合的场景很明确你已经过了一遍教材或网课知识点有印象但不成体系需要一份东西把公式、结论、易错点串起来在考前两到四周做集中回顾。它的写法是结论优先、例题佐证拿来对着真题查漏补缺效率很高——比如做完一套卷子错在堆的判断就翻到堆那一节把 2i、2i1 的核对方法再走一遍错在补码范围就把 A 和 B 的记忆技巧默写一次。不适合的场景同样明确。如果你完全没接触过数据结构和计算机组成直接啃这份笔记会很难受因为它是“压缩包”解压需要前置知识。另一个不适合的场景是把它当唯一复习材料笔记覆盖的是高频考点和规律但软考中级还有软件工程、数据库设计、面向对象这些板块光靠这一份不够。场景适合用不适合用考前 2~4 周集中回顾是—做完真题后定位薄弱点是—零基础第一次学数据结构—是先看教材当唯一复习资料—是需配合其他板块资料背复杂度表和稳定性结论是—有个习惯值得养成每次做错一道规则题不要只记正确答案而是把“我混在哪一步”写下来——是扫描方向记反了还是行和列搞混了还是把“不存在”当成了某个具体值。这些混淆点积累到五六个你会发现错的其实是同一类思维惯性。我自己复习这类规则题时踩过的坑是总觉得自己“看懂了”一合上笔记就说不清前缀和后缀的操作数顺序。后来强制自己每道错题都手写一遍栈的弹出过程写满三遍之后才真正稳住。从那以后我每次遇到“看起来会了”的规则题都强制走一遍手推流程不再靠眼睛扫。希望这份笔记的整理思路能帮你在复习时少走几段弯路。本文还有配套的精品资源点击获取