简介这份文档面向备考软考中级软件设计师的考生尤其适合需要系统梳理考点、攻克难点公式与易错点的复习阶段使用。内容围绕数据结构与算法主线展开涵盖邻接矩阵在无向图、有向图中的度与出入度计算顺序、链式、散列、索引等存储结构的适用场景以及二叉排序树、哈夫曼树与WPL计算、平衡二叉树、满二叉树等树结构要点查找部分讲解二分查找与分块查找的实现与优劣排序部分则逐一分析直接插入、简单选择、冒泡、希尔、快速、堆、归并、基数排序的过程及时间复杂度与稳定性对比。资源包共1个docx文件约3.37MB以文字笔记形式集中呈现公式、例题解析与易错提醒便于打印或对照刷题。目前已有382人学习适合作为考前查漏补缺的精华笔记使用。1. 软件设计师中级考什么从一道哈夫曼题看整张卷子的拿分逻辑很多人翻开软件设计师中级的真题第一反应是“知识点太散”——数据结构、排序、编码、指令系统全挤在一张卷子里。但真正拉开分差的往往不是那些背了就能答的定义题而是像哈夫曼编码这种“看着会、算起来翻车”的计算题。这类题在上午卷里稳定出现分值不高但极稳属于必须拿下的基础分。这份考点笔记精华版把邻接矩阵、哈夫曼树、排序复杂度、原码补码、表达式记法这些高频计算点集中整理配了公式和例题适合已经过了一遍教材、需要把“会看”变成“会算”的备考人。整场考试的核心逻辑就一句话概念题靠记忆计算题靠套路套路熟了分就稳了。2. 数据结构高频考点邻接矩阵、树与广义表的计算套路2.1 邻接矩阵的度、出度、入度怎么数邻接矩阵是图这一章的必考入口题目通常不问你“什么是邻接矩阵”而是直接给一个矩阵让你数度。无向图的邻接矩阵是对称的第 i 行元素之和就是顶点 i 的度有向图不对称第 i 行之和是出度第 j 列之和是入度。笔记里举的例子很典型顶点 4 的度就是第四行的和顶点 3 的出度和入度分别是 5 和 16。这类题面试官出题人最想看到的是你分清“行还是列”而不是背定义。答题时按三步走先判断图是有向还是无向无向只看行有向行看出、列看入再逐行或逐列累加注意矩阵里存的是 0/1 还是权值最后核对对称性无向图如果算出来不对称基本就是数错了。容易翻车的地方是把有向图的入度也按行去加或者把带权矩阵的权值当成 1 来数。2.2 二叉排序树、平衡二叉树、满二叉树的判定树结构这一块真题喜欢用“下列说法正确的是”来考判定。二叉排序树的核心性质是左子树所有节点小于根、右子树所有节点大于等于根中序遍历得到递增序列关键字最大的结点可以有左子树但一定没有右子树。平衡二叉树AVL 树的判定标准是左右子树高度差的绝对值不超过 1且左右子树本身也是平衡二叉树。满二叉树则是除最后一层外每层结点都有两个子结点。这类题通常这么答先看中序序列是否递增不递增直接排除二叉排序树再算每个结点左右子树高度差出现大于 1 的就不是 AVL满二叉树看结点总数是否为 2 的 k 次方减 1。面试官最想听的是你按性质逐条验证而不是凭印象选。2.3 哈夫曼树与 WPL 计算一道真题拆开讲哈夫曼树是带权路径长度WPL最短的树权值越大的叶子越靠近根。真题里给字符频率表第一问求定长编码码长第二问求“face”的哈夫曼编码。定长编码看字符个数6 个字符用 3 位二进制000 到 101就够所以码长选 3。哈夫曼编码则要先构造树每次取两个最小权值合并左小右大左 0 右 1再从根走到目标字符读出路径。import heapq def huffman_codes(freq): # freq: {a: 频率, ...} heap [[w, [ch, ]] for ch, w in freq.items()] heapq.heapify(heap) while len(heap) 1: lo heapq.heappop(heap) # 最小权值 hi heapq.heappop(heap) # 次小权值 for pair in lo[1:]: pair[1] 0 pair[1] # 左分支补 0 for pair in hi[1:]: pair[1] 1 pair[1] # 右分支补 1 heapq.heappush(heap, [lo[0] hi[0]] lo[1:] hi[1:]) return sorted(heap[0][1:], keylambda p: (len(p[-1]), p)) freq {a: 45, b: 13, c: 12, d: 16, e: 9, f: 5} for ch, code in huffman_codes(freq): print(ch, code)这段代码用最小堆模拟“每次取两个最小权值合并”的过程lo和hi分别代表左、右子树左分支统一补 0、右分支补 1最后按编码长度排序输出。参数freq就是题目给的频率表换成真题数据直接能跑出编码。考试时不需要写代码但用代码验证一遍能帮你确认手工构造的树没搭错。易错点是左右子树权值写反导致 0/1 颠倒以及忘记“权值大的靠近根”这条检验标准。2.4 广义表的长度与深度广义表考的是数括号。长度是删掉最外层括号后剩下的元素个数深度是括号的层数。笔记里的例子L1((a,(a,b),((a,b),c)))长度 1、深度 4L2((1,2,3))长度 1、深度 2L3(1,2,3)长度 3、深度 1。答题时先数最外层逗号分隔了几块定长度再逐层往里数括号定深度。常见错误是把 L2 的长度数成 3忘了它外面还套了一层括号整体只算一个元素。3. 排序与查找高频考点复杂度表格背后的必考题3.1 八种排序的时间复杂度与稳定性对比排序这一章的真题几乎绕不开“哪个排序最坏是 O(n²)”“哪个不稳定”。笔记里那张对比表就是标准答案来源直接背下来比现场推更稳。排序方法最好平均最坏辅助空间稳定性直接插入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(1)“快速排序最坏情况”选 O(n²)都是这张表直接对应。3.2 堆的判定一道选择题的完整思路真题给四个序列问哪个是堆。堆的定义是任一结点都不大于或不小于其左右孩子用数组下标表示就是 k[i] ≤ k[2i] 且 k[i] ≤ k[2i1]小顶堆。笔记里答案是 B(10,18,15,20,50,80,30,60)。验证方法是从最后一个非叶结点往前逐个查下标 4 的 20 和它的孩子 50、80 比20 最小下标 3 的 15 和孩子 30、60 比15 最小下标 2 的 18 和孩子 20、50 比18 最小下标 1 的 10 自然最小。全部满足就是小顶堆。这类题通常这么答先确定是小顶堆还是大顶堆再从 n/2 向下取整的位置开始往前验证任何一处违反父子关系就排除。易错点是只看了前几个元素就下结论或者把完全二叉树的下标关系记错左孩子是 2i 不是 2i-1。3.3 二分查找与分块查找的适用条件二分查找要求表有序且不常变动、查找频繁优点是比较次数少、速度快缺点是插入删除困难。分块查找适合结点动态变化的情况块间有序、块内无序先查索引表再查块内速度比顺序查找快但不如二分。真题常问“哪种查找适合动态变化”答案就是分块查找。答题时抓住“有序”和“动态”两个关键词就能区分有序静态选二分动态变化选分块无序小表选顺序。3.4 归并路数的公式题归并路数公式是 k ⌈logₘn⌉ 的反用笔记里写作归并路数 |logₖm|其中 m 为元素个数、k 为多路归并趟数。真题27 个元素只进行三趟多路归并求归并路数。代入 log 以 3 为底 27 的对数等于 3选 B。这类题就是套公式易错点是把“趟数”和“路数”代反看到“三趟”就把 3 放在底数位置别放错。4. 计算机基础高频考点编码、表达式与指令系统4.1 原码、反码、补码、移码的转换与范围符号数编码是上午卷的固定考点。正数的原码、反码、补码都等于自身二进制负数的原码符号位为 1反码符号位不动其余取反补码在反码基础上加 1移码无论正负把补码符号位取反即可。应用上最适合加减运算的是补码最适合表示浮点数阶码的是移码。范围记忆用笔记里的技巧设 A2^(n-1)B1-2^(-(n-1))则原码和反码的定点整数范围是 [-(A-1), A-1]补码和移码是 [-A, A-1]定点小数原码反码是 [-B, B]补码移码是 [-1, B]。真题常考“补码能表示的最小整数”记住补码比原码多表示一个 -2^(n-1) 就行。易错点是负数补码忘记加 1或者移码和补码的符号位关系记反。4.2 前缀、中缀、后缀表达式的求值三种表达式考的是栈的操作方向。前缀表达式从右往左扫描遇数字压栈遇运算符弹出栈顶两个数做“栈顶 op 次顶”的运算后缀表达式从左往右扫描遇运算符做“次顶 op 栈顶”的运算。笔记里前缀“- × 3 4 5 6”算出 29后缀“3 4 5 × 6 -”也算出 29两者等价。def eval_postfix(expr): stack [] for token in expr.split(): if token in -*/: b stack.pop() # 栈顶 a stack.pop() # 次顶 if token : stack.append(a b) elif token -: stack.append(a - b) elif token *: stack.append(a * b) else: stack.append(a // b) else: stack.append(int(token)) return stack[0] print(eval_postfix(3 4 5 * 6 -)) # 输出 29代码里b先弹出是栈顶、a后弹出是次顶减法除法必须用a - b、a // b顺序反了结果就错。参数就是空格分隔的表达式字符串考试时手工算也按这个顺序。易错点集中在前缀表达式的“栈顶 op 次顶”和后缀的“次顶 op 栈顶”容易记混建议各手算三遍形成肌肉记忆。4.3 指令寻址方式的速度排序立即寻址操作数直接在指令里获取最快直接寻址操作数地址在指令中寄存器寻址操作数在寄存器中寄存器间接寻址操作数地址在寄存器中。真题常问“获取操作数最快的方式”选立即寻址。答题时按“操作数离 CPU 越近越快”排序指令内 寄存器 内存。易错点是把寄存器寻址和寄存器间接寻址混为一谈前者拿的是操作数本身后者拿的是地址。4.4 CPU 组成与控制器职责CPU 由运算器、控制器、寄存器和内部总线组成。控制器不仅要保证程序正确执行还要能处理异常事件。真题会问“控制器的作用”或“CPU 包含哪些部件”按笔记原文答即可。这类概念题不需要展开记准“运算器管算、控制器管指挥和异常”这条分工就不会选错。5. 易错点集中营五类最容易丢分的题5.1 邻接矩阵行列入度出度数反错在哪有向图里把入度也按行去加。为什么错行对应出度、列对应入度这是定义决定的不是习惯问题。怎么答对动笔前先在矩阵旁标“行出、列入”加完行再核对列无向图则只加行并检查对称。5.2 哈夫曼编码左右子树颠倒错在哪构造树时把大权值放左边或者 0/1 赋值反了。为什么错哈夫曼树只要求 WPL 最短左右顺序本身不唯一但题目通常约定左小右大、左 0 右 1不按约定读出的编码就和选项对不上。怎么答对严格按“取两个最小、左小右大、左 0 右 1”操作最后用“权值大的离根近”验一遍。5.3 排序稳定性记混错在哪把快速排序当成稳定排序或者以为希尔排序有明确的最坏复杂度。为什么错快排跨元素交换会破坏相对次序希尔排序的复杂度与增量序列有关笔记里明确写“不存在”。怎么答对只记稳定四兄弟——插入、冒泡、归并、基数其余全不稳定希尔的最好最坏都答“不存在”。5.4 补码范围少算一个数错在哪把补码定点整数范围写成和原码一样的 [-(A-1), A-1]。为什么错补码的 0 只有一种表示省出的编码用来表示 -2^(n-1)所以下界多一个。怎么答对看到补码和移码整数范围直接写 [-A, A-1]小数写 [-1, B]和原码反码区分开。5.5 表达式求值弹出顺序搞反错在哪后缀表达式里用栈顶减次顶。为什么错后缀是“次顶 op 栈顶”前缀才是“栈顶 op 次顶”两者方向相反。怎么答对后缀从左扫、前缀从右扫减法除法先写对顺序再算算完用中缀还原验证一次。6. 考前抢分把公式和易错点压成一张答题卡到了冲刺阶段最有效的动作不是再刷一遍教材而是把计算类考点压成一张能反复过目的答题卡。我的做法是按“公式—例题—易错点”三列整理邻接矩阵写“无向行和度、有向行和出度列和入度”哈夫曼写“取两最小、左小右大、左 0 右 1、WPLΣ权×路径长”排序写“稳定四兄弟、快排最坏 n²、归并空间 n”编码写“补码移码 [-A, A-1]、加减用补码、阶码用移码”表达式写“后缀次顶 op 栈顶、前缀栈顶 op 次顶”。每列后面跟一道真题编号过一遍公式就手算一道算错立刻回看易错点那一条。考点一句话公式对应易错点邻接矩阵无向行和度有向行和出度、列和入度入度按行加哈夫曼取两最小合并左 0 右 1WPLΣ权×路径左右颠倒排序复杂度稳定插入冒泡归并基数快排最坏 O(n²)快排当稳定补码范围整数 [-2^(n-1), 2^(n-1)-1]少算一个数表达式后缀次顶 op 栈顶弹出顺序反这张表不用背得多漂亮关键是每天过一遍后立刻动手算算完对照易错点自查。血泪经验是计算题丢分从来不是因为不会而是因为“以为会了”就跳过手算上了考场一紧张顺序就乱。从那以后我每次复习这类考点都强制走一遍“读公式—手算例题—对答案—标易错”的流程哪怕题再简单也不省这一步。希望帮到你。本文还有配套的精品资源点击获取