企业官网建设流程全解析

简介：《软件设计师（中级）——考点笔记精华版》面向备考软考中级软件设计师的考生，聚焦高频考点梳理与易错点攻克。文档围绕数据结构、树与二叉树、查找与排序等核心模块展开，既讲邻接矩阵在无向图、有向图中的度与出入度计算，也梳理顺序、链式、散列、索引四种存储结构的适用场景；对满二叉树、平衡二叉树、哈夫曼树及WPL计算给出判定方法与例题解析，并归纳二分查找、分块查找的适用条件与实现思路。排序部分覆盖直接插入、简单选择、冒泡、希尔、快速、堆、归并、基数等方法，附时间复杂度、辅助空间与稳定性对比表，便于快速记忆和查漏补缺。资源包共1个docx文件，约3.37MB，结构紧凑，适合打印或平板批注复习。已有382人学习，可作为冲刺阶段的知识清单与错题回溯参考。

1. 数据结构到底在考什么：从一张邻接矩阵说起

翻开软件设计师（中级）的考纲，第一页几乎全是数据结构的词：邻接矩阵、哈夫曼树、希尔排序、广义表。每个词单独看都能懂，凑在一起就变得难以理解。很多人准备软考中级时遇到的问题，往往在于能背出定义、却讲不清这个概念在解决什么问题，而题目恰恰都考在概念的边界上。

打个比方，数据结构这门学问就像整理衣柜：衣服是数据，挂衣杆、抽屉、收纳盒是存储结构，而怎么在三十秒内翻出那件黑毛衣，就是查找和排序要回答的事。同一堆衣服，换个收纳方式，效率能差出十倍。考证路上那些容易出错的题，本质上都在问同一句话：这份数据放在哪儿、怎么找、怎么排更划算。

2. 存储结构与树的家族：为什么同一份数据要换着花样存

2.1 顺序存储和链式存储，到底在权衡什么

先想一个场景：电影院里一排连号座位，坐满了人。这时候你朋友迟到，想坐进第 7 号位，你得让 7 号之后的所有人全体往右挪一格。这就是顺序存储的日常——数据元素放在一组地址连续的存储单元里，好处是找第几个人一步到位，坏处是中间插队代价极高。

顺序存储的地址计算有个很简单的公式：第 i 个元素的地址等于起始地址加上 i 乘以单个元素的长度。所以只要知道下标，访问任何一个元素的耗时都一样，这就是常说的随机访问。代价是插入和删除平均要搬动一半元素，元素一多，开销就很明显。

链式存储换了个思路：座位不连号，每个人手里攥着一张小纸条，写着下一位坐在几号厅。这组存储单元可以是连续的，也可以是不连续的，只要纸条能串起来就行。这种结构找第 i 个元素必须从头一个个走，但要在某人后面插一位，只改两张纸条就完事。所以原文那句话说得很准：顺序存储适用于频繁查询的时候，链式存储适用于比较频繁地插入、删除、更新元素的时候。

链表家族里还有三种常见变体，考试里经常拿来对比。单链表只有后继指针，走到头就停；循环链表把尾节点的指针指回头节点，形成一个环，适合做轮询类的处理；双链表每个节点有两个指针域，一个指前一个指后。双链表因为多了一个指针域，灵活度优于单链表，往前走往后走都方便，但开支要大一些——每个节点多占一份指针的存储空间，插入删除时要多维护一根线，写代码时漏掉一根就是经典的血泪经验。

再说两种容易被忽略的存储方式。散列存储是把数据元素的存储位置与关键码之间建立确定对应关系的查找技术，说白了就是键值对：给一个键，用散列函数算一下，直接跳到对应的位置。理想情况下查找是常数时间，但它不是万能的，不同的键可能算出同一个位置，这种撞车要靠额外手段处理，而且它天生不支持按范围查找。索引存储则是另一套思路，索引是一个单独的、物理的数据库结构，它是某个表中一列或若干列值的集合，以及相应的指向表中物理标识这些值的数据页的逻辑指针清单。翻书的目录就是索引，你不会从第一页翻到最后一页找某一章，而是先看目录定位页码。

把这四种放在一起看，其实就是一句话：顺序存储拿空间换时间，链式存储拿时间换空间，散列存储拿顺序性换查找速度，索引存储拿额外的存储换检索效率。题目里问「某场景该选哪种存储」，答案基本都能从这几个权衡里推出来。

