企业官网建设流程全解析

简介：面向备考软考中级软件设计师的考生，这份考点笔记精华版以docx文档形式系统梳理了考试核心知识。内容围绕数据结构展开，涵盖邻接矩阵在无向图与有向图中的度、出度、入度计算，顺序、链式、散列与索引四种存储结构的适用场景，以及二叉排序树、哈夫曼树与平衡二叉树的构造要点，并配有定长编码与Huffman编码的例题解析。查找方法部分对比二分查找与分块查找的适用条件与优缺点，排序章节则逐一讲解直接插入、简单选择、冒泡、希尔、快速、堆、归并与基数排序的实现思路，并附时间复杂度与稳定性对照表，便于横向记忆。资源包共1个docx文件，大小约3.37MB，结构紧凑、重点突出，适合考前集中背诵与查漏补缺。目前已有382人学习，可作为难点公式与易错点的随身复习清单。

1. 从一道“算度数”的题说起：软考中级到底考什么

邻接矩阵那道题，很多人第一次做会愣住：给一个无向图的矩阵，问某个顶点的度。答案其实就藏在第 i 行元素之和里，有向图则换成行和算出度、列和算入度。这类题不难，但它精准暴露了软件设计师（中级）的考法——不考你背概念，考你能不能在具体结构上把定义“用出来”。整张卷子的上午题大量是这种“定义 + 一个小计算”的组合，数据结构、排序查找、树、编码、指令寻址轮番上阵；下午题则把这些结构落到流程图、算法填空和简单设计里。拿分的关键不是刷题量，而是把每个考点的判定规则记成条件反射：看到矩阵想行和列和，看到排序先问稳定性，看到编码先画树。这份考点笔记精华版适合已经过了一遍教材、需要把散点收成答题模板的人，也适合时间紧、想直接对着高频考点背的人。

2. 数据结构高频考点：存储结构、图与树的判定规则

2.1 存储结构怎么选，题目问法就三种

顺序存储用一组地址连续的单元依次放元素，链式存储用任意存储单元、靠指针串起来，散列存储把存储位置和关键码建立确定对应关系，索引存储则单独建一个索引结构指向物理数据页。考试不会让你长篇论述，常见问法是“频繁查询选什么”“频繁插入删除选什么”“数据库里靠什么加快检索”。答题口径很固定：频繁查询、元素个数相对稳定，选顺序存储；频繁插入、删除、更新，选链式存储；要按关键码快速定位，选散列；数据量大且需要按索引列检索，选索引。

链表这一块要能横向比较。单链表一个指针域，循环链表首尾相接，双链表两个指针域。双链表灵活度优于单链表，因为能双向走，但开支更大，多一个指针的空间和维护成本。题目常把“灵活度”和“开销”放在一起设陷阱，问“双链表一定比单链表好吗”，正确答法是看场景：需要频繁前后移动、删除给定结点时双链表更稳，内存紧张、只做单向遍历时单链表更合适。

提示：存储结构题几乎不考定义原文，考的是“场景—结构”的匹配，背的时候把场景词和结构名绑在一起记。

2.2 二叉树三兄弟：二叉排序树、平衡二叉树、满二叉树

二叉排序树的判定要同时满足三条：左子树非空则左子树所有结点值小于根，右子树非空则右子树所有结点值大于等于根，左右子树本身也是二叉排序树。这里有个高频细节：关键字最大的结点可以有左子树，但一定没有右子树。中序遍历二叉排序树得到递增序列，这句话既是性质也是解题工具，题目给一个序列问“哪个是某二叉排序树的中序结果”，直接找递增即可。

平衡二叉树（AVL 树）的核心性质是左右两个子树高度差的绝对值不超过 1，且左右子树也都是平衡二叉树。注意它和 AVL 算法不是一回事，题目里出现“AVL 树”指的是这种平衡结构。满二叉树的表述要抠字眼：除最后一层无任何子结点外，每一层上的所有结点都有两个子结点或 0 个子结点。很多考生把“满二叉树”和“完全二叉树”混着答，这是失分重灾区。

2.3 哈夫曼树与 WPL：一道真题走完整个流程

