软考中级软件设计师考点笔记：数据结构高频考点与易错点详解

简介软件设计师中级考点笔记精华版为软考中级备考者系统梳理了数据结构、查找与排序等核心模块覆盖邻接矩阵、顺序/链式/散列存储、二叉树、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、深度 4L2((1,2,3)) 的长度是 1、深度是 2L3(1,2,3) 的长度是 3、深度是 1。很多人第一次做 L2 会写成长度 3错在没搞清楚外层括号删掉后剩下的其实只有一个子表 (1,2,3)。表达式的三种记法是另一个容易送分的点。前缀表达式从右往左扫描遇到数字压栈遇到运算符弹出栈顶两个数做“栈顶 op 次顶”计算注意和前者的顺序相反后缀表达式从左往右扫描遇到运算符做“次顶 op 栈顶”计算。笔记里的例子是“3 4 5 × 6 -”从左扫到右3、4 入栈碰到 弹出 4 和 3 计算 347然后 5 入栈碰到 × 弹出 5 和 7 计算 7×535再 6 入栈最后一个 - 让 35-6 得到 29。这里最容易算反的是减法顺序前、后缀分别规定栈顶和次顶的位置背不下来就做题时自己写一遍。3. 树与二叉树核心二叉排序树、AVL 与哈夫曼编码题怎么写3.1 二叉排序树中序遍历递增与“最大结点无右子树”二叉排序树BST的定义看似简单但考试喜欢在细节上设陷阱。左子树所有结点值小于根节点右子树所有结点值大于等于根节点同时左右子树也各自满足二叉排序树定义。这个“大于等于”很关键有些教材里写“大于”还是“大于等于”直接决定重复元素放左还是放右。另一个高频结论是中序遍历一棵二叉排序树会得到一个递增序列所以判断一棵树是不是二叉排序树最稳的办法就是中序遍历后看序列是否单调不减。笔记里还有一句容易忽略的话“关键字最大的结点可以有左子树但一定没有右子树”因为它的值已经是整棵树里最大的要是再有右孩子那个右孩子的值必然比它大就矛盾了。同样地最小关键字结点可以有右子树但一定没有左子树。选择题如果给出树形图问你哪个是中序遍历结果直接从最左走到最右就能排除两个选项。3.2 哈夫曼树与 WPL从定长编码到“face”编码例题哈夫曼树是下午题和上午题都喜欢碰的一块。先明确概念带权路径长度 WPL 最小的二叉树叫哈夫曼树权值越大的叶子节点越靠近根节点。构造口诀很简单从森林里取两个权值最小的节点合并成一个新节点权值相加再放回森林里重复直到只剩一棵树。笔记给了一个典型例题某文件中有六个字符 a、b、c、d、e、f 及对应频率如果用定长编码六个符号至少需要 3 位二进制因为 2^24 不够2^38 正好所以第一问选 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(nrd))O(d(nrd))O(d(nrd))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 和 1510 小于 18、10 小于 15根满足再看下标 1 的孩子是下标 3 的 20 和下标 4 的 5018 小于 20、18 小于 50下标 2 的孩子是下标 5 的 80 和下标 6 的 3015 小于 80、15 小于 30最后下标 3 的孩子是下标 7 的 6020 小于 60。全表都满足父节点不大于孩子节点所以这是合法小根堆。考试时用这个“逐节点检查法”比自己凭感觉判断快得多每一步只要算一遍左孩子下标 2i1、右孩子下标 2i2最多检查到 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)) 的长度是____”。用笔记里的内容把这些填空题出成二十道每天换着顺序做错的题标记出来第二天先复习错题再测新题。这套方法看上去很土但它能把“看着会”的模糊记忆变成“写得出来”的扎实记忆。另一个进阶技巧是给每个算法配一道“判断型”小题比如给一个序列直接问“这是小根堆吗”然后按下标检查法画完全二叉树这也是我考前最爱用来练手的题型。做完这些之后再回到笔记里看所有“易错点”标注你会发现那些坑基本都踩过了。从那以后我每次考前都会强制自己走一遍这种“填表式自测”不再盲目翻笔记当复习虽然过程枯燥但效果比反复阅读强不少。希望帮到你。本文还有配套的精品资源点击获取