简介软件设计师中级考点笔记精华版是一份面向软考中级考生的浓缩复习资料以单个 docx 文档文件打包大小仅为三点三七兆字节3.37MB。内容聚焦数据结构与算法高频考点邻接矩阵的度、出度入度计算顺序、链式、散列、索引等存储结构的特点与适用场景二叉树部分覆盖满二叉树、平衡二叉树、哈夫曼树的定义及构造逻辑并附有哈夫曼树带权路径长度计算与编码方式例题。查找与排序部分系统梳理了二分查找、分块查找的适用前提以及直接插入、简单选择、冒泡、希尔、快速、堆、归并、基数排序等算法的流程与时间复杂度对比便于考生快速辨析易混概念。目前已有三百八十一人学习下载适合在考前用于查漏补缺和强化记忆是一份能帮助备考者提升复习效率的章节精华汇总。1. 软考中级备考这份考点笔记解决的不只是“背什么”软件设计师中级考证的复习资料多到看不完但真正能落地用的不多。这份考点笔记精华版 docx 的价值在于它把数据结构、查找排序、表达式记法、编码体系这些高频考点做了压缩整理每个知识点后面直接跟真题思路比如哈夫曼编码、归并路数、堆排序判定这类易错题笔记里都给了公式和解法推导。对正在备考软考中级的从业者来说它解决的不是“有没有资料”的问题而是“哪些考点必须拿分、哪些地方最容易丢分”的问题。无论你是科班出身想要快速回顾还是半路转行需要系统突击这份笔记都能当复习主线用。2. 数据结构与存储邻接矩阵、存储结构、二叉树的考点对照2.1 邻接矩阵的度计算无向图看行和有向图看行列邻接矩阵是图的一种顺序存储方式用一个二维数组存放顶点间关系。笔记里反复强调的考点非常具体无向图的邻接矩阵是对称矩阵第 i 行元素之和就是顶点 i 的度。比如顶点 4 的度直接数第四行有几个非零元素即可。有向图则要分开算第 i 行元素之和是顶点 i 的出度第 j 列元素之和是顶点 j 的入度。实际做题时有个常见陷阱就是题目给的是带权图而非简单图矩阵里存的是权值而非 0/1。这时“行和”不能直接当度数算得先数非零元素个数。我在给 A 同学讲题时发现他在这里翻过车——把带权矩阵的数值累加当成度结果对不上标准答案。所以拿到题先确认是邻接矩阵还是带权矩阵再决定是数非零个数还是求和。# 邻接矩阵度计算的判别逻辑 def vertex_degree(matrix, vertex_index, directedFalse): 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 次方小于 62 的 3 次方大于等于 6。哈夫曼编码“face”要从根出发沿路径收集 0/1 编码方向是左 0 右 1。# 哈夫曼树 WPL 计算框架 import heapq class HuffmanNode: def __init__(self, weight, charNone): 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 次方减 1k 为层数。这两个概念经常和二叉排序树放在一起考。排序树强调值有序平衡树强调形状均衡满二叉树关注节点是否填满。复习时用一张表把定义、判定条件、典型应用列清楚做题时先判断题目问的是值序还是形态再套对应规则。3. 查找与排序算法复杂度对照与真题识别技巧3.1 二分查找与分块查找有序性前提和索引建法二分查找也叫折半查找前提是线性表有序且存储结构支持随机访问也就是顺序存储。算法逻辑是取中间位置记录与目标比较相等则找到目标小则在前半段继续目标大则在后半段继续。优点是比较次数少、速度快、平均性能好缺点是要求表必须有序插入删除困难。所以“不经常变动而查找频繁的有序表”是二分查找最典型的适用场景。分块查找是折中方案适用于节点动态变化的情况。它把大表分成若干块块内节点可以任意存放块与块之间必须有序——第 i 块所有节点的关键码值都小于第 i1 块所有节点。同时建一个索引表存放每块最大关键码值按块顺序排列。查找时先在索引表里定位块块内用顺序查找。平均查找长度是两个阶段查找长度之和这个公式在选择题里出现过。# 二分查找的边界处理模板 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 rightmid 取中间向下取整。如果目标值比中间值大左边界移到 mid1这是防止死循环的关键。很多人在手写时把 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(2i1) 的是小根堆反之是大根堆。四个选项一一代入验证即可这个直接验证比背堆排序过程快得多。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 前缀、中缀、后缀表达式三种记法的栈运算规则表达式记法是软考上午题的常客前缀表达式波兰式运算符在前中缀是我们平时写的 ab-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 入栈遇到 算 75 入栈遇到 × 算 356 入栈遇到 - 算 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 次顶元素”恰好与后缀相反。这个对称关系是记忆的关键。考试中有一类题是给中缀表达式让转后缀或者给后缀让转前缀。常见的做法是用栈处理运算符优先级但这需要画状态表比较费时。我一般用的是“完全括号化”方法把中缀表达式每步运算加上括号然后把运算符移到对应括号的右边后缀或左边前缀再删掉括号。例如 abc 先变成 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]。实际做题时题目给 n8问某码制可表示的最小负数是多少直接代公式算。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)现象题目问 n8 时补码定点整数的最小值写成 -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 分钟过四五张。考前一周每晚只做消消乐复盘不再刷整套模拟题。那次考试上午题的数据结构和算法部分基本没失分因为每个考点的解题入口都在笔记里标注过考场上看到题目就能直接映射到对应的处理流程。从那以后每次复习考证类资料我都强制走一遍“速过→卡壳标记→消消乐消卡→错题卡冲刺”的流程不再对着厚厚的教材做无效阅读。希望这份考点笔记也能帮你把有限的复习时间花在刀刃上软考中级一次过关。本文还有配套的精品资源点击获取