企业官网建设流程全解析

简介：面向备考软考中级软件设计师的考生，这份考点笔记精华版以单个 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 块中所有结点的关键码值都必须小于第 i+1 块中所有结点的关键码值。

此外还要建立一个索引表，把每块中的最大关键码值作为索引表的关键码值，按块的顺序存放到一个辅助数组中，这个辅助数组按关键码值非递减排序。查找时分两步：先在索引表里查，确定目标结点所在的块；索引表有序，所以可以用顺序查找也可以用折半查找；然后到相应块里用顺序查找找到目标结点。

平均查找长度记作 E(n)，教材给的设定是：线性表中共有 n 个结点，分成大小相等的 b 块，每块有 s=n/b 个结点。考试里如果让算平均查找长度，基本就是“索引查找的代价 + 块内顺序查找的代价”两部分，先确认题目给的块数和每块结点数，再代进去。

3.3 八种排序的答题模板：每种记一句话

直接插入排序：每一趟把一个待排序的记录按关键字大小插入到有序队列的合适位置，直到全部插入完成，类比斗地主抽牌后往手里插牌。

简单选择排序：每趟从待排序记录中选出关键字最小的记录，顺序放在已排序记录序列的末尾，直到排完。

冒泡排序：两两比较待排序的关键字，交换不满足次序要求的那一对数，直到整个表满足次序要求。

希尔排序：把记录按步长 gap 分组，每组用直接插入排序；随着步长逐渐减小，每组包含的记录越来越多，步长减到 1 时整个数据合成一组，排序完成。

快速排序：一趟排序把数据分割成独立的两部分，分割点左边都是比它小的数，右边都是比它大的数，再对两部分递归快排，用的是分治策略。

堆排序：n 个元素的序列 {k1, k2, …, kn} 满足 ki≤k2i 且 ki≤k2i+1，或者 ki≥k2i 且 ki≥k2i+1（i=1,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(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 序列 n=8，i 从 1 到 4：i=1，10≤18 且 10≤15，成立；i=2，18≤20 且 18≤50，成立；i=3，15≤80 且 15≤30，成立；i=4，20≤60，成立。四项全满足，B 是堆。A 在 i=2 处 50≤30 不成立，C 在 i=4 处 50≤20 不成立，D 在 i=2 处 30≤20 不成立。所以答案是 B。

这类题不需要画出整棵树，按 i 从 1 到 ⌊n/2⌋ 逐个验证父子关系就行，一般验证到第二、第三个位置就能排除三个错误选项。

4. 计算类小题：符号数、表达式、广义表与归并路数的一遍过

4.1 原码、反码、补码、移码：四种码的转换规则

正数的原码等于自身的二进制数；负数的原码第一位为 1，这是符号位，表示负数，后面是自身的二进制数。正数的反码等于自身二进制数；负数的反码符号位不动，其余各位按位取反。正数的补码等于自身二进制数；负数的补码是在反码的基础上加 1。移码又叫增码，无论正负数，只要把补码的符号位取反即可。

应用场景是固定考点：计算机中最适合数字加减运算的编码是补码，最适合表示浮点数阶码的编码是移码。这两句话几乎每年都以选择题形式出现，看到“加减运算”找补码，看到“阶码”找移码。

转换题的手工流程：先写出绝对值的二进制，负数补上符号位 1 得到原码；原码除符号位外全部取反得到反码；反码末位加 1 得到补码；补码符号位取反得到移码。正数四码相同，不用折腾。

4.2 定点数范围：用 A、B 两个记号代替硬背

定点数就是小数点的位置固定不变的数，有两种约定：定点整数是纯整数，小数点在最低有效数值位之后；定点小数是纯小数，小数点在最高有效数值位之前。机器字长为 n 时，各种码制表示的带符号数范围如下。

记忆技巧是设 A=2^(n-1)，B=1-2^-(n-1)，那么原码和反码的定点整数范围都是 [-(A-1), A-1]，定点小数都是 [-B, B]；补码和移码的定点整数范围都是 [-A, A-1]，定点小数都是 [-1, B]。

规律很明显：补码比原码多表示一个最小负数，定点小数能表示到 -1。答题时先判断题目问的是定点整数还是定点小数，再看码制，最后套 A、B 两个记号，比现场推导快且不容易错。

4.3 前缀、中缀、后缀表达式：扫描方向和弹出顺序是命门

中缀表达式就是平时写的 a+b-c 这种形式。前缀表达式又叫波兰式，从右至左扫描表达式，遇到数字压栈，遇到运算符弹出栈顶的两个数，用运算符对它们做计算，注意是栈顶元素 op 次顶元素，结果入栈，重复到最左端。后缀表达式又叫逆波兰式，从左至右扫描，遇到运算符时弹出栈顶两个数，计算时是次顶元素 op 栈顶元素，重复到最右端。

教材例子：前缀表达式 “- × + 3 4 5 6”，从右往左把 6、5、4、3 压栈；遇到 + 弹出 3 和 4，3 是栈顶、4 是次顶，算 3+4=7 入栈；遇到 × 弹出 7 和 5，算 7×5=35 入栈；最后遇到 -，算 35-6=29。后缀表达式 “3 4 + 5 × 6 -”，从左往右压 3、4；遇到 + 弹出 4 和 3，算 3+4=7；压 5；遇到 × 弹出 5 和 7，算 7×5=35；压 6；遇到 - 算 35-6=29。

两个例子的结果都是 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、深度 2，L3 长度 3、深度 1。这三个例子建议直接背下来，考试遇到同类题照着数。

操作要点：长度看最外层逗号分隔出几项，深度从最外层往内数左括号最多叠几层。两者不要混，长度是“横向”的，深度是“纵向”的。

4.5 归并路数与寻址方式、CPU 组成

归并排序的归并路数公式写作 归并路数 = |log_k m|，其中 m 为元素个数，k 为多路归并趟数。教材例题：若对 27 个元素只进行三趟多路归并排序，则选取的归并路数为多少，选项是 2、3、4、5。按公式，log 以 3 为底、27 为真数的结果是 3，所以选 B。

答题时先分清题目给的是“趟数”还是“路数”。给趟数求路数，就是问 k 的几次方等于 m；给路数求趟数，就是问 m 需要几次 k 路归并才能归完。27=3³，所以三趟对应三路，这类数字通常是整数次幂，凑不出来就回看题干是否把 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³=27，k=3，不涉及对数换底，心算就能出。

6. 答题顺序与押题思路：先把稳的分装进口袋

上午卷的时间够用，但心态容易崩，所以顺序比速度重要。我的建议是分三档：第一档是邻接矩阵求度、排序复杂度查表、符号数转换、寻址方式判断，这些看到题干就能出答案，先扫一遍全部做完，把能拿的分锁死；第二档是哈夫曼编码、表达式求值、广义表长度深度，需要动笔推两步，放在中间做；第三档是堆的判断、归并路数、二分查找比较次数这类要验算的，留到最后，因为即使时间不够，蒙一个也有四分之一的命中率。

押题思路按分值密度排，优先级如下。

最后说个血泪教训。我早年做排序复杂度题，习惯先看时间复杂度再看稳定性，结果有一次四个选项的时间复杂度全写成 O(nlog2n)，只有稳定性不同，我盯了半天时间那一列，硬是没往下看，选了个不稳定但时间“看起来最顺眼”的。从那以后我每次做这类题都强制走一遍“先圈稳定性、再看时间、最后看空间”的三步，哪怕题干只问一句话。希望帮到你。

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