2.2 邻接矩阵里藏着的度、出度和入度

图这种结构比线性表复杂，因为节点之间是多对多的关系，所以存法也不一样。邻接矩阵是拿一个 n 行 n 列的二维表格来表示：第 i 行第 j 列是 1，就说明顶点 i 到顶点 j 有边；是 0 就没边。n 个顶点就要开 n 乘 n 的格子，空间开销是平方级的，所以它只适合顶点数目不多的场景。

它的妙处在于，很多图的性质可以直接用「数格子里有几个 1」求出来。

无向图的边没有方向，两个顶点互为邻居，矩阵沿着对角线对称。这时候邻接矩阵第 i 行元素的和，就是这个顶点 i 的度——也就是它连了几条边。原文给的例子是：顶点 4 的度就是第四行的和，即 2。数一下那一行有两个 1，它就连了两条边，很直觉。

有向图就不一样了，边有箭头，从一个顶点指向另一个顶点。这时候第 i 行元素之和变成了顶点 i 的出度——从它出发的箭头有几根；而第 j 列元素之和是顶点 j 的入度——指向它的箭头有几根。原文那个例子说顶点 3 的出度和入度分别为 5 和 16，说明这个顶点「撒出去」五条边，「收进来」十六条边，两者不相等，正是有向图的特征。

用一小段代码把这件事跑一遍，比盯着定义看快得多。

# 邻接矩阵演示：无向图求度，有向图求出度与入度 # 这里用 4 个顶点的无向图，1 表示有边，0 表示无边 graph = [ [0, 1, 0, 0], # 顶点 1：连着顶点 2 [1, 0, 0, 1], # 顶点 2：连着顶点 1、4 [0, 0, 0, 1], # 顶点 3：连着顶点 4 [0, 1, 1, 0], # 顶点 4：连着顶点 2、3 ] # 无向图：第 i 行之和就是顶点 i 的度 degrees = [sum(row) for row in graph] print(degrees) # 输出 [1, 2, 1, 2]，顶点 4 的度为 2 # 有向图：抓住方向，行看出去、列看进来 n = len(graph) out_degree = [sum(row) for row in graph] # 行求和 = 出度 in_degree = [sum(graph[i][j] for i in range(n)) for j in range(n)] # 列求和 = 入度

这段代码里有三个要点值得记住。sum(row)是把一整行加起来，对应「行和」这个动作；列求和那行稍微绕，graph[i][j]固定列号 j、让行号 i 变，正好把一列扫一遍；索引从 0 开始数，所以代码里的下标 3 对应题目里说的「顶点 4」。矩阵是对称的，无向图的行和列和必然相等，如果算出来不相等，那要么图是有向的，要么矩阵写错了。

2.3 二叉排序树、平衡二叉树、哈夫曼树各自的活儿

树是这一章的重头戏，三种树经常被混在一起问，但它们的分工完全不同。

二叉排序树管的是「有序」。它的定义有三条：若左子树非空，则左子树上所有节点的值均小于它的根节点的值；若右子树非空，则右子树上所有结点的值均大于等于它的根节点的值；它的左、右子树也分别为二叉排序树。这三条合起来就是一个性质：中序遍历这棵树，能得到一个递增序列。所以判断一棵树是不是二叉排序树，最快的办法不是逐个比较，而是中序遍历一遍看结果是否递增。

它还有个常考的小结论：关键字最大的结点可以有左子树，但一定没有右子树。理由很直白，最大值的右边不可能再有比它大的东西，右子树一旦存在就违反了定义。

平衡二叉树管的是「别长歪」。它又被称为 AVL 树（有别于 AVL 算法，这两个名字撞车是常见坑），性质是：它是一棵空树，或者它的左右两个子树的高度差的绝对值不超过 1，并且左右两个子树都是一棵平衡二叉树。为什么要在意高度差？因为二叉排序树的查找效率跟树高直接相关，如果插入的顺序恰好是从小到大，树会退化成一条链，查找就变成了逐个比较。平衡二叉树就是给这种退化打的补丁。

满二叉树管的是「排满」。原文的定义是：除最后一层无任何子节点外，每一层上的所有结点都有两个子结点或 0 个子节点的二叉树。换个通俗说法，就是每一层都塞得满满当当，没有任何空缺的位置。它更像一个形状标准，考点通常是数节点数、算层数，而不是查找。

