简介面向备考软考中级软件设计师的考生这份考点笔记精华版以单个 docx 文档整理考试核心知识帮助读者在有限的复习周期内抓住高频考点、难点公式与易错之处。内容围绕数据结构与算法展开邻接矩阵中无向图度数、有向图出度入度的判定顺序、链式、散列、索引四种存储结构的适用场景二叉排序树、平衡二叉树AVL、满二叉树与哈夫曼树及 WPL 计算例题二分查找、分块查找的实现要点与平均查找长度以及直接插入、希尔、快速、堆、归并、基数等排序的过程特点与时间复杂度、空间复杂度、稳定性对比表。资源包共 1 个 docx 文件压缩后约 3.37MB结构紧凑便于打印或平板标注。已有 382 人学习适合按知识点逐条过筛、考前查漏补缺也便于对照例题理解解题思路。1. 上午题里最容易拿分的一项藏在邻接矩阵里软件设计师中级上午卷 75 道选择题数据结构与算法接近三分之一其中真正能靠结论直接拿分的是图的邻接矩阵和排序复杂度这类“看一眼就能答”的点。很多人栽在邻接矩阵求度、出度、入度上原因不是不会而是把行列方向记反了。这份考点笔记精华版把散落在教材各章的定义、公式、复杂度表和真题摞在一起按考点模块重新排了一遍目标是让你在考场上看到题干前半句就知道该套哪个结论。适合已经过了一遍教材、需要把分数从及格线往上抬的考生也适合时间紧、只想抓高频结论的人。2. 数据结构基础邻接矩阵、存储结构与二叉排序树的必考结论2.1 邻接矩阵一行一列定度数邻接矩阵是图这一章最常出选择题的地方规则本身不复杂复杂的是题干会换着法子问。无向图的邻接矩阵是对称的第 i 行元素的和就是顶点 i 的度。教材里的原例是顶点 4 的度就是第四行的和即 2。这句话要背到条件反射——看到“无向图”“第几行”“求和”答案就是那个顶点的度。有向图则要分两个方向看第 i 行元素之和是顶点 i 的出度第 j 列元素之和是顶点 j 的入度。原例给的是顶点 3 的出度和入度分别为 5 和 16也就是说第三行加起来是 5第三列加起来是 16。这里最容易踩的坑是把行当入度、列当出度一旦记反四个选项里总能找到一个“看起来很对”的干扰项。答题时按三步走第一步看题干说的是有向图还是无向图第二步无向图只算行有向图行算出、列算入第三步如果题目给的是具体矩阵先数行数列数确认顶点编号从 0 还是从 1 开始。考试里经常出现“顶点 v2 的度是多少”这种问法编号起点看错整道题白做。提示无向图邻接矩阵一定对称有向图不一定。看到矩阵不对称先怀疑自己是不是把有向图当无向图算了。2.2 四种存储结构题目问场景你就答增删还是查询存储结构这块不会直接考定义默写考的是“给一个场景选哪种结构合适”。顺序存储结构用一组地址连续的存储单元依次存放线性表元素下标计算直接适合频繁查询链式存储结构用一组任意的存储单元存放元素这些单元可以连续也可以不连续适合频繁插入、删除、更新。散列存储结构是在数据元素的存储位置和关键码之间建立确定对应关系本质是键值对查找性能好但会有冲突处理的问题。索引存储结构是一个单独的、物理的数据库结构它是某个表中一列或若干列值的集合以及相应的指向表中物理标识这些值的数据页的逻辑指针清单数据库里的索引就是典型例子。存储结构典型特征适用场景常见考法顺序存储地址连续按下标访问频繁查询、很少增删问“查找为主”选哪个链式存储存储单元任意靠指针连接频繁插入、删除、更新问“增删为主”选哪个散列存储关键码与位置建立对应等值查找、键值对场景问“查找效率最高”索引存储单独的索引结构加指针清单数据库检索、大表查询问“数据库索引属于哪种”这张表建议直接背场景对应关系而不是背定义。题目只要出现“经常变动”“频繁插入删除”优先往链式存储上想出现“有序表”“快速定位”优先想顺序存储加二分出现“键值对”“哈希”就是散列存储。2.3 单链表、循环链表、双链表灵活度和开销的取舍链表这一族考的是比较不是实现。单链表只有一个指针域从头走到尾插入删除要知道前驱循环链表尾结点指回头结点适合环形处理双链表有两个指针域既能往后走也能往前走因此灵活度优于单链表但每个结点多一个指针开支要大一些。这组对比常以“以下说法正确的是”出现正确选项往往就是“双链表灵活度优于单链表但空间开销更大”的改写。错误选项一般会把“灵活度”和“开销”说反或者把循环链表说成必须双向遍历。答题时抓住一句话多一个指针域换来的是双向移动能力代价是空间。2.4 二叉排序树、平衡二叉树、满二叉树三棵树的边界要分清二叉排序树的定义有三条若左子树非空则左子树上所有结点的值均小于根结点的值若右子树非空则右子树上所有结点的值均大于等于根结点的值左、右子树本身也分别是二叉排序树。它最常考的性质是中序遍历二叉排序树得到一个递增序列。还有一条冷门但出过题的结论——关键字最大的结点可以有左子树但一定没有右子树。平衡二叉树又叫 AVL 树性质是它是一棵空树或者左右两个子树的高度差的绝对值不超过 1并且左右两个子树也都是平衡二叉树。注意它和 AVL 算法不是一回事题干里出现“AVL 树”指的是这种平衡结构。满二叉树的定义是除最后一层无任何子结点外每一层上的所有结点都有两个子结点或 0 个子结点。这三棵树容易混的地方在于二叉排序树保证的是“有序”平衡二叉树保证的是“高度差”满二叉树保证的是“形状满”。题干问“查找效率稳定”往平衡二叉树上答问“中序有序”往二叉排序树上答问“结点数和高度的关系”往满二叉树上答。2.5 哈夫曼树与 WPL构造步骤和编码题的完整链路哈夫曼树也叫最优二叉树定义是带权路径长度 WPL 最短的树权值越大的叶子结点越靠近根结点。构造过程是每次从待选集合里取两个权值最小的结点合并新结点的权值是两者之和放回集合重复到只剩一个根。左小右大、左 0 右 1 是做题时的惯例写法虽然哈夫曼树的左结点未必要比右结点小但按这个惯例写不容易乱。真题是这样的已知一个文件中出现的各字符及其对应的频率若采用定长编码则该文件中字符的码长应为多少若采用 Huffman 编码则字符序列“face”的编码应是什么。选项码长是 2、3、4、5编码是四组二进制串。第一问考定长编码字符一共 6 个a 到 f用 000 到 101 就能表示所以最合适的码长是 3 位。4 位、5 位当然也能表示但题目问的是“最合适”答案取能满足要求的最小位数。第二问按构造好的哈夫曼树从根结点出发走到 f、a、c、e 这四个叶子把路径上的 0 和 1 依次记下来拼出的序列对应选项 B。这类题丢分通常不是不会构造而是构造完不检查合并顺序错一次整棵树的编码全变。答完题花十秒回代把编码逐位走一遍树能救回不少分。提示哈夫曼编码题做完务必回代验证从根按编码走一遍能不能落到对应叶子比重新构造一遍快得多。3. 查找与排序八种排序的复杂度、稳定性与两道真题演练3.1 二分查找适用条件比算法本身更常考二分查找也叫折半查找适用情况是不经常变动而查找频繁的有序列表。优点是比较次数少、查找速度快、平均性能好缺点有两条要求待查表为有序表插入删除困难。这两条缺点几乎是必考项题干经常问“二分查找不适用于哪种场景”答案就是频繁插入删除的表。算法过程是假设表中元素按升序排列将表中间位置记录的关键字与查找关键字比较相等则查找成功否则用中间位置把表分成前、后两个子表如果中间位置记录的关键字大于查找关键字则进一步查找前一子表否则查找后一子表。重复这个过程直到找到满足条件的记录或者子表不存在为止此时查找不成功。答题时注意两个细节一是“有序”是前提题目给的表没排序就不能直接二分二是比较次数按 ⌊log2n⌋1 估算n 个元素最多比较到这个数量级选项里出现 n 次、n/2 次的可以直接排除。3.2 分块查找块间有序、块内无序分块查找的适用情况是结点动态变化的情况优点比顺序查找快得多缺点速度不如折半查找法。实现方式是把一个大的线性表分解成若干块每块中的结点可以任意存放但块与块之间必须排序。假设按关键码值非递减那么对任意的 i第 i 块中所有结点的关键码值都必须小于第 i1 块中所有结点的关键码值。此外还要建立一个索引表把每块中的最大关键码值作为索引表的关键码值按块的顺序存放到一个辅助数组中这个辅助数组按关键码值非递减排序。查找时分两步先在索引表里查确定目标结点所在的块索引表有序所以可以用顺序查找也可以用折半查找然后到相应块里用顺序查找找到目标结点。平均查找长度记作 E(n)教材给的设定是线性表中共有 n 个结点分成大小相等的 b 块每块有 sn/b 个结点。考试里如果让算平均查找长度基本就是“索引查找的代价 块内顺序查找的代价”两部分先确认题目给的块数和每块结点数再代进去。3.3 八种排序的答题模板每种记一句话直接插入排序每一趟把一个待排序的记录按关键字大小插入到有序队列的合适位置直到全部插入完成类比斗地主抽牌后往手里插牌。简单选择排序每趟从待排序记录中选出关键字最小的记录顺序放在已排序记录序列的末尾直到排完。冒泡排序两两比较待排序的关键字交换不满足次序要求的那一对数直到整个表满足次序要求。希尔排序把记录按步长 gap 分组每组用直接插入排序随着步长逐渐减小每组包含的记录越来越多步长减到 1 时整个数据合成一组排序完成。快速排序一趟排序把数据分割成独立的两部分分割点左边都是比它小的数右边都是比它大的数再对两部分递归快排用的是分治策略。堆排序n 个元素的序列 {k1, k2, …, kn} 满足 ki≤k2i 且 ki≤k2i1或者 ki≥k2i 且 ki≥k2i1i1,2,…,⌊n/2⌋就称为堆。归并排序把待排序序列看成 n 个长度为 1 的有序序列相邻有序表成对归并得到 n/2 个长度为 2 的有序表再归并得到 n/4 个长度为 4 的有序序列反复下去直到得到一个长度为 n 的有序序列。基数排序不需要比较关键字大小根据关键字中各位的值通过若干趟“分配”与“收集”实现排序。教材的例子是序列 {50, 123, 543, 187, 49, 30, 0, 2, 11, 100}把 0 到 9 看成 10 个桶先按个位数分类入桶再从 0 号桶到 9 号桶依次取出得到按个位递增的序列 {50, 30, 0, 100, 11, 2, 123, 543, 187, 49}然后继续按十位、百位重复。答题时不用背代码背“一句话特征 一个类比”就够了。题干问“哪一趟之后序列变成什么样”先判断是哪种排序再按那一句话推一趟。3.4 复杂度对比表和稳定性这张表值好几分排序方法最好时间复杂度平均时间复杂度最坏时间复杂度辅助空间稳定性直接插入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(nlog2n)O(nlog2n)O(n²)O(log2n)不稳定堆排序O(nlog2n)O(nlog2n)O(nlog2n)O(1)不稳定归并排序O(nlog2n)O(nlog2n)O(nlog2n)O(n)稳定基数排序O(d(nrd))O(d(nrd))O(d(nrd))O(rd)稳定这张表要横着背不要竖着背。竖着背容易记串横着背每一行就是一个完整故事直接插入最好情况是已经有序所以是 O(n)最坏是逆序O(n²)辅助空间只要一个临时变量稳定。快速排序最坏退化到 O(n²)辅助空间是递归栈的 O(log2n)不稳定。归并排序三种情况都是 O(nlog2n)但要额外 O(n) 空间稳定。稳定性有个顺口记法稳定的有直接插入、冒泡、归并、基数其余不稳定。希尔排序的最好和最坏时间复杂度教材明确写“不存在”考试如果出选项里带具体值的直接排除。真题演练堆是一种数据结构下面哪个是堆选项 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 序列 n8i 从 1 到 4i110≤18 且 10≤15成立i218≤20 且 18≤50成立i315≤80 且 15≤30成立i420≤60成立。四项全满足B 是堆。A 在 i2 处 50≤30 不成立C 在 i4 处 50≤20 不成立D 在 i2 处 30≤20 不成立。所以答案是 B。这类题不需要画出整棵树按 i 从 1 到 ⌊n/2⌋ 逐个验证父子关系就行一般验证到第二、第三个位置就能排除三个错误选项。4. 计算类小题符号数、表达式、广义表与归并路数的一遍过4.1 原码、反码、补码、移码四种码的转换规则正数的原码等于自身的二进制数负数的原码第一位为 1这是符号位表示负数后面是自身的二进制数。正数的反码等于自身二进制数负数的反码符号位不动其余各位按位取反。正数的补码等于自身二进制数负数的补码是在反码的基础上加 1。移码又叫增码无论正负数只要把补码的符号位取反即可。应用场景是固定考点计算机中最适合数字加减运算的编码是补码最适合表示浮点数阶码的编码是移码。这两句话几乎每年都以选择题形式出现看到“加减运算”找补码看到“阶码”找移码。转换题的手工流程先写出绝对值的二进制负数补上符号位 1 得到原码原码除符号位外全部取反得到反码反码末位加 1 得到补码补码符号位取反得到移码。正数四码相同不用折腾。4.2 定点数范围用 A、B 两个记号代替硬背定点数就是小数点的位置固定不变的数有两种约定定点整数是纯整数小数点在最低有效数值位之后定点小数是纯小数小数点在最高有效数值位之前。机器字长为 n 时各种码制表示的带符号数范围如下。码制定点整数范围定点小数范围原码[-(2^(n-1)-1), 2^(n-1)-1][-(1-2^-(n-1)), 1-2^-(n-1)]反码[-(2^(n-1)-1), 2^(n-1)-1][-(1-2^-(n-1)), 1-2^-(n-1)]补码[-2^(n-1), 2^(n-1)-1][-1, 1-2^-(n-1)]移码[-2^(n-1), 2^(n-1)-1][-1, 1-2^-(n-1)]记忆技巧是设 A2^(n-1)B1-2^-(n-1)那么原码和反码的定点整数范围都是 [-(A-1), A-1]定点小数都是 [-B, B]补码和移码的定点整数范围都是 [-A, A-1]定点小数都是 [-1, B]。规律很明显补码比原码多表示一个最小负数定点小数能表示到 -1。答题时先判断题目问的是定点整数还是定点小数再看码制最后套 A、B 两个记号比现场推导快且不容易错。4.3 前缀、中缀、后缀表达式扫描方向和弹出顺序是命门中缀表达式就是平时写的 ab-c 这种形式。前缀表达式又叫波兰式从右至左扫描表达式遇到数字压栈遇到运算符弹出栈顶的两个数用运算符对它们做计算注意是栈顶元素 op 次顶元素结果入栈重复到最左端。后缀表达式又叫逆波兰式从左至右扫描遇到运算符时弹出栈顶两个数计算时是次顶元素 op 栈顶元素重复到最右端。教材例子前缀表达式 “- × 3 4 5 6”从右往左把 6、5、4、3 压栈遇到 弹出 3 和 43 是栈顶、4 是次顶算 347 入栈遇到 × 弹出 7 和 5算 7×535 入栈最后遇到 -算 35-629。后缀表达式 “3 4 5 × 6 -”从左往右压 3、4遇到 弹出 4 和 3算 347压 5遇到 × 弹出 5 和 7算 7×535压 6遇到 - 算 35-629。两个例子的结果都是 29但弹出顺序相反这是最容易记混的点。口诀是“前缀从右往左、栈顶在前后缀从左往右、次顶在前”。后缀求值的代码逻辑可以写成这样帮助理解弹出顺序。def eval_rpn(tokens): stack [] for t in tokens: if t not in -*/: stack.append(int(t)) else: b stack.pop() # 先弹出的是栈顶作为右操作数 a stack.pop() # 后弹出的是次顶作为左操作数 if t : stack.append(a b) elif t -: stack.append(a - b) elif t *: stack.append(a * b) else: stack.append(a // b) return stack[0] print(eval_rpn(3 4 5 * 6 -.split())) # 输出 29代码里 b 先弹出、a 后弹出减法就是 a-b 而不是 b-a这个顺序写反结果会变成 6-35-29。参数 tokens 是按空格切分后的表达式列表运算符判断只覆盖四则运算考试不会考更复杂的符号。把这段在纸上走一遍比背十遍定义都管用。4.4 广义表的长度和深度删括号和数括号广义表的长度是把最外面那层的括号删掉以后剩下的元素或组数深度是括号的层数。教材例子L1((a,(a,b),((a,b),c)))L2((1,2,3))L3(1,2,3)。L1 删掉最外层括号后剩下 a、(a,b)、((a,b),c) 三部分所以长度是 1这里要注意教材给的答案是 L1 长度 1、深度 4。原因是 L1 最外层只有一个元素即 ((a,(a,b),((a,b),c)))它是一个整体。深度数括号层数L1 嵌套了 4 层。L2 长度 1、深度 2L3 长度 3、深度 1。这三个例子建议直接背下来考试遇到同类题照着数。操作要点长度看最外层逗号分隔出几项深度从最外层往内数左括号最多叠几层。两者不要混长度是“横向”的深度是“纵向”的。4.5 归并路数与寻址方式、CPU 组成归并排序的归并路数公式写作 归并路数 |log_k m|其中 m 为元素个数k 为多路归并趟数。教材例题若对 27 个元素只进行三趟多路归并排序则选取的归并路数为多少选项是 2、3、4、5。按公式log 以 3 为底、27 为真数的结果是 3所以选 B。答题时先分清题目给的是“趟数”还是“路数”。给趟数求路数就是问 k 的几次方等于 m给路数求趟数就是问 m 需要几次 k 路归并才能归完。273³所以三趟对应三路这类数字通常是整数次幂凑不出来就回看题干是否把 27 看成了别的数。计算机指令系统的寻址方式立即寻址的操作数包含在指令中获取操作数最快直接寻址的操作数地址在指令中寄存器寻址的操作数在寄存器中寄存器间接寻址的操作数地址在寄存器中。四种方式按“操作数在哪”排队指令里最快寄存器次之内存最慢。CPU 的组成包括运算器、控制器、寄存器和内部总线。控制器的职责不仅是保证程序正确执行还要能够处理异常事件这句话在选择题里出现频率很高正确选项通常就是把“处理异常事件”挂在控制器身上。5. 易错点五个最容易在考场上翻车的地方5.1 邻接矩阵把行和列记反错在哪有向图题里把第 i 行之和当成入度或者把第 j 列之和当成出度。为什么错无向图行和列对称怎么记都不会暴露问题一到有向图行和列的含义就分家了平时没刻意区分考场上凭手感就翻车。怎么答对在草稿纸上写“行出列入”四个字再动笔算。题目给矩阵就先标出第几行第几列算完回读一遍题干问的是出度还是入度。5.2 排序稳定性当成复杂度一起背错在哪把快速排序记成稳定或者把归并排序记成不稳定。为什么错复杂度表里快速排序和归并排序的时间复杂度长得几乎一样都是 O(nlog2n)背的时候只记了时间稳定性那一列被忽略。怎么答对单独记一张四行的稳定性小表——稳定直接插入、冒泡、归并、基数不稳定简单选择、希尔、快速、堆。做题时先看稳定性要求再看时间复杂度顺序反了容易被干扰项带跑。5.3 哈夫曼树构造完不回代错在哪合并顺序对但编码结果和选项对不上或者构造出的树左右颠倒后编码全反。为什么错哈夫曼树的左结点未必要比右结点小题目按左小右大、左 0 右 1 的惯例给答案考生自己构造时随意摆放编码自然对不上。怎么答对统一按左小右大、左 0 右 1 写构造完从根按编码逐位走一遍能落到对应叶子才落笔选答案。走不通就说明合并时取了错的权值。5.4 补码和移码的符号位处理混用错在哪求移码时把补码整体取反或者求补码时忘了符号位不动。为什么错反码和补码的规则里都有“取反”移码也有“取反”三个取反混在一起记串了。怎么答对分两步走——负数先求反码符号位不动、其余取反再在反码末位加 1 得补码移码只把补码的符号位取反其余位一个都不动。正数四码相同先判断正负再动笔。5.5 归并路数公式代错方向错在哪题目给三趟多路归并、27 个元素考生把 3 当底数、27 当真数算成 3方向对了但写成 log 以 27 为底 3结果算不出来或者把趟数和路数对调。为什么错公式里 k 是路数、m 是元素个数题干语序一变k 和 m 就认错了。怎么答对先圈出题干里的“趟”和“元素个数”写出 k^趟数 m 这个关系式再解。27 个元素三趟就是 k³27k3不涉及对数换底心算就能出。6. 答题顺序与押题思路先把稳的分装进口袋上午卷的时间够用但心态容易崩所以顺序比速度重要。我的建议是分三档第一档是邻接矩阵求度、排序复杂度查表、符号数转换、寻址方式判断这些看到题干就能出答案先扫一遍全部做完把能拿的分锁死第二档是哈夫曼编码、表达式求值、广义表长度深度需要动笔推两步放在中间做第三档是堆的判断、归并路数、二分查找比较次数这类要验算的留到最后因为即使时间不够蒙一个也有四分之一的命中率。押题思路按分值密度排优先级如下。优先级考点常见题型拿分动作高排序复杂度与稳定性选择“哪个说法正确”横着背表先看稳定性高邻接矩阵出度入度给矩阵求度数行出列入草稿写四个字高补码移码转换给十进制求某码分正负两步走中哈夫曼编码给频率求序列编码构造后回代验证中前缀后缀表达式求表达式值认准弹出顺序中二叉排序树性质中序序列、最大结点画小树验证低广义表长度深度给三个表求值背教材原例最后说个血泪教训。我早年做排序复杂度题习惯先看时间复杂度再看稳定性结果有一次四个选项的时间复杂度全写成 O(nlog2n)只有稳定性不同我盯了半天时间那一列硬是没往下看选了个不稳定但时间“看起来最顺眼”的。从那以后我每次做这类题都强制走一遍“先圈稳定性、再看时间、最后看空间”的三步哪怕题干只问一句话。希望帮到你。本文还有配套的精品资源点击获取