哈夫曼树又叫最优二叉树，定义是带权路径长度 WPL 最短的树，权值越大的叶子结点越靠近根结点。构造规则是每次取两个最小权值合并，新结点权值为两者之和，放回集合继续取最小。真题里常见两问：定长编码码长是多少，某字符序列的哈夫曼编码是什么。

以笔记中的例题为例，文件中有 a、b、c、d、e、f 六个字符。定长编码要能区分 6 个字符，2 位只能表示 4 种，不够；3 位可以表示 8 种，够用，所以码长选 3。第二问求“face”的编码，做法是先按频率构造哈夫曼树，通常写成左小右大、左 0 右 1，然后从根出发找 f、a、c、e 四个字母的路径。笔记给出的答案是 B，即 001110110011。这类题的关键不是背答案，而是把“合并最小两个—标 0/1—从根走到叶子”这三步练熟，考场上一张草稿纸就能画完。

注意：哈夫曼树的左结点未必要比右结点小，但做题时统一写成左小右大、左 0 右 1，能避免自己前后不一致导致编码对不上选项。

2.4 真题演练：堆的判定

题目给四个序列，问哪个是堆。堆的定义是 n 个元素的序列满足 ki ≤ k2i 且 ki ≤ k2i+1（小顶堆），或 ki ≥ k2i 且 ki ≥ k2i+1（大顶堆），i 从 1 到 n/2 向下取整。答题思路是逐项套定义，先看第一个元素和它的两个孩子。以选项 B（10，18，15，20，50，80，30，60）为例，10 的两个孩子是 18 和 15，都大于 10；18 的孩子是 20 和 50，都大于 18；15 的孩子是 80 和 30，都大于 15；20 的孩子是 60，大于 20，满足小顶堆定义，所以选 B。这类题不要凭感觉看“像不像”，一定按 i 和 2i、2i+1 的下标关系逐层验。

3. 查找与排序：复杂度表背后的答题套路

3.1 二分查找与分块查找：适用条件比算法本身更常考

二分查找适用于不经常变动而查找频繁的有序列表。优点是比较次数少、查找速度快、平均性能好；缺点有两个，要求待查表有序，且插入删除困难。答题时把这三优两缺说全，基本就是标准答案。实现逻辑是：假设升序排列，取中间位置关键字与目标比较，相等则成功；中间值大于目标就查前一子表，小于目标就查后一子表，重复直到找到或子表不存在。

分块查找适用于结点动态变化的情况，速度比顺序查找快得多，但不如折半查找。它的结构要求是块内结点可任意存放，块与块之间必须有序，即第 i 块所有关键码都小于第 i+1 块所有关键码；同时建立索引表，把每块最大关键码按块顺序存入辅助数组。查找时先在索引表里查（可顺序可折半），确定块后再在块内顺序查找。平均查找长度常考公式：n 个结点分成大小相等的 b 块、每块 s = n/b，索引查找与块内查找的代价要分开算再相加。

3.2 八种排序的判定口诀与复杂度表

排序这一块的考法分两层。第一层是“给场景选算法”：数据量小、基本有序，直接插入排序；元素不多、对时间要求不高，简单选择排序；要求稳定且能接受较低效率，冒泡排序；大规模数据想改进插入排序，希尔排序；追求平均性能、能接受不稳定，快速排序；要求最坏情况也稳定在 O(nlog2n) 且空间紧张，堆排序；要求稳定且能接受 O(n) 辅助空间，归并排序；关键字位数固定、不需要比较大小，基数排序。

第二层是复杂度与稳定性，必须背成表。直接插入最好 O(n)、平均和最坏 O(n²)、空间 O(1)、稳定；简单选择三种情况都是 O(n²)、空间 O(1)、不稳定；冒泡最好 O(n)、平均最坏 O(n²)、空间 O(1)、稳定；希尔平均 O(n^1.3)、最好和最坏不存在固定值、空间 O(1)、不稳定；快速排序最好和平均 O(nlog2n)、最坏 O(n²)、空间 O(log2n)、不稳定；堆排序三种情况都是 O(nlog2n)、空间 O(1)、不稳定；归并排序三种情况都是 O(nlog2n)、空间 O(n)、稳定；基数排序为 O(d(n+rd))、空间 O(rd)、稳定。

