软考中级考点笔记全解析：数据结构、排序与高频易错点

简介：软件设计师中级考点笔记精华版定位为软考中级考证冲刺资料，面向正在系统复习数据结构、算法与程序设计的考生。内容聚焦考试常考的核心知识点、难点公式与易错陷阱，将邻接矩阵、顺序/链式/散列/索引存储结构、满二叉树、AVL树、哈夫曼树，以及二分查找、分块查找和常用排序算法等高频考点集中整理，便于在有限时间内快速建立知识框架。资源共1个文件，为docx文档，压缩包仅3.37MB，查阅方便，可直接用于标注、打印或手机端浏览。文档结合具体例题与计算过程，如哈夫曼树WPL计算、排序算法复杂度对比，帮助理解而非死记硬背；目前已有381人学习下载，适合考前冲刺、薄弱点强化及考场前速览复习。无论是初次备考还是二战巩固，这份精华笔记都能提供清晰的梳理和重点提醒。

1. 软考中级备考，先搞清楚这份考点笔记压中了什么

考软件设计师（中级）的人，最纠结的就是知识点又多又散，上午题 75 道选择题里，数据结构和计算机系统基础占了将近一半的分值。这份考点笔记精华版把高频考点按模块压好了：邻接矩阵、二叉排序树、哈夫曼树、八大排序、原码补码、指令寻址，全是选择题里反复出现的面孔。它适合两类人：一类是准备软考中级考证的考生，想在考前把考点系统地过一遍；另一类是刷过几套真题但总差几分的考生，你的失分点大概率在广义表长度深度、归并路数、前缀后缀表达式这种小坑上。下面按模块讲清楚考什么、怎么答、哪里容易翻车。

2. 数据结构：图的邻接矩阵与存储结构是送分题

2.1 邻接矩阵：无向图看行，有向图行是出度、列是入度

邻接矩阵是软考上午题里出现频率很高的一类小题，难度不大，但很多人在有向图上栽跟头。先记两个结论：无向图里，邻接矩阵第 i 行元素的和就是顶点 i 的度；有向图里，第 i 行元素之和是顶点 i 的出度，第 j 列元素之和是顶点 j 的入度。

举笔记里的例子，一个无向图如果邻接矩阵中第四行只有两个位置是 1，那顶点 4 的度就是 2，因为无向图里一条边会在矩阵里以对称的两个 1 出现，对行求和正好数出和顶点 4 相连的边数。有向图的例子是顶点 3 的出度为 5、入度为 16，说明从顶点 3 出发的弧比指向顶点 3 的弧少得多，这在邻接矩阵里一眼就能看出行和与列和的差距。

这类题通常这么答：先判断题给的是无向图还是有向图，无向图直接对行求和，不用区分方向；有向图必须分开算，行和是出度、列和是入度。最怕的就是题目明明给的是有向图，你还对行求和当作"度"用，那必错。另外无向图的邻接矩阵一定是对称的，有向图不一定对称，这也是快速排除错误选项的抓手。

真题里还有一种变体：给出某个顶点的出度和入度，反推邻接矩阵某一行或某一列的和。这题看起来唬人，本质还是在考「行出列入」的结论。你只要在草稿纸上把行和、列和分别标出来，就不会被绕晕。平时刷题时建议养成习惯：有向图一律把行、列分开写，哪怕题目没问，也顺手算一遍。

2.2 存储结构：四种结构按场景对号入座

顺序存储结构用一组地址连续的存储单元依次存放线性表的数据元素，适合频繁查询的场景。因为地址连续，按下标就能直接算出元素位置，查询代价低。链式存储结构在计算机里用一组任意的存储单元存放数据元素，这组存储单元可以连续也可以不连续，元素之间靠指针维护关系，插入和删除只需要改指针，所以适合较频繁地插入、删除、更新元素的场景。

散列存储结构是把数据元素的存储位置与关键码之间建立确定对应关系，也就是键值对，通过散列函数直接定位，查找速度非常快。索引存储结构是一个单独的物理数据库结构，它是某个表中一列或若干列值的集合和相应的指向表中物理标识这些值的数据页的逻辑指针清单，典型场景就是数据库索引。