哈夫曼树管的是「省地方」，也叫最优二叉树，定义是带权路径（WPL）最短的树，权值越大的叶子节点越靠近根节点。WPL 是每个叶子节点的权值乘以它到根的路径长度，再全部加起来。同样的叶子，摆放方式不同，这个总和能差不少，所以要让权重大的叶子离根近一点，走的步数少一点。

构造哈夫曼树的套路是固定的：每次从当前集合里挑出两个权值最小的节点，合成一个新节点，新节点的权值是两者之和，再把这个新节点扔回集合，重复到只剩一个节点为止。构造完之后给边赋值，通常左 0 右 1，从根走到叶子经过的 0/1 序列就是这个字符的编码。

原文那道编码题的思路值得拆开看。文件里出现 6 个字符 a、b、c、d、e、f。如果用定长编码，需要多少位？二的 3 次方是 8，二的 2 次方只有 4，不够表示 6 个字符，所以 3 位就够，答案是 3。这里容易翻车的地方是有人觉得「位数越多越保险」，但题目问的是最合适的长度，够用就停。

第二问问字符序列「face」的哈夫曼编码。做法是建好树以后，从根节点出发找 f、a、c、e 这四片叶子，把路径上的 0 和 1 连起来。要注意树形不唯一：左节点未必要比右节点小，但通常做题时需要写成左小右大的形式，再左 0 右 1 赋值，这样答案才能和选项对上。原文给的答案是 110001001101，选 B。这类题只要养成「先定规则再走路径」的习惯，基本不会错。

WPL 的计算也是同理，把每个叶子的权值乘上它的深度，加起来就完事。考试里常出的变形是「给一组频率，求平均码长」，本质就是 WPL 除以总权值，理解了这一层，题目怎么变都不慌。

3. 查找与排序：为什么没有「最好的算法」这回事

3.1 二分查找的前提条件比效率更重要

二分查找也叫折半查找，过程像猜数字游戏：心里想一个 1 到 100 的数，对方每次猜中间值，你说大了还是小了，七次之内必中。算法描述是：假设表中元素按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复这个过程，直到找到满足条件的记录，或者子表不存在为止，此时查找不成功。

它的适用情况写得很明确：不经常变动而查找频繁的有序列表。优点有三条——比较次数少、查找速度快、平均性能好；缺点也有两条——要求待查表为有序表、插入删除困难。这两条缺点才是关键。很多人只记住「二分查找快」，却忘了它建立在「已经排好序」这个前提上，每次插入新数据都要重新维护顺序，频繁增删的场景下，维护成本会把省下来的查找时间全吃掉。

实现上有几个小地方容易踩坑。一是中间位置的取法，写成(low + high) / 2在元素特别多的时候可能溢出，安全写法是low + (high - low) / 2。二是循环的边界，到底是low < high还是low <= high，取决于区间是左闭右开还是双闭，两种写法混用就会出现死循环或者漏查最后一个元素。三是序列必须是升序或降序的单调序列，如果表本身乱序，先排序再二分的总成本可能还不如直接顺序扫一遍。

3.2 分块查找解决了什么问题

分块查找夹在顺序查找和折半查找中间，它要解决的是一个现实矛盾：数据既要能快速查，又要能频繁变动。

它的做法是把一个大的线性表分解成若干块，每块中的节点可以任意存放，但块与块之间必须排序。假设是按关键码值非递减的，那么这种块与块之间必须满足已排序要求，实际上就是对于任意的 i，第 i 块中的所有节点的关键码值都必须小于第 i+1 块中的所有节点的关键码值。此外还要建立一个索引表，把每块中的最大关键码值作为索引表的关键码值，按块的顺序存放到一个辅助数组中，这个辅助数组自然是有序的。

查找分两步走：先在索引表里查，确定目标落在哪一块，因为索引表有序，所以这一步可以用顺序查找也可以用折半查找；然后在那一块里用顺序查找，把目标捞出来。

它的适用情况是节点动态变化的情况——新数据来了，只要往对应的块里塞，块满了就分裂成两块、更新一下索引，不需要像二分查找那样整体重排。优点是比顺序查找快得多，缺点是速度不如折半查找。原文还给了平均查找长度 E(n) 的设定：假设某个线性表中共有 n 个节点，分成大小相等的 b 块，每块有 s = n/b 个节点。这个设定是用来推平均查找次数的，索引表查一次、块内平均查一半，两部分加起来就是总开销。理解这个思路比背公式有用，因为公式的形式会变，思路不会。