这张表建议默写三遍，尤其是“快速排序最坏 O(n²)”“归并排序空间 O(n)”“希尔排序最好最坏不存在”这三个点，出题人特别喜欢在这里设选项。

3.3 真题演练：归并路数怎么反推

题目：对 27 个元素只进行三趟多路归并排序，选取的归并路数是多少。笔记给的公式是归并路数 = |log_k m|，其中 m 为元素个数，k 为多路归并趟数。代入 m=27、趟数 3，即求以 3 为底 27 的对数，结果为 3，选 B。答题时注意公式里“趟数”和“路数”的位置别搞反：题目给趟数求路数，就把趟数放在底数位置；给路数求趟数，就求以路数为底、元素个数为真数的对数并向上取整。这个公式在上午题里出现频率不低，属于背了就能拿分的类型。

3.4 基数排序：不比较大小的那一类

基数排序和前七种都不同，它不比较关键字大小，而是按关键字各位的值做若干趟“分配”与“收集”。以序列 50、123、543、187、49、30、0、2、11、100 为例，把 0 到 9 看成 10 个桶，先按个位数分桶，再按桶编号 0 到 9 依次取出，得到按个位递增的序列；接着按十位、百位重复，最终整体有序。答题时要强调两点：一是它不需要比较，二是它稳定，因为收集时按桶顺序取，相同关键字的相对次序不变。题目若问“哪种排序不需要比较关键字”，直接锁定基数排序。

4. 树、表达式与编码：那些必须动手画的小计算

4.1 广义表的长度与深度

广义表的长度是删掉最外层括号后剩下的元素（组）个数，深度是括号的层数。笔记给了三个例子：L1 = ((a,(a,b),((a,b),c)))，长度 1、深度 4；L2 = ((1,2,3))，长度 1、深度 2；L3 = (1,2,3)，长度 3、深度 1。这类题最容易错在把“元素个数”和“括号层数”混在一起数。稳妥做法是先数最外层逗号分隔出几项定长度，再从外往里数左括号层数定深度，两步分开做，不要一边看一边猜。

4.2 前缀、中缀、后缀表达式：栈的弹出顺序是命门

中缀就是我们平常写的 a+b-c。前缀表达式从右至左扫描，遇数字压栈，遇运算符弹出栈顶两个数，用“栈顶元素 op 次顶元素”计算后入栈。以“- × + 3 4 5 6”为例：从右往左压入 6、5、4、3；遇 + 弹出 3 和 4，算 3+4=7 入栈；遇 × 弹出 7 和 5，算 7×5=35 入栈；遇 - 算 35-6=29。后缀表达式从左至右扫描，遇运算符用“次顶元素 op 栈顶元素”计算。以“3 4 + 5 × 6 -”为例：压 3、4，遇 + 算 3+4=7；压 5，遇 × 算 7×5=35；压 6，遇 - 算 35-6=29。

前缀和后缀的差别就在弹出顺序：前缀是栈顶 op 次顶，后缀是次顶 op 栈顶。很多人考场上一紧张就写反，导致减法和除法全错。练的时候固定写一行注释“前缀：顶在前；后缀：顶在后”，做完回代验算一次。

4.3 真题演练：用代码模拟后缀求值

把上面的规则写成代码，能同时练栈操作和边界处理。下面这段 Python 只支持加减乘除和一位以上整数，注释标了每一步对应哪个考点。

def eval_rpn(tokens): stack = [] for t in tokens: if t in {"+", "-", "*", "/"}: # 后缀表达式：先弹出的是栈顶，作为右操作数 right = stack.pop() left = stack.pop() if t == "+": stack.append(left + right) elif t == "-": stack.append(left - right) elif t == "*": stack.append(left * right) else: # 整数除法向零截断，避免 Python 的向下取整干扰结果 stack.append(int(left / right)) else: stack.append(int(t)) return stack[0] print(eval_rpn(["3", "4", "+", "5", "*", "6", "-"])) # 输出 29

