简介：软件设计师（中级）考点笔记精华版是一份面向软考中级考生的浓缩复习资料，以单个 docx 文档文件打包，大小仅为三点三七兆字节（3.37MB）。内容聚焦数据结构与算法高频考点：邻接矩阵的度、出度入度计算，顺序、链式、散列、索引等存储结构的特点与适用场景；二叉树部分覆盖满二叉树、平衡二叉树、哈夫曼树的定义及构造逻辑，并附有哈夫曼树带权路径长度计算与编码方式例题。查找与排序部分系统梳理了二分查找、分块查找的适用前提，以及直接插入、简单选择、冒泡、希尔、快速、堆、归并、基数排序等算法的流程与时间复杂度对比，便于考生快速辨析易混概念。目前已有三百八十一人学习下载，适合在考前用于查漏补缺和强化记忆，是一份能帮助备考者提升复习效率的章节精华汇总。
1. 软考中级备考，这份考点笔记解决的不只是“背什么”
软件设计师（中级）考证的复习资料多到看不完，但真正能落地用的不多。这份考点笔记精华版 docx 的价值在于它把数据结构、查找排序、表达式记法、编码体系这些高频考点做了压缩整理，每个知识点后面直接跟真题思路，比如哈夫曼编码、归并路数、堆排序判定这类易错题，笔记里都给了公式和解法推导。对正在备考软考中级的从业者来说，它解决的不是“有没有资料”的问题，而是“哪些考点必须拿分、哪些地方最容易丢分”的问题。无论你是科班出身想要快速回顾，还是半路转行需要系统突击，这份笔记都能当复习主线用。
2. 数据结构与存储：邻接矩阵、存储结构、二叉树的考点对照
2.1 邻接矩阵的度计算：无向图看行和有向图看行列
邻接矩阵是图的一种顺序存储方式，用一个二维数组存放顶点间关系。笔记里反复强调的考点非常具体：无向图的邻接矩阵是对称矩阵，第 i 行元素之和就是顶点 i 的度。比如顶点 4 的度直接数第四行有几个非零元素即可。有向图则要分开算，第 i 行元素之和是顶点 i 的出度，第 j 列元素之和是顶点 j 的入度。
实际做题时有个常见陷阱，就是题目给的是带权图而非简单图，矩阵里存的是权值而非 0/1。这时“行和”不能直接当度数算，得先数非零元素个数。我在给 A 同学讲题时发现他在这里翻过车——把带权矩阵的数值累加当成度，结果对不上标准答案。所以拿到题先确认是邻接矩阵还是带权矩阵，再决定是数非零个数还是求和。
# 邻接矩阵度计算的判别逻辑 def vertex_degree(matrix, vertex_index, directed=False): n = len(matrix) if not directed: # 无向图：数第 i 行非零元素个数 return sum(1 for v in matrix[vertex_index] if v != 0) else: # 有向图：出度看行，入度看列 out_degree = sum(1 for v in matrix[vertex_index] if v != 0) in_degree = sum(1 for row in matrix if row[vertex_index] != 0) return out_degree, in_degree这个判别逻辑对应笔记里的核心公式：无向图行和即度，有向图行和是出度、列和是入度。参数说明：matrix 是邻接矩阵二维列表，vertex_index 是顶点编号，directed 控制是否按有向图处理。实际考试中这个知识点常与图的遍历、连通性判断结合出题，单独考的分数不高，但作为后续题目的基础判断，错了会连带丢分。
复习时要把无向图对称性、有向图行列分离这两个特征写在同一张卡片上对比记忆，因为考题经常把两者放在同一题的选项里混淆你。
2.2 顺序、链式、散列、索引：四种存储结构的适用场景判断
笔记把这四种存储结构归在一起对比，核心是“什么场景选什么结构”。顺序存储用一组地址连续的存储单元依次存放数据，适合频繁查询的场景，因为按下标访问是 O(1) 复杂度。链式存储用任意一组存储单元存放，每个节点带指针指向后继，适合频繁插入删除的场景，因为不需要移动大量数据。
单链表、循环链表、双链表的对比也是高频小题。双链表有两个指针域，可前向后向遍历，灵活度优于单链表，但每个节点要多存一个指针，存储开销大。循环链表解决的是从任意节点出发都能遍历整张表的问题，但判空条件要从 head.next 是否为 null 变成是否回到头节点。
散列存储就是键值对，把存储位置与关键码建立对应关系，查找效率理论上是 O(1)。索引存储结构则是单独维护一张索引表，表中存放关键码值和指向物理数据页的指针，数据库系统里用得最多。考题常给一个业务场景问选哪种存储，判断标准就三条：查询多选顺序或索引，增删多选链式，等值快速查找选散列。
2.3 二叉排序树与哈夫曼树：构造规则和编码计算的拿分点
二叉排序树是软考常客，定义有三条：左子树所有节点值小于根，右子树所有节点值大于等于根，左右子树自身也满足这个递归定义。中序遍历二叉排序树得到的是递增序列，这个特性经常用来判断一棵树是不是合法的二叉排序树。还有一个容易记混的结论：关键字最大的节点可能有左子树，但一定没有右子树。
哈夫曼树是带权路径长度 WPL 最短的二叉树，权值越大的叶子越靠近根。构造过程就是每次取两个权值最小的节点合并，生成一个新节点，权值为两者之和，再放回集合中继续。笔记里给了完整的真题：6 个字符 a-f，定长编码码长是 3 位（因为 2 的 2 次方小于 6，2 的 3 次方大于等于 6）。哈夫曼编码“face”要从根出发沿路径收集 0/1 编码，方向是左 0 右 1。
# 哈夫曼树 WPL 计算框架 import heapq class HuffmanNode: def __init__(self, weight, char=None): self.weight = weight self.char = char self.left = None self.right = None def build_huffman_tree(freq_dict): heap = [[w, HuffmanNode(w, c)] for c, w in freq_dict.items()] heapq.heapify(heap) while len(heap) > 1: w1, n1 = heapq.heappop(heap) w2, n2 = heapq.heappop(heap) merged = HuffmanNode(w1 + w2) merged.left, merged.right = n1, n2 heapq.heappush(heap, [merged.weight, merged]) return heap[0][1]参数说明：freq_dict 是字符到频率的映射，堆中存放 [权值, 节点] 便于每次取最小。构建的树中，左子树放较小权值节点，右子树放较大权值节点。考试不要求手写代码，但理解这个合并过程才能算出 WPL 和编码。易错点是权值相等的节点合并顺序不同会得到不同的哈夫曼树，但 WPL 相同，编码长度可能不同——考题如果问“编码是什么”就得看题目给定的合并方向和左右子树约定，不能自己随意定。
2.4 平衡二叉树与满二叉树：概念判断的两条硬规则
平衡二叉树 AVL 的判定规则就是空树或左右子树高度差绝对值不超过 1，且左右子树本身也是平衡二叉树。题目给一棵树的层次遍历序列，问它是不是 AVL 树，我需要做的就是先重建二叉树，再递归计算每个节点左右子树高度差。满二叉树则要简单些，除最后一层外每层节点都有两个子节点，节点总数满足 2 的 k 次方减 1（k 为层数）。
这两个概念经常和二叉排序树放在一起考。排序树强调值有序，平衡树强调形状均衡，满二叉树关注节点是否填满。复习时用一张表把定义、判定条件、典型应用列清楚，做题时先判断题目问的是值序还是形态，再套对应规则。
3. 查找与排序算法：复杂度对照与真题识别技巧
3.1 二分查找与分块查找：有序性前提和索引建法
二分查找也叫折半查找，前提是线性表有序且存储结构支持随机访问，也就是顺序存储。算法逻辑是取中间位置记录与目标比较，相等则找到，目标小则在前半段继续，目标大则在后半段继续。优点是比较次数少、速度快、平均性能好；缺点是要求表必须有序，插入删除困难。所以“不经常变动而查找频繁的有序表”是二分查找最典型的适用场景。
分块查找是折中方案，适用于节点动态变化的情况。它把大表分成若干块，块内节点可以任意存放，块与块之间必须有序——第 i 块所有节点的关键码值都小于第 i+1 块所有节点。同时建一个索引表，存放每块最大关键码值，按块顺序排列。查找时先在索引表里定位块，块内用顺序查找。平均查找长度是两个阶段查找长度之和，这个公式在选择题里出现过。
# 二分查找的边界处理模板 def binary_search(arr, target): left, right = 0, len(arr) - 1 while left <= right: mid = (left + right) // 2 if arr[mid] == target: return mid elif arr[mid] < target: left = mid + 1 else: right = mid - 1 return -1二分查找的边界条件是 left <= right，mid 取中间向下取整。如果目标值比中间值大，左边界移到 mid+1，这是防止死循环的关键。很多人在手写时把 left 写成 mid 导致死循环或漏查，考场上笔算不会死循环，但查数的过程会重复比较。分块查找的索引表可以用顺序查找也可以用折半查找，因为索引表本身有序，后者更快。
3.2 六大排序算法：从直接插入到归并的时间复杂度速查
软考对排序算法的考查集中在时间复杂度和稳定性，以及“某序列用某算法第一趟排序后的结果”。直接插入排序每趟把一个记录按关键字大小插入有序队列，好比斗地主摸牌后插牌，最好情况 O(n)，平均 O(n²)。简单选择排序每趟选最小放末尾，无论数据分布如何都是 O(n²)，不稳定。冒泡排序两两比较交换，最好情况 O(n)，这是指初始基本有序的情况。
希尔排序按步长分组，组内直接插入，步长逐渐减小到 1，时间复杂度平均约为 O(n^1.3)。快速排序用分治法，每趟选一个基准把数据分成左右两半，平均 O(nlog₂n)，最坏退化成 O(n²)，发生在基准每次都是最大或最小值时。堆排序利用堆结构，建堆后反复取堆顶，时间复杂度稳定在 O(nlog₂n)，不稳定。归并排序把序列看成 n 个长度为 1 的有序表，两两归并直到合并成一个，时间复杂度始终 O(nlog₂n)，需要 O(n) 辅助空间，稳定。
稳定性的记忆口诀：稳定的有直接插入、冒泡、归并、基数；不稳定的有选择、希尔、快速、堆。考题常给出一个序列问“以下哪个是堆”，比如笔记里的例题，判断标准就是堆的定义：对 i 从 1 到 n/2，满足 ki ≤ k(2i) 且 ki ≤ k(2i+1) 的是小根堆，反之是大根堆。四个选项一一代入验证即可，这个直接验证比背堆排序过程快得多。
3.3 归并路数公式：log 运算的快速解法
归并排序的归并路数公式是 k = log_{m} 开根方向，笔记里写成归并路数 = |log_k m|，其中 m 是元素个数，k 是多路归并趟数。例题问“对 27 个元素只进行三趟多路归并排序，则选取的归并路数”，做法是求 log 以 3 为底 27 的对数，答案是 3。
import math def merge_ways(m, rounds): # m 为元素个数，rounds 为归并趟数，求归并路数 k return round(math.log(m, rounds))这个公式我第一次复习时没注意，做题直接卡住。它的本质是每次归并把 k 个有序序列合并成一个，趟数为 r，则元素总数 m 和 k、r 的关系是 k^r = m。所以 k 等于 m 开 r 次方根，也就是 log 以 r 为底 m 的对数。考试遇到这类题先套公式，不要试图画归并树来推，那样太慢还容易错。
3.4 平均查找长度与分块参数的关系
分块查找的平均查找长度 E(n) 涉及块数 b 和每块大小 s。假设线性表共 n 个节点，分成大小相等的 b 块，每块 s = n/b。索引表查找加上块内顺序查找，总查找长度约为 b/2 + 1 + s/2，即索引表折半或顺序查找的平均次数加上块内顺序查找的平均次数。这个公式在题目给出 n、b、s 时直接代入即可。
需要注意的点是：块间有序是分块查找的前提，块内无序是它的特点，这正是它比顺序查找快又比折半查找灵活的原因。考题如果描述“节点动态变化但需要较快查找”，分块查找是第一选择，因为平衡二叉树和折半查找都要求数据有序性高，动态维护成本大。
4. 表达式记法与编码体系：逆波兰式、原反补移码全解
4.1 前缀、中缀、后缀表达式：三种记法的栈运算规则
表达式记法是软考上午题的常客，前缀表达式（波兰式）运算符在前，中缀是我们平时写的 a+b-c，后缀表达式（逆波兰式）运算符在后。三种记法对应三种求值方式。
前缀表达式从右至左扫描，遇数字压栈，遇运算符弹出栈顶两个数，计算方式是“栈顶元素 op 次顶元素”，结果再入栈。比如前缀表达式“- × + 3 4 5 6”，从右往左看，先把 6、5、4、3 压栈，遇到 + 弹出 3 和 4 算 7，遇到 × 弹出 7 和 5 算 35，遇到 - 弹出 35 和 6 算 29。后缀表达式从左至右扫描，遇数字压栈，遇运算符弹出次顶元素 op 栈顶元素，例如“3 4 + 5 × 6 -”，先 3 和 4 入栈，遇到 + 算 7，5 入栈，遇到 × 算 35，6 入栈，遇到 - 算 29。
# 后缀表达式求值实现 def eval_postfix(expr): stack = [] for token in expr.split(): if token.isdigit(): stack.append(int(token)) else: b = stack.pop() a = stack.pop() if token == '+': stack.append(a + b) elif token == '-': stack.append(a - b) elif token == '*': stack.append(a * b) elif token == '/': stack.append(a / b) return stack[0]这个实现对应笔记里的后缀求值规则：弹出的是次顶元素和栈顶元素，先弹出的是 b 即右操作数，后弹出的是 a 即左操作数。减法除法必须保持这个顺序，否则结果反了。前缀求值的代码逻辑与后缀对称，但扫描方向相反，且弹栈后计算顺序是“栈顶元素 op 次顶元素”，恰好与后缀相反。这个对称关系是记忆的关键。
考试中有一类题是给中缀表达式让转后缀，或者给后缀让转前缀。常见的做法是用栈处理运算符优先级，但这需要画状态表，比较费时。我一般用的是“完全括号化”方法：把中缀表达式每步运算加上括号，然后把运算符移到对应括号的右边（后缀）或左边（前缀），再删掉括号。例如 a+bc 先变成 a+(bc)，后缀是 abc*+。熟练后这个方法比栈模拟快很多。
4.2 原码、反码、补码、移码：机器字长 n 的表示范围
符号数的编码是软考必考点，笔记整理得很清晰。原码：正数就是二进制本身，负数首位为 1 作符号位，后面是数值。反码：正数同原码，负数符号位不动其余按位取反。补码：正数同原码，负数在反码基础上加 1。移码：无论正负，把补码的符号位取反即可。
机器字长为 n 时，各类码制表示的定点整数范围不同。原码和反码的定点整数范围是 [-(2^(n-1)-1), 2^(n-1)-1]，补码和移码是 [-2^(n-1), 2^(n-1)-1]。注意补码多了一个最小值 -2^(n-1)，这是因为补码的 0 只有一种表示，空出来的全 0 之外的编码可以多表示一个负数。定点小数范围也是常考点，原码反码是 [-(1-2^-(n-1)), 1-2^-(n-1)]，补码移码是 [-1, 1-2^-(n-1)]，补码可以表示 -1。
记忆技巧是把 A = 2^(n-1)，B = 1-2^-(n-1)，这样原码反码定点整数是 [-(A-1), A-1]，补码移码是 [-A, A-1]。实际做题时，题目给 n=8，问某码制可表示的最小负数是多少，直接代公式算。
4.3 计算机指令系统：五种寻址方式的辨析
指令系统部分常考寻址方式，笔记里列了四种：立即寻址是操作数包含在指令中，获取操作数最快；直接寻址是操作数的地址在指令中；寄存器寻址是操作数在寄存器中；寄存器间接寻址是操作数的地址在寄存器中。考题给一条指令问是哪种寻址，关键是看指令中存放的是数据本身还是地址，以及地址在内存还是寄存器。
# 寻址方式判断速查 立即寻址: MOV R1, #100 # #100 是数据本身 直接寻址: MOV R1, [100] # 100 是内存地址 寄存器寻址: MOV R1, R2 # R2 中存的是数据 寄存器间接: MOV R1, [R2] # R2 中存的是地址这个对比来自典型指令格式。立即寻址最快但灵活性差，因为指令中只能放常量。直接寻址需要访问一次内存取操作数。寄存器寻址不需要访问内存，但数据必须在寄存器中。寄存器间接寻址需要先读寄存器得到地址，再访问内存取数据。软考常把五种的优缺点混在一起出选择，核心记忆点是“快慢排序：寄存器寻址约等于立即寻址最快，直接寻址次之，间接寻址最慢”，因为每多一次内存访问就多一层延迟。
4.4 CPU 组成：运算器、控制器、寄存器的分工
中央处理器 CPU 的组成包括运算器、控制器、寄存器和内部总线。笔记特别强调控制器不仅要保证程序的正确执行，还要能处理异常事件。这个是高频判断题，很多人会误以为异常处理是操作系统的事，实际上 CPU 控制器中的中断逻辑负责响应异常和中断请求。运算器负责算术逻辑运算，寄存器组提供临时存储，内部总线连接各部分传递数据和控制信号。
考试会给一句描述问“这是 CPU 的哪个部件”，比如“负责指令译码并产生控制信号”对应控制器，“执行算术运算和逻辑运算”对应运算器，“存放当前正在执行的指令”对应指令寄存器。这个知识点不难，但要记准确，因为选项之间长得像，尤其是控制器和运算器的职责边界。
5. 避坑：复习考点笔记时最常见的五个误读与失误
5.1 把带权邻接矩阵的行和当成顶点度
现象：题目给出一个带权邻接矩阵，求某顶点度数，直接对行内数值求和，得到错误结果。
原因：邻接矩阵的度定义是“邻接点的个数”，即非零元素的个数。带权矩阵中非零元素可能为 3、5、8 等权值，求和得到的是权重和而非度数。
解决：凡是用邻接矩阵表示图，先看矩阵元素是 0/1 还是任意数值。若是带权图，度 = 该行非零元素个数；若是无权图，行和就是度。做题时把题目给的矩阵在草稿纸上圈出非零元素位置，再数个数，避免被数值干扰。
5.2 哈夫曼编码左右子树方向搞反
现象：构造哈夫曼树时把大权值放左边、小权值放右边，或者左右子树赋值反了，导致编码结果与答案不符。
原因：教材默认约定左小右大、左 0 右 1，但哈夫曼树定义本身没有这个限制。考题的选项往往是按约定方向生成的，如果自己改了方向，编码自然对不上。
解决：复习时统一采用“左小右大，左 0 右 1”的约定。做题时先检查题目是否显式规定方向，没有规定就按约定。构造时每次合并取两个最小权值节点，小的放左边，大的放右边，生成的新节点权值为两者之和，再参与下一轮合并。WPL 只与树形有关，编码才与方向有关，这个区分要刻在脑子里。
5.3 堆排序判定时忽略完全二叉树结构
现象：判断一个序列是否为堆时，只验证序列数值的大小关系，没考虑堆必须是完全二叉树。
原因：堆排序里的堆是“完全二叉树 + 堆序性质”双重定义。软考题目给的序列长度可能不是 2^k-1，有些人直接把序列下标当成完全二叉树的下标，但没有先确认层序排列能否构成完全二叉树。
解决：在草稿纸上按完全二叉树规则画出下标对应的树形结构——第 1 个元素为根，第 2、3 个为左右孩子，依此类推。画完后检查是否有“有右无左”的空缺节点，若有则不是完全二叉树，必然不是堆。之后再验证小根堆或大根堆的不等式关系。这个过程每次做题都画一遍，比心算可靠。
5.4 后缀表达式求值时弹栈顺序反了
现象：计算后缀表达式“3 4 -”，弹出后算成 4 - 3 = 1，正确答案是 3 - 4 = -1。
原因：后缀表达式求值规则是“次顶元素 op 栈顶元素”，先弹出的是右操作数，后弹出的是左操作数。很多人习惯先弹出的是左操作数，正好与正确规则相反。
解决：写代码时用 a = pop() 作为次顶元素即左操作数，b = pop() 作为栈顶元素即右操作数，计算 a op b。笔算时，把栈中倒数第二个元素写在运算符左边，栈顶元素写在右边。每次遇到运算符都默念“左边减右边”，避免搞反。前缀表达式相反，是“栈顶元素 op 次顶元素”，两个规则对称记忆。
5.5 补码表示范围漏掉最左侧的 -2^(n-1)
现象：题目问 n=8 时补码定点整数的最小值，写成 -127，漏了 -128。
原因：原码和反码的最小值是 -(2^(n-1)-1)，补码和移码的最小值是 -2^(n-1)。补码的 0 只有一种编码，多出来的全 1 编码（10000000）表示为 -128，这个特殊值经常被忽略。
解决：背范围时用对比法：原码反码是对称的，补码移码是非对称的，左边多一个最小值。做题时先判断码制，再决定用哪个公式。若题目问“8 位补码可表示的最小数”，直接答 -2^7 = -128。这个知识点在上午题几乎年年出现，拿到分很容易，丢分很可惜。
6. 考前一周：用考点笔记做“消消乐”复盘法
最后一阶段不建议再从头到尾翻笔记，那样效率低且看不出薄弱点。我习惯用消消乐方式复盘：把笔记里每个小节看成一张卡片，比如“邻接矩阵的度”“哈夫曼 WPL 计算”“二分查找边界”“补码范围”这些，逐张过，能完整复述解题步骤的直接划掉，卡壳的留下。
具体操作分三步走。第一步，用一张白纸盖住笔记里的解题过程，只看题目或结论句，自己在纸上推导。比如看到“27 个元素三趟多路归并”，立刻写 log₃27 = 3；看到“8 位补码定点整数范围”，立刻写 [-128, 127]。能写出来就说明这个考点真正掌握了。第二步，把卡壳的考点集中抄到一张错题卡上，每张卡只写考点名和关键公式，不写推导。第三天再单独过这些卡，直到能脱卡复述。第三步，考前最后两天不再做新题，只看错题卡和笔记里的例题，保持手感。
验证复习效果的另一个技巧是“出题人视角”：随意翻开笔记某一节，假装自己是出题人，针对这个考点设计一道选择题。比如看到二叉排序树，就设计“哪个序列是中序遍历结果”，看到后缀表达式，就设计“以下哪个是 3 4 + 5 × 的求值结果”。这个过程强迫你从记忆层面切换到理解层面，能发现很多自以为会但实际讲不清楚的考点。
我在备考软考中级时，最有效的做法是把笔记里的公式和数据结构的判定条件写在 A5 卡片上，随身带着，通勤时抽 10 分钟过四五张。考前一周每晚只做消消乐复盘，不再刷整套模拟题。那次考试上午题的数据结构和算法部分基本没失分，因为每个考点的解题入口都在笔记里标注过，考场上看到题目就能直接映射到对应的处理流程。
从那以后，每次复习考证类资料我都强制走一遍“速过→卡壳标记→消消乐消卡→错题卡冲刺”的流程，不再对着厚厚的教材做无效阅读。希望这份考点笔记也能帮你把有限的复习时间花在刀刃上，软考中级一次过关。
本文还有配套的精品资源，点击获取
