简介一份面向软考软件设计师中级考生的核心考点笔记精编自考试高频内容适合考前快速建立知识框架并针对薄弱环节强化记忆。笔记系统展开数据结构、树结构、查找与排序四大模块覆盖邻接矩阵、顺序/链式/散列/索引存储满二叉树、平衡二叉树、哈夫曼树二分查找、分块查找以及直接插入、冒泡、希尔、快速、堆排序等算法并附有复杂度对比、易错点提示与典型例题解析。其中哈夫曼树、AVL树、堆排序等重难点均配有计算演示和解题思路便于考生在有限时间内掌握得分关键。文档另含难点公式与常见错误提醒备考时可快速定位重点。资源为单个Word文档压缩包大小3.37MB下载后可导入阅读或打印背诵。目前已有381人学习下载对冲刺软考中级、查漏补缺和考前背记均有实用价值。1. 软件设计师中级考点笔记为什么上午题的高频考点几乎都集中在这四块先交代场景。考过软考中级软件设计师的人都有同感上午的选择题不难难在“记不住”。上午题考的是概念的一锤定音比如邻接矩阵的出入度、堆的判断、哈夫曼编码一道题一分错了就是错了没有过程分。这份精华版笔记做的就是把官方教材里散落的考点按数据结构、查找、排序、存储与编码四个块重新归档每个考点给结论、给例题、给易错提醒。适合两类人一类是已经看完教材但不知道重点在哪想在考前快速过一遍另一类是直接拿它当主线配合真题查漏补缺。它不是教材的替代品而是把教材里最容易出选择题的“判断型考点”提炼出来的浓缩版。数据结构这部分在上午题里的占比不低常考的其实就三类图的邻接矩阵、存储结构选型、广义表的长度深度。这三类考点的共性是“概念简单但措辞刁钻”比如同样一个矩阵无向图和有向图的读法完全不同。下面逐个拆。2.1 邻接矩阵无向图看行有向图分着看出度和入度邻接矩阵是上午选择题里的常客考法很固定给你一个矩阵问某个顶点的度、出度、入度。规律就两条记死它就行。无向图的邻接矩阵一定是对称的顶点 i 的度等于矩阵第 i 行所有元素之和。比如一个 4 顶点无向图的邻接矩阵1 2 3 4 1 0 1 1 0 2 1 0 1 1 3 1 1 0 1 4 0 1 1 0顶点 3 的度就是第三行的和1 1 0 1 3。有向图的矩阵不一定对称第 i 行元素之和是顶点 i 的出度第 j 列元素之和是顶点 j 的入度。原笔记里那个例子顶点 3 的出度和入度分别是 5 和 16就是同时看了行和列才得出的。提示有向图题目里最容易翻车的是搞反行列。出度看行、入度看列可以默念“行为出、列为入、无向只看行”。为什么考点喜欢落在邻接矩阵而不是邻接表因为矩阵可以用数组直接定位时间复杂度好算图顶点少的时候写矩阵最直观。考试如果问“什么场景适合用邻接矩阵”答案就是顶点数目不多、且需要频繁判断两个顶点之间是否有边的情况。顶点多了矩阵就是稀疏矩阵浪费空间。2.2 四种存储结构顺序、链式、散列、索引的适用边界存储结构这道题基本是送分题但每年都有人选错原因是不看场景直接背定义。我按“什么时候用哪个”给你整理成一张对照关系。存储结构核心特征适用场景代价顺序存储地址连续的存储单元依次存放频繁查询、很少增删插入删除要移动元素链式存储任意地址存储通过指针链接频繁插入、删除、更新存储密度低查找要遍历散列存储数据位置与关键码建立确定关系键值对等值查找多、查找快冲突处理复杂索引存储索引表指针指向数据页数据库表检索索引本身要占空间顺序存储适合“查多改少”链式存储适合“改多查少”这个结论永远对。链式里还有单链表、循环链表、双链表的比较双链表有两个指针域向前向后都能走灵活度比单链表好但每个节点多一个指针的开销因此“灵活度优、开支大”是双链表的标签。散列存储就是哈希表那一套key 经过散列函数直接算存储位置时间复杂度可以做到 O(1)但散列冲突处理开放定址法、链地址法才是隐藏考点。索引存储最典型的例子是数据库的 B 树和 B 树索引表里存的是关键码值和指向数据页的逻辑指针用来减少磁盘 IO不是把所有数据再存一份。2.3 广义表删掉最外层括号数长度数括号层数求深度广义表是一个容易被忽略的小考点但考到了就是白给分。定义很绕实际操作只有两条规则长度 把最外面那层括号删掉之后剩下的元素或子表的个数。深度 括号的最大层数也就是嵌套层数。例题原笔记里给了三组L1 ((a,(a,b),((a,b),c)))最外层括号里只有 1 个元素这是一个子表所以长度是 1剥开括号一层层数最深嵌套到 4 层深度是 4。L2 ((1,2,3))同理长度 1深度 2。L3 (1,2,3)长度 3深度 1。很多人把 L1 的长度数成 3 或 6就是把“最外层括号内元素个数”和“总共有几个原子”搞混了。长度只看括号结构不看原子数这道题几十秒就能做完值得拿分。广义表在考试里很少单独深挖但它和二叉树、递归的关联是下午题喜欢用的背景。你把长度和深度的定义记牢遇到变体题比如让求某个子表的表头和表尾也能顺着推。3. 树与查找二叉排序树、AVL、哈夫曼树与二分查找的固定套路树和查找放一起复习效率最高因为两者都围绕“有序”做文章二叉排序树靠中序有序二分查找靠序列有序哈夫曼树靠权值排序。上午题考树和查找基本就是考你对“有序”两个字的理解深度。3.1 二叉排序树与平衡二叉树中序递增、高度差不超过 1二叉排序树的定义是递归的左子树非空时左子树所有节点的值都小于根节点右子树非空时右子树所有节点的值都大于等于根节点左、右子树本身也是二叉排序树。这里有个细节容易踩坑——右子树是大于等于不是大于题目如果给一个值相等的节点它仍然可以落在右子树。二叉排序树的考题通常有两种一是问中序遍历的结果是什么答案一定是递增序列二是判断某个序列能不能构成二叉排序树的查找序列。后者要验证的不只是大小关系还要看查找路径是否满足二叉排序树性质。平衡二叉树AVL 树的定义是它是一棵空树或者左右两个子树的高度差的绝对值不超过 1并且左右子树也都是一棵平衡二叉树。注意这里说的“高度差”不是节点个数差而是路径长度差。满二叉树的定义则更简单除最后一层外每一层所有节点都有两个子节点或者 0 个子节点。满二叉树和完全二叉树经常被放在一起考满二叉树是“每层都满”完全二叉树是“最后一层从左往右连续”两个词不能混用。3.2 哈夫曼树带权路径最短权值大的叶子靠根哈夫曼树也叫最优二叉树它满足“带权路径长度WPL最短”并且权值越大的叶子越靠近根节点。记住这两点哈夫曼树的题就活了。构造方法固定每次从森林里选两个权值最小的节点合并生成一个新节点新节点权值等于两者之和再放回森林重复直到只剩一棵树。WPL 的计算有两种办法一是所有叶子权值乘以其到根路径长度之和二是在构造过程中把所有合并产生的权值累加两者结果一样。原笔记那道经典题文件中出现 6 个字符 a、b、c、d、e、f问定长编码的码长和“face”的哈夫曼编码。定长编码的码长取决于字符总数6 个字符用 3 位二进制000~101就够了这个逻辑很简单。哈夫曼编码则要画树先按频率排序每次合并最小的两个左子树标 0、右子树标 1做题时统一按“左小右大”画虽然哈夫曼树本身没规定左右大小但考试默认这样画方便写编码再从根节点走到目标字符途经的 0/1 串起来就是编码。这道题答案是 B001110110011。提示如果题目只问编码长度最短不等于问 WPL 最小。前者是单个字符的码长后者是所有字符加权后的总长度别混。3.3 二分查找与分块查找有序是前提索引是桥梁二分查找折半查找的适用场景非常明确不经常变动但查找频繁的有序列表。优点是比较次数少、查找速度快、平均性能好缺点有两个一是待查表必须有序二是插入删除困难。这组优缺点几乎每年都有选项在考看到“折半查找”同时出现“插入删除方便”这种说法可以直接排除。实现逻辑假设表按升序排列每次取中间位置记录的关键字与目标比较相等就命中关键字比目标大则在前一子表继续折半比目标小则在后一子表继续折半重复直到子表不存在。这里需要注意二分查找的下标计算涉及 (low high) / 2递归或迭代都能写考试主要考比较次数和最坏时间复杂度。分块查找是顺序查找和二分查找的折中把一个大的线性表分成若干块块内节点可以任意存放但块与块之间必须有序对任意 i第 i 块中的所有节点关键码值都小于第 i1 块的所有节点。同时建立一个索引表把每块的最大关键码值作为索引值存起来。查找时先在索引表中确定节点属于哪一块索引表有序可以用顺序或折半查再在块内用顺序查找。它适合节点动态变化的情况速度比顺序查找快得多但不如折半查找。如果题目给 n 个节点分成 b 块、每块 s 个平均查找长度要按索引表内查找长度加块内查找长度来算这个值的计算经常被出成大题里的小问。4. 八大排序插入、选择、冒泡、希尔、快排、堆排、归并、基数怎么选排序是上午题里最稳定的一块几乎每次都会考两三道。难点不在写代码而在把八个算法的时间复杂度、空间复杂度、稳定性背成条件反射以及看懂“某场景该选哪个”的描述。这一章我把它们按简单和进阶分开讲最后给一张可直接背的对照表。4.1 四个简单排序谁在什么时候最划算直接插入排序形象理解就是扑克牌抓牌每抓到一张把它插到手里已经有序的牌中合适位置。它最好的情况是序列基本有序此时接近 O(n)最坏和平均都是 O(n²)。它稳定空间 O(1)数据量不大时它就是首选因为代码短、常数小。简单选择排序每趟从待排序序列里选出关键字最小的放到已排序末尾。它的比较次数固定和初始序列无关最好最坏平均都是 O(n²)这个特性很容易被拿来出题——问“哪种排序的时间复杂度和初始状态无关”时要想到它。它不稳定因为相同关键字的相对位置可能被打破。冒泡排序两两比较相邻元素顺序不对就交换一趟下来最大的元素沉到末尾所以叫冒泡。它对“基本有序”的序列极其友好最好情况 O(n)但一般场景下效率低最坏 O(n²)稳定。下午题偶尔会要求模拟一趟冒泡后的序列注意是相邻交换不是选择和某个固定位置换。希尔排序是直接插入排序的改进核心是分组按步长 gap 分组每组做直接插入排序gap 逐渐减小最后 gap1 时整个序列变成一组再做一次插入。它的时间复杂度无法精确给出教材上通常标“不存在”或近似 O(n^1.3)空间 O(1)不稳定。考概念题时记住“希尔排序是插入排序的改进”就够了。4.2 四个进阶排序分治、堆、归并与基数快速排序是分治策略的典型代表一趟排序选定一个基准值把序列分成独立两部分左边都比基准小、右边都比基准大然后递归处理左右两部分。平均时间复杂度 O(n log2 n)最坏情况是序列已经有序且每次基准都选到端点会退化到 O(n²)这也是快排的主要缺点。辅助空间 O(log2 n)递归栈不稳定。堆排序基于堆的定义n 个元素的序列当且仅当满足 ki ≤ k2i 且 ki ≤ k2i1小顶堆或 ki ≥ k2i 且 ki ≥ k2i1大顶堆时称为堆。堆排序分建堆和调整两步常考的是判断给定序列是否构成堆其次考它的时间复杂度最好最坏平均全是 O(n log2 n)辅助空间 O(1)不稳定。归并排序是把序列看成 n 个长度为 1 的有序序列把相邻的有序表成对归并得到 n/2 个长度为 2 的有序表再继续归并直到整个序列有序。它最有价值的特性是稳定辅助空间 O(n)时间稳定在 O(n log2 n)。如果题目要求“排序算法必须稳定且时间复杂度 O(n log2 n)”答案就是归并排序。基数排序和前面七种完全不同它不比较关键字大小而是按关键字的各个位的值做“分配”和“收集”。准备从 0 到 9 十个桶先按个位数分配再把桶里的数按桶编号从 0 到 9 依次收集得到按个位排序的序列再按十位、百位重复。复杂度 O(d(nrd))其中 d 是关键字的位数、rd 是基数通常是 10空间 O(rd)稳定。看到“不需要比较关键字大小”的直接选基数排序。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(n log2 n)O(n log2 n)O(n²)O(log2 n)不稳定堆排序O(n log2 n)O(n log2 n)O(n log2 n)O(1)不稳定归并排序O(n log2 n)O(n log2 n)O(n log2 n)O(n)稳定基数排序O(d(nrd))O(d(nrd))O(d(nrd))O(rd)稳定秒杀技巧三条。第一稳定且效率高锁定归并。第二初始基本有序找直接插入或冒泡。第三最坏时间 O(n²) 且平均是 O(n log2 n) 的只有快排所以题目说“最坏情况下效率最低的 O(n log2 n) 算法”指的就是快速排序的退化场景。5. 常见问题与避坑堆判断、归并路数、表达式记法、码制范围的高频翻车点以下这几类题目是我反复看到备考群和学员出错的集中区每一条都是“现象—原因—解决”三步走。5.1 堆排序判断题先画完全二叉树再验父子大小关系现象很多人在做“下列序列哪个是堆”时喜欢直接把序列排个序看到有序序列就以为是堆结果选错。原因堆不是完全有序而是局部有序。小顶堆只要求父节点不大于两个子节点并不要求兄弟节点之间有序。直接排序后的序列当然满足这个条件但它不是判断依据反而会干扰你。解决把序列按完全二叉树的位置摆放第 i 个元素的两个孩子是 2i 和 2i1逐个检查是否满足 ki ≤ k2i 且 ki ≤ k2i1小顶堆。原题四个选项只有 B(10,18,15,20,50,80,30,60) 满足父节点小于等于子节点。检查顺序注意 i 只需要取到 ⌊n/2⌋后面的节点都是叶子不用验。5.2 归并路数公式三趟 27 个元素路数是 3 不是 2现象题目“若对 27 个元素只进行三趟多路归并排序则选取的归并路数为多少”有人按常规二路归并去推选成 2。原因教材默认讲的是二路归并但考试会放大到多路归并m 个元素经过 k 路归并一趟能处理 k 个有序子序列所以公式是 k^t ≥ m换算成对数就是归并路数 |log 以 k 为底 m 的对数|本题 log 以 3 为底 27 的对数等于 3。解决看到“多路归并”四个字先确认路数不是 2把元素个数和趟数代入公式答案选 B。这类题只要记住公式就稳了不要靠直觉。5.3 前缀表达式与后缀表达式扫描方向和运算顺序别记反现象前缀表达式“- × 3 4 5 6”和后缀表达式“3 4 5 × 6 -”结果一样都是 29但有人计算过程中把 3 和 4 的相加顺序搞反或者把减法的被减数和减数弄反。原因前缀是从右往左扫描遇到运算符弹出栈顶两个数计算时要按“栈顶元素 op 次顶元素”的顺序做后缀是从左往右扫描计算时按“次顶元素 op 栈顶元素”。两道题看起来都是 3 和 4 相加但减法这种不满足交换律的运算符顺序错了答案就反了。解决做题前先在草稿纸上写下扫描方向再写运算顺序。前缀记“右扫、栈顶在前”后缀记“左扫、次顶在前”分别对应“弹出两个数后谁当被减数”。平时练习时每次做完用中缀还原验算一遍能明显降低出错率。5.4 原码反码补码移码范围表与记忆技巧一起背现象机器字长为 n 时补码定点整数的下界是多少有人把范围和原码搞混写成 -(2^(n-1)-1)漏掉了补码能多表示一个负数的事实。原因原码和反码的整数范围是对称的 [-(2^(n-1)-1), 2^(n-1)-1]补码和移码范围是 [-2^(n-1), 2^(n-1)-1]正因为不对称所以补码能表示的最小负数比原码多一位。如果只背零散数字考试时很容易记混。解决把 A 2^(n-1)、B 1-2^-(n-1) 设出来直接套规律——原码反码整数范围都是 [-(A-1), A-1]补码移码是 [-A, A-1]定点小数方面原码反码是 [-B, B]补码移码是 [-1, B]。配合“补码最适合加减运算、移码最适合表示浮点阶码”这条应用结论一起记选择题基本不会失手。5.5 指令寻址方式与 CPU 组成零散小分也别丢现象立即寻址、直接寻址、寄存器寻址、寄存器间接寻址这四种方式经常混在一起考题干问“哪种方式获取操作数最快”有人选了直接寻址。原因四种方式信息获取路径不同。立即寻址的操作数直接写在指令里取指的时候就能拿到是最快的直接寻址拿到的是操作数地址还要再访问一次内存寄存器寻址操作数在寄存器里比访存快但不如指令直接携带寄存器间接寻址拿的是地址要去内存取真正操作数。关键区分是“操作数本身在哪”和“操作数地址在哪”。解决把四种方式按“取操作数的步骤数”排序立即寻址 寄存器寻址 直接寻址 寄存器间接寻址。CPU 组成那道常考题就一句话运算器、控制器、寄存器、内部总线控制器既要保证程序正确执行也要处理异常事件千万别把“存储器”加进 CPU 组成里。6. 考前 72 小时复习路径用精华笔记做三遍查漏补缺拿到这份精华版笔记最忌讳的是从头到尾当小说读一遍就算复习完。我用它带过不止一轮备考最后三天的用法固定是三条线并行第一遍按章节快速过一遍所有“适用场景”的结论。数据结构、存储结构、查找排序这些考点的选择题本质考的是“什么场景用什么方案”。我习惯把每个结论用笔划出来比如“顺序存储适合频繁查询”“链式存储适合频繁插入删除”“二分查找要求有序表”划完合上笔记自己拿白纸把这十几条结论默写出来写不出来的就是漏洞回头再看一眼。第二遍把笔记里的例题全部挡住答案重做。哈夫曼 face 编码、堆判断、归并路数、前缀后缀表达式计算、邻接矩阵的度数这几道是高频原题变形重做时不要只看算出来的数对不对要把中间步骤也写出来比如哈夫曼树的合并过程、堆的父子关系检查过程因为考试时步骤分在草稿上对错一目了然。第三遍考前一个晚上专门默写两张表一张是八大排序的复杂度和稳定性对照表另一张是原码反码补码移码的范围表。这两张表能在考试前五分钟帮你快速定位四五道送分题性价比最高。我备考软考软件设计师中级时吃过最大的亏就是只看定义不做例题觉得“哈夫曼树我懂了”结果真题里换个字符、换个权值就卡住。从那以后每份笔记到我手里都会强制走一遍“先做题、后看解析、再回头读定义”的流程。你有这份精华笔记在手把例题吃透再配上近三年下午题练手上午题这部分分数是稳的。希望帮到你。本文还有配套的精品资源点击获取