真题经常给一句话场景让选存储结构，这种题别靠死背，靠关键词锁定：

这种选型题通常这么答：读题划线，出现"查询多"就选顺序，出现"插入删除多"就选链式，出现"键值对"就选散列，出现"数据库"就选索引。四个选项全考的情况下，把每种结构对应的典型例子写在一旁，再对照题干关键词，基本不会丢分。

2.3 链表三兄弟：单链表、循环链表、双链表怎么选

链表属于链式存储，考试会拿单链表、循环链表、双链表三者做比较。单链表只有一个指针域，每个结点存一个 next 指针；循环链表把尾结点的指针指向头结点，形成环；双链表每个结点多了一个前驱指针，两个指针域分别指向前驱和后继。笔记里的结论很直白：双链表有两个指针域，灵活度优于单链表，但开支也要大一些，因为每个结点都要多存一个指针。

选择题里问"哪种链表既能向前找又能向后找"，答案必然是双链表；问"哪种结构开销最小"，通常选单链表。还有一类题比较删除操作：单链表删除某个结点，如果已知前驱是 O(1)，未知前驱就得遍历查找；双链表因为有前驱指针，删除当前结点可以直接操作。

A同学第一次做这类题时，觉得"双链表这么灵活为什么不都用双链表"，后来才想明白：资源有限，双链表用空间换时间。面试官想听的就是这句"以空间换时间"，你把指针域的额外开销答出来，比只说一句"双链表灵活"要稳得多。真题里偶尔会把存储结构和后面排序的"稳定性"放在一起考，这时候要清楚存储结构的"开销"和排序算法的"稳定"是两个维度，别混。

3. 树型结构：二叉排序树、哈夫曼树、平衡二叉树的高频考法

3.1 二叉排序树：左小右大，中序遍历得到递增序列

二叉排序树（也称二叉查找树）的考点非常固定：若左子树非空，则左子树上所有结点的值均小于它的根结点的值；若右子树非空，则右子树上所有结点的值均大于等于它的根结点的值；左、右子树也分别为二叉排序树。

围绕这个定义能出好几道题。第一类是判断一个二叉树是不是二叉排序树，做法是看中序遍历序列是否递增，如果中序序列是严格递增（或按题目要求非递减），就是。第二类是给一个插入序列，问构造出的二叉排序树长什么样，直接按定义逐个插入即可。第三类考性质：关键字最大的结点可以有左子树，但一定没有右子树。为什么？如果它有右子树，右子树上的值都要大于等于它，它就不可能是最大的；而左子树的值都比它小，所以可以存在。

这类题通常这么答：最大结点只看右子树空不空，最小结点只看左子树空不空。很多人把这两个记反，拿到题先画图验证一遍，别凭感觉。还有一个很隐蔽的考法：中序遍历二叉排序树得到一个递增序列，问你该序列最后一个元素对应哪个结点——必然是关键字最大的那个，而且它没有右孩子，这个结论可以直接用。

3.2 哈夫曼树：权值越大的叶子越靠近根，WPL 才最短

哈夫曼树也叫最优二叉树，定义是带权路径长度 WPL 最短的树。记住一句核心：权值越大的叶子节点越靠近根节点。这样权值大的结点路径短，权值小的结点路径长，整体 WPL 才能最小。

构造哈夫曼树的步骤只有一句话：把所有叶子按权值从小到大排好，每次取出两个权值最小的结点合并成一个新结点，新结点的权值等于两者之和，再放回集合里继续重复，直到只剩一棵树。做题时务必在草稿纸上画出来，别心算。

WPL 计算是高频题，公式是每个叶子权值乘以它到根的距离之和。注意哈夫曼树中新增的"内部结点"不参与编码，只参与路径计算。考试时最常见的是给出字符和频率，让你构造哈夫曼树再算 WPL，或者直接问某个字符序列的哈夫曼编码。

3.3 平衡二叉树与满二叉树：判断标准要分清

平衡二叉树又叫 AVL 树，性质是：它是一棵空树，或者它的左右两个子树的高度差的绝对值不超过 1，并且左右两个子树都是一棵平衡二叉树。注意两个"都"字：根的左右子树高度差不超过 1 还不够，左右子树内部也必须各自平衡。这是选择题常挖的坑——给你一棵根结点左右高度差为 1、但某一侧的孩子高度差为 2 的树，问是不是 AVL，答案是"不是"。