这段代码的关键在right = stack.pop()先于left，对应“次顶元素 op 栈顶元素”。如果把两个 pop 顺序写反，减法和除法结果就会变成相反数或倒数，加法乘法看不出问题，考场上很容易蒙混过去，所以验算时一定用带减号的表达式。参数上，tokens是字符串列表，运算符只认四则，除法用int()截断以贴近考试口径。

5. 易错点集中营：这五类题年年有人翻车

5.1 邻接矩阵行和列搞反

错在哪：无向图问度、有向图问入度出度，考生把行和列记混。为什么错：无向图矩阵对称，行和列和相等，平时练习没暴露问题；一到有向图，出度看行、入度看列，记反就全错。怎么答对：固定口诀“无向看行，有向行出列入”，做题时先在草稿上写“第 i 行 = 出度，第 j 列 = 入度”，再动笔算。

5.2 平衡二叉树与满二叉树概念串味

错在哪：把“左右子树高度差不超过 1”说成满二叉树的性质，或把满二叉树说成“每层都满”。为什么错：两个概念都带“满/平衡”字眼，教材表述接近，背的时候只记了关键词没记判定条件。怎么答对：平衡二叉树只认高度差 ≤ 1 且子树也平衡；满二叉树认“除最后一层外每层结点都有两个子结点或 0 个子结点”。答题时先写判定条件再下结论，不要直接抛名词。

5.3 排序稳定性记成“快归堆稳定”

错在哪：把快速排序、归并排序、堆排序的稳定性混着答。为什么错：这三个都是 O(nlog2n) 级别，容易打包记忆。怎么答对：记“快不稳定、堆不稳定、归并稳定”，再补一句归并需要 O(n) 辅助空间。稳定性题往往和空间复杂度一起考，两个点绑在一起背更牢。

5.4 前缀后缀弹出顺序写反

错在哪：前缀表达式里用“次顶 op 栈顶”，后缀里用“栈顶 op 次顶”。为什么错：两个规则长得像，考场紧张时凭手感写。怎么答对：前缀从右往左扫、栈顶在前；后缀从左往右扫、栈顶在后。做完用加法交换律验算不了，就用减法表达式回代，一步就能发现顺序错没错。

5.5 归并路数公式代错位置

错在哪：把元素个数放在底数、趟数放在真数位置。为什么错：公式 |log_k m| 里 k 是趟数、m 是元素个数，和直觉“路数在底数”相反。怎么答对：先写“趟数做底、元素个数做真数”，再代入；结果是整数就直接选，不是整数按题目要求向上取整。

6. 考场答题节奏：把公式和判定条件变成条件反射

上午题的时间分配，我的建议是先把所有“判定类”小题扫一遍，这类题单题不超过一分钟，看到邻接矩阵、堆、广义表、表达式求值就直接套规则，不纠结。真正要留时间的是带计算的编码题和复杂度对比题，哈夫曼树画一遍大约两三分钟，画完立刻标 0/1，不要等全部画完再回头标，容易漏枝。排序复杂度表不要现场推，考前默写到能闭眼写出八行，考场上直接对照选项排除。

下午题里，数据结构和算法填空往往给一段不完整的代码或流程，考的是你能不能顺着上下文补出循环条件和边界。我的习惯是先把题目里的输入输出例子代进去走一遍，看缺的那一行在例子中应该产生什么值，再反推写法。比如后缀求值填空，先看弹出顺序，再看运算符分支，最后补stack[0]返回。这个顺序比从头读代码快，也不容易被无关变量带偏。

押题方向上，图的行列和、哈夫曼编码、堆判定、排序稳定性与复杂度、前缀后缀求值、归并路数这六类几乎每年都能见到变体，优先把它们练到不假思索。其次是存储结构场景匹配和二叉排序树判定，属于送分题，错一道都可惜。考前最后一遍不要刷新题，把这份笔记里的公式表和易错点过一遍，每道错题问自己“当时是哪个条件没想起来”，比再做十道新题有用。

从那以后我每次进考场前，都强制把“无向看行、有向行出列入”“前缀顶在前、后缀顶在后”“趟数做底、元素个数做真数”这三句话在草稿纸上默写一遍，写完再动笔。这个习惯帮我挡掉了至少两次本可以避免的翻车。希望帮到你。

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