简介：这份文档面向备考软件设计师（中级）的考生，聚焦软考中级核心考点，将数据结构、查找与排序等高频内容整理成便于速查的笔记精华，适合需要系统梳理知识框架、攻克难点公式与易错点的复习场景。压缩包共1个文件，为docx格式文档，整体约3.37MB，内容以图文与表格结合的方式呈现，便于打印或电子端翻阅。文档围绕邻接矩阵的度与出入度计算、顺序与链式及散列、索引等存储结构的适用条件展开，并梳理满二叉树、平衡二叉树、哈夫曼树与WPL计算、二叉排序树等树结构要点；查找部分覆盖二分查找与分块查找的适用情况与平均查找长度，排序部分则归纳直接插入、希尔、快速、堆、归并、基数等算法的过程与复杂度对比表。目前已有382人学习，适合作为考前查漏补缺与公式速记的辅助材料。
1. 软件设计师中级：一张知识地图先看清全貌
软件设计师（中级）这张卷子的知识分布，说散很散，说集中也很集中。翻完这份考点笔记精华版，我最大的感受是：它不像某些考试那样靠死记硬背堆量，而是围绕「数据怎么存、怎么找、怎么排、怎么算」这条主线铺开的。数据结构与算法占了相当大的比重，从邻接矩阵、链表、二叉树一路延伸到八大排序和查找方法；再往外一圈是计算机系统基础，符号数编码、定点数范围、指令寻址方式这些偏底层的点；最外层才是 CPU 组成这类概念性内容。换句话说，复习时如果先把数据结构这条主干吃透，其余模块都是挂在上面的枝叶，不会觉得零散。这份笔记适合已经过了一遍教材、需要系统梳理和查漏补缺的人，也适合临考前想快速定位重点公式和易错点的人。
2. 数据结构与存储结构：图、表、树的底层逻辑
2.1 邻接矩阵与四种存储结构怎么选
图这一块，考试最爱考邻接矩阵的行列含义。无向图的邻接矩阵是对称的，第 i 行元素之和就是顶点 i 的度；有向图则要分开看，第 i 行之和是出度，第 j 列之和是入度。笔记里举的例子很典型：顶点 4 的度就是第四行的和，顶点 3 的出度和入度分别是 5 和 16。这类题不难，但容易在「行还是列」上翻车，做题时先在草稿纸上标清楚方向再算。
存储结构的选择是另一条高频考点，核心是「什么场景用什么结构」：
| 存储结构 | 特点 | 适用场景 |
|---|---|---|
| 顺序存储 | 地址连续，依次存放 | 频繁查询 |
| 链式存储 | 存储单元可连续可不连续 | 频繁插入、删除、更新 |
| 散列存储 | 关键码与存储位置建立确定对应关系（键值对） | 高效查找 |
| 索引存储 | 单独的物理结构，指向数据页的逻辑指针清单 | 数据库检索 |
单链表、循环链表、双链表的比较也常出选择题。双链表因为有两个指针域，灵活度优于单链表，但开支更大——这句话几乎可以原样背下来，考场上直接对应选项。
2.2 二叉树家族：二叉排序树、哈夫曼树、平衡二叉树
树结构里最容易被混淆的是几种「特殊二叉树」的定义和性质。二叉排序树的三条性质要记牢：左子树非空则左子树所有节点值小于根节点；右子树非空则右子树所有节点值大于等于根节点；左右子树本身也分别是二叉排序树。查找时中序遍历能得到一个递增序列，这个结论经常作为判断题出现。还有一个细节：关键字最大的结点可以有左子树，但一定没有右子树。
哈夫曼树是带权路径长度（WPL）最短的树，权值越大的叶子节点越靠近根节点。构造和 WPL 计算是必考题型，笔记里给了一道完整例题：6 个字符用定长编码，3 位二进制就够（000 到 101 表示 a 到 f），所以码长选 3；求 “face” 的 Huffman 编码时，按左小右大、左 0 右 1 的规则从根节点走一遍，答案是 001110110011。这里有个血泪经验：哈夫曼树的左节点未必要比右节点小，但做题时通常写成左小右大的形式，否则编码对不上标准答案。
平衡二叉树（AVL 树）的性质是左右两个子树高度差的绝对值不超过 1，且左右子树也都是平衡二叉树。满二叉树则是除最后一层外每一层节点都有两个子节点或 0 个子节点。这两个定义经常被放在一起做辨析题，记的时候抓住「高度差」和「每层节点数」两个关键词就不会混。
2.3 广义表与表达式记法
广义表的长度是删掉最外层括号后剩下的元素个数，深度是括号的层数。笔记里的例子很能说明问题：L1=((a,(a,b),((a,b),c))) 长度 1、深度 4；L2=((1,2,3)) 长度 1、深度 2；L3=(1,2,3) 长度 3、深度 1。数括号层数时从最外层往里数，别把最外层漏掉。
表达式记法分前缀（波兰式）、中缀、后缀（逆波兰式）三种。前缀从右往左扫描，遇到运算符弹出栈顶两个数，注意是「栈顶元素 op 次顶元素」；后缀从左往右扫描，规则反过来是「次顶元素 op 栈顶元素」。这两个方向搞反是最高频的翻车点，建议做题时在草稿上画个小栈，一步步压弹，别心算。
3. 查找与排序：八种排序的复杂度与稳定性
3.1 三种查找方法的适用边界
二分查找（折半查找）适用于不经常变动而查找频繁的有序列表，优点是比较次数少、查找速度快、平均性能好，缺点也明确：要求待查表有序，且插入删除困难。分块查找适合节点动态变化的情况，比顺序查找快得多，但速度不如折半查找。它的实现要点是块间有序、块内可任意存放，再建一个索引表存每块最大关键码，查找时先查索引表再查块内。
平均查找长度 E(n) 的公式也要有印象：n 个节点分成大小相等的 b 块，每块 s=n/b，这个设定在计算题里会直接给出。
3.2 八大排序的核心思想一句话记忆
排序这一章内容多，但每种算法都能压缩成一句话：
- 直接插入排序：每趟把一个待排序记录插入有序队列的合适位置，像斗地主抽牌。
- 简单选择排序：每趟选出关键字最小的记录，放到已排序序列末尾。
- 冒泡排序：两两比较相邻关键字，不满足次序就交换。
- 希尔排序：按步长 gap 分组，组内直接插入排序，步长减到 1 时完成。
- 快速排序：一趟分割成左右两部分，左边都比它小、右边都比它大，递归处理，采用分治法。
- 堆排序：n 个元素的序列满足 ki≤k2i 且 ki≤k2i+1（小顶堆）或反之（大顶堆）。
- 归并排序：把序列看成 n 个长度 1 的有序表，成对归并，直到合成一个长度 n 的序列。
- 基数排序：不比较关键字大小，按各位的值做「分配」与「收集」，比如 0~9 十个桶。
3.3 复杂度与稳定性对照表
这张表是复习的重中之重，考试直接考、做题也靠它判断：
| 排序方法 | 最好 | 平均 | 最坏 | 辅助空间 | 稳定性 |
|---|---|---|---|---|---|
| 直接插入 | 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(nlog₂n) | O(nlog₂n) | O(n²) | O(log₂n) | 不稳定 |
| 堆排序 | O(nlog₂n) | O(nlog₂n) | O(nlog₂n) | O(1) | 不稳定 |
| 归并 | O(nlog₂n) | O(nlog₂n) | O(nlog₂n) | O(n) | 稳定 |
| 基数 | O(d(n+rd)) | O(d(n+rd)) | O(d(n+rd)) | O(rd) | 稳定 |
记忆技巧：稳定的只有插入、冒泡、归并、基数四个；辅助空间为 O(1) 的是插入、选择、冒泡、希尔、堆；快速排序最坏退化到 O(n²)，这是它最大的软肋。
3.4 堆的判断与归并路数公式
堆的判断题给一组序列，逐个检查是否满足父子关系即可。笔记里的例题 (10,18,15,20,50,80,30,60) 就是标准小顶堆，因为每个父节点都不大于它的两个子节点。判断时从第一个非叶子节点开始往下比，比从头到尾扫一遍快。
归并路数的公式是 k = |logₘ n| 的反向应用：m 为元素个数，k 为多路归并趟数。27 个元素做三趟多路归并，log 以 3 为底 27 的对数是 3，所以归并路数选 3。这个公式考法固定，套进去就行，但要注意「趟数」和「路数」别搞反。
4. 计算机系统基础：符号数、定点数与指令寻址
4.1 原码、反码、补码、移码的转换规则
四种码制的转换是系统基础里最基础也最容易记混的部分。正数的原码、反码、补码都等于自身二进制数；负数的原码符号位为 1，反码符号位不动、其余按位取反，补码在反码基础上加 1；移码无论正负，把补码的符号位取反即可。
应用场景要记死：计算机中最适合数字加减运算的编码是补码，最适合表示浮点数阶码的编码是移码。这两句话几乎每年都以选择题形式出现。
4.2 定点数表示范围与记忆技巧
机器字长为 n 时，各种码制表示的带符号数范围如下：
| 码制 | 定点整数 | 定点小数 |
|---|---|---|
| 原码 | [-(2ⁿ⁻¹-1), 2ⁿ⁻¹-1] | [-(1-2⁻⁽ⁿ⁻¹⁾), 1-2⁻⁽ⁿ⁻¹⁾] |
| 反码 | [-(2ⁿ⁻¹-1), 2ⁿ⁻¹-1] | [-(1-2⁻⁽ⁿ⁻¹⁾), 1-2⁻⁽ⁿ⁻¹⁾] |
| 补码 | [-2ⁿ⁻¹, 2ⁿ⁻¹-1] | [-1, 1-2⁻⁽ⁿ⁻¹⁾] |
| 移码 | [-2ⁿ⁻¹, 2ⁿ⁻¹-1] | [-1, 1-2⁻⁽ⁿ⁻¹⁾] |
笔记里给了一个很实用的记忆技巧：令 A=2ⁿ⁻¹，B=1-2⁻⁽ⁿ⁻¹⁾，则原码和反码的定点整数范围是 [-(A-1), A-1]，定点小数是 [-B, B]；补码和移码的定点整数是 [-A, A-1]，定点小数是 [-1, B]。这样一压缩，四行公式变成两组对称结构，考场上现推也来得及。
4.3 指令寻址方式的速度排序
四种寻址方式的核心区别在于操作数或操作数地址放在哪：
- 立即寻址：操作数直接包含在指令中，获取操作数最快。
- 直接寻址：操作数的地址在指令中。
- 寄存器寻址：操作数在寄存器中。
- 寄存器间接寻址：操作数的地址在寄存器中。
速度排序上，立即寻址最快是送分点，其余三种按「操作数离 CPU 越近越快」的原则理解即可。CPU 组成方面，运算器、控制器、寄存器和内部总线四部分要记住，控制器的职责不仅是保证程序正确执行，还要能处理异常事件——后半句常被忽略，却是出题点。
5. 易错点清单：五个最容易翻车的地方
5.1 邻接矩阵的行列方向
易漏点：无向图算度、有向图算出度入度时，行和列的含义搞反。 为什么漏：无向图对称，行和列结果一样，练多了形成惯性，遇到有向图直接套用就错。 怎么补：做题前先在矩阵上方标「出」、右侧标「入」，强迫自己区分方向再动笔。
5.2 前缀与后缀表达式的弹栈顺序
易漏点：前缀是「栈顶 op 次顶」，后缀是「次顶 op 栈顶」，两个方向相反。 为什么漏：两种记法只差一个扫描方向，背的时候容易只记一半。 怎么补：记口诀「前右后左，弹栈反着来」，每次做题画栈图验证一步。
5.3 哈夫曼编码的左右约定
易漏点：构造哈夫曼树时左小右大、左 0 右 1 的约定不统一，导致编码与选项对不上。 为什么漏：定义上左节点未必要比右节点小，但考试按约定俗成的写法给答案。 怎么补：固定按左小右大构造，编码时从根往下走，左分支记 0、右分支记 1，别中途换规则。
5.4 排序稳定性的记忆偏差
易漏点：把希尔排序或快速排序误记为稳定。 为什么漏：稳定与不稳定没有直观规律，纯靠记忆，容易张冠李戴。 怎么补：只记稳定的四个（插入、冒泡、归并、基数），其余全按不稳定处理，反向排除更快。
5.5 补码与移码的范围混淆
易漏点：补码定点整数范围是 [-2ⁿ⁻¹, 2ⁿ⁻¹-1]，比原码多表示一个负数，容易记成和原码一样。 为什么漏：原码、反码、补码三行连在一起看，视觉上容易串行。 怎么补：用 A、B 记忆法压缩成两组，补码和移码归为一组，原码和反码归为另一组，分组记不易混。
6. 复习清单：考前一周怎么查漏补缺
到了冲刺阶段，最怕的是「感觉都会、一做就错」。我的做法是把这份笔记拆成三层来刷：第一层是公式层，邻接矩阵行列含义、归并路数公式、四种码制范围、八大排序复杂度表，这些必须做到提笔就写、不假思索；第二层是判断层，堆的判断、二叉排序树性质辨析、寻址方式速度排序，靠做题保持手感；第三层是计算层，哈夫曼树构造与 WPL、前缀后缀表达式求值、二分查找过程推演，必须动手算，不能只看答案。
具体到每天的安排，可以按下面这个清单走一遍：
| 复习项 | 自检标准 | 薄弱时的补救 |
|---|---|---|
| 邻接矩阵 | 能口述行列出度入度关系 | 重做笔记例题，标方向 |
| 存储结构选择 | 四种结构对应场景不混 | 列表对比，遮住右列自测 |
| 二叉树性质 | 三种特殊树定义能区分 | 画图对比高度差与节点数 |
| 哈夫曼编码 | 独立构造并算出 WPL | 按左小右大重走一遍 |
| 排序复杂度 | 默写整张对照表 | 只记稳定四个，反向排除 |
| 码制范围 | 用 A、B 法现推 | 每天推一遍四行范围 |
| 表达式求值 | 前后缀各算一题 | 画栈图，标弹栈顺序 |
最容易忽略的是「计算层」的动手量。很多人公式背得滚瓜烂熟，一到哈夫曼树构造就卡在合并顺序上，或者后缀表达式弹栈时把操作数顺序写反。这类错误看答案觉得理所当然，自己上手就原形毕露。建议每两天完整手算一道哈夫曼题和一道表达式题，算完对照笔记里的例题步骤，看每一步的中间结果是否一致。
还有一点血泪经验：排序复杂度表不要整张死背，先记「稳定的四个」和「辅助空间 O(1) 的五个」，剩下的用排除法推。考场上时间紧，排除法比回忆法快得多。从那以后我每次复习这类对照表，都强制自己先默写稳定性和空间两列，再补时间复杂度的三列，正确率明显上来了。希望这份梳理能帮到你，把地图装进脑子，剩下的就是反复走几遍。
本文还有配套的精品资源，点击获取
