简介这是一份面向软件设计师中级软考考生的考点笔记精华版聚焦数据结构、二叉树、查找与排序算法等核心高频考点适合在系统学习后快速复盘、考前集中记忆。内容以邻接矩阵、顺序、链式、散列、索引存储、满二叉树与平衡二叉树、哈夫曼树构造及带权路径长度计算、二分与分块查找、常用排序算法对比等为主线从内容预览可见文档还整理了图顶点入度与出度判定、哈夫曼树编码例题、各种排序算法的时间复杂度与稳定性等易错细节并配有公式和典型例题可直接用于冲刺阶段查漏补缺。资源为1个docx文档压缩包大小3.37MB文档为Word格式便于打印、批注和按章节跳转复习。目前已有381人学习适合正在备考软考中级、需要系统梳理知识框架并强化易错点的考生使用。1. 软件设计师备考地图数据结构这条主线怎么走软件设计师中级科目里数据结构与算法部分占了将近三分之一的出题比重而它也是最容易拿分也最容易丢分的模块。梳理完你会发现考试真正反复敲打的不是某个算法多复杂而是几个底层判断数据存下来是为了频繁查还是频繁改、图里一个顶点的度该看行还是看列、一棵树的带权路径怎么算、一组序列能不能构成堆。这份考点笔记精华版恰好把这些散点串成一条「存储结构与图→树结构→查找与排序→表达式与系统基础」的主线备考软考中级的人可以用它做一轮系统性自查把复习范围收敛到几组可复盘的结论上。它适合正在过第二轮的人不教基础概念只帮你把覆盖面收住再把容易翻车的位置提前标出来。2. 存储结构与图邻接矩阵、四种存储方式的复习重点2.1 邻接矩阵无向图与有向图的度怎么数邻接矩阵的考法很固定给你一个矩阵问某个顶点的度、出度、入度。无向图的邻接矩阵一定是对称的矩阵第 i 行元素之和就是顶点 i 的度因为每条边在行和列各出现一次只看行就足以数清。笔记里的例子顶点 4 的度是第四行元素的和结果是 2说明它与两个顶点相邻。这里有个快速验证技巧无向图所有顶点的度之和恒等于边数的两倍数完行和随手核对基本不用怕算错。有向图就要分方向了第 i 行元素之和是顶点 i 的出度第 i 列元素之和是顶点 i 的入度。笔记里顶点 3 的出度为 5、入度为 1说明从它出发的弧有 5 条指向它的弧只有 1 条。判断自己有没有把行和列搞反可以想「行是水平的从左到右就像箭头射出去的方向所以对应出度」这个联想虽然朴素但做题时确实管用。更严谨的校验是所有顶点的出度之和必然等于入度之和因为每条有向弧都贡献一个出度和一个入度加总后对不上就是某行某列加错了。还要提醒一个细节邻接矩阵适用于顶点数目不多的场景因为要开 n×n 的空间顶点一多矩阵会迅速膨胀。考试判断题如果题干说「顶点很多但边很少适合用邻接矩阵」那大概率是错的稀疏图更适合邻接表。2.2 顺序、链式、散列、索引四种存储结构的适用场景对比四种存储结构是数据结构的底层选择题命题方式通常是给出一段场景描述让你选最合适的存储方式。存储结构存储思路适用场景记忆锚点顺序存储地址连续的存储单元依次存放频繁查询像数组按位置直达链式存储一组任意的存储单元逻辑相邻靠指针频繁插入、删除、更新像链表改指针即可散列存储存储位置与关键码建立确定对应关系按 key 快速查找键值对一个函数算出位置索引存储索引表存关键码集合与逻辑指针数据库检索先查索引再定位数据页这个表看着简单考场上的坑在「优先级」。选项里常把两个特征拼在一起比如「频繁查询且偶尔删除」——但四种结构是并列的题目让你选「最适合」就只能看主导特征查询是主导选顺序存储插入删除是主导选链式存储。散列存储考的是「键值对」这个特征词看到「建立关键码与位置的对应关系」就选它不需要考虑顺序问题。索引存储带「索引」和「逻辑指针」两个标志词看到数据库、索引表这类描述就选它。最容易忽略的是链式存储的插入删除优势是有前提的——你得先知道操作位置。如果题目说「在表尾插入」顺序存储往末尾追加同样很快这类边界题近年有出现做题时把「频繁」二字圈出来再选。另一个容易混淆的点是散列存储与索引存储散列是直接由关键码算出存储位置多一步函数计算但无需二次查找索引存储则允许数据本身无序先查索引表确定块或页再定位数据。一个是「算出来」一个是「查出来」这两个动词在题干里出现时基本可以直接对应到答案。2.3 链表的三种形态单链表、循环链表、双链表的取舍链表部分通常只占一题但题型固定比较三种链表的灵活度与开销。单链表每个节点一个指针域只能从头往后走循环链表把尾节点的指针指向头节点形成一个环适合需要循环遍历的场景双链表每个节点有两个指针域既可以找前驱又可以找后继所以灵活度在三者中最高但每个节点多一个指针的开销插入和删除时需要同时维护两个方向的指针动作反而比单链表繁琐。所以答题时看问法问「灵活度最高」选双链表问「开销更省」选单链表问「从尾节点回到头节点方便」选循环链表。笔试里常常出现一个争议选项「双链表插入删除一定比单链表快」这个表述是错的——如果只知道要删除某个节点的后继单链表和双链表都要先找到该节点的位置只有在已知待操作节点本身、需要找它的前驱时双链表才能免去从头遍历优势才真正体现。把它当成「比较的前提条件」来理解比死记结论更稳妥。简单说双链表是「以空间换灵活」单链表是「以空间省维护」循环链表是「以结构换遍历」。3. 树结构专题二叉树、哈夫曼树与平衡树的考点拆解3.1 二叉排序树三条性质与中序遍历的联动二叉排序树在复习时只需抓住三句话左子树非空则左子树上所有节点的值均小于根节点的值右子树非空则右子树上所有节点的值均大于等于根节点的值左、右子树本身也都是二叉排序树。注意第二句用的是「大于等于」这是真题里埋了无数次的细节——很多考生写成「大于」于是遇到有相等元素的序列时判定错误。实际上考试给的序列一般不含重复值但概念题会明晃晃地问表达是否正确大于等于才是标准表述。三条性质推出来的核心结论是中序遍历一棵二叉排序树得到的是一个递增序列。因此「判断某树是否为二叉排序树」的通用做法就是中序遍历看结果是否单调不减而不是只看根与左右孩子的大小关系——只看根是不够的因为二叉排序树要求的是「左子树所有节点」都小于根也就是递归成立。还有一个高频判断题关键字最大的结点可以有左子树但一定没有右子树。理由是右子树里所有值都大于等于根如果最大关键字结点还有右子树那右子树里必然存在更大的值这与「最大」矛盾。对称地关键字最小的结点可以有右子树但一定没有左子树。这两句配合中序遍历递增的性质一起记基本能覆盖二叉排序树在选择题里的全部考法。3.2 哈夫曼树构造、WPL 与编码题的实战套路哈夫曼树又名最优二叉树核心定义是带权路径长度 WPL 最短的树构造原则是权值越大的叶子越靠近根节点。构造步骤不需要多说关键是 WPL 的计算方式每个叶子的权值乘以它到根节点的路径长度再全部加起来。真题里常把「定长编码码长」和「哈夫曼编码」放在同一个题干里考笔记中的例题很典型文件中只有 a、b、c、d、e、f 六个字符定长编码需要多少位才能表示 6 种字符2 位只能表示 4 种3 位能表示 8 种所以最小的码长是 3 位答案选 C。不要选 4 或 5因为题目问的是「最合适」的码长。第二问是给定字符频率表求字符序列「face」的哈夫曼编码答案是 B 项 001110110011。这类题的做题步骤固定先把频率最小的两个节点合二为一反复合并直到只剩一棵树然后给每个左分支编 0、右分支编 1从根出发走到目标字符沿途经过的 0/1 串起来就是该字符的编码。笔记里特意提醒了一个容易引起争议的点哈夫曼树的左节点未必要比右节点小但做题时通常按左小右大的形式建树再按左 0 右 1 赋值。如果题目允许左右交换每个字符的编码串会变但 WPL 仍然是最短的真题一般按常规约定出题不必过分纠结左右方向。做题时可以在草稿上只标出每个叶子的路径长度先算 WPL再顺手读编码能省一遍重复画树的时间。3.3 平衡二叉树与满二叉树边界条件的辨析平衡二叉树AVL 树是容易「一眼看错」的概念。定义上它是一棵空树或左右两个子树的高度差绝对值不超过 1并且左右两个子树各自也是平衡二叉树。很多考生只检查了根节点的左右高度差忽略「子树也要平衡」这一条于是遇到一个根节点平衡、某个孙子节点处失衡的树就会误判成 AVL。判断一棵树是不是 AVL必须从叶子到根逐层检查或者用递归思路自顶向下验证每个节点的左右子树高度差。真题常画一棵「根左右高差为 1但左子树的右子树高差为 2」的树问是不是平衡二叉树答案是否定的原因就在于定义要求递归成立。满二叉树的定义相对直白除最后一层无任何子节点外每一层上的所有节点都有两个子节点或 0 个子节点。注意「两个子节点或 0 个」是一句完整描述「或 0 个」对应最后一层的叶子也就是说非叶子节点度都是 2。满二叉树的节点数与层数关系是 2^h - 1共 h 层。它与完全二叉树的差别在于完全二叉树只要求最后一层从左到右连续排列不要求每层都铺满所以完全二叉树不一定是满二叉树满二叉树一定是完全二叉树。考试若给出层序遍历数组问「是否满二叉树」直接数节点数是否等于 2^h - 1 即可问「是否完全二叉树」则要检查最后一个节点的位置是否满足从左到右连续。3.4 广义表长度看第一层深度看括号层数广义表是容易被忽略的小考点但它的计算规则清晰属于复习性价比极高的知识点。长度定义为「把最外层括号删掉后剩下的元素组个数」深度定义为「括号嵌套的层数」。很多人把长度理解成「里面最终有几个数」这就是广义表题翻车的主要原因。笔记里的三道小题把这组概念考透了L1((a,(a,b),((a,b),c)))删掉最外层括号后剩下 (a,(a,b),((a,b),c)) 这一个元素组所以长度为 1从最外层往里数括号最多嵌套到第 4 层所以深度为 4答案写作长度 1、深度 4。L2((1,2,3))删掉最外层后剩 (1,2,3) 一项长度是 1但 1、2、3 实际被两层括号包着深度是 2最容易错的就是把它写成「长度 3」。L3(1,2,3)删掉最外层剩 1、2、3 三项长度是 3深度是 1。归纳一下长度数「最外层第一层被逗号分隔出几块」深度数「括号最多叠了几层」两者各数各的不要互相影响。4. 查找与排序二分、分块与八大排序的复杂度对比4.1 二分查找与分块查找适用条件决定解法二分查找折半查找的适用条件非常明确不经常变动而查找频繁的有序列表。算法本身是从中间位置记录的关键字开始比较比目标大就进前半子表比目标小就进后半子表直到找到或子表不存在。它的优点是比较次数少、查找速度快、平均性能好缺点则是要求待查表必须有序插入删除困难。所以这个算法的真实使用场景是「读多写少且有序」——如果列表频繁变动每次变动都要重新排序折半省下的查找时间会被维护有序的成本吞掉。分块查找适用的是另一种情况节点动态变化。它把一个大的线性表分解成若干块块内节点可以任意存放但块与块之间必须排序——第 i 块所有节点的关键码值都必须小于第 i1 块所有节点的关键码值。此外还要建一个索引表把每块的最大关键码值按块顺序存到辅助数组中。查找时先在索引表里定位块由于索引表有序可以顺序查或折半查再在块内用顺序查找。这个方法比顺序查找快很多因为可以先跳过无关的块但速度不如折半查找因为块内仍然是顺序扫描。理解它的设计动机有助于记忆它把「全局有序」这个苛刻条件放宽成「块间有序」换来了插入删除时只调整块内部、不波及其他块的灵活性。对比记忆的锚点有三个折半查找强调「有序列表」四个字见到有序表优先想到它分块查找强调「块间有序 索引表」两个特征题目中出现「分块」「索引表」「块内无序」时选它顺序查找则是兜底方案数据无序且数据量小时用它即可。4.2 八大排序复杂度与稳定性对比表排序部分最重要的是一张对比表软考中级的选择题几乎都围绕它出。排序方法最好平均最坏辅助空间稳定性直接插入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(n log n)O(n log n)O(n²)O(log n)不稳定堆排序O(n log n)O(n log n)O(n log n)O(1)不稳定归并排序O(n log n)O(n log n)O(n log n)O(n)稳定基数排序O(d(nrd))O(d(nrd))O(d(nrd))O(rd)稳定这张表的记忆突破口先抓稳定性稳定的一组是直接插入、冒泡、归并、基数不稳定的一组是简单选择、希尔、快速、堆。记忆口诀可以用「插冒归基稳选希快堆不稳」四个稳定的里三个最坏是 O(n²)只有归并保持在 O(n log n)这说明稳定性与效率并不挂钩不能凭「好算法应该稳定」来猜答案。几个需要解释的坑希尔排序的最好和最坏复杂度在理论上没有统一结论笔记里写平均 O(n^1.3)考试问到就直接选这个不要纠结推导过程快速排序最坏退化到 O(n²)原因是每次分割点都选在序列的两端递归深度变成 n这属于选基准策略的问题不改变它平均意义上的分治优势归并排序辅助空间 O(n)因为每趟归并需要一个临时数组承接两个有序子表的合并结果。复杂度表中「最好 O(n)」的两项是直接插入和冒泡它们都在序列基本有序时只需扫一遍就能结束这也是判断题「序列越有序插入排序越快」的出处。4.3 堆排序怎么判断一个序列是不是堆堆排序的概念判断题通常是给几个序列问哪个是堆。堆的定义n 个元素的序列若满足 ki ≤ k2i 且 ki ≤ k2i1小根堆或 ki ≥ k2i 且 ki ≥ k2i1大根堆其中 i 1, 2, …, ⌊n/2⌋就称为堆。这个定义实质上是把序列当作一棵完全二叉树的层次遍历结果要求每个父节点都不大于小根堆或不小于大根堆它的两个孩子。判断时把序列按层次写成一棵完全二叉树从第一个非叶子节点开始逐对检查父子大小关系即可。笔记里的例题是下面这个四选一用一段小代码验证最直观def is_min_heap(arr): n len(arr) # 只需要检查前 n//2 个父节点后面的都是叶子 for i in range(n // 2): # 左孩子下标 2*i1右孩子下标 2*i2 if arr[i] arr[2 * i 1]: return False if 2 * i 2 n and arr[i] arr[2 * i 2]: return False return True print(is_min_heap([10, 18, 15, 20, 50, 80, 30, 60])) # B 选项输出 True print(is_min_heap([10, 50, 80, 30, 60, 20, 15, 18])) # A 选项输出 False这段代码的逻辑说明n 个元素只需要检查前 n//2 个父节点因为完全二叉树中下标大于 n//2 的节点都是叶子i 从 0 开始对应公式里的 k1。每次比较父节点 arr[i] 与左孩子 arr[2i1]、右孩子 arr[2i2]一旦出现父节点大于孩子就说明不是小根堆。右孩子是否越界要先判断因为最后一个父节点可能只有左孩子。运行结果 B 选项返回 TrueA 选项返回 False与真题答案一致。考试时不必写代码但这套逐对检查的逻辑就是手算的步骤先把序列写成完全二叉树再按 i1、2、3… 的顺序逐对验证哪个选项全对就选哪个。提示手算时必须从 i1 开始一路检查到 ⌊n/2⌋少检查一个都可能放错选项。A 选项这类干扰项往往是「前半段像大根堆、后半段像小根堆」的混合体逐对比大小最容易暴露。4.4 基数排序与归并路数两个送分考点的公式化处理基数排序是八大排序里唯一不比较关键字大小的算法它根据关键字各位的值对 N 个元素进行若干趟「分配」与「收集」。笔记里的例子初始序列 {50, 123, 543, 187, 49, 30, 0, 2, 11, 100}第一趟按个位数分配到 0~9 十个桶中再按桶编号 0 到 9 依次取出来得到的序列在个位上是递增的之后按十位、百位重复同样的分配与收集最终整体有序。复杂度 O(d(nrd)) 的含义是d 为关键字位数决定趟数rd 为基数决定桶的数量n 为元素个数决定每趟分配和收集的代价。考试如果问「基数排序每趟在做什么」答案里出现「分配」「收集」字样即可锁定。归并路数公式是容易记混但一记就送分的内容归并所需趟数等于 log 以归并路数为底、元素个数为真数的值即 路数^趟数 元素个数。看笔记例题若对 27 个元素只进行三趟多路归并排序则选取的归并路数为多少设路数为 k则 k³ 27解得 k 3选 B。做题时把等式写成「路数^趟数 元素个数」缺哪个量就求哪个量如果元素个数不是路数的整数次幂趟数向上取整这类题基本不会绕太多弯但「向上取整」这个细节容易被忽略选择题里若给出小数形式的对数值要记得取整再选。5. 易漏易错点表达式、符号数与指令系统的翻车区复习到这里知识模块基本覆盖完整了。这一章不引入新概念只把整份笔记里最容易错、最容易漏的三类问题单独拎出来每条按「易漏点 → 为什么漏 → 怎么补」的顺序展开。你会发现这些点有个共同特征不是不会而是做题时被某个习惯性认知带偏。5.1 易漏点一前缀与后缀表达式的扫描方向与操作数顺序易漏点前缀表达式从右至左扫描后缀表达式从左至右扫描且遇到运算符时前缀算的是「栈顶元素 op 次顶元素」后缀算的是「次顶元素 op 栈顶元素」。为什么漏因为中缀表达式是从左向右读的这个习惯在遇到前缀表达式时会产生强烈惯性很多人天然地「从左开始压栈」结果遇到第一个运算符时栈里只有一个操作数或顺序错乱。而「栈顶 op 次顶」与「次顶 op 栈顶」的差异又常常被加法和乘法掩盖一旦换成减法或除法结果立刻错。怎么补做题时第一笔就在表达式上方画一条带方向的扫描线前缀画 ←后缀画 →后面的每一步都沿着箭头走同时用非交换运算符做一次对照实验——前缀 - × 3 4 5 6从右扫到 时栈顶是 3、次顶是 4算 34继续遇到 ×弹出 7 和 5算 7×535最后遇到 -弹出 35 和 6算 35-629。后缀 3 4 5 × 6 -从左扫到 时栈顶是 4、次顶是 3算的仍是 347遇到 × 算 35遇到 -栈顶是 6、次顶是 35算 35-629。两个表达式结果相同但中途「谁在运算符左边」是由扫描方向与弹出顺序共同决定的碰到减法或除法时把先入栈的那个数当作左操作数不会错。中缀转前缀或后缀时还有一个子坑括号拆解不彻底。有人直接按中缀的运算符优先级顺序把符号挪到一边结果符号相对位置错乱。补法是先按优先级把中缀式补全括号再把每个运算符移动到它所在括号的左边前缀或右边后缀最后删掉全部括号中间态的括号在草稿上一定保留。这一步虽然多花几秒但能大幅降低符号顺序错误。5.2 易漏点二补码范围、移码关系与定点数边界易漏点补码的范围比原码、反码多一个负数移码与补码只差一个符号位定点整数与定点小数的范围公式容易写串。为什么漏原码天生正负对称大家默认「负数也有对应的正数」忽略了补码把 -0 的编码腾出来表示 -2^(n-1)移码很少单独考教材通常一句话带过定点数的两张范围表放在一起形态相似但不完全对应临场默写容易写串行。怎么补用 n8 的具体数对照机器字长为 8 时原码和反码的定点整数范围都是 -127~127补码是 -128~127多出来的就是最左边那个 10000000移码的记法则是「无论正负数将补码的符号位取反即可」所以看到「浮点数阶码」四个字就直接锁定移码——浮点数的阶码要能直观比较大小符号位取反后数值顺序刚好满足排序需求。定点小数补码范围是 [-1, 1-2^-(n-1)]它和定点整数补码的 [-2^(n-1), 2^(n-1)-1] 不要混记记住「补码的 1000...0 在定点整数里是 -2^(n-1)在定点小数里是 -1」两个范围就不会再串。原码和反码的定点小数范围则是 [-(1-2^-(n-1)), 1-2^-(n-1)]正好比补码少一个 -1。5.3 易漏点三CPU职责与寻址方式的「层级」误判易漏点控制器不仅要保证程序的正确执行还要能够处理异常事件四种寻址方式的「地址层数」容易被排列组合绕晕。为什么漏「处理异常」听起来像处理数据很容易被安到运算器头上而「操作数」「地址」「指令」「寄存器」四个词反复出现直接寻址与寄存器间接寻址尤其容易混淆——前者是操作数的地址在指令中后者是操作数的地址在寄存器中。怎么补把 CPU 四部件的职责列成对位清单运算器管算术逻辑运算控制器管指令执行流程与异常处理寄存器管暂存指令与数据内部总线管部件间数据传输。选择题若出现「控制器负责算数」「运算器负责指挥程序执行」这类选项按对位表一票否决。寻址方式则按「取操作数要走几步」来记立即寻址把操作数直接包含在指令中获取最快零步直接寻址按指令中给出的地址去内存取数一步寄存器寻址直接从寄存器取数一步寄存器间接寻址先从寄存器拿到地址、再到内存取数两步。题目问「哪一种获取操作数最快」选立即寻址问「操作数的地址在寄存器中」选寄存器间接寻址这一条几乎每年都有。6. 复习清单与查漏补缺把易错点变成默写卡6.1 三张自查表先过模块再过细节复习到最后阶段不建议再从头翻笔记而是按模块做「合书自测」。下面这张表把各模块必会考点压缩成自测题目每项能在 5 分钟内独立写出来才算过关模块必会考点自测方法存储与图邻接矩阵的度 / 四种存储结构适用场景默写「频繁查询→顺序、频繁增删→链式、键值对→散列、索引表→索引」四连句树结构二叉排序树中序递增 / 哈夫曼 WPL / AVL 递归定义 / 广义表长度深度画出 5 个字符的哈夫曼树并写出每个字符的编码查找二分查找适用条件 / 分块查找块间有序 索引表写一遍分块查找的步骤先查索引表定位块再块内顺序查排序八大排序复杂度与稳定性默写稳定性口诀「插冒归基稳」填出快速排序最坏复杂度表达式与系统前缀后缀扫描方向 / 补码范围 / 四种寻址方式各算一题前缀与后缀表达式对照结果默写「补码 1000...0」在定点整数和定点小数的含义6.2 把易错点变成一张默写卡冲刺期最容易出现的情况是做题时会、合书就忘。这是因为很多结论只是「认得」还没变成「写得出来」。我的做法是把上一章的三类易漏点浓缩成一张卡片正面写题干关键词背面写对应结论前缀从右扫、后缀从左扫前缀是栈顶 op 次顶后缀是次顶 op 栈顶补码比原码多一个负数移码是补码符号位取反AVL 的子树也要各自平衡分块查找要求块间有序、块内无所谓归并趟数看「路数^趟数 元素个数」。每次刷题前后都默写一遍写不出来就回到对应小节读一段读到能复述为止。从那以后我每次复习数据结构部分都强制自己先默这张卡再做题概念类选择题的错误率明显下降。这份笔记的电子档建议下载后当作第二轮复习的主线配合章节对照做标记效果比零散刷题更稳。希望帮到你。本文还有配套的精品资源点击获取