满二叉树按笔记里的定义：除最后一层无任何子节点外，每一层上的所有结点都有两个子结点或 0 个子节点。这个定义容易和"完全二叉树"混，但考试以教材定义为准。满二叉树是每层都被填满，完全二叉树是最后一层从左往右连续。判断方式就是画图：满二叉树每一层的结点数都达到最大值。

很多考生在这两个概念上丢分，不是因为不知道定义，而是做题太快没看全选项。真题常把 AVL、满二叉树、二叉排序树放在同一个选择题的不同选项里，你必须在读题时先把"平衡"和"排序"两个属性分开：AVL 管的是高度差，二叉排序树管的是值的大小关系，二者互不排斥——一棵树可以既是二叉排序树又是平衡二叉树。

3.4 真题演练：定长编码码长与哈夫曼编码 "face"

来看笔记里的一道完整原题：已知一个文件中出现的各字符及其对应的频率，若采用定长编码，则字符的码长应为多少？若采用 Huffman 编码，则字符序列 "face" 的编码应为多少？

先解决定长编码。文件里一共有 a、b、c、d、e、f 六个字符，定长编码要能区分 6 个不同的字符。用 2 位二进制只能表示 4 种组合，不够；3 位二进制可以表示 8 种组合，足够覆盖 6 个字符。所以第一问选 B（3 位）。这类题的关键是看字符种类数 n，码长取满足 2^k ≥ n 的最小整数。

第二问是哈夫曼编码。构造哈夫曼树时，通常写成左小右大的形式，赋值时左 0 右 1。"face" 的编码就是分别找到 f、a、c、e 四个字符，从根节点出发记下路径上的 0 和 1。假设按左 0 右 1 推导，f 的编码为 1100，a 为 010，c 为 011，e 为 01，拼接起来就是 110001001101，对应选项 A。

为什么会有考生在这题上翻车？一是定长编码算成 2 位，忘记 2 位最多表示 4 种状态；二是哈夫曼编码的方向没统一，一会儿左 0 右 1，一会儿左 1 右 0，只要有一个字符方向错，整道题就废了。这类题通常这么答：先数字符个数定码长，再老老实实在草稿纸上画树，最后把路径串起来。别想着省那两分钟。

4. 查找与排序：二分查找、分块查找与八大排序复杂度

4.1 二分查找：有序表才配得上折半

二分查找（折半查找）的适用情况很明确：不经常变动而查找频繁的有序列表。优点是比较次数少、查找速度快、平均性能好；缺点是要求待查表为有序表，插入删除困难。

实现逻辑是：假设表中元素按升序排列，取表中间位置记录的关键字与查找关键字比较。相等则查找成功；如果中间记录的关键字大于查找关键字，说明目标在前半部分，进一步查找前一子表；否则查找后一子表。重复以上过程，直到找到或子表不存在。

def binary_search(arr, target): left, right = 0, len(arr) - 1 while left <= right: mid = (left + right) // 2 if arr[mid] == target: return mid elif arr[mid] > target: right = mid - 1 # 目标在左半区，收缩右边界 else: left = mid + 1 # 目标在右半区，收缩左边界 return -1

这段代码里，arr 是升序排列的有序表，target 是要查的关键字。mid 用整数除法取中间位置，每次比较后要么直接返回，要么把区间缩小一半。循环条件是 left <= right，如果写成 left < right 会漏掉区间只剩一个元素的情况。这个细节选择题爱考：问"循环结束条件写错会导致什么"，答案通常是漏查边界元素。

笔试里二分查找的变体题很多，比如查找第一个不小于目标值的位置、旋转数组找最小值，但软考上午题主要还是考最基础的版本。这类题通常这么答：先确认数组有序，再模拟一次折半过程，把每次的 mid 算出来。很多考生习惯直接套代码不画过程，结果选项里给的 mid 下标全错，建议小题也在草稿纸上画三步。

4.2 分块查找：索引表 + 块间有序、块内随意

