简介：软件设计师（中级）考点笔记精华版为软考中级备考者系统梳理了数据结构、查找与排序等核心模块，覆盖邻接矩阵、顺序/链式/散列存储、二叉树、AVL树、哈夫曼树、二分查找、分块查找以及直接插入、冒泡、希尔、快排、堆排、归并、基数排序等算法，并通过表格对比时间复杂度、辅助空间和稳定性。压缩包共1个文件，为docx格式文档，大小3.37MB，知识点按模块集中排版，方便在电脑或移动设备上阅读，也可打印后反复标注。目前已有381人学习下载。笔记不仅归纳了顺序存储适合频繁查询、链式存储适合频繁增删、索引存储适合数据库检索等应用场景，还结合定长编码、哈夫曼编码等典型例题给出解题思路，帮助考生理解难点公式与易错点。文档适合希望在冲刺阶段快速过考点、强化记忆并提升选择题和案例分析题得分率的考生。
1. 软考中级软件设计师考证：这份考点笔记为何值得过一遍
备考软件设计师中级的人，大多在数据结构这类上午题上栽过跟头：概念都见过，一到题目就分不清出度入度、排序稳定性、哈夫曼编码对不对。这份考点笔记精华版，把散落在教材里的高频考点按“结论 + 例题 + 易错点”切成了小块，邻接矩阵的度、二叉排序树、二分查找、八大排序、广义表和表达式的坑都收进去了，适合考证前一个月反复翻，也适合下午题废了的上班族快速找回手感。它不是那种通篇定义的全书摘抄，更像一份可以直接拿来背的清单：每条都对着题目讲，遇到哪种问法该看行还是看列、该用哪种查找方式，笔记里都给了明确交代。下面按我拆这份笔记的阅读顺序，把每个容易卡住的知识点展开讲透。
2. 数据结构与存储结构：邻接矩阵的度、存储选型与表达式记法
2.1 邻接矩阵：无向图行和为度，有向图行列分出入
邻接矩阵是图这章最常考的表达方式，考前必须形成一个条件反射：看到“无向图”三个字，直接用第 i 行的元素和作为顶点 i 的度。比如笔记里那个例子，顶点 4 的度就是邻接矩阵第四行所有元素的和，等于 2，不需要再去看列，因为无向图的邻接矩阵一定是对称的，行和等于列和。换到有向图，问题就变了：第 i 行元素之和是顶点 i 的出度，第 j 列元素之和才是顶点 j 的入度。笔记里特意给了一个数据，某个有向图的顶点 3 出度和入度分别是 5 和 16，考场上如果题干把“列”换成“行”，答案立刻翻车。我一般做题时会先圈题干里的“无向”还是“有向”，再圈问的是“出”还是“入”，两个都确定后再去数矩阵。还有一个小坑是自环：无向图对角线上的 1 在计算度的时候要算进去，部分题目故意用对角线上的值干扰你，这时候逐行逐列数比背公式更稳。
2.2 顺序、链式、散列、索引：四种存储结构怎么选
存储结构这部分的考点很直白，关键在于记清“什么操作频繁”对应“哪种结构”。顺序存储结构用一组地址连续的存储单元依次存放数据元素，逻辑相邻物理也相邻，它最大的优势是按下标随机访问，频繁查询时效率高，缺点就是插入删除要挪动大片元素。链式存储结构用一组任意的存储单元，物理上连续或不连续都行，为了维护逻辑关系需要加重指针域的开销，但换来的是插入、删除、更新元素时只需要改指针，因此它特别适合频繁增删的场景。散列存储结构是把数据元素的存储位置与关键码之间建立确定对应关系，也就是键值对映射，查找时直接算哈希地址，时间复杂度逼近 O(1)，但它不保证元素顺序，也没有办法做范围查找。索引存储结构在数据库里最常见：索引是一个单独的物理数据库结构，存的是某表中一列或若干列值的集合，以及指向表中对应数据页的逻辑指针清单。这几类结构放在一张表里看更清楚：
| 存储结构 | 核心特征 | 适合场景 | 主要缺点 |
|---|---|---|---|
| 顺序存储 | 地址连续，逻辑相邻物理相邻 | 频繁查询、少增删 | 插入删除成本高 |
| 链式存储 | 地址任意，通过指针串联 | 频繁插入、删除、更新 | 指针占用额外空间 |
| 散列存储 | 关键码与存储位置直接对应 | 高频等值查找 | 顺序性差，哈希冲突难处理 |
| 索引存储 | 建立辅助索引表定位数据 | 数据库大表检索 | 索引本身有存储和维护开销 |
考试里选择题的典型问法是“某系统查询频繁但几乎不更新，应该选哪种结构”，这时候顺序存储是首选；如果题干里写“经常增删改”，那答案大概率落在链式存储上。我备考时把这句话抄在了笔记封面：查询选顺序，增删选链式，等值查找选散列，数据库大表选索引。这条经验应对上午题基本够用。
2.3 链表三兄弟：单链表、循环链表、双链表怎么取舍
链表部分不用死记代码，但要能分清三种形态的差异。单链表只有一个指向后继的指针域，循环链表在单链表基础上把尾结点的指针指向头结点，形成环路，好处是能从任意一个结点出发遍历全表。双链表每个结点有两个指针域，既指向前驱也指向后继，灵活度明显优于单链表，但代价是每个结点多花一个指针的存储空间，笔记里那句话说得直接：“双链表的灵活度优于单链表，但是双链表的开支要大一些”。选择题如果问“哪个结构从已知结点删除前驱更方便”，答案就是双链表，因为单链表要删除某个结点前必须从头遍历才能找到它的前驱；循环链表则适合解决约瑟夫环这类需要绕圈访问的问题。做题时我习惯在草稿纸上画三条链，把“指向前驱/后继”的箭头标出来，这样无论题目怎么换说法都不会被绕进去。
2.4 广义表与三种表达式记法：数括号与栈操作
广义表这一小节，笔记里给了三个例子对比长度和深度。求长度时先把最外层那对括号删掉，再看剩下的是几个元素或子表；求深度则是看括号最多嵌套几层。L1=((a,(a,b),((a,b),c))) 的答案是长度 4、深度 4；L2=((1,2,3)) 的长度是 1、深度是 2；L3=(1,2,3) 的长度是 3、深度是 1。很多人第一次做 L2 会写成长度 3，错在没搞清楚外层括号删掉后剩下的其实只有一个子表 (1,2,3)。表达式的三种记法是另一个容易送分的点。前缀表达式从右往左扫描，遇到数字压栈，遇到运算符弹出栈顶两个数做“栈顶 op 次顶”计算，注意和前者的顺序相反；后缀表达式从左往右扫描，遇到运算符做“次顶 op 栈顶”计算。笔记里的例子是“3 4 + 5 × 6 -”，从左扫到右，3、4 入栈，碰到 + 弹出 4 和 3 计算 3+4=7，然后 5 入栈，碰到 × 弹出 5 和 7 计算 7×5=35，再 6 入栈，最后一个 - 让 35-6 得到 29。这里最容易算反的是减法顺序，前、后缀分别规定栈顶和次顶的位置，背不下来就做题时自己写一遍。
3. 树与二叉树核心：二叉排序树、AVL 与哈夫曼编码题怎么写
3.1 二叉排序树：中序遍历递增与“最大结点无右子树”
二叉排序树（BST）的定义看似简单，但考试喜欢在细节上设陷阱。左子树所有结点值小于根节点，右子树所有结点值大于等于根节点，同时左右子树也各自满足二叉排序树定义。这个“大于等于”很关键，有些教材里写“大于”还是“大于等于”，直接决定重复元素放左还是放右。另一个高频结论是：中序遍历一棵二叉排序树会得到一个递增序列，所以判断一棵树是不是二叉排序树，最稳的办法就是中序遍历后看序列是否单调不减。笔记里还有一句容易忽略的话：“关键字最大的结点可以有左子树，但一定没有右子树”，因为它的值已经是整棵树里最大的，要是再有右孩子，那个右孩子的值必然比它大，就矛盾了。同样地，最小关键字结点可以有右子树，但一定没有左子树。选择题如果给出树形图问你哪个是中序遍历结果，直接从最左走到最右就能排除两个选项。
3.2 哈夫曼树与 WPL：从定长编码到“face”编码例题
哈夫曼树是下午题和上午题都喜欢碰的一块。先明确概念：带权路径长度 WPL 最小的二叉树叫哈夫曼树，权值越大的叶子节点越靠近根节点。构造口诀很简单：从森林里取两个权值最小的节点合并成一个新节点，权值相加，再放回森林里重复，直到只剩一棵树。笔记给了一个典型例题：某文件中有六个字符 a、b、c、d、e、f 及对应频率，如果用定长编码，六个符号至少需要 3 位二进制，因为 2^2=4 不够，2^3=8 正好，所以第一问选 B。第二问是“face”的哈夫曼编码，这题最考验的是你是否按统一的规则建树。做题时我一般会强制自己把“左小右大、左 0 右 1”写在使用说明里：每次合并时，权值小的放左边，权值大的放右边，然后给左树枝标 0、右树枝标 1，这样从根到叶子路径上的 0/1 序列就是该字符的哈夫曼编码。按这套约定建出来的树，“face”四个字母对应的编码串才是参考答案里那个选项。需要特别提醒的是：如果建树过程中遇到权值相同的节点，可能出现多种合法树形，不同树形会得到不同的编码串，但 WPL 一定相同。所以复习时不用死背某串二进制，真正要练的是 WPL 计算和路径标号规则。计算 WPL 时，把所有叶子节点的权值乘以它所在层数再求和，也可以用“合并过程中每次新节点的权值叠加”来快速校验，两种方法结果一致就没有大问题。
3.3 平衡二叉树与满二叉树：高度差绝对值不超过 1
平衡二叉树（AVL 树）的定义分两步：它是一棵空树，或者它的左右两个子树的高度差绝对值不超过 1，并且左右两个子树也分别都是平衡二叉树。注意这里说的是“高度差绝对值不超过 1”，不是“左边必须比右边高”，所以高度差为 0 或 1 都满足条件。判断一棵树是不是 AVL，要递归地看每一个结点，不能只看根节点。满二叉树在笔记里的定义是“除最后一层无任何子节点外，每一层上的所有结点都有两个子结点或 0 个子节点”，说人话就是每个非叶子节点恰好有两个孩子，所有叶子在同一层。常考结论：深度为 k 的满二叉树节点数是 2^k - 1，其中第 i 层节点数是 2^(i-1)。这两棵树放一起学特别容易混，我的办法是画图对比：满二叉树每一层都填满，像三角形；平衡二叉树只要求每个节点左右高度差不超过 1，可以少一些分支。
4. 查找与排序算法：八大排序复杂度、稳定性与堆判断实战
4.1 二分查找与分块查找：有序表和动态表的不同解法
二分查找的适用条件很苛刻：要求待查表是有序表，且不经常变动而查找频繁。它每次取中间位置记录的关键字和目标比较，如果相等就成功；如果中间记录的关键字大于目标，说明目标在前半部分，否则在后半部分，不断把区间一分为二直到找到或区间空。比较次数少、查找速度快、平均性能好是它的三大优点，但插入删除困难，因为要保持有序性。分块查找则放宽了要求：每块内部节点可以任意存放，但块与块之间按关键码值有序。实际做法是把一个大线性表分成若干块，再建一个索引表，索引表里存每块的最大关键码值，索引表本身有序。查找时先对索引表用顺序查找或折半查找确定目标所在块，再在块内做顺序查找。分块查找比顺序查找快得多，但速度不如折半查找。这是典型的“从无序到有序的折中”。笔记里提到的平均查找长度公式 E(n) 隐含了分块大小 s 的选择会影响整体效率，实际做题时如果题干给了 n 和 b，直接按“先在索引表中找块，再在块内找记录”的步骤算期望比较次数，不必硬记公式变形。
4.2 八大排序算法：从直接插入到基数排序的思想辨析
排序算法是上午题的必考区，也是很多人失分的重灾区。直接插入排序像斗地主摸牌，每趟把一个记录按关键字大小插入到前面已经有序的序列里，适合数据量不大且基本有序的序列。简单选择排序每趟从待排记录中选出关键字最小的放到已排序序列末尾，比较次数固定，与初始序列无关，但不稳定，因为交换可能把相等元素的相对顺序打乱。冒泡排序通过相邻两两比较并交换不满足次序要求的一对，每趟把一个最大（小）值送到最终位置，实现简单但效率低。希尔排序按步长 gap 分组，对每组做直接插入排序，然后逐步缩小 gap 直到 1，相当于先让序列宏观有序再微观有序，是插入排序的改进版。快速排序用分治策略，一趟排序把数据分割成两部分，分割点左边都比它小、右边都比它大，再递归排两部分，平均表现最好但最坏情况会退化到 O(n²)，而且不稳定。堆排序利用堆结构来选最大或最小值，每趟把堆顶和最末元素交换再调整堆，全程 O(nlog₂n)，但没有利用缓存局部性，且不稳定。归并排序把序列看成 n 个长度为 1 的有序表，两两归并，直到合成一个有序表，稳定但需要 O(n) 辅助空间。基数排序不看关键字大小，而是按各位的值做“分配”和“收集”，比如先按个位数入 0 到 9 的桶再按桶顺序取出，再按十位重复，适合数字位数不多的情况。做题时遇到“哪种排序最坏也是 O(nlog₂n)”就选堆排序或归并排序，遇到“稳定”就排除选择和快排希尔堆排。
4.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(n+rd)) | O(d(n+rd)) | O(d(n+rd)) | O(rd) | 稳定 |
记忆方法有很多，我用的是“稳四家”：直接插入、冒泡、归并、基数稳定，剩下四个不稳定。辅助空间只看耗内存多的：归并 O(n)、基数 O(rd)、快排 O(log₂n)，其余都是 O(1)。堆排序的时间复杂度三个情况全是 O(nlog₂n)，这个特征是它和归并排序共同的优势。
4.4 堆判断实战：用序列验证小根堆
堆排序里“什么是堆”经常单独出题。堆的定义是 n 个元素的序列满足一组不等式，小根堆要求每个父节点值小于等于两个孩子节点值。笔记原题给了四个序列，问哪个是堆排序里的堆，正确答案是 B：(10, 18, 15, 20, 50, 80, 30, 60)。拿它做范例，我习惯把数组下标按完全二叉树排开：下标 0 是根 10，下标 1 和 2 是它的两个孩子 18 和 15，10 小于 18、10 小于 15，根满足；再看下标 1 的孩子是下标 3 的 20 和下标 4 的 50，18 小于 20、18 小于 50；下标 2 的孩子是下标 5 的 80 和下标 6 的 30，15 小于 80、15 小于 30；最后下标 3 的孩子是下标 7 的 60，20 小于 60。全表都满足父节点不大于孩子节点，所以这是合法小根堆。考试时用这个“逐节点检查法”比自己凭感觉判断快得多，每一步只要算一遍左孩子下标 2i+1、右孩子下标 2i+2，最多检查到 n/2 位置。
5. 常见问题排查：五类高频易错点的复盘
5.1 邻接矩阵的行列混淆：问入度却数了行
现象：遇到有向图求“某顶点入度”，直接在邻接矩阵第 i 行上求和，然后和选项对不上。原因：有向图的出度才看第 i 行，入度要看第 j 列，相邻矩阵的行列含义不对称。解决：做题前先在草稿纸写一行字“行出列入”，然后在矩阵旁边标清当前题目问的是出度还是入度，再决定数行还是数列。无向图不需要区分，但也要注意对角线和自环的值要算进度。
5.2 哈夫曼编码和参考答案不一致：不是算错而是约定不同
现象：自己按哈夫曼树构造得出的“face”编码串和官方解析给出的不一样，怀疑自己建错树。原因：哈夫曼构造过程不唯一，尤其是存在权值相等的节点时，合并顺序可以不同，且左右子树互换也会改变 0/1 路径。解决：先核对 WPL，只要 WPL 最小，树就是合法的；再看题目有没有规定“左小右大、左 0 右 1”或教材统一约定，如果题目给定了约定，就按约定重新执行一遍合并。刷题时我会把题目答案里的编码串反推回树形，检查路径深度和字符频率是否对应，这样能快速判断是自己顺序错了还是出题人的约定不同。
5.3 排序稳定性记忆翻车：把堆排序当成稳定排序
现象：选择题问“以下哪种排序算法是稳定的”，选了堆排序或者快速排序。原因：稳定性取决于相等元素在排序过程中是否可能发生相对位置交换。堆排序在调整堆时，父子节点交换可能让相等元素的先后关系改变；快速排序的分割交换同样会破坏相对顺序。解决：直接背结论“直接插入、冒泡、归并、基数稳定”，其他全是“不稳定”。如果还记不住，就反过来想：不稳定的一共五个字“选择希快堆”，这五个字每次考前默一遍，正确率比临场推理高很多。
5.4 广义表长度深度数错：把 L2=((1,2,3)) 的长度写成 3
现象：遇到 L2=((1,2,3))，第一反应是长度 3，因为看到三个数字。原因：求长度要把最外层那对括号删掉后再看剩下几个元素组，L2 删掉最外层括号后剩下的是 (1,2,3) 这一个子表，所以长度是 1。解决：先画括号层级，数完最外层括号内部的逗号个数再减掉无关干扰。L1=((a,(a,b),((a,b),c))) 的最外层括号内部有四个元素组，所以长度 4，深度从最外层到最内层数四层括号也是 4。每次做这类题都先写“长度看最外层内部逗号拆分出的组数，深度看括号嵌套层数”，就能避免凭眼睛数数字的毛病。
5.5 CPU 组成与寻址方式：忽略控制器处理异常的能力
现象：单选题问 CPU 由哪些部分组成，考生少选了控制器或漏掉“处理异常事件”这个职责。原因：把 CPU 简单等同于“运算器+寄存器”，忘了控制器不仅要保证程序正确执行，还要在遇到异常事件时做出响应。解决：把 CPU 组成背成一句话“运算器、控制器、寄存器、内部总线”，再记住立即寻址获取操作数最快，因为操作数直接包含在指令中，不需要访存。这些题属于纯记忆题，丢分很可惜，整理成口诀每天扫一眼即可。
6. 考点笔记的进阶用法：考前自测卡与条件反射训练
这份笔记通读两遍只能算“见过”，真正能帮你在考场上拿分的是把每个结论变成条件反射。我的习惯是考前十天每天花二十分钟做一张自测卡：把笔记里的重要结论挖空，然后像做填空题一样快速默写。比如“有向图邻接矩阵第 j 列元素之和是____”“八大排序中稳定的四个是____”“哈夫曼树的带权路径长度计算方式是____”“广义表 L2=((1,2,3)) 的长度是____”。用笔记里的内容把这些填空题出成二十道，每天换着顺序做，错的题标记出来，第二天先复习错题再测新题。这套方法看上去很土，但它能把“看着会”的模糊记忆变成“写得出来”的扎实记忆。另一个进阶技巧是给每个算法配一道“判断型”小题，比如给一个序列直接问“这是小根堆吗”，然后按下标检查法画完全二叉树，这也是我考前最爱用来练手的题型。做完这些之后，再回到笔记里看所有“易错点”标注，你会发现那些坑基本都踩过了。从那以后我每次考前都会强制自己走一遍这种“填表式自测”，不再盲目翻笔记当复习，虽然过程枯燥，但效果比反复阅读强不少。希望帮到你。
本文还有配套的精品资源，点击获取
