简介一份针对软件设计师中级资格考试的考点笔记精华版以Word文档形式系统整理了软考核心知识体系适合正在系统复习或考前冲刺的考生。内容覆盖高频考点数据结构存储方式顺序、链式、散列、索引的适用场景邻接矩阵在有向图与无向图中的度计算满二叉树、平衡二叉树的判定性质以及哈夫曼树的构造与带权路径长度求解。查找部分梳理了二分查找、分块查找的条件与实现步骤排序部分则汇总了直接插入、简单选择、冒泡、希尔、快速、堆、归并等常用算法并对比了它们的时间复杂度、稳定性与适用数据规模。笔记还集中标注了难点公式、易错点与典型例题便于考生快速定位薄弱环节。文档内特别收录了哈夫曼编码、查找长度计算等典型例题解析以及常见错误提醒能帮助读者在实战中加深理解。整个资源包为单个Word文档约3.37MB下载后可按需翻阅目前已吸引381位学习者。对备战软考中级的考生而言这份浓缩考点笔记可作为高效复习的实用参考资料。1. 软考软件设计师考点地图先抓住数据结构与算法这条主线软件设计师中级考试的知识面铺得很开但把历年真题和这本考点笔记对照着看会发现数据结构与算法才是真正的分值大头也是“学懂了能一直拿分、学不懂只能靠蒙”的区分度所在。这份考点笔记精华版把散落在教材各处的难点公式、易错结论集中整理了出来比如邻接矩阵的度与出/入度计算、哈夫曼树的构造与 WPL 求解、八大排序的时间复杂度对比、原码反码补码移码的数值范围都是考场上反复出现的“固定套路”。我们备考时最大的误区是把时间平均分配给所有章节结果每个模块都只混了个脸熟。正确的策略是先把数据结构、算法、计算机组成原理这三块核心吃透再回头补软件工程、数据库等记忆型内容。这篇笔记就是按这个思路来的——先讲清楚知识地图的全貌再逐个模块拆解重点最后落到一份可以直接照着查漏补缺的复习清单上。无论你现在是刚过完第一遍教材还是已经进入刷题阶段这份梳理都能帮你快速定位“自己到底哪里还欠着火候”。2. 图与存储结构邻接矩阵、四种存储方式的选择题套路2.1 邻接矩阵无向图看行和有向图分出入邻接矩阵是图这章最常考的知识点题型很固定给你一个矩阵让你算某个顶点的度、出度或入度。笔记里的结论可以直接背下来——无向图的邻接矩阵第 i 行元素之和就是顶点 i 的度有向图的第 i 行元素之和是顶点 i 的出度第 j 列元素之和是顶点 j 的入度。举个例子一个无向图有 5 个顶点邻接矩阵第 4 行的元素是 0、1、1、0、0那顶点 4 的度就是这行求和等于 2。这背后的原理很简单无向图的边在矩阵里是对称存储的顶点 i 与哪些顶点相连第 i 行就有多少个 1而有向图里行代表“从这个顶点出发的弧”列代表“指向这个顶点的弧”。最容易翻车的地方在于矩阵的行列下标从 0 还是从 1 开始计。有的题目给的是 1 到 n 的编号有的直接给矩阵让你自己数行号审题时先确认顶点编号规则否则算出来刚好差一个“偏移量”。2.2 四种存储结构适用场景是选择题的高频考点存储结构这块笔记里总结的四种方式——顺序、链式、散列、索引——几乎是每年必考 2 到 3 分的记忆型题目。直接照笔记的结论整理存储结构核心特征适用场景典型例子顺序存储地址连续的存储单元依次存放频繁查询数组链式存储任意存储单元物理可连续可不连续频繁插入、删除、更新单链表、双链表散列存储存储位置与关键码建立确定对应关系高效查找键值对哈希表索引存储索引表 指向数据页的逻辑指针数据库检索数据库索引链式存储是三者的比较重头戏。笔记里特别点明双链表因为有两个指针域灵活度优于单链表但开销更大。这个“灵活度 vs 开销”的权衡就是选择题最爱挖的坑——题目说“某应用需要频繁删除节点请选择存储结构”如果你选了顺序存储那基本就是送分给别人了。散列存储的关键词是“键值对”和“确定对应关系”注意它并不是把元素按大小顺序排列而是通过散列函数直接算出存储位置。索引存储则要区分清楚索引本身是一个单独的物理数据库结构它是列值的集合和指向数据页的逻辑指针清单重点在“逻辑指针”四个字。2.3 链式结构的三兄弟单链表、循环链表、双链表的辨析链表家族在笔记里占了不少篇幅主要考查不同链表的操作特点。单链表只能从头到尾单向遍历适合“只关心后继”的场景循环链表把尾节点的指针指向头节点解决了“走到头回不去”的问题双链表每个节点有两个指针域既能向前也能向后代价是每个节点多占一个指针的存储空间。做题时记住一个口诀要频繁找前驱就用双链表要循环遍历就用循环链表普通场景单链表就够了。另外“删除节点”这个操作在三种链表里的代价也不同——单链表删除要知道前驱节点只能从头找双链表直接通过前驱指针就能完成这就是双链表“灵活度优于单链表”的具体体现。提示考试里常把“顺序存储适合频繁查询链式存储适合频繁插入删除”和“数组 vs 链表”的选择题混在一起考本质是一个知识点记住适用场景比记住定义更重要。3. 树与查找方法二叉排序树、哈夫曼树到二分与分块查找3.1 二叉排序树左小右大中序遍历必递增二叉排序树是树结构里最基础也最常考的一种。它的定义有三个要点左子树非空时左子树上所有节点值都小于根节点右子树非空时右子树上所有节点值都大于等于根节点左右子树本身也都是二叉排序树。这里注意“大于等于”和“小于”是不对称的——右子树允许等于根节点的值这是很多人会忽略的细节。二叉排序树有一个非常重要的性质中序遍历它得到的一定是一个递增序列。这个性质经常被用来出判断题比如“对一棵二叉排序树进行中序遍历输出的序列一定是从小到大排列的”答案就是正确。反过来如果题目给你一个序列让你判断它是否可能是某棵二叉排序树的中序遍历结果那只要看它是否递增即可。还有一个易漏点关键字最大的节点可以有左子树但一定没有右子树。这个结论的理由很简单——如果它有右子树右子树上必然有比它更大的值矛盾。考试中可能出现“以下关于二叉排序树的说法哪个是错误的”这类题这个细节就是用来区分认真复习和走马观花的。3.2 哈夫曼树与 WPL构造步骤和编码计算是计算题主力哈夫曼树也叫最优二叉树核心定义是带权路径长度WPL最短。笔记那一道例题非常典型6 个字符 a、b、c、d、e、f 及其频率第一问考定长编码的码长第二问考哈夫曼编码。先解决定长编码6 个字符用二进制表示至少需要 3 位2^24 不够2^38 够所以码长为 3 位。第二问的哈夫曼编码则要动手画树。构造规则是每次从森林中选两个权值最小的节点合并新节点的权值为二者之和重复直到只剩一棵树。注意做图时有一个不成文的约定——通常写成左小右大的形式然后左分支赋 0、右分支赋 1。编码一个字符序列时比如“face”就是从根节点出发分别找到 f、a、c、e 四个字符所在的叶子节点把路径上的 0/1 串拼接起来。这题的四个选项里只有 B 选项符合要求。血泪经验是很多人构造哈夫曼树时把“左小右大”当成强制规则但实际它只是方便我们统一赋值的习惯并不影响编码的正确性只要保证每次取两个最小权值合并、赋值规则一致即可。WPL 的计算也要会WPL 所有叶子节点的权值 × 对应路径长度之和也就是编码总长度。考试中常见两种考法给字符频率让你构造哈夫曼树并求 WPL或者给一棵已构造好的哈夫曼树让你直接数路径长度算 WPL。后者更简单前者需要你熟练树的合并过程。3.3 平衡二叉树与满二叉树定义辨析概念题别再丢分平衡二叉树AVL 树的定义是它是一棵空树或者它的左右两个子树的高度差的绝对值不超过 1并且左右两个子树也都分别是平衡二叉树。注意这个定义是递归的——不仅根节点要平衡每一棵子树也都要平衡。考试中常见的坑是把“平衡”理解为“左右子树节点数一样”但实际衡量的是“高度差”。一个极端例子左子树有 3 层、右子树有 2 层高度差为 1是平衡的但左子树有 10 个节点、右子树只有 3 个节点只要高度差不超过 1仍然算平衡二叉树。满二叉树的定义相对简单除最后一层外每一层上的所有节点都有两个子节点最后一层是叶子节点0 个子节点。注意满二叉树和完全二叉树的区别——完全二叉树允许最后一层从左到右连续缺失右侧叶子而满二叉树不允许任何缺失。这个辨析在选择题里几乎年年出现复习时一定要分开记。3.4 二分查找与分块查找适用条件、平均查找长度二分查找法折半查找法的适用条件很苛刻不经常变动且查找频繁的有序列表。笔记里总结了它的一大堆优点——比较次数少、查找速度快、平均性能好缺点也很明确——要求待查表必须有序且插入删除困难。实现算法的核心就是“掐头去尾取中间”假设表中元素按升序排列把中间位置记录的关键字与查找关键字比较。相等则成功中间记录的关键字大于查找关键字则在前一子表继续小于则在后一子表继续。重复直到找到或子表不存在。这里要特别留意的是“中间位置”的取法——当表长为偶数时中间位置通常取下整。有些题目会专门考“查找第几次能命中”本质上就是在模拟这个二分过程。分块查找是介于顺序查找和折半查找之间的方法适用节点动态变化的情况。它的思路分两步先把大线性表分解成若干块块内的节点可以任意存放但块与块之间必须有序然后建立一个索引表存每块的最大关键码值。查找时先在索引表中确定节点所在块因为索引表有序可用顺序查找或折半查找然后在块内顺序查找。分块查找的平均查找长度公式要记牢假设线性表共有 n 个节点分成大小相等的 b 块每块有 s n/b 个节点则平均查找长度为 (b1)/2 (s1)/2也就是索引表查找的平均长度加块内查找的平均长度。这个公式在计算题里出现过别只记概念不记公式。注意二分查找的“有序”是硬性前提分块查找的“块间有序”是软性前提。题目只要说“表是动态变化的”二分查找基本可以直接排除因为插入删除太困难了。4. 八大排序算法全梳理复杂度对比、堆判断与归并路数4.1 三大基础排序插入、选择、冒泡的适用场景直接插入排序的思路特别生活化——像斗地主抽牌每来一张新牌就插入到手里已经排好序的牌中。每一趟把一个待排序记录按关键字大小插入到有序队列的合适位置直到全部插入完成。它最好的时间复杂度是 O(n)平均和最坏都是 O(n²)是稳定的排序方法。适用场景是数据量不大的情况。简单选择排序则是每趟从待排序记录中选出关键字最小的记录顺序放在已排序序列的末尾。它的时间复杂度无论什么情况都是 O(n²)因为即使序列已经有序每一趟仍然要扫描剩余的所有元素找出最小值。这是它与直接插入排序最大的区别——插入排序在序列基本有序时能提前结束选择排序不行。不稳定这点常考。冒泡排序是两两比较、交换不满足顺序要求的数对直到整个表有序。最好情况 O(n)表已经有序一趟下来没有交换即可提前结束平均和最坏 O(n²)是稳定的。它适合对稳定性要求高的情况但效率偏低大规模数据不推荐。4.2 进阶排序希尔、快速、堆与归并的思路差异希尔排序是直接插入排序的改进版把记录按步长 gap 分组每组用直接插入排序随着步长逐渐减小分组包含的记录越来越多当步长减小到 1 时整个数据合成一组完成排序。希尔排序的平均时间复杂度约 O(n^1.3)空间 O(1)不稳定。注意它“不存在”一个精确的最好或最坏复杂度分析考试记平均即可。快速排序是分治法的典型应用一趟排序把数据分割成独立的两部分分割点左边都比它小、右边都比它大然后递归处理两部分。最好和平均都是 O(nlog₂n)最坏 O(n²)——最坏情况发生在每次分割都极端不平衡时比如序列已经有序却每次选第一个元素作基准。空间复杂度 O(log₂n)递归栈不稳定。它通常是所有排序里实际运行最快的但“最坏 O(n²)”这个结论必须记牢。归并排序也是分治把序列看成 n 个长度为 1 的有序序列相邻两两归并得到 n/2 个长度为 2 的有序表再归并……直到得到一个长度为 n 的有序序列。无论什么情况时间复杂度都是 O(nlog₂n)但需要 O(n) 的辅助空间是稳定的。它的代价是额外空间这在“空间受限”的场景题里是不选它的理由。堆排序基于堆这种数据结构时间复杂度无论好坏都是 O(nlog₂n)空间 O(1)不稳定。它有点“原地排序 高效稳定时间”的组合优势但实际常数比快速排序大所以工程上不常直接用。4.3 基数排序不比较关键字的神奇排序基数排序和其他七种排序本质不同——它不比较关键字的大小而是根据关键字中各位的值通过对 n 个元素进行若干趟“分配”与“收集”来实现排序。笔记里的例子很直观初始序列 {50, 123, 543, 187, 49, 30, 0, 2, 11, 100}先把 0~9 视为 10 个桶按个位数分配到桶中然后按桶编号 0 到 9 依次取出得到个位数递增的序列再对十位数、百位数重复这个过程。基数排序的时间复杂度是 O(d(nrd))其中 d 是关键字的位数趟数rd 是基数十进制就是 10空间 O(rd)是稳定的。从复杂度公式可以看出如果数字位数很多效率会下降但基数固定时它比 O(nlog₂n) 的比较排序更快适合数值范围大但位数少的场景。4.4 复杂度对比口诀与堆判断例题八大排序的时间复杂度对比是每年必考的表格题这里整理成一张速查表排序方法最好时间平均时间最坏时间辅助空间稳定性直接插入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(nlog₂n) 里归并稳定快排和堆排不稳定。这一组对比能帮你秒杀掉大多数选择题。堆排序的判断例题也很有代表性。题目给了四个序列问哪个是堆。我们需要验证序列是否满足堆的定义n 个元素的序列 {k1, k2, ..., kn}当且仅当满足 ki ≤ k2i 且 ki ≤ k2i1小顶堆或 ki ≥ k2i 且 ki ≥ k2i1大顶堆其中 i 1, 2, ..., ⌊n/2⌋。验证时把序列画成完全二叉树更直观从上到下、从左到右填充节点然后逐层检查父节点和子节点的关系。笔记里选 B就是因为只有 B 序列对应的树满足所有父节点都小于等于其子节点。4.5 归并路数公式log 计算别再懵归并排序的归并路数公式是独立考点归并路数 |log_k m|其中 m 为元素个数k 为多路归并趟数趟数是“向上取整”的那个值。例题若对 27 个元素只进行三趟多路归并排序则选取的归并路数为多少由公式可得 log₃27 3所以选 B3 路归并。理解这个公式的关键在于“归并路数”和“趟数”的关系k 路归并每趟能把元素个数缩小为原来的 1/k经过 t 趟后元素个数变为 m / k^t。要 t 趟归并完成就需要 k^t ≥ m即 k ≥ m^(1/t)。题目给了 m27、t3所以 k3。记住这个推导过程比死背公式更稳因为考试可能换个数字但逻辑不变。提示堆判断题型最容易错在“只看前几个元素”而不验证所有 i ≤ ⌊n/2⌋ 的父节点。每次判断堆老老实实把序列画成完全二叉树再逐层检查虽然慢一点但绝对不丢分。5. 易漏考点重灾区广义表、表达式求值与符号数编码5.1 广义表的长度与深度括号层数是关键广义表的长度和深度是容易被忽视的小考点。笔记给出的定义很清晰广义表的长度是把最外层括号删掉后剩下的元素组个数深度则是括号的层数。这俩定义各有一个坑长度数的是“逗号分隔的第一层元素”不是所有元素的总个数深度数的是“括号嵌套的最多层数”。看例题L1 ((a,(a,b),((a,b),c)))L2 ((1,2,3))L3 (1,2,3)。L1 去掉最外层括号后剩一个元素——即 (a,(a,b),((a,b),c)) 这个整体所以长度为 1数括号嵌套深度最外层一层、第二层里还有两层共 4 层。L2 去掉最外层括号后剩 (1,2,3) 这一个元素所以长度也是 1深度是 2。L3 去掉最外层括号后剩 1、2、3 三个元素长度为 3深度为 1。很多同学第一次做这类题时容易把 L1 的长度数成 7把最里面的 a 也块数进去了这就是没理解“长度只看最外层括号内的元素个数”——括号括起来的整组算一个元素。考试时先在草稿纸上把括号层次画出来再数长度和深度基本不会错。5.2 三种表达式记法前缀、中缀、后缀的栈操作细节表达式求值是数据结构栈部分的经典题考的是对三种记法扫描方向、弹栈顺序的精确记忆。中缀表达式就是日常写的 ab-c不需要多解释前缀表达式波兰式从右至左扫描后缀表达式逆波兰式从左至右扫描。前缀表达式的计算过程从右至左扫描遇数字入栈遇运算符弹出栈顶两个数用“栈顶元素 op 次顶元素”计算结果入栈。注意这个顺序和后缀表达式是反着的——后缀表达式遇运算符时弹出的是“次顶元素 op 栈顶元素”。看似只是一个顺序差异但算错的人特别多。拿笔记里的例子验证前缀表达式“- × 3 4 5 6”。从右往左扫先把 6、5、4、3 依次入栈遇 弹出 3栈顶和 4次顶算 347入栈遇 ×弹出 7 和 5算 7×535入栈遇 -弹出 35 和 6算 35-629。注意这里是“栈顶元素 op 次顶元素”也就是 35 - 6而不是 6 - 35。后缀表达式“3 4 5 × 6 -”从左往右扫3、4 入栈遇 弹出 4栈顶和 3次顶算 347这次是“次顶 op 栈顶”5 入栈遇 ×弹出 5 和 7算 7×5356 入栈遇 -弹出 6 和 35算 35-629。这两种记法的区别总结成一句话就是前缀弹出的是“栈顶 op 次顶”后缀弹出的是“次顶 op 栈顶”。做题时最好先在草稿上模拟压栈弹栈不要心算因为心算很容易把顺序搞混。5.3 原码、反码、补码、移码各自的定义与“最适合”场景符号数是计算机组成原理的送分点但也是容易失分的地方因为四种编码各有各的“变”法记混一个就全错。笔记的定义如下原码正数的原码就是自身的二进制数负数的原码第一位为 1符号位表示负数后面是数值本身的二进制数。反码正数的反码等于自身二进制数负数的反码是符号位不动其余各位按位取反。补码正数的补码等于自身二进制数负数的补码是在反码基础上加 1。移码增码无论正负数只要把补码的符号位取反即可。背下来还不行考试真正考的是“应用”在计算机中最适合数字加减运算的数字编码是补码最适合表示浮点数阶码的数字编码是移码。这两句话必须刻在脑子里。为什么负数用补码存储因为补码可以把减法统一成加法运算硬件实现最简洁为什么浮点数的阶码用移码因为移码能方便地比较指数大小——全 0 对应最小阶码全 1 对应最大阶码单调递增不需要额外的符号判断逻辑。定点数的范围表也是一个高频计算考点。机器字长为 n 时记住两个关键量A 2^(n-1)B 1 - 2^(-(n-1))就有如下规律码制定点整数范围定点小数范围原码[-(A-1), A-1][-B, B]反码[-(A-1), A-1][-B, B]补码[-A, A-1][-1, B]移码[-A, A-1][-1, B]这个规律的核心记忆点是原码和反码关于 0 对称所以负端到不了 -A补码和移码能表示 -A 这个额外的最小值因为它们把“-0”的编码利用起来了。定点整数补码的最小值是 -2^(n-1)而不是 -2^(n-1)1这个点单独拎出来记。5.4 指令寻址方式与 CPU 组成高频但容易混的分指令系统里的寻址方式是另一个易错点笔记里的四种要分清立即寻址——操作数包含在指令中获取操作数最快直接寻址——操作数的地址在指令中寄存器寻址——操作数在寄存器中寄存器间接寻址——操作数的地址在寄存器中。前两种“在指令里”后两种“和寄存器有关”区别在于操作数是“数据本身”还是“数据的地址”。考试喜欢考“哪种寻址方式获取操作数最快”——答案永远是立即寻址因为指令拿来就能用其他方式最少也要多一次内存或寄存器访问。也常考“哪种寻址方式支持操作数地址动态变化”——寄存器间接寻址因为寄存器里的值可以随时改相当于指针变量的效果。CPU 的组成是五分的常客运算器、控制器、寄存器和内部总线。注意四个组成部分缺一不可但考试更爱考功能尤其是控制器——它不仅保证程序的正确执行还要能够处理异常事件。很多人以为“异常处理是操作系统的职责”但在 CPU 组成这个层面控制器的功能里明确包含异常事件处理一定要加进去。注意广义表“长度数外层元素个数、深度数括号层数”这条规则做题时先写括号层次图再下笔表达式求值先分清扫描方向再模拟栈符号数范围直接套 A/B 规律省时不易错。6. 考前查漏补缺清单从知识地图到高分执行策略复习到冲刺阶段最怕的不是“没见过”而是“见过但记混了”。以下这份查漏补缺清单是按照历年真题的命题频率和笔记里反复强调的内容整理的建议在考前两周开始逐条自测每一条都要能做到“不看笔记直接说出结论”。表格速查自测模块必会知识点自测方式图邻接矩阵无向图度/有向图出入度给矩阵手算一次对答案存储结构四种存储方式的适用场景默写“查询用顺序、增删用链式”树二叉排序树中序遍历递增画一棵树验证中序序列哈夫曼构造过程 WPL 计算用 6 个字符频率完整做一遍查找二分查找过程、分块平均查找长度模拟一次二分推导公式排序八种排序的复杂度与稳定性默写对比表错一处重默堆堆的定义验证用 8 个元素序列画完全二叉树检查广义表长度与深度三层嵌套的例子单独练表达式前缀后缀的弹栈顺序各做一个含四则运算的例子编码原反补移码的范围与用途默写 A/B 规律的完整表格寻址四种寻址方式的定义做两道“最快/动态”选择题CPU四大组成 控制器职责合上笔记默写刷题阶段的三个习惯第一错题分类整理。不要只改答案要在错题旁边标注“错因类型”——是概念记混、计算失误还是审题偏差。笔记里提到“软件设计师的考试难点公式以及易错点”就是因为这些易错点在真题里反复出现。把错因归类后你会发现真正反复丢分的其实只有三五个点。第二计算题必须手写过程。哈夫曼树的合并过程、二分查找的中间位置取法、堆排序的初始建堆光看是看不会的。每天抽 20 分钟专门练一道计算题草稿纸上的过程清晰了考场上才不会手忙脚乱。第三时间投入要按分值配比。数据结构与算法大约占上午选择题的 20 到 25 分计算机组成原理约 10 到 15 分软件工程与项目管理约 15 分数据库约 10 分。如果你现在还在反复背软件工程的概念而哈夫曼树还没搞懂优先级应该立刻调整——算法计算题是“理解一道就会一类”记忆型题目是“背十个才能答对一个”投入产出比差异很大。最后一个教训是审题陷阱。软考下午题里的算法设计题很多时候不是算法难而是题目给的条件没看清比如“有向图用邻接表存储求某个顶点的出度”和上午的邻接矩阵题是同一个知识点的两种考法但解法完全不同。从那以后我每次做图相关的题都强制自己先画一遍结构草图再动笔计算。这个习惯帮我避免了至少 5 分的无谓失误。复习到这个阶段如果你想拿一份可以直接背诵的高频结论合集这份考点笔记精华版里的“难点公式”和“易错点”部分就是你的后悔药——它把散落在教材各处的结论集中到了一起省去了自己整理的时间。希望这份系统梳理能帮你在考场上多拿几分顺利通过软件设计师中级考试。本文还有配套的精品资源点击获取