分块查找的适用情况是节点动态变化。它比顺序查找快得多，但速度不如折半查找法，是介于两者之间的折中方案。

实现算法分两步。第一步，把一个大的线性表分解成若干块，每块中的节点可以任意存放，但块与块之间必须排序。比如按关键码值非递减排序，那么第 i 块中的所有节点的关键码值都必须小于第 i+1 块中的所有节点的关键码值。第二步，建立一个索引表，把每块中的最大关键码值作为索引表的关键码值，按块的顺序存放到一个辅助数组中。注意索引表本身也是有序的。

查找时先在索引表中定位所在块。因为索引表有序，所以可以对索引表采用顺序查找或折半查找；确定块之后，块内再采用顺序查找。这里有个很容易忽略的考点：索引表查的是块，块内查的是记录。选择题经常把这两步的顺序颠倒，说成"先在块内顺序查找，再在索引表折半定位"，那就不对了。

笔记里还提到了平均查找长度的概念：总共有 n 个节点，分成大小相等的 b 块，每块有 s = n/b 个元素。分块查找的代价等于索引表的查找代价加块内顺序查找的代价。真题一般只要求定性判断：当块数少、每块元素多时，块内顺序查找代价大；当块数多、每块元素少时，索引表查找代价上升。你要能说出"分块查找把顺序查找和折半查找做了个组合"这个设计思路，选择题就难不倒你。

4.3 八大排序：复杂度表背下来，选择题秒杀

排序是软考上午题的必考模块，八大排序各自对应一句话：直接插入排序是每趟把一个记录按其关键字大小插入到有序队列的合适位置，斗地主摸牌就是这规则；简单选择排序每趟从待排序记录中选出关键字最小的，放在已排序记录序列末尾；冒泡排序两两比较并交换不满足次序要求的元素；希尔排序按步长 gap 分组，对每组做直接插入排序，步长逐渐减小到 1；快速排序通过一趟排序把数据分割成独立的两部分，分割点左边都比它小、右边都比它大，用了分治法；堆排序借助堆这种数据结构反复调整；归并排序把 n 个长度为 1 的有序序列两两归并；基数排序不看关键字大小，按个位、十位等各位的值做"分配"与"收集"。

这张表是性价比最高的一张表，几乎每年都直接考或间接考。记忆要点：稳定的只有直接插入、冒泡、归并、基数四个，其余四个不稳定；快排在平均和最好的情况下是 O(n log₂n)，最坏退化成 O(n²)，这也是快排最大的软肋；归并排序的辅助空间是 O(n)，快排是 O(log₂n)，堆排序是 O(1)，选择题问"哪个排序辅助空间最大"时选归并。

复杂度选择题通常这么答：先看稳定性，稳定集合里排除不稳定项；再看辅助空间，排除明显不符的；最后看最坏复杂度。比如问"最坏情况下时间复杂度为 O(n²) 且不稳定的是"，快排和简单选择、堆排序都落在候选里，再结合"平均也是 O(n log₂n)"锁定快排。

4.4 真题演练：堆排序的判定

堆的定义：n 个元素的序列 {k1, k2, …, kn} 当且仅当满足 ki ≤ k2i 且 ki ≤ k2i+1（小根堆）或 ki ≥ k2i 且 ki ≥ k2i+1（大根堆）时称为堆。真题给出四个序列，问哪个可以作为堆排序里的堆：

A. (10, 50, 80, 30, 60, 20, 15, 18) B. (10, 18, 15, 20, 50, 80, 30, 60) C. (10, 15, 18, 50, 80, 30, 60, 20) D. (10, 30, 60, 20, 15, 18, 50, 80)

正确答案是 B。验证方法很简单：把序列看成一棵完全二叉树的层序序列，下标 1 到 n，只需要检查 i = 1 到 floor(n/2) 的结点，看它是否小于等于它的左右孩子。B 序列中，10 ≤ 18 且 10 ≤ 15；18 ≤ 20 且 18 ≤ 50；15 ≤ 80 且 15 ≤ 30；20 ≤ 60，全部满足，构成小根堆。

