数据结构与算法专题 DS & Algo · 栈队列 · 树图 · 排序 · 策略
软考 · 软件设计师 ｜ 上午约 9 分 + 下午试题四 C 算法填空约 15 分｜ 希赛累计：排序 18、二分/贪心/栈队列/特殊二叉树各 9
⏱ 考前 10 分钟速览
① 栈 / 队列： 栈后进先出（递归、后缀、括号）；队列先进先出（层次遍历、BFS）。② 单链表： 插删头结点不用 遍历；删尾一定要遍历 （找前驱）。顺序表按下标 O(1)，插中间要搬。③ 树： 叶子 n0 = 1 + n2 + 2n3 + 3n4 + …。二叉树永远 n0 = n2 + 1。④ 森林→二叉树： 左孩子=第一个孩子，右孩子=兄弟。森林叶子 = 二叉树里没有左孩子 的结点。⑤ 查找： 有序顺序表才能二分；n=29 最坏 5 次。保证 比较次数上限 → 别选哈希、别选歪 BST。⑥ 排序稳定： 冒泡 / 插入 / 归并 / 基数。选择、快排、堆、希尔不稳定 。简单选择每趟把剩下最小的换到前面。⑦ 策略： 重叠子问题+最优子结构=动规 ；当前最优=贪心；独立分解=分治；深度试探=回溯；广度搜解空间=分支限界。⑧ 复杂度从小到大： 1 < log n < n < n log n < n² < n³ < 2ⁿ < n!
⚡ 今早先看 · 对照表
看见题干 闭眼选 递归怎么返回 / 后缀式 / 括号匹配 栈 层次遍历 / 广度优先 队列 单链表「正确的是」插删头 / 尾 删最后一个一定遍历 （找前驱） 二叉树叶子、度为 2 的结点 n0 = n2 + 1 树的度 4，给各度结点数求叶子 n0 = 1 + n2 + 2n3 + 3n4 森林转二叉树后，原来的叶子 二叉树里没有左孩子 的结点 哈夫曼 / 最优二叉树 没有度为 1 的结点；WPL 最小 二叉排序树中序 得到有序 序列 保证最多比 k 次 有序表二分 （不要选哈希） 稳定排序 冒泡 / 插入 / 归并 / 基数 简单选择排序走两趟 每趟把剩下最小的 换到当前最前 最优子结构 + 重叠子问题 动态规划 只根据当前信息做选择、不回头 贪心 大问题拆成独立相同的小问题 分治 深度优先搜解空间，走不通就退 回溯 广度优先搜解空间 分支限界
① 顺序表、链表、栈、队列 线性结构
顺序表（数组） 单链表 按下标找 O(1) O(n)，要从头爬 在中间插入 / 删除 后面元素要搬，O(n) 改指针 O(1)（已经站在该结点上时） 插、删头 插头要整体后移 不用遍历 插、删尾 有长度就能直接到尾 删尾一定要遍历找前驱 。插尾：没尾指针才要遍历
🎯 单链表没有「尾巴的前一个」指针。删最后一个结点必须爬到倒数第二个，所以「删除最后一个节点需要遍历」一定对。插尾如果题目没给尾指针也对，但选项里更稳的是删尾。
栈 Stack 队列 Queue 进出 后进先出 LIFO 先进先出 FIFO 卷面场景 函数调用 / 递归返回、后缀计算、括号匹配、DFS 用栈 层次遍历、BFS、打印排队 循环队列满 — 常留一个空位，(rear+1)%n == front 为满；front==rear 为空。用来消灭顺序队列的假溢出
栈的进出有约束：后进的必须先出来。出栈序列若第一个是 3，则 1、2 已在栈里且 2 压在 1 上，下一个只能出 2，不可能紧接着出 1 。
两栈共享 V[1..n]：栈 1 从左往右长，栈 2 从右往左长。题干「空时 top[1]=1、top[2]=n」表示 top 指向下一次要写的格子 。栈满 = 两边下一笔已经交叉：top[1]−top[2]==1。
练一练 · 2020下 · 顺序存储特点
2020下 存储方式
通过元素在存储空间中的相对位置来表示数据元素之间的逻辑关系，是（ ）的特点。
A. 顺序存储B. 链表存储C. 索引存储D. 哈希存储
答案 A
挨着放，下标差就是逻辑邻居。链表靠指针，索引靠目录，哈希靠函数算地址。
练一练 · 2022下 · 出栈序列
2022下 栈
设栈初始时为空，对于入栈序列 1，2，3，⋯n，这些元素经过栈之后得到出栈序列 P1,P2,P3,⋯Pn，若 P3=4，则 P1，P2 不可能的取值为（ ）。
A. 6,5B. 2,3C. 3,1D. 3,5
答案 C
P1=3 时栈里从上到下是 2、1，下一个只能出 2，P2 不能是 1。A 可以先把 1..6 压进去再连续弹出。
练一练 · 2021下 · 两栈共享 / 循环队列
2021下 Q57–58 栈满 · 循环队列
（57）若栈采用顺序存储方式，现有两栈共享空间 V[1..n]，top[i] 代表第 i（i=1,2）个栈的栈顶（两个栈都空时 top[1]=1、top[2]=n），栈 1 的底在 V[1]，栈 2 的底在 V[n]，则栈满的条件是（ ）。
（57）A. top[1]=top[2] B. top[1]+top[2]==1 C. top[1]+top[2]==n D. top[1]−top[2]==1A. 入队和出队可以在队列的同端点进行操作B. 入队和出队操作都不需要移动队列中的其他元素C. 避免出现队列满的情况D. 避免出现队列空的情况
答案 D、B
（57）空时下一笔写在 1 和 n。栈 1 的 top 往右加，栈 2 的 top 往左减。交叉时差为 1。
练一练 · 2024上 · Q16 链表
2024上 Q16 单链表
关于链表操作中，说法正确的是（16）。
A. 新增一个头节点需要遍历链表B. 新增一个尾节点需要遍历链表C. 删除最后一个节点需要遍历链表D. 删除第一个节点需要遍历链表
答案 C
A、D：头插、头删改头指针即可，不遍历。C：单链表删尾必须找到前驱，一定遍历。B 在「没有尾指针」时也对，有尾指针时插尾不用遍历——所以最稳、任何实现都成立的是 C。希赛回忆也按「删最后一个要遍历」。
② 数组（行优先地址）
二维数组按行优先 排：先把第 0 行排完，再第 1 行……每个元素占 s 个单元，A[0][0] 的地址是 a0，共 n 列（下标从 0 起）：
Loc(A[i][j]) = a0 + (i × n + j) × s
卷面常不告诉你 n，用一个已知元素反推列数，再代另一个下标。
练一练 · 2024上 · Q17 地址
2024上 Q17 行优先
已知二维数组 A 按行优先方式存储，每个元素占 2 个存储单元，第一个元素 A[0][0] 的地址为 100，元素 A[3][3] 的存储地址是 220，则元素 A[5][5] 的地址是（17）。
A. 300 B. 306 C. 310 D. 296
答案 A
100 + (3n+3)×2 = 220 → 3n+3 = 60 → n = 19。300 。
③ 树与二叉树
3.1 度和叶子（年年有计算）
结点的度 = 孩子个数。树的度 = 最大的那个结点度。叶子 = 度为 0。
任意树：边数 = 结点数 − 1 = 1·n1 + 2·n2 + 3·n3 + … 整理得：
🎯 叶子公式：n0 = 1 + n2 + 2 n3 + 3 n4 + … （n1 消掉了）。二叉树是它的特例：只有 n0、n1、n2，所以 n0 = n2 + 1 。
练一练 · 2024上 · Q18 叶子
2024上 Q18 树的度
对于一棵树，每个结点的孩子结点个数称为结点的度，结点度数的最大值称为树的度。某树 T 的度为 4，其中有 5 个度为 4 的结点，8 个度为 3 的结点，6 个度为 2 的结点，10 个度为 1 的结点，则 T 中的叶子结点个数为（18）。
A. 38 B. 29 C. 66 D. 57
答案 A
n0 = 1 + n2 + 2n3 + 3n4 = 1 + 6 + 16 + 15 = 38 。n1=10 用不上。
3.2 遍历
名字 顺序 用途 先序（前序） 根 → 左 → 右 复制树、先根 中序 左 → 根 → 右 BST 中序 = 有序 后序 左 → 右 → 根 删树、后缀表达式（语法树） 层次 一层一层，用队列 —
已知先序+中序，或后序+中序，可以唯一还原二叉树。只给先序+后序一般不能 唯一确定（左右子树无法分辨）。
中序 = 左根右，所以「中序时 n 排在 m 前面」= n 在 m 的左边（m 在 n 的右边）。祖先/子孙都推不出中序谁先谁后（左子孙在前，右子孙在后）。
练一练 · 2022下 · 中序谁在前
2022下 中序
设 m 和 n 是某二叉树上的两个节点，中序遍历时，n 排在 m 之前的条件是（ ）。
A. m 是 n 的祖先节点B. m 是 n 的子孙节点C. m 在 n 的左边D. m 在 n 的右边
答案 D
中序先左后根再右。n 在 m 前面 ⇒ n 在左、m 在右，也就是 m 在 n 的右边。C 说反了。
练一练 · 2022上 · 同样的叶子公式
2022上 树的度
已知树 T 的度为 4，且度为 4 的节点数为 7 个、度为 3 的节点数为 5 个、度为 2 的节点数为 8 个、度为 1 的节点数为 10 个，那么 T 的叶子节点个数为（ ）。
A. 30 B. 35 C. 40 D. 49
答案 C
n0 = 1 + n2 + 2n3 + 3n4 = 1 + 8 + 10 + 21 = 40。和 2024 上 Q18 同一套路，换数字。
3.3 特殊二叉树（累计 9 分）
名字 样子 题眼 满二叉树 每层都是满的 高 h（层数）结点数 = 2h −1 完全二叉树 最后一层从左往右排满，中间不缺 编号 i 的左孩子 2i、右孩子 2i+1（从 1 起） 二叉排序树 BST 左 < 根 < 右 中序有序；最坏退化成链，查找 O(n) 平衡二叉树 AVL 左右高差绝对值 ≤ 1 查找 O(log n) 哈夫曼 / 最优二叉树 权小的离根远 没有度为 1 的结点 ；带权路径 WPL 最小线索二叉树 空指针改成前驱/后继线索 左线索=前驱，右线索=后继 堆 完全二叉树 + 父≤子（小根）或父≥子（大根） 堆排序的底；任意结点都满足堆序
哈夫曼构造：每次挑权最小的两棵合并，新树权=两者之和，再扔回堆里。所以没有度为 1 的结点 ；n0=n2+1 ⇒ 结点总数一定是奇数。权大的叶子离根更近。权相同的两个叶子，因为每次选哪两棵可以有并列，到根的路径长度不一定相同 。
练一练 · 2020下 · 哈夫曼「错误的是」
2020下 Huffman
以下关于 Huffman（哈夫曼）树的叙述中，错误 的是（ ）。
A. 权值越大的叶子离根节点越近B. Huffman（哈夫曼）树中不存在只有一个子树的节点C. Huffman（哈夫曼）树中的节点总数一定为奇数D. 权值相同的节点到树根的路径长度一定相同
答案 D
并列权值时先合并哪两个，树的形状可以不一样，路径长度不必相同。A、B、C 都对：每次并两棵所以没有度 1；n0=n2+1，总数 2n2+1 为奇数。
3.4 森林 ↔ 二叉树
左孩子 = 第一个孩子，右孩子 = 下一个兄弟。反过来：二叉树的右孩子链是森林里的并排各棵树。
🎯 森林里的叶子 = 没有孩子 = 转成二叉树后没有左孩子 （右孩子是兄弟，有没有都行）。空白卷 OCR 写成「森林的叶子节点是」，按高频考法是「转换成二叉树后」。
小例子：森林两棵树，第一棵 A 下面一个孩子 B（B 是叶子），第二棵就一个根 C（也是叶子）。转二叉树：A 的左孩子=B，A 的右孩子=C（各棵树的根是兄弟）。B、C 都没有左孩子；A 有左孩子，它在森林里不是叶子。
森林: A C 二叉树: A
| / \
B B C
练一练 · 2024上 · Q19 森林叶子
2024上 Q19 森林转换
森林的叶子节点是（19）。空白卷 OCR 就是这句，没写「转换成二叉树后」。若按字面，C「度为 0」是叶子的定义；希赛和历年标准问法是「转换成二叉树后没有左孩子」选 A。本页按希赛 / 历年问法标 A，并承认 OCR 缺那半句。
A. 二叉树中没有左孩子的节点B. 二叉树中没有右孩子的节点C. 森林中度为 0 的节点D. 二叉树中度为 1 的节点
答案 A
转换规则：左=长子、右=兄弟。没孩子的叶子转过去就没有左孩子。C 是叶子的定义，循环解释；标准考法要对上「二叉树里哪类结点」。
④ 图
存储 适合 空间 邻接矩阵 稠密图、快速问两点是否相邻 n² 邻接表 稀疏图 n + e
DFS 深度：顺着一条路走到底再回头，用栈 / 递归。邻接矩阵通常按结点编号从小到大挑下一个。BFS 广度：用队列，一层一层。
拓扑排序 （AOV 网）：有向无环 图。反复选入度为 0 的点输出，删它的出边。有环就排不成。用来「课要先修谁」。
关键路径是 AOE 网，算最长路，见 软件工程专题 的 PERT 节，本页不重复。
邻接表里「边结点」无向图每条边会出现两次 （两端各挂一个），所以边结点数一定是偶数。出现奇数个边结点 ⇒ 只能是有向图 。
拓扑序列里 Vi 在 Vj 前面：一定不存在弧 <Vj, Vi> （否则 Vj 必须更前）。不必真有 <Vi, Vj>，两人可以毫无关系。
练一练 · 2022上 · 邻接表奇数条边
2022上 有向图
某图 G 的邻接表中共有奇数个表示边的表节点，则图 G（ ）。
A. 有奇数个顶点B. 有偶数个顶点C. 是无向图D. 是有向图
答案 D
无向图每条边在邻接表出现两次，边结点数必为偶数。奇数 ⇒ 有向。顶点数奇偶推不出来。
练一练 · 2021下 · 拓扑先后
2021下 拓扑排序
对有向图 G 进行拓扑排序得到的拓扑序列中，顶点 Vi 在顶点 Vj 之前，则说明 G 中（ ）。
A. 一定存在有向弧 <Vi, Vj>B. 一定不存在有向弧 <Vj, Vi>C. 必定存在从 Vi 到 Vj 的路径D. 必定存在从 Vj 到 Vi 的路径
答案 B
若存在 <Vj,Vi>，拓扑里 Vj 必须在 Vi 前面，与题干矛盾。A、C 不必：两人可以没关系，只是恰好 Vi 被排在前面。
练一练 · 2024上 · Q20 DFS
2024上 Q20 邻接矩阵 DFS
对下列有向图的邻接矩阵，进行深度遍历的次序是（20）。（∞ 表示没有边。从 v1 出发，下一结点按编号从小到大。）
V1 V2 V3 V4 V5 V6
V1 ∞ 18 3 ∞ ∞ ∞
V2 ∞ ∞ 5 ∞ 4 ∞
V3 ∞ ∞ ∞ ∞ ∞ ∞
V4 ∞ 15 ∞ ∞ ∞ ∞
V5 ∞ ∞ ∞ 12 ∞ ∞
V6 ∞ ∞ ∞ ∞ ∞ ∞
A. v1-v2-v3-v4-v5-v6B. v1-v4-v2-v3-v5-v6C. v1-v2-v3-v5-v4-v6D. v1-v2-v5-v4-v3-v6
答案 C
v1 的出边到 v2、v3，先走编号小的 v2。v2 到 v3、v5，先 v3。v3 没出边，回到 v2 再走 v5。v5 到 v4。v4 的 v2 已访问。最后剩下 v6。顺序 v1-v2-v3-v5-v4-v6。D 是从 v2 先走了 v5，编号顺序不对。
⑤ 查找：二分、BST、哈希
方法 前提 最坏比较次数 顺序查找 随便 n 二分 / 折半 必须有序顺序表 ⌈log2 (n+1)⌉ BST 树形态 平衡 log n；歪成链就是 n 哈希 散列函数 不保证 上限（冲突时可能一串）
二分时每次取中点。题干给一串比较关键字，问「不可能」：中点切完若走了「更大」的一边，后面不能再出现更小的那个。
哈希：装填因子越大越容易撞，即使 ≤ 1/2 也不能避免冲突 。线性探测容易聚集 。链地址同一槽位可以一串同义词，平均查找长度不是 1 。查找时该位置可能是关键字、同义词、甚至非同义词（探测占过）。
练一练 · 2022上 · 哈希
2022上 散列表
以下关于散列表（哈希表）及其查找特点的叙述中，正确的是（ ）。
A. 在散列表中进行查找时，只需要与待查找关键字及其同义词进行比较B. 只要散列表的装填因子不大于 1/2，就能避免冲突C. 用线性探测法解决冲突容易产生聚集问题D. 用链地址法解决冲突可确保平均查找长度为 1
答案 C
线性探测会扎堆。A：探测占位后，该槽位还可能是非同义词。B：因子小只是少撞，避免不了。D：同一条链可以挂多个同义词。
练一练 · 2024上 · Q21 保证 5 次
2024上 Q21 二分
在 29 个元素构成的查找表中查找任意一个元素时，可保证最多与表中 5 个元素进行比较即可确定查找结果，则采用的查找表及查找方法是（21）。
A. 二叉排序树上的查找B. 顺序表上的顺序查找C. 有序顺序表上的二分查找D. 散列表上的哈希查找
答案 C
⌈log2 (29+1)⌉ = ⌈log2 30⌉ = 5，二分最坏刚好 5。「保证」二字：顺序最坏 29；歪 BST 最坏 29；哈希不保证。只能是有序表二分。
练一练 · 2023上 · 二分不可能序列
2023上 折半查找
对某有序表进行折半查找（二分查找）时，进行比较的关键字序列不可能是（ ）。
A. 42, 61, 90, 85, 77B. 42, 90, 85, 61, 77C. 90, 85, 61, 77, 42D. 90, 85, 77, 61, 42
答案 C
比完 61 再比 77，说明要找的数 > 61，已经丢弃了左半。后面不可能再跟 42 比。
⑥ 排序（累计 18，全场最高单点）
稳定 = 关键字相同的两个元素，排完相对位置不变。
算法 平均 最坏 空间 稳定？ 直接插入 n² n² O(1) 稳定 冒泡 n² n² O(1) 稳定 简单选择 n² n² O(1) 不稳定 希尔 看增量 — O(1) 不稳定 快速排序 n log n n²（已有序最惨） O(log n) 不稳定 堆排序 n log n n log n O(1) 不稳定 归并 n log n n log n O(n) 稳定 基数 d(n+r) — O(n+r) 稳定
🎯 稳定四兄弟：插、冒、归、基 。选择、快、堆、希尔都不稳。问「稳定的是」看见冒泡就下手。
简单选择：第 i 趟在 a[i..n] 里找最小的，和 a[i] 对调。走两趟 = 最小的两个已经就位（非降序时在最前面）。
练一练 · 2024上 · Q22 简单选择两趟
2024上 Q22 简单选择
采用简单选择排序算法对序列 (49,38,65,97,76,13,27,49) 进行非降序排列，两趟后的序列为（22）。
A. (13,27,65,97,76,49,38,49)B. (38,49,65,76,13,27,49,97)C. (13,38,65,97,76,49,27,49)D. (38,49,65,13,27,49,76,97)
答案 A
第 1 趟最小 13，和首位 49 对调 → (13,38,65,97,76,49,27,49)。第 2 趟剩下里最小 27，和现在的第二位 38 对调 → (13,27,65,97,76,49,38,49)。C 只走了一趟。
练一练 · 2022上 · 稳定排序
2022上 稳定性
排序算法的稳定性是指将待排序列排序后，能确保排序码中的相对位置保持不变。（ ）是稳定的排序算法。
A. 冒泡排序B. 快速排序C. 堆排序D. 简单选择排序
答案 A
四个里只有冒泡稳定。
⑦ 算法策略与复杂度
策略 人话 题眼 分治 切成独立 的相同小问题，再合并 二分、归并、最大子段和划成两半 动态规划 也切小问题，但小问题互相重叠 ，用表记住 最优子结构 + 重叠子问题 贪心 每步只看眼前最优，选定不改 哈夫曼、找零钱（特定面值）、活动安排 回溯 深度优先试探，走不通就退一步 n 皇后、迷宫、「尝试下一列」 分支限界 广度（或最小耗费）搜解空间，剪掉没希望的枝 「以广度优先的方式搜索解空间」
分治把数组对半切、左右各解再合并跨中点，时间一般是 T(n)=2T(n/2)+O(n)=O(n log n)。最大子段和用这个切法就是 O(n log n)。
练一练 · 2021上 · 分治最大子段和
2021上 分治
最大子段和：在 n 个整数的数组中求元素之和最大的非空连续子数组。求解时将数组分为两个 n/2 的子数组，则最大子段或者在前半段，或者在后半段，或者跨越中间元素，继续划分子问题直至求出。该算法的时间复杂度为（ ）。
A. O(n lg n)B. O(n³)C. O(n² lg n)D. O(n²)
答案 A
二分 log n 层，每层扫一遍合并跨中点 O(n)，总 O(n log n)。
时间复杂度从小到大（n 足够大时）：
O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(n³) < O(2ⁿ) < O(n!)
1000n 仍是 O(n)；n2/3 （三分之二次方）在 log n 和 n 之间，小于线性。卷面写成 n^{2/3}，不是 n²÷3。
练一练 · 2021上 · 动规 / 分支限界
2021上 策略两空
在求解某问题时，经过分析发现该问题具有最优子结构和重叠子问题性质。则适宜采用（ ）算法设计策略得到最优解；若定义问题的解空间，并以广度优先的方式搜索解空间，则采用的是（ ）算法设计策略。
第一空：A. 分治 B. 贪心 C. 动态规划 D. 回溯
答案 C、D
重叠 + 最优子结构 = 动规（不要选分治，分治的子问题独立）。广度搜解空间 = 分支限界；回溯是深度。
练一练 · 2020下 · 复杂度排序
2020下 渐进
根据渐进分析，表达式序列：n⁴， lg n， 2ⁿ， 1000n， n2/3 ， n！ 从低到高排序为（ ）。
A. lg n, 1000n, n2/3 , n⁴, n！, 2ⁿB. n2/3 , 1000n, lg n, n⁴, n！, 2ⁿC. lg n, 1000n, n2/3 , 2ⁿ, n⁴, n！D. lg n, n2/3 , 1000n, n⁴, 2ⁿ, n！
答案 D
n2/3 是「n 的 2/3 次方」，比线性慢、比对数快。顺序：lg n < n2/3 < 1000n < n⁴ < 2ⁿ < n！。若看成 n²÷3 会误选 A——那是另一道数量级。
⑧ 下午试题四：C 填空怎么认策略
下午必答第 4 题：给说明 + C 代码，填 5 个空，再问用了哪种策略。代码不用从零写，对着说明把缺的表达式补上。
说明里出现 策略 代码长什么样 第 i 个皇后放第 i 行，冲突就下一列，超出就回上一个 回溯 递归 + 冲突检查 + 撤销 把数组对半切，解在左或右或跨中点 分治 两步递归 + 合并 dp 表、f[i] 由 f[i−1] 推 动规 数组存中间结果 每次选当前最优（最短边、最早结束） 贪心 排序后扫一遍
🎯 2023 下样题 n 皇后：说明里「冲突则考虑下一列；超出最后一列则重新确定上一个」= 标准回溯。空往往是：列循环、冲突判断、递归下一行、撤销、边界输出。
真题按年索引
2020下 顺序存储 ·
2020下 哈夫曼 ·
2020下 复杂度 ·
2021上 动规 ·
2021上 分治 ·
2021下 两栈/循环队列 ·
2021下 拓扑 ·
2022上 叶子 ·
2022上 有向图 ·
2022上 哈希 ·
2022上 稳定排序 ·
2022下 出栈 ·
2022下 中序 ·
2023上 二分不可能 ·
2024上 链表 ·
数组地址 ·
树叶子 ·
森林叶子 ·
DFS ·
二分 5 次 ·
选择排序两趟
2024 上题干来自空白卷 OCR。Q19 OCR 写成「森林的叶子节点是」，按历年「转换成二叉树后」的标准问法解析。Q20 按编号从小到大取邻接点。
本专题速记总收 删尾必遍历 。无左孩子 。哈夫曼无度 1 结点。BST 中序有序。
↑