3.3 八种排序的分工与稳定性

排序这一块最容易背混，因为名字多、复杂度多、稳定性还要单独记。把每种排序的「动作画面」想清楚，比死记表格靠谱得多。

直接插入排序的描述是：每一趟将一个待排序的记录，按照其关键字的大小插入到有序队列的合适位置里，直到全部插入完成。原文打的比方特别好——斗地主抽牌就是这样的规则，你手里已经有一把排好的牌，新摸一张就插到该在的位置。它的特点是数据越接近有序，效率越高。

简单选择排序是：每趟从待排序的记录中选出关键字最小的记录，顺序放在已排序的记录序列末尾，直到全部排序结束。它的动作很像整理书架：每次从剩下的书里挑最薄的一本放到最左边，不管中间过程，只保证每一轮挑出的都是当前最小。

冒泡排序是：两两比较待排序的关键字，并交换不满足次序要求的那对数，直到整个表都满足次序要求为止。它的画面感最强，大的数一轮一轮往右「冒」上去。效率不高，但胜在稳定、好写、容易理解。

希尔排序是：把记录按步长 gap 分组，对每组记录采用直接插入排序方法进行排序；随着步长逐渐减小，所分成的组包含的记录越来越多，当步长的值减小到 1 时，整个数据合成为一组，构成一组有序记录，则完成排序。它是对插入排序的改良：插入排序怕的是元素离目标位置太远，要一步一步挪；希尔排序先用大步长让元素快速跳到大致位置，再用小步长精修。步长怎么选是个玄学，选得好效率明显提升，选得差就退化成普通插入排序。

快速排序是：通过一趟排序将要排序的数据分割成独立的两部分，分割点左边都是比它小的数，右边都是比它大的数，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。原文点明它采用了分治法的算法策略。它的平均表现很好，但最坏情况下会退化成平方级，触发条件通常是序列本身已经基本有序，而每次又恰好挑到端点的元素当基准。

堆排序要先理解堆的定义：n 个元素的序列 {k1, k2, …, kn} 当且仅当满足每个节点都小于等于它的两个子节点，或者都大于等于它的两个子节点时，称为堆。前一种是小顶堆，后一种是大顶堆。堆排序就是把序列调成一个堆，然后反复把堆顶（最大或最小）取出来放到末尾，再重新调整剩下的部分。它全程在原数组里操作，辅助空间是常数，这是它的杀手锏。

归并排序是：将待排序序列看成 n 个长度为 1 的有序序列，将相邻的有序表成对归并，得到 n/2 个长度为 2 的有序表；将这些有序序列再次归并，得到 n/4 个长度为 4 的有序序列；如此反复进行下去，最后得到一个长度为 n 的有序序列。它的思路是「先拆到最小，再两两合并」，全程稳定，代价是需要额外的数组空间。

基数排序跟前七种都不一样，它不需要比较关键字的大小。它是根据关键字中各位的值，对排序的 N 个元素进行若干趟「分配」与「收集」来实现排序的。原文的例子很清楚：初始序列是 50、123、543、187、49、30、0、2、11、100，任何一个阿拉伯数的各个位数上的基数都是以 0 到 9 来表示的，所以不妨把 0 到 9 视为 10 个桶。先按个位数的数字分类，把数分到指定的桶里，比如 50 个位数是 0，就进 0 号桶；分类完再从 0 号桶到 9 号桶依次取出来，这时序列就是个位数递增的：50、30、0、100、11、2、123、543、187、49。接着按十位、百位重复同样的动作，几趟之后整个序列就有序了。

3.4 时间复杂度表怎么读

八种排序的复杂度可以汇总成一张表，但读表有技巧，不要硬背。

第一眼看这张表，记住三件事就够用了。稳定的是直接插入、冒泡、归并、基数，剩下四个不稳定，口诀是「快些选堆」不稳——快速、希尔、选择、堆排序。辅助空间是常数的有插入、选择、冒泡、希尔、堆，快排要递归栈所以是对数级，归并要额外数组所以是线性级，基数排序要桶所以跟基数有关。