选项 A 在 i=2 的位置，50 大于左孩子 30，直接淘汰；选项 C 在 i=4 的位置，50 大于左孩子 20，淘汰；选项 D 在 i=2 的位置，30 大于左孩子 20，淘汰。这类题通常这么答：不要试图心算，把序列按完全二叉树形式在草稿纸上画出来，一层层排好，再逐结点验证父子关系。堆排序的核心不是"数值上像不像有序数组"，而是"每个父结点和它的孩子之间是否满足大小关系"。

5. 高频易错点：广义表、归并路数、表达式记法与码制范围

5.1 广义表的长度和深度：一个删括号，一个数括号

错在哪：把长度和深度搞反，或者数错括号层数。这是软考上午题里典型的"看着会、一做就错"的小题。

为什么错：广义表的长度，是把最外面那层的括号删了以后，剩下的元素（组）个数；深度是括号的层数。两者的计算方式完全不同，很多人只记"长度是元素个数"，然后就按"括号里有多少个原子"去数，忽略了"子表整体算一个元素"。

笔记里的三个例子足够说明。L1 = ((a,(a,b),((a,b),c)))，把最外层一对括号删掉，剩下 (a,(a,b),((a,b),c)) 这整个子表，所以长度是 1，不是 4；深度从外往里数括号嵌套层数为 4。L2 = ((1,2,3))，删掉最外层括号后只剩 (1,2,3) 一个组，长度 1，深度 2。L3 = (1,2,3)，删掉最外层括号后是 1、2、3 三个元素，长度 3，深度 1。

怎么答对：拿到广义表先画括号层级，删一层算长度，逐层数算深度。长度看最外层逗号分割出的组数，深度看最多嵌套几层括号。考试时经常把 L1、L2、L3 放一起让你对应，这种题只要按"先删括号再数"的流程走一遍就一定不会错。

5.2 归并路数公式：别把指数和趟数搞反

错在哪：把"归并路数"直接当成"归并趟数"算，或者公式代错。归并排序选择题里有一道经典题：若对 27 个元素只进行三趟多路归并排序，则选取的归并路数是多少？

为什么错：多路归并里，k 路归并的意思是每趟把 k 个有序段合并成 1 个有序段。经过 t 趟归并，理论上最多能把 k^t 个初始段合并完。因此 m 个元素（或 m 个初始归并段）、t 趟归并、k 路归并三者之间满足 k^t = m。放进例题就是 k³ = 27，所以 k = 3。

怎么答对：读题先分清哪个是趟数、哪个是路数。题目说"三趟"是指 t = 3，求的是 k。如果反过来给 k = 2，问几趟能把 100 个元素归并完，那就是求满足 2^t ≥ 100 的最小整数 t。这题的坑在于把 27 开三次方，很多人直接选 2，理由是"二路归并最常见"，但题干已经限定三趟完成，二路归并三趟最多合并 2³ = 8 个段，根本覆盖不了 27 个元素。

5.3 前缀后缀表达式：扫描方向不同，弹栈顺序差一个身位

错在哪：前缀表达式从右往左扫，后缀表达式从左往右扫，但很多人统一按从左往右处理，导致运算顺序颠倒。

为什么错：前缀记法（波兰式）遇到运算符时弹出栈顶两个元素，计算的是"栈顶元素 op 次顶元素"；后缀记法（逆波兰式）遇到运算符时也弹出栈顶两个元素，但计算的是"次顶元素 op 栈顶元素"。加法、乘法无所谓顺序，减法和除法一颠倒就错。

以前的真题：前缀表达式 "- × + 3 4 5 6"，从右往左扫描，把 6、5、4、3 依次入栈；遇到 +，弹出 3 和 4，这里栈顶是 3，次顶是 4，计算 3+4 = 7；遇到 ×，弹出 7 和 5，计算 7×5 = 35；遇到 -，弹出 35 和 6，计算 35-6 = 29。后缀表达式 "3 4 + 5 × 6 -"，从左往右扫码：3、4 入栈，遇 + 弹出 4 和 3，加法无影响；7、5 入栈，遇 × 弹出 5 和 7，乘法无影响；35、6 入栈，遇 - 弹出 6 和 35，必须计算 35-6 = 29。

