简介软件设计师中级考点笔记精华版定位为软考中级考证冲刺资料面向正在系统复习数据结构、算法与程序设计的考生。内容聚焦考试常考的核心知识点、难点公式与易错陷阱将邻接矩阵、顺序/链式/散列/索引存储结构、满二叉树、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 个字符。所以第一问选 B3 位。这类题的关键是看字符种类数 n码长取满足 2^k ≥ n 的最小整数。第二问是哈夫曼编码。构造哈夫曼树时通常写成左小右大的形式赋值时左 0 右 1。face 的编码就是分别找到 f、a、c、e 四个字符从根节点出发记下路径上的 0 和 1。假设按左 0 右 1 推导f 的编码为 1100a 为 010c 为 011e 为 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 块中的所有节点的关键码值都必须小于第 i1 块中的所有节点的关键码值。第二步建立一个索引表把每块中的最大关键码值作为索引表的关键码值按块的顺序存放到一个辅助数组中。注意索引表本身也是有序的。查找时先在索引表中定位所在块。因为索引表有序所以可以对索引表采用顺序查找或折半查找确定块之后块内再采用顺序查找。这里有个很容易忽略的考点索引表查的是块块内查的是记录。选择题经常把这两步的顺序颠倒说成先在块内顺序查找再在索引表折半定位那就不对了。笔记里还提到了平均查找长度的概念总共有 n 个节点分成大小相等的 b 块每块有 s n/b 个元素。分块查找的代价等于索引表的查找代价加块内顺序查找的代价。真题一般只要求定性判断当块数少、每块元素多时块内顺序查找代价大当块数多、每块元素少时索引表查找代价上升。你要能说出分块查找把顺序查找和折半查找做了个组合这个设计思路选择题就难不倒你。4.3 八大排序复杂度表背下来选择题秒杀排序是软考上午题的必考模块八大排序各自对应一句话直接插入排序是每趟把一个记录按其关键字大小插入到有序队列的合适位置斗地主摸牌就是这规则简单选择排序每趟从待排序记录中选出关键字最小的放在已排序记录序列末尾冒泡排序两两比较并交换不满足次序要求的元素希尔排序按步长 gap 分组对每组做直接插入排序步长逐渐减小到 1快速排序通过一趟排序把数据分割成独立的两部分分割点左边都比它小、右边都比它大用了分治法堆排序借助堆这种数据结构反复调整归并排序把 n 个长度为 1 的有序序列两两归并基数排序不看关键字大小按个位、十位等各位的值做分配与收集。排序方法最好时间平均时间最坏时间辅助空间稳定性直接插入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 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 ≤ k2i1小根堆或 ki ≥ k2i 且 ki ≥ k2i1大根堆时称为堆。真题给出四个序列问哪个可以作为堆排序里的堆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 ≤ 1518 ≤ 20 且 18 ≤ 5015 ≤ 80 且 15 ≤ 3020 ≤ 60全部满足构成小根堆。选项 A 在 i2 的位置50 大于左孩子 30直接淘汰选项 C 在 i4 的位置50 大于左孩子 20淘汰选项 D 在 i2 的位置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计算 34 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)因此最小值比原码多一位。码制定点整数范围定点小数范围原码[-(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)]记忆技巧令 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 判定、二分查找条件、前缀后缀表达式这几类题几乎每年轮换着出属于押题命中率最高的区域。笔记里的易错点部分我每次考前都强制重看一遍尤其是有向图行列入度出度别看简单考场上一紧张最容易犯糊涂。从那以后我每次考前都把码制范围表和排序复杂度表手写一遍再不想当然地跳步骤。希望帮到你。本文还有配套的精品资源点击获取