简介这份《软件设计师中级——考点笔记精华版》面向备考软考中级软件设计师的考生尤其适合需要系统梳理核心考点、攻克难点公式与易错点的复习阶段使用。文档围绕数据结构、树结构、查找与排序方法等高频考点展开涵盖邻接矩阵、顺序与链式存储、散列与索引存储、二叉排序树、哈夫曼树与WPL计算、平衡二叉树、二分查找、分块查找以及直接插入、希尔、快速、堆、归并、基数等排序算法的时间复杂度与稳定性对比并配有典型例题解析便于对照理解与查漏补缺。资源包共1个docx文件约3.37MB内容以考点笔记与例题讲解为主结构清晰适合按模块检索学习。目前已有381人学习下载可作为备考路上的系统复习资料帮助考生在有限时间内巩固知识框架、提升解题能力。1. 从一份 docx 说起软考中级软件设计师的考点笔记到底能省多少事很多人备考软件设计师中级的第一反应是买教材、刷真题但真正拖慢进度的往往不是题不会做而是知识点散落在三四本书里查一个「邻接矩阵求度」要翻半天。这份《软件设计师中级——考点笔记精华版 .docx》解决的就是这个问题它把数据结构、查找排序、系统基础、指令系统这几块高频考点压缩成一份可检索的文档公式、例题、对比表都在同一页里。它适合两类人一是已经过了一遍教材、需要快速回查公式和结论的二战考生二是时间紧、想直接抓高频考点的在职备考者。不适合零基础第一遍学因为笔记是压缩过的没有铺垫。下面我按「怎么用这份笔记 → 核心考点怎么落地 → 坑在哪」的顺序拆开讲。2. 数据结构核心考点邻接矩阵、存储结构与二叉树怎么快速回查2.1 邻接矩阵求度无向图和有向图的区别邻接矩阵是图在内存里最直观的表示方式但考试里最容易混的是「行和」和「列和」分别代表什么。笔记里给了一个很干脆的结论无向图的邻接矩阵是对称的第 i 行的元素之和就是顶点 i 的度有向图不对称第 i 行之和是出度第 j 列之和是入度。这个结论看起来简单但考场上经常换个问法给你一个邻接矩阵问某个顶点的度是多少。我的习惯是先把矩阵画出来标上行号列号然后按方向加。下面用 Python 把笔记里的逻辑跑一遍方便你验证自己的手算结果。# 邻接矩阵求度无向图行和度有向图行和出度、列和入度 import numpy as np # 无向图邻接矩阵示例对称 undirected np.array([ [0, 1, 1, 0], [1, 0, 0, 1], [1, 0, 0, 1], [0, 1, 1, 0] ]) # 有向图邻接矩阵示例不对称 directed np.array([ [0, 1, 0, 1], [0, 0, 1, 0], [1, 0, 0, 0], [0, 0, 1, 0] ]) print(无向图各顶点度, undirected.sum(axis1)) # 行和 print(有向图各顶点出度, directed.sum(axis1)) # 行和 print(有向图各顶点入度, directed.sum(axis0)) # 列和逻辑说明sum(axis1)是按行求和对应出度或无向图的度sum(axis0)是按列求和对应入度。参数上唯一要注意的是矩阵必须是方阵且对角线为 0无自环。如果题目给了自环对角线为 1行和里会多算一次自身需要单独减掉。2.2 顺序存储 vs 链式存储什么时候用哪个笔记里把存储结构分成顺序、链式、散列、索引四类考试最常考的是前两种的取舍。顺序存储用连续地址支持随机访问查第 k 个元素是 O(1)但插入删除要挪元素平均移动 n/2 个。链式存储用任意存储单元插入删除只改指针但查找必须从头遍历。判断标准很简单频繁查询用顺序频繁插入删除用链式。双链表比单链表多一个前驱指针灵活度更高但每个节点多一个指针域的开销。考试里如果问「哪种存储结构适用于频繁插入删除」直接选链式问「哪种支持随机访问」选顺序。2.3 二叉排序树与哈夫曼树构造和 WPL 计算二叉排序树的性质笔记里写得很清楚左子树所有节点小于根右子树所有节点大于等于根中序遍历得到递增序列。这里有个容易忽略的点——关键字最大的节点可以有左子树但一定没有右子树。因为如果有右子树右子树里的值会比它大矛盾。哈夫曼树的构造是考试高频。步骤是每次从权值集合里取两个最小的合并成一个新节点新节点权值为两者之和放回集合重复直到只剩一个节点。WPL 等于所有叶子节点的权值乘以路径长度之和。笔记里给了一道「face」编码的例题答案是 BA思路是先构造哈夫曼树再按左 0 右 1 走路径。# 哈夫曼树构造与WPL计算 import heapq def huffman_wpl(weights): heap weights[:] heapq.heapify(heap) total 0 while len(heap) 1: a heapq.heappop(heap) b heapq.heappop(heap) merged a b total merged # 每次合并的权值累加即为WPL heapq.heappush(heap, merged) return total # 笔记例题中的字符频率示例 weights [5, 7, 10, 15, 20, 43] print(WPL , huffman_wpl(weights))逻辑说明heapq是小顶堆每次弹出两个最小值。total merged累加的是每次合并产生的新节点权值这个累加值恰好等于 WPL不需要额外算路径长度。参数上weights是各叶子节点的权值列表长度至少为 2。如果只有一个节点WPL 为 0。3. 查找与排序二分查找、分块查找和八大排序的对比记忆3.1 二分查找的边界条件与实现二分查找的前提是有序表优点是比较次数少、查找速度快缺点是插入删除困难。笔记里强调了适用场景不经常变动而查找频繁的有序列表。实现上最容易翻车的是边界条件——low high还是low highmid要不要加一减一。# 二分查找标准实现 def binary_search(arr, target): low, high 0, len(arr) - 1 while low high: # 注意是 mid (low high) // 2 if arr[mid] target: return mid elif arr[mid] target: low mid 1 # 注意 1 else: high mid - 1 # 注意 -1 return -1 arr [1, 3, 5, 7, 9, 11, 13] print(binary_search(arr, 7)) # 输出 3逻辑说明low high保证区间为空时退出mid 1和mid - 1避免死循环。参数上arr必须是有序数组升序降序都可以但比较符号要对应改。如果数组有重复元素这个实现返回的是其中一个位置不保证是第一个或最后一个。3.2 分块查找的索引表设计分块查找适合节点动态变化的情况比顺序查找快但不如折半查找。核心是「块间有序、块内无序」第 i 块所有节点的关键码都小于第 i1 块。索引表存每块的最大关键码查找时先在索引表里定位块再在块内顺序查找。平均查找长度 ASL 的公式是(n/s s)/2 1其中 n 是总节点数s 是每块节点数。最优的 s 是 √n此时 ASL 最小。考试里如果问「分块查找的索引表怎么建」答「取每块最大关键码按块顺序存放」。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(nrd))O(d(nrd))O(d(nrd))O(rd)稳定记忆技巧稳定的排序有「插入、冒泡、归并、基数」其余不稳定。快速排序最坏退化到 O(n²)归并排序需要 O(n) 额外空间堆排序原地且最坏也是 O(nlog₂n)。3.4 堆排序的判断题怎么快速排除笔记里给了一道堆的判断题答案是 B。判断方法把序列按完全二叉树画出来检查每个父节点是否都小于等于或大于等于子节点。选项 B 是(10,18,15,20,50,80,30,60)画出来每个父节点都小于子节点是小顶堆。选项 A 里 50 的子节点 30 比它小不满足。选项 C 里 80 的子节点 30 比它小不满足。选项 D 里 30 的子节点 20 比它小不满足。4. 系统基础与表达式求值原码补码、前缀后缀和指令寻址4.1 原码、反码、补码、移码的转换规则笔记里把四种码制的规则写得很紧凑正数的原码、反码、补码相同负数的反码是符号位不动、其余取反补码是反码加一移码是补码符号位取反。应用场景加减运算用补码浮点数阶码用移码。机器字长为 n 时补码的定点整数范围是[-2^(n-1), 2^(n-1)-1]比原码和反码多表示一个负数。这个「多一个」是考试常考点因为 0 在补码里只有一种表示。4.2 前缀、中缀、后缀表达式的求值前缀表达式从右至左扫描遇到数字压栈遇到运算符弹出两个数计算栈顶 op 次顶结果入栈。后缀表达式从左至右扫描遇到数字压栈遇到运算符弹出两个数计算次顶 op 栈顶结果入栈。注意两者的操作数顺序是反的这是最容易错的地方。# 后缀表达式求值 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] print(eval_postfix(3 4 5 * 6 -)) # 输出 29逻辑说明b先弹出是栈顶a后弹出是次顶计算时是a op b。参数上表达式用空格分隔只支持整数和四则运算。如果要做前缀求值把expr.split()改成reversed(expr.split())同时a和b的弹出顺序对调。4.3 指令寻址方式的速度排序笔记里列了四种寻址立即寻址、直接寻址、寄存器寻址、寄存器间接寻址。获取操作数最快的是立即寻址因为操作数直接在指令里寄存器寻址次之操作数在寄存器里直接寻址要访问一次内存寄存器间接寻址要访问两次先读寄存器拿地址再读内存拿数据。考试里如果问「哪种寻址方式获取操作数最慢」选寄存器间接寻址。如果问「哪种不需要访问内存」选立即寻址和寄存器寻址。5. 避坑与排查这份笔记用错姿势的五个血泪教训5.1 把笔记当教材零基础直接啃现象翻开笔记第一页就是邻接矩阵的行和列和没有图的基础概念看了半小时不知道在说什么。原因这份笔记是压缩过的考点精华默认你已经过了一遍教材。解决先花两天把教材里数据结构的基础章节翻一遍再回来用笔记做回查和刷题。5.2 只背结论不推过程题目换个问法就翻车现象记住了「无向图行和是度」但题目给的是有向图问入度顺手也按行和算了。原因笔记里的结论是成对出现的背的时候只背了一半。解决每一条结论都自己画一个 3×3 的矩阵验证一遍手算行和列和确认方向。5.3 排序稳定性记混选择题连续丢分现象快速排序和归并排序的稳定性记反了考试里连错两道。原因稳定性没有统一的推导逻辑纯靠背容易混。解决用「稳定 相等元素排序后相对位置不变」这个定义去推插入、冒泡、归并、基数都满足其余不满足。5.4 哈夫曼树构造时左小右大搞反现象WPL 算对了但编码题选错了因为左 0 右 1 的赋值和题目要求反了。原因笔记里写了「通常做题时写成左小右大的形式」但没说死。解决构造时严格按左小右大赋值时左 0 右 1如果题目有特殊要求以题目为准。5.5 表达式求值搞混操作数顺序现象后缀表达式算出来结果不对检查发现a和b弹反了。原因前缀和后缀的操作数顺序是反的笔记里用「注意与后缀表达式做比较」提醒了但容易忽略。解决后缀是「次顶 op 栈顶」前缀是「栈顶 op 次顶」写代码时把变量名标清楚。6. 进阶用法把 docx 笔记转成可检索的刷题卡片这份笔记最大的价值不是读一遍而是反复回查。我的习惯是把 docx 里的每个考点拆成一张问答卡片用 Python 脚本批量生成导入 Anki 或任何支持间隔重复的工具。下面是一个最小实现把笔记里的「结论句」抽出来自动生成「问题 → 答案」对。# 把考点笔记转成问答卡片 import re notes 无向图邻接矩阵第i行元素的和即为顶点i的度 有向图邻接矩阵第i行元素之和为顶点i的出度 有向图邻接矩阵第j列元素之和为顶点j的入度 顺序存储结构适用于频繁查询时使用 链式存储结构适用于较频繁地插入删除更新元素时使用 二分查找法要求待查表为有序表 def make_cards(text): cards [] for line in text.strip().split(\n): line line.strip() if not line: continue # 按「即为」「为」「适用于」「要求」切分 for sep in [即为, 适用于, 要求]: if sep in line: q, a line.split(sep, 1) cards.append((q.strip() , a.strip())) break else: if 为 in line: q, a line.split(为, 1) cards.append((q.strip() , a.strip())) return cards for q, a in make_cards(notes): print(fQ: {q}\nA: {a}\n)逻辑说明make_cards按关键词切分句子生成问答对。参数上notes是笔记里的结论句每行一条。切分关键词可以根据你的笔记内容调整比如加上「是指」「包括」等。生成的结果可以直接导出成 CSV再导入刷题工具。我一般会把这个脚本跑一遍把生成的卡片过一眼手动修掉切分错误的条目。从那以后我每次拿到新的考点笔记都强制走一遍「拆卡片 → 刷三天 → 回查错题」的流程比单纯读三遍效果好得多。希望帮到你。本文还有配套的精品资源点击获取