def eval_postfix(tokens): stack = [] for token in tokens: if token.isdigit(): stack.append(int(token)) else: right = stack.pop() # 栈顶出栈，作为右操作数 left = stack.pop() # 次顶出栈，作为左操作数 if token == '-': stack.append(left - right) elif token == '+': stack.append(left + right) return stack[0]

代码里最关键的是 pop 的先后：先 pop 出来的是栈顶，但要当右操作数；后 pop 出来的是次顶，要当左操作数。如果写反，遇到减法就会算出负值。怎么答对：遇到运算符，永远记住"离运算符最近的扫描方向决定谁先出栈"；后缀表达式里，先出栈的是右操作数。按这个规则代入，所有题目都能做对。

5.4 原码反码补码移码：范围表是最后的防线

错在哪：补码表示的有符号整数，最小值记成 -(2^(n-1) - 1)，漏掉了 -2^(n-1)。为什么错：原码和反码都允许 +0 和 -0 两种表示，所以正负范围对称；补码把 -0 的空间省出来表示 -2^(n-1)，因此最小值比原码多一位。

记忆技巧：令 A = 2^(n-1)，B = 1 - 2^-(n-1)，原码和反码范围内外都对称，补码和移码在负数端多出 -A 和 -1。符号数的应用也常考：最适合数字加减运算的数字编码是补码，最适合表示浮点数阶码的数字编码是移码。

怎么答对：看到"机器字长为 n"立刻把 A = 2^(n-1) 写在草稿纸上；看到"加减运算"选补码，看到"浮点数阶码"选移码。还有一个高频考法是把补码、反码转换放在一起，负数的补码是在反码基础上加 1，反码是符号位不动、其余各位按位取反。这条链路每次考都有人断在半路，建议考前把"原码 → 反码 → 补码 → 移码"四步自己手写两遍。

6. 指令寻址、CPU 组成与考前答题技巧

6.1 指令寻址：四种方式一个表记牢

选择题很喜欢把寄存器寻址和寄存器间接寻址放一起考，让你选"操作数在寄存器里"的是哪个——答案选寄存器寻址。而"寄存器的内容是操作数的地址"则是寄存器间接寻址。这种题没有计算，纯考定义，但每年都有考生混淆，因为四个选项看起来太像了。我的答题习惯是：先把"访问几次内存"标出来，立即寻址和寄存器寻址不访问内存，直接寻址访问一次，寄存器间接寻址访问一次，选择题一列就清楚。

6.2 CPU 组成：控制器的职责别记成运算器

CPU 的组成是运算器、控制器、寄存器和内部总线。其中控制器不仅要保证程序的正确执行，而且要能够处理异常事件。选择题经常问"哪个部件负责异常处理"，答案不是运算器，是控制器。运算器只负责算术和逻辑运算，控制器才负责取指令、分析指令、执行指令和控制程序流程。

还有一个易错点：内部总线也属于 CPU 组成的一部分，有些考生把总线单独划出 CPU，看到选项有"存储器"就犹豫。记住 CPU 内部只有运算器、控制器、寄存器、内部总线四块，外部才接存储器和 I/O。这类题通常这么答：把四部件在草稿纸上写一遍，再逐项看选项，凡是出现"主存""外存"的都不属于 CPU 组成。

6.3 考前一周的答题顺序与提分动作

软考上午题全是客观题，拿分策略比想象中重要。我的建议是：发卷后先做数据结构和排序，因为这两块最像"背了就有分"；再做树型结构和查找题，最后处理系统基础部分的码制和寻址。遇到广义表、归并路数这种小题，先跳过，把后面的大分题保住。

考前一周务必把三张表默写出来：八大排序复杂度与稳定性表、四种码制定点数范围表、四种寻址方式对比表。默写不是背概念，而是练"看到关键词立刻反应"的肌肉记忆。哈夫曼编码、堆判定、AVL 判定、二分查找条件、前缀后缀表达式，这几类题几乎每年轮换着出，属于押题命中率最高的区域。笔记里的易错点部分我每次考前都强制重看一遍，尤其是有向图行列入度出度，别看简单，考场上一紧张最容易犯糊涂。从那以后我每次考前都把码制范围表和排序复杂度表手写一遍，再不想当然地跳步骤。希望帮到你。

本文还有配套的精品资源，点击获取