第二件事是「最好情况最好」的那两个：直接插入和冒泡在数据本来就有序时是 O(n)，一轮扫下来发现不用换就结束了。希尔排序的那一栏写「不存在」，因为它的复杂度跟步长序列强相关，没有一个公认的最好或最坏表达，这是它区别于其他算法的地方。

第三件事是快排的悖论：平均 O(nlog₂n)，最坏 O(n²)。这不是理论上的边角情况，实际工程里如果数据已经接近有序又没做随机化，真的会翻车。有人觉得快排「最快」所以哪里都用，这就是典型的把平均当保证。

堆的判断也是高频题。原文给出的例题是四个序列，问哪个是堆，按定义逐个节点检查它和两个子节点的关系，答案是第二个序列 10、18、15、20、50、80、30、60。检查的方法很机械：第 1 个元素 10 的两个子节点是第 2、3 个元素 18 和 15，10 比它们都小，符合小顶堆；第 2 个元素 18 的子节点是第 4、5 个元素 20 和 50，18 比它们都小，也符合；一路查下去都对，就是堆。这个检查顺序值得养成习惯，从左往右、从上往下过一遍，不要跳着看。

4. 常见误区与易混概念：那些年一起搞混的树、表和表达式

4.1 满二叉树、完全二叉树、平衡二叉树不是一回事

易混点：三种树都带「二叉」，名字里都有形容「整齐」的字，做题时看到图和描述就容易对错号。

为什么混：它们的判据完全不同。满二叉树看的是每一层是否排满；完全二叉树看的是最后一层是否从左到右连续填充；平衡二叉树看的是左右子树高度差的绝对值是否不超过 1。一棵树完全可能满而不平衡（几乎不可能，但逻辑上判据独立），也可能平衡但远没满。

怎么区分：拿到题先问自己「题目在问形状还是在问高度」。问节点数、层数、叶子数，多半在考满二叉树；问「编号为 i 的节点其父节点是谁」这种数组下标关系，是在考完全二叉树；问查找效率、树高、旋转，是在考平衡二叉树。判据不同，答案自然不同。

4.2 广义表的长度是数最外层元素，深度是数括号层数

易混点：长度和深度这两个词都像在形容「有多大」，看广义表((a,(a,b),((a,b),c)))更难分辨。

为什么混：广义表是嵌套结构，一层套一层，初学者数着数着就糊涂了，尤其括号一多，不知道哪个括号算一层。

怎么区分：原文给的定义很干脆——长度是将最外面那层的括号删了以后所剩下的元素（组）个数，深度是括号的层数。用这个规则套三个例子：L1 = ((a,(a,b),((a,b),c)))，删掉最外层括号后里面只有一个元素，所以长度是 1；括号从外往里数一共 4 层，深度是 4。L2 = ((1,2,3))，删掉最外层剩下一个组，长度 1；括号两层，深度 2。L3 = (1,2,3)，删掉最外层剩三个元素，长度 3；只有一层括号，深度 1。

记住一句话就够：长度数「逗号隔开几坨」，深度数「套了几层壳」。逗号在括号里面的不算。

4.3 前缀和后缀表达式的弹栈顺序正好相反

易混点：两种表达式都是用栈算，都要弹两个数，但谁减谁、从哪边扫，方向一乱结果就错。

为什么混：中缀表达式我们从小用到大，a+b-c谁前谁后一目了然；一旦改成前缀或后缀，操作数还在，运算符的位置变了，人的直觉就跟不上了。

怎么区分：记两条规则，方向相反、顺序相反。前缀表达式是从右至左扫描，遇到数字压栈，遇到运算符弹出栈顶的两个数，用运算符对它们做相应的计算（栈顶元素 op 次顶元素）。后缀表达式是从左至右扫描，遇到数字压栈，遇到运算符弹出栈顶的两个数，用运算符计算（次顶元素 op 栈顶元素）。

拿同一道题验证：前缀- × + 3 4 5 6，从右往左扫，先把 6、5、4、3 压栈；遇到+弹出 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。两个答案一样，但弹出顺序完全相反，这就是最容易出错的地方。

用代码把后缀求值写一遍，规则就忘不掉了。

# 后缀表达式求值：从左往右扫，数字入栈，运算符弹两个算完再入栈 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) # 注意是 a - b，不是 b - a elif t == "*": stack.append(a * b) else: stack.append(int(a / b)) return stack[0] print(eval_rpn(["3", "4", "+", "5", "*", "6", "-"])) # 输出 29

