简介面向软件设计师中级考试备考者的考点笔记精华文档覆盖数据结构、二叉树、查找与排序等核心模块专为冲刺阶段梳理难点公式与易错点而整理。文档以邻接矩阵、顺序/链式/散列/索引存储结构为切入点结合满二叉树、AVL树、哈夫曼树及WPL计算等高频考点并系统对比二分查找、分块查找与直接插入、简单选择、冒泡、希尔、快速、堆、归并、基数等排序算法辅以复杂度分析表与典型例题解析便于考生快速定位薄弱环节。资源为单份Word文档.docx仅1个文件压缩包大小3.37MB内容精炼无冗余适合考前集中复习与反复查阅。目前已有381人学习下载兼具知识框架梳理与实战解题参考价值可帮助考生在有限时间内巩固核心考点、提升应试效率。1. 软件设计师中级考点为什么背会了结论做题还是靠蒙备考软件设计师中级的人多半会在数据结构这里卡一下邻接矩阵、哈夫曼树、基数排序……乍看像上世纪教材目录跟日常写业务代码毫无关系。但把考试吃透的人会发现一个反直觉的事实——软考中级真正考的不是你记没记住结论而是懂不懂底层为什么这么设计。比如“邻接矩阵第 i 行元素之和就是顶点 i 的度”背下来只要十秒但搞懂它为什么成立能让你在“有向图出度入度”“存储结构选型”这些变形题上不再靠猜。下面按“现象→机制→实现”的顺序把这份考点笔记里最有分量的几个原理拆开讲清楚它们怎么来的、怎么用、哪些地方最容易翻车。2. 图的存储与查找为什么“度”能直接数出来查找却要分三六九等2.1 邻接矩阵第 i 行之和为什么恰好是顶点 i 的度邻接矩阵是图的一种存储方式核心思想是用一个 n×n 的二维数组记录顶点之间的边关系。对于无向图如果顶点 i 和顶点 j 之间有边就把 matrix[i][j] 和 matrix[j][i] 都置为 1没有边就置为 0。因为无向图的边不区分方向所以这个矩阵一定是对称的。你去看第 i 行这一行里的每一列代表“顶点 i 到顶点 j 是否有边”把这行的所有元素加起来统计的其实是“顶点 i 到底连出去了多少条边”——这正是无向图中顶点 i 的度。笔记里顶点 4 的度是 2就是第四行元素之和为 2说明它只跟两个顶点相连。有向图则多了一层方向语义。第 i 行记录的是“从顶点 i 出发指向其他顶点”的边所以行元素之和是出度第 j 列记录的是“从其他顶点指向顶点 j”的边列元素之和就是入度。一个可以自检的性质是有向图所有顶点的出度之和一定等于入度之和因为每条有向边既贡献一个出度也贡献一个入度。考试里如果给出所有出度让你反推某个入度用这个守恒关系能快速验算比闷头数矩阵靠谱得多。# 用邻接矩阵统计无向图/有向图的度 def degree(matrix, vertex, directedFalse): n len(matrix) if not directed: return sum(matrix[vertex]) # 无向图第i行之和度 out_degree sum(matrix[vertex]) # 有向图第i行之和出度 in_degree sum(matrix[i][vertex] for i in range(n)) # 第j列之和入度 return out_degree, in_degree这段代码背后藏着邻接矩阵最重要的性质无向图因为边对称统计行和列结果一样所以只算行就够有向图必须行、列分开看。理解了这一点遇到“某顶点出度为 5、入度为 16”这类抽象数字你不再需要背公式回到矩阵定义里数一遍就能判断对错。另外要注意邻接矩阵的空间代价是 O(n²)顶点多了矩阵会迅速膨胀所以它适合顶点数目不多的场景——这也是笔记里强调“适用图中顶点数目不多”的原因。2.2 四种存储结构为什么说链式适合增删、散列适合查找笔记把存储结构分成顺序、链式、散列、索引四类。它们不是孤立的四种写法而是分别对应不同的成本权衡。顺序存储用一组地址连续的单元依次存放数据元素任意元素的地址可以直接算出来随机访问是 O(1)但插入和删除往往要搬动大量元素所以它适合频繁查询、很少改动的场景。链式存储用一组任意的存储单元通过指针把逻辑上相邻的元素串起来插入删除只需要改指针不需要搬数据代价是每个元素多一个指针域的内存开销而且访问某个元素必须从头往后找。单链表、循环链表、双链表的区别也在这个权衡里双链表有两个指针域既知道后继也知道前驱所以灵活度优于单链表比如删除当前结点不需要从头找它的前驱但每个结点多一个指针内存开支更大笔记里那句“灵活度优于单链表但开支要大一些”说的就是这个取舍。循环链表解决了单链表从尾部回到头部要遍历的问题但代价是边界判断更多。散列存储把数据元素的存储位置与关键码之间建立确定对应关系也就是键值对。它的机制是设计一个散列函数把关键码映射到存储地址查找时再算一次散列函数就能定位到元素理想情况下是 O(1)。但散列会撞车两个不同关键码映射到同一个地址所以工程上还要处理冲突最常见的是链地址法和开放定址法。索引存储则是单独建立一个物理结构它保存的是某个表中一列或若干列值的集合以及指向物理数据页的逻辑指针清单数据库系统里的索引就是典型代表。提示四种结构不是互斥的。一个数据库表本身可能是堆组织或顺序组织索引又是额外的索引存储结构两者叠加使用实际系统里很常见。考试问“什么场景选什么”本质是在问你要为哪种操作付出代价。2.3 二分查找与分块查找“有序”是分治的前提二分查找折半查找的适用条件写得很清楚不经常变动而查找频繁的有序列表。它的机制是每次把查找范围对半砍用中间位置记录的关键字与目标比较目标小就搜前半段目标大就搜后半段直到找到或区间为空。这个策略能成立完全依赖“表有序”这个前提——只有有序你才能断定目标一定在某一半里从而安全地丢掉另一半。def binary_search(arr, target): low, high 0, len(arr) - 1 while low high: mid (low high) // 2 if arr[mid] target: return mid # 命中 if arr[mid] target: high mid - 1 # 目标在左半段 else: low mid 1 # 目标在右半段 return -1 # 未找到二分查找的好处是次数少、速度快、平均性能好但它的缺点同样源于“有序”待查表必须是物理有序或逻辑有序而且插入删除困难因为维持有序本身要付出成本。分块查找是对二分查找和顺序查找的折中把大的线性表分解成若干块每块里的节点可以任意存放但块与块之间必须排序——第 i 块中所有节点的关键码值都小于第 i1 块。另外建立一个索引表把每块的最大关键码值作为索引项按块顺序存到辅助数组里。查找时先在索引表里找目标所在的块索引表有序可以用顺序查找或折半查找再在块内顺序查找。分块查找比顺序查找快得多但速度不如折半查找它换来的好处是节点动态变化时插入删除容易——因为块内无序新数据只要落在对应块里就行不需要全局重排。它的平均查找长度由两部分组成索引表的查找长度加上块内的顺序查找长度。理解了这个结构你就明白为什么它恰好是二分和顺序之间的“中间档”。3. 树结构二叉排序树、AVL 与哈夫曼的共同逻辑是“结构即效率”3.1 二叉排序树中序遍历为什么一定递增二叉排序树的定义有三句话左子树所有节点的值都小于根节点的值右子树所有节点的值都大于等于根节点的值左右子树也分别是二叉排序树。这其实是在用树结构编码一个有序序列使查找、插入、删除都沿着树的路径进行而不需要搬动整片数据。查找时从根开始比较目标值比当前节点小就往左走比当前节点大就往右走直到找到叶子或路径走完。中序遍历的顺序是“左子树-根-右子树”。因为左子树的所有值都小于根右子树的所有值都大于等于根所以中序遍历天然得到一个递增序列。这是“二叉排序树”这个名字的由来——排序能力被编码进了树的结构本身而不是依赖数组中元素的物理位置。笔记里那句“关键字最大的结点可以有左子树但一定没有右子树”是定义的直接推论如果关键字最大的结点还有右子树那右子树里必然存在比它更大的值与“最大”矛盾。这类判断题在软考里反复出现本质上都在考察定义的严格性——你要学会从定义出发推结论而不是背结论。插入结点的过程也是一样从根出发比当前节点小往左、大往右走到空位就放进去整个过程没有回溯。3.2 AVL 树平衡因子怎么维持“高度差不超过 1”平衡二叉树AVL 树的要求是它是一棵空树或者左右两个子树的高度差的绝对值不超过 1并且左右两个子树也都是平衡二叉树。这个“高度差不超过 1”就是平衡因子的概念。为什么要加这个约束因为二叉排序树的查找效率取决于树的高度树越矮查找路径越短。如果插入顺序恰好是递增的二叉排序树会退化成一条链查找退化成 O(n)AVL 树通过在插入删除后执行旋转操作把树高控制在 O(log n) 量级。旋转操作是 AVL 的精华分成四种情况。不平衡发生在某个节点的左子树的左子树叫 LL 型右旋一次发生在右子树的右子树叫 RR 型左旋一次发生在左子树的右子树叫 LR 型先左旋再右旋发生在右子树的左子树叫 RL 型先右旋再左旋。旋转的本质是重新选择子树的根让整棵树的左右高度差回到 1 以内同时保持二叉排序树的中序有序性不变。考试里判断一个序列是不是 AVL 树不是看旋转过程那通常在应用题的大题里而是检查每个节点的左右子树高度差是否都不超过 1。笔试题最常埋的坑是只检查根节点高度差忘了检查子树的子树。AVL 的定义是递归的任何一个节点的平衡因子超出范围整棵树就不满足 AVL 条件。这个“递归地满足条件”的判定方式和二叉排序树的定义方式是一模一样的抓住这个共性就能少踩一半坑。3.3 哈夫曼树WPL 最短是怎么构造出来的哈夫曼树最优二叉树的定义是带权路径长度 WPL 最短的树权值越大的叶子节点越靠近根节点。WPL 是所有叶子节点的权值乘以路径长度的总和。要构造一棵哈夫曼树常见的做法是把所有节点按权值放进一个集合每次取出权值最小的两个节点合并成一个新节点新节点的权值是两者之和再放回集合重复直到只剩一个根节点。这个过程可以用优先队列最小堆高效实现。import heapq def huffman_wpl(weights): heap list(weights) heapq.heapify(heap) total 0 while len(heap) 1: w1 heapq.heappop(heap) # 最小的权值 w2 heapq.heappop(heap) # 次小的权值 merged w1 w2 total merged # 累加合并代价 WPL heapq.heappush(heap, merged) return total这段代码展示了哈夫曼构造的核心每次合并都让最小权值节点尽量靠近根或者参与高层次合并从而让权值越大的节点路径越短。要生成编码构造时还要记录每个节点的左右孩子从根节点出发走到左孩子记为 0走到右孩子记为 1每个叶子节点对应的 0/1 序列就是它的编码。笔记里的例题透露了两个关键点。第一问文件里有 a 到 f 六个字符定长编码用 3 位就够因为 3 位二进制能表示 8 个不同的值覆盖 6 个字符绰绰有余4 位、5 位虽然也能表示但不是“最合适”的码长。第二问字符序列“face”的哈夫曼编码需要找到 f、a、c、e 四个叶子从根节点出发把路径上的 0/1 拼出来。解析里特意强调“哈夫曼树的左节点未必要比右节点小但通常做题写成左小右大再左 0 右 1 赋值”——这说明左右子树的大小约定只是一种书写习惯真正的答案以路径为准不要默认一定左 0 右 1。哈夫曼编码能压缩整体码长的原因是高频字符获得短编码、低频字符获得长编码且编码满足前缀码性质任何一个字符的编码都不是另一个字符编码的前缀解码时才能无歧义地切分。4. 排序算法从直接插入到基数排序每一条复杂度都对应一种设计选择4.1 插入类直接插入与希尔排序直接插入排序的过程像斗地主抓牌每抓到一张新牌把它插到手里已经排好序的牌中合适的位置。对计算机来说每一趟把一个待排序记录按关键字大小插入到前面已经有序的序列里直到全部插入完成。它的最好情况是 O(n)发生在序列基本有序时——每趟只比较一次就找到位置平均和最坏都是 O(n²)。数据量小或基本有序时直接插入是首选因为常数极小。希尔排序是直接插入排序的改进它按步长 gap 把记录分成若干组每组内部做直接插入排序随着步长逐渐减小每组包含的记录越来越多当步长减到 1 时整个序列变成一组再做一次完整的插入排序。希尔排序的直觉是先让数据“宏观有序”再让数据“微观有序”。直接插入排序的问题在于一次只能把元素移动一个位置而希尔排序允许元素跨大步长移动大幅减少了总移动次数。笔记里希尔排序的平均时间复杂度写“不存在”因为它的复杂度严重依赖 gap 的选择方式不同的步长序列会产生不同的性能目前没有一个统一的精确表达式常见教材给出 O(n^1.3) 这样的经验值。这其实是一个很好的提醒复杂度不是算法的固有属性而是“算法 输入 参数”共同的属性。4.2 交换类冒泡排序与快速排序冒泡排序是两两比较相邻的关键字不满足次序要求就交换每一趟把当前未排序部分的最大值“冒”到末尾。它的最好情况是 O(n)一趟下来没有任何交换说明序列已经有序平均和最坏都是 O(n²)。冒泡排序稳定、容易实现但比较次数多只适合数据量小且对稳定性有要求的场景。快速排序把冒泡的“交换”发扬光大一趟排序把数据分割成独立的两部分分割点左边都是比它小的数右边都是比它大的数然后递归地对两部分重复这个过程。它采用分治策略平均时间复杂度 O(n log n)。最坏情况发生在每次分割都极度不均匀时比如序列已经有序而基准总是取到边界值递归深度变成 n复杂度退化为 O(n²)——这是软考选择题里高频的陷阱点。def quick_sort(arr): if len(arr) 1: return arr pivot arr[len(arr) // 2] # 取中间元素做基准 left [x for x in arr if x pivot] mid [x for x in arr if x pivot] right [x for x in arr if x pivot] return quick_sort(left) mid quick_sort(right)这个简洁递归实现展示了分治的核心每层分割把所有元素过一遍递归深度平均是 O(log n)所以总复杂度是 O(n log n)。快速排序在实际运行中通常比堆排序快因为它的局部性更好、常数更小但它的最坏情况是 O(n²)而堆排序最坏也能保证 O(n log n)。选择哪种算法本质上是在“平均性能”和“最坏保障”之间做取舍。4.3 选择类简单选择与堆排序简单选择排序每趟从待排序记录中选出关键字最小的顺序放在已排序序列末尾直到全部排完。它的特点是比较次数固定——不管初始序列是否有序都要比较大约 n²/2 次所以最好、平均、最坏都是 O(n²)。它不稳定原因在于选取最小元素时可能跨越很远的距离交换两个相同关键字的记录把原来的相对顺序打乱。堆排序利用堆这种数据结构。堆的定义是n 个元素的序列 k1,k2,…,kn 满足 ki ≤ k(2i) 且 ki ≤ k(2i1)小顶堆或者 ki ≥ k(2i) 且 ki ≥ k(2i1)大顶堆其中 i 从 1 到 ⌊n/2⌋。这个定义的本质是用数组表示一棵完全二叉树下标 i 的左右孩子正好在下标 2i 和 2i1。堆排序反复把堆顶最大值或最小值与末尾元素交换再调整剩余元素重新成堆。笔记里的例题问四个序列哪个是堆答案选 B(10, 18, 15, 20, 50, 80, 30, 60)。验证方式是把数组画成完全二叉树10 是根两个孩子是 18 和 15都大于等于 1018 的孩子是 20 和 50都大于等于 1815 的孩子是 80 和 30都大于等于 1520 的孩子是 60大于等于 20。所有父子关系都满足 ki ≤ k(2i) 且 ki ≤ k(2i1)所以它是小顶堆。这种题不看数组结构、只凭空想很容易看错画成树形图一目了然。4.4 归并、基数与复杂度总表归并排序把待排序序列看成 n 个长度为 1 的有序序列将相邻的有序表成对归并得到 n/2 个长度为 2 的有序表再归并得到 n/4 个长度为 4 的有序表反复进行直到得到一个长度为 n 的有序序列。它的复杂度稳定在 O(n log n)因为每趟归并要遍历全部元素共约 log n 趟代价是需要 O(n) 的辅助空间存放归并结果。归并排序是稳定的因为它把“交换”变成了“合并”相同关键字的记录在合并时不会跨越远距离交换。基数排序与前面所有排序都不同它不比较关键字大小而是根据关键字各位的值通过对元素进行若干趟“分配”与“收集”完成排序。以十进制数为例把 0~9 看成 10 个桶先按个位数字分桶再把 0 到 9 号桶里的数依次取出来得到个位有序的序列然后按十位、百位重复。因为分配和收集都不做比较和远距离交换它是稳定的复杂度是 O(d(nrd))其中 r 是基数十进制为 10d 是位数。排序方法最好平均最坏辅助空间稳定性直接插入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) 的只有归并因为它需要额外的临时数组来合并。这样推一遍比逐行背表格可靠得多。5. 避坑编码表示、表达式求值和广义表里最容易翻车的细节5.1 原码、反码、补码、移码范围记忆的玄学在这里机器字长为 n 时四种码制能表示的定点数范围不同。原码和反码的定点整数范围是 [-(2^(n-1)-1), 2^(n-1)-1]因为它们把 -0 和 0 各占一个编码所以正负不对称补码和移码能表示到 -2^(n-1)因为补码把 -0 的编码让给了最小负数。这是考试里最常出现“范围差一个”的地方。一个可靠的记忆技巧是设 A2^(n-1)B1-2^-(n-1)于是原码/反码定点整数是 [-(A-1), A-1]补码/移码是 [-A, A-1]定点小数部分原码/反码是 [-B, B]补码/移码是 [-1, B]。为什么补码不保留 -0因为补码的设计目标是让加减法统一——正数加负数直接按二进制加法就能得到正确结果不需要判断符号和绝对值大小。原码做减法要先判断符号同号相减、异号相加电路复杂得多。移码则更特殊把补码的符号位取反就得到移码。这样做的目的是让浮点数的阶码大小顺序直接等于无符号数的大小顺序比较阶码时不需要额外的符号判断逻辑。所以笔记里“最适合数字加减运算的数字编码是补码最适合表示浮点数阶码的数字编码是移码”这两句话背后都是硬件设计的成本考量而不是约定俗成的死规定。做题时最容易踩的坑是把“加减运算用补码”记成“原码”或者把“阶码用移码”记成“补码”只要理解了“补码为了算得快、移码为了比得快”就不会混。5.2 前缀与后缀表达式栈顶和次顶的顺序不能记反前缀表达式波兰式从右至左扫描遇到数字压入堆栈遇到运算符时弹出栈顶的两个数计算“栈顶元素 op 次顶元素”结果入栈。后缀表达式逆波兰式从左至右扫描遇到数字压栈遇到运算符时弹出两个数计算“次顶元素 op 栈顶元素”。这个顺序差异在减法、除法这种不满足交换律的运算里会直接导致结果错误。def eval_postfix(tokens): stack [] for tok in tokens: if tok.isdigit(): stack.append(int(tok)) else: b stack.pop() # 栈顶 a stack.pop() # 次顶 if tok : stack.append(a b) elif tok -: stack.append(a - b) # 必须是 a - b elif tok *: stack.append(a * b) elif tok /: stack.append(a / b) return stack[-1]后缀表达式 “3 4 5 × 6 -” 的求值过程足够典型压入 3 和 4遇 弹出 4 和 3计算 347压入 5遇 × 弹出 5 和 7计算 7×535压入 6遇 - 弹出 6 和 35计算 35-629。关键在最后一步如果顺序记反35-6 会被算成 6-35。我的习惯是后表达式里谁先进栈谁在运算符前前缀表达式正好相反。考试遇到这类题先把中缀表达式化成后缀或前缀再走一遍栈模拟比凭感觉写答案稳妥得多。5.3 广义表长度是顶层元素个数深度是括号层数广义表是数据结构里最容易混淆“长度”和“深度”的定义题。长度是把最外层那层括号删掉以后所剩下的元素组个数深度是括号嵌套的层数。笔记里的例子L1((a,(a,b),((a,b),c)))把最外层括号删掉里面只剩一个元素组所以长度是 1数括号嵌套的层数深度是 4。L2((1,2,3))长度是 1深度是 2L3(1,2,3)长度是 3深度是 1。这个考点几乎没有推导余地纯粹是对定义的理解。但很多人会栽在“长度”上——把里面的元素拆开来数成多个。关键要抓住长度只看最外层括号内的逗号分隔项一个用括号包住的子表不管里面有多复杂整体只算一个元素。深度的判定则相反必须一层一层数括号。备考时建议自己多构造几个嵌套例子练手比如把元组、列表、子表混在一起写几组数据数完长度再数深度能有效避免考场上看花眼。5.4 归并路数公式别把趟数和路数搞反归并排序里有一个常考的换算题归并趟数和归并路数的关系。公式是对 m 个元素进行 k 路归并需要的趟数是 log 以 k 为底 m向上取整。例题“对 27 个元素只进行三趟多路归并排序则归并路数为几”答案就是把 27 开三次方得到 3选 B。这个公式最常出错的地方是搞混未知量已知趟数求路数时要按公式反推已知路数求趟数时要计算对数值。另一个容易忽略的点是向上取整——即使最后一趟只剩不到 k 个元素也还是要算一趟。另外注意不要和堆排序的复杂度公式混在一起堆排序的 O(n log n) 是总时间而归并路数公式只算“趟数”这个维度。6. 考点背后的设计取舍为什么“知道为什么”比“记住是什么”更能拿分回头看这份笔记里的所有考点能发现一条共同逻辑每个“规定”背后都有一个工程权衡。补码选作加减运算的编码是因为它让符号位参与运算省掉符号判断电路移码选作浮点阶码是因为它让负数阶码的大小能直接用无符号比较器判断。AVL 树牺牲了插入删除的常数时间换来了查找的稳定性分块查找牺牲了全局有序换来了动态插入的灵活性。指令系统里立即寻址的操作数包含在指令中获取操作数最快不需要额外访问内存直接寻址要到内存取操作数寄存器寻址虽然也在 CPU 内部但比立即寻址多了一步寄存器访问——这些都是“快在哪里、贵在哪里”的取舍而不是孤立的知识点。我备考时最大的教训就是一开始抱着复杂度表死背结果遇到“哪个排序稳定”“快排最坏什么时候发生”“为什么堆排序最坏也是 O(n log n)”这类变形题照样错。后来我换了一个方法每学一个知识点先问自己三个问题——它要解决什么问题它牺牲了什么它适合什么场景比如看到稳定排序不要先背结果先想“归并为什么稳定、快排为什么不稳定”稳的本质是相同关键字的记录会不会被远距离交换破坏相对顺序。这样想一遍选项里任何组合都能直接判断而不是靠排除法猜一个。从那次之后我每次都强制走一遍“问题→代价→场景”三步流程再做历年真题数据结构和算法部分才算真正稳定不丢分。这份考点笔记已经把关键机制和易错点整理出来了配合自己的推导去验证每个结论备考效率比单纯看一遍笔记高得多。希望帮到你。本文还有配套的精品资源点击获取