这段代码的关键只有一处注释里写的那点：先弹出的是右操作数，后弹出的才是左操作数。减法除法不满足交换律，顺序反了结果就错。前缀表达式要改两处：把序列反转后从右往左处理，同时把a - b换成b - a。这一点在纸上推一遍比看十遍定义都管用。

4.4 原码、反码、补码、移码各自适合什么

易混点：四种码都是把二进制数换个写法，正数在三种码里还完全一样，导致记不住谁是谁。

为什么混：正数的原码、反码、补码等于自身的二进制数，这个「三码合一」让人放松警惕，一到负数就全乱。

怎么区分：先记住符号位这个前提。原码是正数等于自身二进制，负数的第一位为 1（符号位，表示负数），后面为自身的二进制数。反码是正数等于自身，负数的符号位不动、其余各位按位取反。补码是正数等于自身，负数的补码是在反码的基础上加 1。移码最特殊，无论正负数，只要将其补码的符号位取反即可。

再记用途，这是考点真正的落点：在计算机中，最适合数字加减运算的数字编码是补码，最适合表示浮点数阶码的数字编码是移码。补码之所以胜任加减法，是因为它把减法统一成了加法，零只有一种表示，不用单独处理正零负零；移码之所以适合阶码，是因为符号位取反之后，整个编码的大小顺序和无符号数一致，比较浮点数大小时可以直接比。

范围的记忆也有技巧。当 A = 2^(n-1)，B = 1 - 2^(-(n-1)) 时，定点整数的原码和反码范围是 [-(A-1), A-1]，补码和移码是 [-A, A-1]；定点小数的原码和反码是 [-B, B]，补码和移码是 [-1, B]。看出规律没有：补码比原码多表示一个负数，这就是它「零只有一种表示」省下来的位置。

4.5 归并路数和归并趟数别弄反

易混点：路数和趟数都带个「数」字，公式里又互为条件，读完题不知道哪个是已知、哪个是要求。

为什么混：多路归并的过程是「几路一起合并」，一趟做一次，两个词天然纠缠在一起。

怎么区分：路数是「一次能合并几个有序段」，趟数是「总共要合并几轮」。原文给的公式是归并路数 = |log_k m|，其中 m 为元素个数，k 为多路归并的趟数。配上例题就好懂了：若对 27 个元素只进行三趟多路归并排序，则选取的归并路数为多少。把 27 当元素个数、3 当趟数代进去，log 以 3 为底、27 为真数，答案是 3，所以选 B。

做这类题的稳妥做法是：先在草稿上写清楚已知的是「总数」还是「轮数」，再套公式，别凭语感猜。归并的场次和路数是反向关系，路数越大，需要的趟数越少，这个方向感能帮你排除明显不合理的选项。

5. 计算机底层那些「约定」：补码、寻址与指令

5.1 补码为什么能省掉一套减法电路

计算机里只有加法器，没有专门的减法器，这不是偷懒，是成本考虑。如果减法要单独做一套硬件，电路会复杂一大截。补码的精妙之处在于，它把「减去一个数」变成了「加上一个数的补码」，同一个加法器把两件事都干了。

举个具体的例子。假设机器字长是 8 位，要算 5 减 3。先把 3 写成补码：3 的原码是 00000011，正数三码合一，补码也是 00000011；取负变成 -3，-3 的原码是 10000011，反码是 11111100，补码是反码加 1，得 11111101。然后算 5 加 -3：00000101 加 11111101 等于 1 00000010，最高位溢出丢掉，剩下 00000010，也就是 2。结果正确。

这套机制还带来一个副产品：零的表示唯一。原码里 00000000 和 10000000 分别表示正零和负零，两个零在比较时是麻烦事；补码里零只有一种写法，判断「是不是零」只需要看是不是全零。原文提到补码的定点整数范围是 [-2^(n-1), 2^(n-1)-1]，比原码的 [-(2^(n-1)-1), 2^(n-1)-1] 多出一个负数，多出来的那个位置就是原先负零占的坑。

定点数本身的概念不难：小数点的位置固定不变的数就叫定点数，有两种约定形式，定点整数（纯整数，小数点在最低有效数值位之后）和定点小数（纯小数，小数点在最高有效数值位之前）。浮点数则相反，小数点的位置是浮动的，用阶码和尾数两部分表示，这也是为什么阶码要用移码——比较两个浮点数的大小，先比阶码，阶码用移码表示就能直接当无符号数比。

5.2 四种寻址方式，谁快谁慢

指令系统这一块，考点集中在「操作数在哪」。寻址方式的名字其实已经把答案写出来了，只是读题时容易看漏一个字。

立即寻址：操作数包含在指令中，获取操作数是最快的。因为数据就躺在指令里面，取指令的同时就把数据拿到了，不用再跑一趟内存。

直接寻址：操作数的地址在指令中。指令里给的是一个门牌号，得按着门牌号去内存里取一次，比立即寻址多一趟。

寄存器寻址：操作数在寄存器中。寄存器在 CPU 内部，速度极快，指令里只需要指明用哪个寄存器，不用访问内存。

寄存器间接寻址：操作数的地址在寄存器中。这是两层跳转：先从寄存器里拿到地址，再按地址去内存取数据。它比直接寻址灵活，因为地址可以动态改变，但多了一次内存访问。

按速度快慢排，大致是立即寻址最快，寄存器寻址紧随其后，直接寻址再次，寄存器间接寻址最慢。判断的口诀是看「操作数或它的地址到底在哪儿」——在指令里最快，在寄存器里次快，在内存里就慢。

5.3 CPU 内部到底有什么

CPU 的组成这道题几乎是送分题，但送分题也常有人失手。原文写得很清楚：CPU 由运算器、控制器、寄存器和内部总线组成，其中控制器不仅要保证程序的正确执行，而且要能够处理异常事件。

这四部分的角色可以类比成一个小工厂。运算器是车间，负责加减乘除和逻辑运算；控制器是调度室，负责从内存取指令、翻译指令、指挥各个部件按顺序干活，还得盯着有没有突发状况（也就是异常事件）；寄存器是手边的小抽屉，放正在处理的几个数，取用最快但容量很小；内部总线是厂区里的传送带，把这几部分连起来，数据和信号在上面跑。

这里容易被忽略的是控制器「处理异常事件」这个职责。很多人以为控制器只管按部就班执行指令，实际上中断、异常这些打断正常流程的情况，也要靠它来接管和恢复。考纲把这个点单独拎出来，说明它容易被漏掉。

把这几块拼起来看，第 2 章到第 4 章的那些结构、算法、编码，最终都要落到这个硬件上跑。数据结构决定了数据在内存里怎么摆，排序查找决定了访问顺序，补码决定了运算怎么实现，寻址方式决定了指令怎么找到数据。一条线串下来，整本笔记就不再是一堆孤立的名词。

6. 什么时候该背公式，什么时候该动手画：一份笔记的使用边界

考点笔记最大的价值不是「背下来」，而是「在对的场合翻到对的那一页」。用错了地方，背得再熟也是白搭。

下面这张表是我自己复习时总结的分工，按题型归类。

表格里最右边那列比左边更重要。复习到后期，最常见的失分不是不会，而是把熟悉的方法用错了地方——比如拿顺序结构去处理频繁插入的场景，或者对无序表用二分查找，题目本身没问题，是前提被忽略了。

那什么时候不该用这本笔记？有两种情况。

第一种是还没建立整体框架就开始刷细节。邻接矩阵的行和列和、原码反码的转换规则、希尔排序的步长选择，这些点单独记都不难，但如果不知道它们在整张地图上的位置，记了也会忘。建议先花半天把「存储结构、树、查找、排序、编码、硬件」这六块的关系捋顺，再回头啃细节。顺序反了，就是纯消耗。

第二种是把笔记当唯一的复习材料。笔记是浓缩过的，浓缩必然有取舍，它告诉你「考什么」，但没法告诉你「为什么这么设计」。遇到看不懂的定义，回到教材或者动手写两行代码验证一下，比反复读同一句话有效得多。

我自己的习惯是每次做错题，都强制走一遍「这道题考的是哪一章的哪个判据」这个动作，而不是把正确答案抄一遍了事。有一次做无向图求度的题，我把行和算成了列和，本来对称的图算出来居然不相等，愣了半天才发现是自己把有向图的规则套上去了。从那以后我每次碰到图的矩阵题，都先写一句「这图有没有方向」，再动笔。这种小动作看着笨，但能挡住大部分低级错误。

希望帮到你。

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