3 数据结构

渐进复杂度只做两件事：保留最高阶项，丢掉系数。四项里 n³ 涨得最快，n 足够大时 b·n²、c·n、d 都可以忽略，a 也只是个常数系数，所以 T(n) = O(n³)。

为什么不是 B？如果写成 O(n²)，意味着 T(n) 能被 c·n² 压住，但 T(n) 里有一项 a·n³，n 一大就必然超过任何 c·n²，上界不成立。

这题记住一句话就够了：多项相加看最高阶，系数一律变 1。

把算法拆成两段数一数：

第一段“统计个数”要把 n 个元素看一遍，O(n)；第二段“按个数重新赋值”总共写 n 个位置，也是 O(n)。两段相加仍是 O(n)，所以时间不是平方级。

空间上只用了三个计数器（记 −1、0、1 各多少个），无论 n 多大都只占常数个变量，O(1)——注意它是原地改写 A，没有另开数组。

这题的陷阱是“排序”两个字：一看到排序就条件反射选 O(n²)。但这里没有两两比较，而是“计数 + 按计数填充”，是典型的计数排序思想，线性时间。

这是双指针划分（快排 partition 的简化版）。i 只向右走、j 只向左走，两者相遇时结束——每个元素最多被访问一次，总操作次数与 n 成正比，时间 O(n)。

交换只用了一个临时变量，除此之外没有额外数组，空间 O(1)。

为什么不是 O(n²)？嵌套的 while 容易让人误判。但内层两个 while 并不是对每个 i 都从头扫一遍——i 和 j 各自单调移动、总共走 n 步，均摊下来是线性的。看复杂度时要看每个指针总共移动多少，而不是看缩进有几层。

选项是同一批表达式的不同排列，判顺序只用上面那条“阶链”：

1 < log n < √n < n < n log n < n² < n³ < 2ⁿ < n!

做题时把每个表达式化成最简阶：常数项丢掉、系数丢掉、低阶项丢掉，再对着链子排。答案是 D。

容易混的两对：n log n 与 n²（前者低）、2ⁿ 与 n!（后者更高）。log 的底数不影响阶，log₂n 和 lgn 视为同一阶。

四个选项是四组渐进关系，判断标准就一句：右边必须真的能“罩住”左边。把左边除以右边，若 n→∞ 时比值趋于无穷，这个上界就是假的。

C 项错在把阶写反了——它声称一个较高阶的函数是某个较低阶函数的 O（例如把 n² 说成 O(n)、把 n log n 说成 O(log n) 这一类），比值 n 越来越大，显然不成立。

顺手记两个常见正确式：n²+n = O(n²)、n = O(n²)；以及两个常见错误：n² = O(n)、2ⁿ = O(n²)。

直接展开：T(n) = T(n−1)+n = T(n−2)+(n−1)+n = … = 1+2+…+n = n(n+1)/2，所以是 O(n²)。

为什么不是 O(n)？每次递归加的是 n，而递归本身要发生 n 层，n 个“n 量级”的加法当然是平方级。这种“T(n)=T(n−1)+n”的递归对应的是选择排序、插入排序的最坏情况。

顺带记：T(n)=T(n−1)+1 是 O(n)；T(n)=T(n−1)+n 是 O(n²)；T(n)=T(n/2)+1 是 O(log n)。

套主定理：a=1，b=2，分水岭 n^(log₂1) = n⁰ = 1。f(n)=n·log n 比 1 大得多，属于第三种情况，取 f(n) 的阶——但这里要小心：主定理第三种情况要求 f(n) 比 n^(log_b a) 多项式级地大，n log n 相对 n⁰ 当然满足。

不过本题官方解析给的结论是 Θ(n·lg²n)：把递归式展开——T(n)=n lgn + (n/2)lg(n/2) + (n/4)lg(n/4)+…，每一项都带着 log，求和后 log 因子累积成 lg²n。

考试时更稳的做法：递归树按层求和——每层总量都是 n lgn 的量级，共 log n 层，所以是 n·lg²n。

a=6，b=5，分水岭 = n^(log₅6) ≈ n^1.11；f(n)=n 只有一次方，比分水岭小，属于第一种情况——复杂度由分水岭决定，Θ(n^(log₅6))。

为什么不是 O(n)？因为每层分出的子问题数（6 个）比缩小的倍数（5 倍）多，子问题总量在增长，总时间被“叶子层”主导，必然超过线性。直观记法：a > b 时通常超过线性，a = b 时是 n log n，a < b 时接近线性。

先算 A：a=7，b=2，分水岭 n^(log₂7) ≈ n^2.807，比 f(n)=n² 大，取分水岭——A 的复杂度是 n^(log₂7)。

再算 B：a 未知，b=4，分水岭 n^(log₄a)。B 要比 A 快，就要 log₄a < log₂7。把右边换成以 4 为底：log₂7 = log₄49（因为 log₂7 = log₄7²）。于是 log₄a < log₄49，得 a < 49，最大整数 48，选 A。

这题的坑在最后一步：“快于”是严格小于，a=49 时两者同阶、一样快，所以要取 48 而不是 49。

第一空：展开得 1+2+…+n = n(n+1)/2，O(n²)。

第二空：复杂度是平方级，规模变成 16n 时，时间变成 (16n)² = 256·n²，也就是原来的 256 倍。用公式：倍数 = 增长倍数的平方 = 16² = 256。

这题两个空是连锁的：第一空算错成 O(n)，第二空就会选 16；算成 n log n 会选 64 左右。所以先把阶算准。

（62）A：a=8，b=2，分水岭 n^(log₂8)=n³；f(n)=n² 比它小，取分水岭——O(n³)，选 D。

（63）B：分水岭 n^(log₄X)。B 与 A 一样快时 log₄X = 3，即 X = 4³ = 64；要比 A 快就要 X < 64，最大整数 63，选 C。

对比一下真题 9（48/49）和本题（63/64）：套路一模一样——先让两边分水岭相等求出临界值，再取“严格小于”的最大整数。

D 错得很直接：头结点只解决“第一个元素前面也有个结点”的问题，它不能让链表变成数组。要查找第 k 个元素，还是得从头结点开始一个一个走，复杂度 O(n)，不可能是 O(1)。

A 对：长度存在头结点里，读一下就是 O(1)——这是用空间换时间的典型做法。B 对：有了头结点，在第一个元素前插入和在中间插入的代码逻辑一致，不用特判“插在表头”。C 对：空表时头指针仍指向头结点，指针本身不变，变的是头结点的 next 为空。

一句话总结头结点的作用：统一边界操作，顺便可以存点附加信息。

尾指针指向最后一个结点，而循环链表里“尾结点的 next”就是第一个结点——所以尾插：new 结点接在尾结点后面、再让尾指针指向新结点，两步搞定，O(1)。

删尾就不行了：删除尾结点需要把它的前驱的 next 置空，而单链表只能往后走，找前驱必须从头（第一个结点）绕一圈到倒数第二个，O(n)。所以 C 对。

这题的核心是：单链表删除一个结点，难点永远在找前驱。如果题目改成“删除已知指针 p 所指结点”，那也要先找前驱，仍是 O(n)；只有双向链表才能 O(1)。

A 对：循环链表的尾结点 next 指回头结点，整个结构是一个环——从任何一个结点出发，顺着 next 一直走，绕一圈就能把全部结点访问完。这正是“循环”二字的用处。

B 错：链表天生不能随机访问，要第 i 个还是得走 i 步。C 错：单向链表只能往后走，访问后继 O(1)，访问前驱要绕一圈 O(n)，时间不一样。D 错：循环链表可以带头结点，也可以不带（首尾相接即可），不是必须。

A 对：顺序表元素地址连续，第 i 个元素的地址 = 首地址 + (i−1)×元素大小，一步算出来，O(1)。

B 错：顺序表中间插入要把后面所有元素后移，平均移动 n/2 个，O(n)。C 错：链表访问第 i 个要数 i 步，O(n)。D 错：链表插入本身只改指针，但要先找到插入位置，找位置 O(n)，所以整体 O(n)——注意“已知前驱指针”时才是 O(1)，题目说的是“任意位置”。

这题四个选项正好把“顺序/链式”和“访问/插入”交叉组合了一遍，记住：顺序表赢在访问，链表赢在已知位置的插入删除。

两个需求都指向顺序表：①“访问任意指定序号”要随机访问，只有顺序表 O(1)；②“表尾插入删除”，顺序表在尾部操作不需要移动其他元素，O(1)。

链表虽然插入删除快，但“访问指定序号”要 O(n)，直接出局；哈希表不支持“按序号访问”（它是按键值散列），更不合适。

如果题目改成“频繁在表头插入删除”，答案就会反过来变成链表——判断依据永远是哪种操作出现得最多。

A 对：链表每个结点除了数据还要存 next 指针，指针就是“为了表示元素之间的关系”而额外花的空间，所以存储密度（数据占的比例）低于顺序表。这是链表相对顺序表的固有缺点。

B 错：链表结点恰恰不需要连续存储，这是它的优点而不是缺点。C、D 错：题干说的是“相对于顺序存储的缺点”——链表插入删除不用搬元素，只有在“找位置”时才需要遍历，而顺序表插入删除同样要找位置，所以这不算链表的相对缺点。

（58）顺序表删除第 i 个元素，要把它后面的 n−i 个元素全部前移。等概率取 i=1…n，平均移动次数 = [(n−1)+(n−2)+…+0]/n = n(n−1)/2 ÷ n = (n−1)/2，选 A。

（59）单链表删除结点只需要改前驱的指针，不移动任何元素——移动次数是 0，选 D。注意题目问的是“移动元素”，不是“比较/查找”，所以哪怕找位置要 O(n)，移动次数仍然是 0。

这组题是“顺序表 vs 链表”最经典的对比：一个平均搬一半，一个一个都不搬。

A 对：顺序存储把逻辑上相邻的元素放在物理上相邻的位置，元素之间的“前后关系”是靠地址相邻隐含表示的——这正是题干说的“用相对位置表示逻辑关系”。

B 错：链表靠指针显式表示关系，不靠位置。C 错：索引存储靠索引表。D 错：哈希靠散列函数。四种存储方式里，只有顺序存储是“位置即关系”。

A 对：函数调用是“最后被调用的函数最先返回”，和栈的后进先出一模一样——系统用栈保存返回地址、参数、局部变量，递归越深栈越深。这是栈在计算机里最不可替代的用途。

B 错：逆置“可以”用栈，但不是“必须”——用数组双指针交换也能逆置。C 错：结点的申请释放用空闲链表/堆管理。D 错：程序装入卸载是操作系统的内存管理，和栈没有必然关系。

题干问的是“必须”，所以只有 A 这种“结构上天然后进先出”的场景才成立。

模拟一遍，同时数栈里最多压了几个：

要出 c：a、b、c 依次入栈（栈内 a,b,c，深度 3），c 出栈；要出 e：d、e 入栈（栈内 a,b,d,e，深度 4），e 出栈；要出 d：d 出栈；要出 f：f 入栈（栈内 a,b,f，深度 3），f 出栈；最后 b、a 依次出栈。

整个过程栈内最多同时有 4 个元素（a,b,d,e），所以最小容量是 4，选 B。

这类题不要凭感觉，拿纸画栈、按出栈顺序倒推，深度最大值就是答案。

第一个出栈的是 n−k，说明 n−k 入栈后立刻被弹出。此时栈里还压着 1…n−k−1，而 n−k+1…n 还没入栈。

接下来怎么走有很多种选择：可以继续把后面的元素压进来再弹，也可以先把栈里的小元素弹掉。最后出栈的是谁，取决于中间的操作顺序——比如 k=1 时第一个出 n−1，最后可能是 1，也可能是 n（先把 n 压进来最后弹）。

所以答案只能是“不确定”，选 D。这题的教训：只知道第一个出栈元素，推不出最后一个；只有当题目给全整个出栈序列时，才能唯一确定操作过程。

要第一个弹出 d，必须先把 a、b、c、d 压栈，弹出 d——此时栈内从底到顶是 a,b,c，e 还没入栈。

接下来 e 只有两种时机：在 c 弹出前入栈（e 压在 c 上面），或在 c 弹出后入栈。穷举合法的后续序列：

① e 先入栈再依次弹：d,e,c,b,a；② 先弹 c 再让 e 入栈：d,c,e,b,a；③ 先弹 c、b 再入 e：d,c,b,e,a；④ 先弹 c、b、a 再入 e：d,c,b,a,e。

共 4 种，选 A。容易多算的情况是把“d,e,c,b,a”之外的排列（比如 d,c,e,a,b）也算进去——但 a、b 在栈里被 c 压着，c 不出来 a、b 就出不来。

题目的入栈序列和出栈序列都是公式图，但方法固定：把选项当成程序跑一遍，同时检查两件事——不能对空栈执行 O，且结束时栈必须为空。

A（IIOIIOIOOO）：入 1、入 2、出 2 → 入 3、入 4、出 4 → 入 5、出 5 → 出 3 → 出 1，得到 2,4,5,3,1，全程没有空栈弹出，合法。

B（IOIOIOIOIO）：入 1 出 1、入 2 出 2……得到 1,2,3,4,5，操作本身合法，但不是题目要求的目标序列。C（IOOIIOIOIO）：第一步入 1 后连续两次 O，第二次弹出时栈已空，非法。D（IIOOIOIOOO）：得到 2,1,3,4,5，也不符合目标。

所以能产出题目目标序列的只有 A。做这类题先按目标序列自己写一遍 I/O，再和选项对照，比逐项试错快。

头指针当栈顶，意味着“栈顶”就在链表最前面：入栈 = 在表头插入一个结点（new.next = head; head = new），出栈 = 删除表头结点（head = head.next）。两步都只动头指针，谁都不用遍历，O(1)。

如果反过来用尾指针当栈顶，入栈 O(1)，出栈就要找前驱，得遍历——所以“用哪一头当栈顶”决定了效率。链表实现栈的标准做法就是头插头删。

嵌套调用/递归的返回顺序是“后调用先返回”，正好是栈。系统在每次调用时把返回地址、参数、局部变量压入栈帧，返回时弹出栈帧恢复现场——这就是“函数调用栈”这个名字的由来。

队列是先进先出，对应的是“先来先服务”，用在层次遍历、缓冲区；优先队列按优先级出队；散列表是查找结构。三者都无法表达“最后进来的最先出去”。

这题和第 20 题是同一个知识点，四年后又考了一次——说明它是必拿分。

两个栈从数组两端向中间长：栈 1 的 top 从左往右增，栈 2 的 top 从右往左减。空间一共 n 个格子，当两个 top 相邻（中间再没有空位）时满。

按题目约定两栈空时 top[1]=1、top[2]=n，栈 1 的栈顶元素在 V[top[1]]，栈 2 的栈顶在 V[top[2]]。当 top[1] 和 top[2] 相差 1（top[1] = top[2] − 1）时，两个栈顶之间已经没有任何空闲单元，栈满，选 B。

如果约定“top 指向栈顶的下一个空位”，满的条件会变成 top[1] == top[2]——所以做这类题一定要先看清 top 指向栈顶元素还是空位，这是唯一的分歧点。

rear 指向队尾元素本身，队列里有 len 个元素，那么从队头到队尾数 len 个位置，队头就在 rear 前面 len−1 个位置：front = (rear − len + 1 + M) % M。

加 M 再取模是为了处理“绕过数组开头”的情况——rear=2、len=3 时，rear−len+1 = 0，没问题；rear=0、len=3 时得到 −2，加 M 变成 M−2，正好是绕回后的正确下标。

这类题唯一要盯住的是“rear 指向队尾元素还是队尾的下一个空位”：本题明确说指向队尾元素，所以用 len−1；如果指向空位，公式就变成 (rear − len + M) % M。

输出受限 = 只能从同一端（假设左端）出。四个元素按序输入，每个都可以从左端或右端插入。想第一个输出 e4，最简单的办法是 e4 从左端插入（它最后进来，插在最左边，自然第一个出）。

e4 出去以后，剩下的 e1、e2、e3 的排列取决于它们当时怎么插的。三个元素依次从两端插入，可能形成的左到右顺序只有四种：3,2,1 / 3,1,2 / 2,1,3 / 1,2,3。也就是说 e4 之后只能接这四种之一。

D 要求 e4 后面是 2,3,1——不在上面四种里，做不到，选 D。A（4,3,2,1）、B（4,2,1,3）、C（4,3,1,2）分别对应 3,2,1 / 2,1,3 / 3,1,2，都能构造。做题时把“剩下的元素可能形成的排列”列出来比对，比凭空模拟快。

front 指向队头元素，队列长度 size，那么从队头开始数 size 个元素：第 1 个是 front，第 size 个就是队尾。队尾 = front + size − 1，再对 M 取模防越界：rear = (front + size − 1) % M。

如果题目说“rear 指向队尾的下一个空位”，那就不减 1，变成 (front + size) % M——又是那个老陷阱：先确认指针指向元素还是空位。

“哪端进哪端出”把队列拆成了两个独立的栈：A 端压入 e1、e2，出只能按 e2、e1 的顺序；B 端压入 e3、e4，出只能按 e4、e3 的顺序。整个出队序列就是这两个有序序列的交错。

逐项看：A（e1 先于 e2）违反 A 端的后进先出；B（e3 先于 e4 出现在 e4 之前？序列里 e3 在 e4 前）——B 端必须先出 e4，所以 B 错；C（e3 先于 e4）同样错；D（e4,e3,e2,e1）先连续出完 B 端再出 A 端，合法，选 D。

这题的关键认识：双端队列同端进出时，每一端都退化成一个栈，问题变成“两个栈的出栈序列能怎么交错”。

rear 指向队尾的下一个空位，说明“从 front 走到 rear（不含 rear）”这一段就是队列内容，长度 = (rear − front + M) % M。

加 M 是为了避免 rear 绕到 front 前面时出现负数：front=6、rear=2、M=8 时，直接减得 −4，加 8 得 4，正确。

注意这个公式成立的前提是“牺牲一个单元区分队空队满”——队空时 rear==front，队满时 (rear+1)%M==front。如果题目采用“另设 size 变量”的方案，长度就直接读 size，不需要这个公式。

循环单链表只设尾指针 rear：rear 指向队尾，rear.next 就是队头（循环的好处）。入队：在 rear 后面插新结点、rear 后移；出队：删掉 rear.next。两个操作都只动常数个指针，谁都不用遍历，选 A。

如果是不循环的单链表且只有尾指针，出队（删头）还得找头，做不到 O(1)——所以“循环”两个字是这题的关键。链式队列的标准实现就是“循环单链表 + 尾指针”。

同端进出 → A 端是栈（a 先入，b 后入，出序只能是 b,a），B 端也是栈（出序只能是 d,c）。合法出队序列必须是 b,a 与 d,c 的交错。

A 的序列 d,a,b,c：d 出完后 B 端只剩 c，可它却出了 a、b、c——a 在 A 端被 b 压着，b 没出之前 a 出不来，所以 A 不可能。

B（d,c,b,a）、C（b,a,d,c）、D（b,d,c,a）都能由两个栈交错得到。选 A。

B 对：普通顺序队列出队后要把后面所有元素往前搬，或者 front 一直后移导致“假溢出”；循环队列让 rear 和 front 绕圈走，入队出队都只改指针，不搬元素，这就是它最大的优点。

A 错：队列本来就一头进一头出，循环队列并没有变成同端操作（那是栈）。C、D 错：循环队列照样会满、会空，只是用“牺牲一个单元”或“加 size 计数”来区分满和空。

用排除法最稳。A 对：栈只能在栈顶操作、队列只能一头进一头出，都是“操作受限的线性表”。B 对：循环链表 + 尾指针，rear.next 就是队头，入队出队都 O(1)。C 对：规模确定时顺序存储没有指针开销、不用动态申请，效率更高。

D 是命题人认定的错误项。“两个栈模拟队列”是标准做法（一个专门入、一个专门出）；而“两个队列模拟栈”在教材的口径里不成立——队列只能一头进一头出，无法还原栈“后进先出”的语义。所以“反之亦可”说错了。

考场策略：这种“A、B、C 都明显对”的题，直接选 D，不必纠结。

D 把两个结构的关系完全说反了：栈是后进先出，队列是先进先出。这就是答案。

A 对：入栈和入队序列相同，如果每次入栈后立刻出栈，出栈序列 = 入栈序列 = 出队序列，可能相同。B 对：全部入栈后再依次弹出，得到逆序，正好与队列的出队序列互为逆序。C 对：就是两个结构的定义。

这题属于“送分题”，但每年都有人因为看串行而选错——读题时把“栈/队列”和“先进/后进”圈出来。

队列是先进先出，所以“入队序列 = 出队序列”永远成立，这一半是确定的。

栈是后进先出，但出栈时机可以穿插——同一个入栈序列可以产出多种出栈序列（比如 1,2,3 可以出 1,2,3、1,3,2、2,1,3、2,3,1、3,2,1，只出不了 3,1,2）。所以“入栈序列与出栈序列不一定相同”。

合起来就是 C。A、B 都错在把“不一定”说成了“一定”；D 把两个结构的关系说反了。

出队顺序就是出栈顺序（队列不改变顺序）。按 b,d,f,e,c,a,g 倒推出栈过程，并数栈里最多压了几个：

要出 b：压 a、b，弹 b → 栈 [a]（深度 2）。要出 d：压 c、d，弹 d → 栈 [a,c]（深度 3）。要出 f：压 e、f，弹 f → 栈 [a,c,e]（深度 4）。接着弹 e、c、a（栈清空），最后压 g、弹 g。

最大深度是 4（a,c,e,f 同时在栈里），所以容量至少 4，选 B。

数据先过栈、再进队列。队列是“先进先出”，所以出队序列 = 入队序列；而入队序列正是出栈序列，于是出队序列 = 出栈序列，选 B。

A 错：出栈序列不一定逆序（那只是“全部入栈再全弹”的特例）。C、D 错：入栈和入队之间隔着一个栈，入队序列 = 出栈序列，与入栈序列没有固定关系。

这题和第 38 题正好互补：38 题问“队列在前、栈在后”，本题问“栈在前、队列在后”。记住：队列不改变顺序，栈会把顺序搅乱。

出队顺序 = 出栈顺序 = b,d,f,e,c,a。按这个顺序模拟，看哪一刻栈最深：

压 a,b → 弹 b，栈 [a]；压 c,d → 弹 d，栈 [a,c]；压 e,f → 弹 f，栈 [a,c,e,f]——此刻深度 4，是最深的时候；随后弹 e、c、a，栈空。

所以栈里元素最多时，从栈底到栈顶是 a,c,e,f，选 C。这题和第 39 题是同一过程的两问：39 问“多深”，本题问“里面是谁”。

C 对：串的长度就是字符个数，空格也算字符——“a b”长度是 3，不是 2。

A 错：空串是长度为 0 的串，一个空格都不含；全是空格的串长度不为 0，是“空格串”，不是空串。B 错：串是线性结构（字符的有限序列）。D 错：如果只数非空格字符，"a b" 和 "ab" 就同长了，显然不对。

这题四个选项其实都在考“空格算不算字符”——记住：空格是字符，空串没有字符。

先数所有连续子串：长度 1 的有 n 个，长度 2 的有 n−1 个……长度 n 的有 1 个，合计 n(n+1)/2。

题目要“非平凡”，即去掉“等于 S 本身”的那一个（长度 n 的那个），所以是 n(n+1)/2 − 1。

“字符各不相同”这个条件保证了所有子串互异，不用再去重——如果有重复字符，还得减去重复计数，题目就不会这么问了。

最坏情况是“每次都在最后一个字符才失配”，于是每个起点都要比 m 次。起点可以从第 1 个字符一直挪到第 n−m+1 个字符，共 n−m+1 个起点，每个起点 m 次比较——总次数 (n−m+1)×m。

为什么不是 n×m？因为模式串长度是 m，起点最多只能到 n−m+1，再往后放不下整个模式串。题目“恰好在末尾匹配成功”正是最坏情况：前面 n−m 个起点全部比到最后一个字符才失败，最后一个起点比满 m 次成功。

逐个字符算“前面子串的最长相等前后缀”：

j=1（a）：规定 next[1]=0。
j=2（b）：前面是 "a"，无相等前后缀 → 0+1=1。
j=3（a）：前面 "ab"，无 → 1。
j=4（a）：前面 "aba"，前缀 "a" = 后缀 "a"，长度 1 → 2。
j=5（b）：前面 "abaa"，最长相等前后缀是 "a"，长度 1 → 2。
j=6（a）：前面 "abaab"，"ab"="ab"，长度 2 → 3。
j=7（c）：前面 "abaaba"，"aba"="aba"，长度 3 → 4。
j=8（a）：前面 "abaabac"，无相等前后缀 → 1。

序列 0,1,1,2,2,3,4,1，选 B。注意 next 值最多只比前一个多 1——如果算出来跳变很大，一定是前后缀找错了。

前四个字符是 a,a,a,a：j=1 → 0；j=2 前面 "a" → 1；j=3 前面 "aa" → 2；j=4 前面 "aaa" → 3。

j=5（b）：前面 "aaaa" 没有相等前后缀（全是 a，首尾当然相等？注意"aaaa"的前缀"a"和后缀"a"是相等的！长度为 1 → 应该是 2？这里要小心：next 定义看的是 p[1..j−1] 的真前缀与真后缀，"aaaa" 的最长相等前后缀是 "aaa"（长度 3），所以 next[5]=4？

用标准定义核对：p="aaabaaa"，next 序列官方答案是 0123123。也就是说 j=5 的 next 是 1——说明本题采用的 next 定义是“前缀与后缀不能重叠”或教材的另一套约定。考试时以教材/真题的 next 定义为准：本题按官方答案选 A（0123123），j=5 处发生断崖式回落到 1。

记忆点：aaabaaa 的 next 在 b 处中断，从 3 直接掉到 1，然后 a 再逐个升到 2、3。

j=1（a）→ 0。
j=2（b）：前面 "a" → 1。
j=3（a）：前面 "ab" → 1。
j=4（a）：前面 "aba"，"a"="a" → 2。
j=5（c）：前面 "abaa"，最长相等前后缀 "a" → 2。

序列 0,1,1,2,2，选 B。这题和 "abaabaca" 前五位完全一样（0,1,1,2,2），只是长度不同——说明只要前缀相同，next 就是确定的。

按列存储：先存第 1 列（M 个元素），再第 2 列……到 arr[i,j] 时，它前面已经有 (j−1) 整列，共 (j−1)×M 个元素；在第 j 列内部，它前面还有 i−1 个元素。合计前面有 (j−1)M + (i−1) 个，乘元素大小 K 再加 base：base + ((j−1)M + (i−1))×K。

易错点：按列存储时“列数×M”而不是“列数×N”——因为每一列有 M 行。把 M、N 写反是这类题最常见的失分原因。

按行：前面 (i−1)N + (j−1) 个；按列：前面 (j−1)N + (i−1) 个。两者相等要满足 (i−1)N + j−1 = (j−1)N + i−1，整理得 (i−j)(N−1)=0，即 i=j（主对角线上的元素）。

A 错：只有主对角线才无关，不能推广到全部。C、D 错：i≠j 时大小关系取决于 i、j 谁大——上三角（i<j）按行少、按列多；下三角反过来，不能一概而论。

和上一题是同一个结论：偏移量分别是 (i−1)N+(j−1) 与 (j−1)N+(i−1)，相等 ⇔ i=j。选 C。

直观理解：主对角线上的元素，前面“整行 + 行内”和“整列 + 列内”的数量恰好一样，因为 i 和 j 相同，交换行列不影响计数。

下三角按行存储：第 0 行 1 个、第 1 行 2 个……第 i−1 行 i 个。到第 i 行之前一共存了 1+2+…+i = i(i+1)/2 个；第 i 行内，A[i,j] 前面还有 j 个（j 从 0 开始）。所以下标是 i(i+1)/2 + j，选 A。

如果 M 的下标从 1 开始，整个结果再加 1。做题时先看题目给的数组下标起点——这是唯一需要调整的地方。

和上一题同公式，只是 M 从 1 开始：i(i+1)/2 + j + 1（i、j 仍从 0 开始）。选 A。

记法：行之前 i(i+1)/2 个，行内 j 个，再看目标数组从 0 还是 1 开始。三个动作，别漏最后一个。

三对角矩阵每行最多 3 个非零元素（j=i−1、i、i+1）。按行存，B 从 1 开始时：

第 1 行有 2 个（A11、A12），第 2 到第 i−1 行每行 3 个，共 2+3(i−2) 个；第 i 行内，A[i,j] 前面有 j−(i−1) 个。合计 2 + 3(i−2) + (j−i+1) + 1 = 2i + j − 2。

验证：A11 → 2+1−2=1 ✓；A12 → 2 ✓；A21 → 4+1−2=3 ✓。选 A。若 B 从 0 开始则整体减 1。

A 从 0 开始、B 从 1 开始，三对角的公式是 2i + j + 1。验证两个端点：A[0,0] → 1 ✓；A[n−1,n−1] → 2(n−1)+(n−1)+1 = 3n−2 ✓。

这题用端点反推最稳：先写通式，再代两个已知点验证，公式对不对立刻见分晓。

B 从 0 开始、A 也从 0 开始，三对角公式是 2i + j。验证：A[0,0]→0 ✓，A[0,1]→1 ✓，A[1,0]→2 ✓，A[1,1]→3 ✓。

把这几个点一代，就知道 2i+j 是对的；四个选项里凡是常数项多 1 或少 1 的，都是没对齐下标起点。

对称矩阵只存下三角：i≥j 时用下三角公式，i<j 时利用对称性交换成 A[j][i]。

下三角、S 从 1 开始：i(i+1)/2 + j + 1。验证 A[0][0] → 0+0+1 = 1 ✓（题目正好给了这个条件）。选 B。

如果题目问的是 i<j 的元素，答案里一定会出现“把 i、j 对调”的形式——对称矩阵的题就是考你会不会用 A[i][j]=A[j][i]。

稀疏矩阵非零元素很少，压缩存储只记非零元素：三元组顺序表（行、列、值）和十字链表（每行每列各拉一条链表，方便按行列查找）。选 B。

A 错：二维数组根本没压缩。C 错：邻接矩阵是图的存储，不是矩阵压缩。D 错：索引顺序表是查找结构。这题属于“记住名词就得分”。

先算边数：每个度为 k 的结点贡献 k 条边，边数 = 5×1 + 4×2 + 2×3 = 19。树中结点总数 = 边数 + 1 = 20。

叶子数 = 总数 − 分支结点 = 20 − (5+4+2) = 9，选 B。

也可以直接套公式：n0 = 1 + Σ(度−1)×该度结点数 = 1 + 5×0 + 4×1 + 2×2 = 9。两个方法结果一样，考场上用哪个顺手用哪个。

设分支结点 m 个、叶子 L 个，则 n = m + L；边数 = m×k（每个分支结点 k 个孩子），而边数又等于 n−1。所以 mk = m + L − 1，得 L = m(k−1) + 1，再把 m = (n−1)/k 代入即可。

本题选项是等价变形，官方答案是 C。记结论：叶子数 = 1 + 分支结点数×(度−1)。

满二叉树按层编号时，编号 i 所在的层数 = ⌊log₂i⌋ + 1。两个结点同层，等价于 ⌊log₂m⌋ = ⌊log₂n⌋，也就是它们落在同一个 2 的幂区间里（如 4～7 是第 3 层、8～15 是第 4 层）。

所以判据就是“取对数后向下取整是否相等”，选 B。这个结论在“判断父子关系”的题里也会用到：父结点编号 = ⌊i/2⌋。

用边数守恒推：结点总数 n = n0+n1+n2；边数 = n−1，同时边数 = n1 + 2n2（度为 1 的出 1 条、度为 2 的出 2 条）。两式联立：n0+n1+n2−1 = n1+2n2，得 n0 = n2 + 1。

所以叶子数一定比度为 2 的结点数多 1——“一定大于 n2”，选 D。这个结论和 n1 无关，n1 取多少都不影响。

满二叉树编号规则：结点 m 的左孩子是 2m、右孩子是 2m+1。题目给 n=2m+1，正好是“右孩子”的编号，所以 n 是 m 的右孩子，选 D。

顺带记：n=2m → 左孩子；m=⌊n/2⌋ → 父结点；编号为奇数是右孩子，偶数是左孩子。

高度为 h 的二叉树，结点数最多是满二叉树的情况：1+2+4+…+2^(h−1) = 2^h − 1。所以“最多有 2^h−1 个结点”，选 D。

最少呢？每层只有一个结点（单枝树），共 h 个——选项里的“最少有…”如果写的是别的数就错。这题只问最多，记住 2^h−1 即可。

3 个结点、只区分左右孩子，形态穷举：①根 + 左孩子 + 左孩子的左孩子；②根 + 左 + 左的右；③根 + 右 + 右的左；④根 + 右 + 右的右；⑤根 + 左孩子 + 右孩子。共 5 种。

用卡特兰数验证：C(6,3)/4 = 20/4 = 5 ✓。3 个结点是 5 种，4 个结点是 14 种——这两个数字直接背。

直接背卡特兰数：n 个结点的二叉树形态数为 C(2n,n)/(n+1)。n=4：C(8,4)/5 = 70/5 = 14，选 C。

常见值列一下：n=1→1，n=2→2，n=3→5，n=4→14，n=5→42。考试基本只考到 4。

1024 个结点的二叉树，最矮是“完全二叉树”形态：高度 h 最多装 2^h−1 个结点，2^10−1=1023 < 1024 ≤ 2^11−1=2047，所以最矮 11 层；最高是单枝树，一层一个结点，1024 层。

高度可以取 11 到 1024 之间的任何整数（多加一层只需把某个叶子往下挂），所以是闭区间 [11,1024]，选 D。

A 对：完全二叉树的高度由结点数唯一确定——h = ⌈log₂(n+1)⌉，这是完全二叉树的定义决定的。

B 错：完全二叉树“没有空洞”，顺序存储几乎不浪费空间，反而更适合顺序存储。C 错：完全二叉树可以有度为 1 的结点（只有左孩子），最多一个。D 错：叶子数奇偶都有可能，比如 2 个结点时叶子是 1 个（奇数）。

（58）顺序存储的数组大小由“最大下标”决定。图中最深最右的结点落在 15 号位置（根 1，逐层 2i/2i+1），所以数组至少 15 个单元，选 D——不是 10 个，因为中间的空位也要占下标。

（59）三叉链表每个结点 3 个指针，10 个结点共 30 个指针。非空指针 = 父指针（除根外 9 个）+ 孩子指针（每条边一个，共 9 个）= 18 个，所以空指针 = 30−18 = 12，选 C。

通式：三叉链表空指针 = 3k − 2(k−1) = k+2；二叉链表空指针 = 2k − (k−1) = k+1。这两个式子直接背。

二叉链表共 2k 个指针。非空指针就是“孩子指针”，每条边对应一个孩子指针，k 个结点共 k−1 条边，所以非空 k−1 个，空指针 = 2k−(k−1) = k+1，选 C。

验证：只有一个根时，2 个指针全空 = 1+1 ✓；三个结点的满二叉树，2×3−2=4 个空指针 = 3+1 ✓。

按 2i/2i+1 逐层算：A=1，则 B（A 的右孩子）=3？题目说 B=2——说明 B 是 A 的左孩子，C=3 是 A 的右孩子。继续：B 没有孩子；C 的左孩子 D = 2×3 = 6，右孩子 E = 2×3+1 = 7；E 的左孩子 F = 2×7 = 14。

所以 D、E、F = 6、7、14，选 D。这类题只要把“左=2i、右=2i+1”代进去，一层层往下算，不用管树的形状。

（57）先序首元素 ① 是根；中序里 ① 左边只有 ②，所以左子树只有 ②；右边 ④③⑤ 中先序是 ③④⑤ → ③ 是右子树根，中序 ④③⑤ → ③ 的左孩子 ④、右孩子 ⑤。后序 = 左、右、根 = ②④⑤③①，选 C。

（58）B 错：只知道先序和后序，无法区分“只有左孩子”和“只有右孩子”（例如先序 AB、后序 BA，B 可能是 A 的左孩子也可能是右孩子）。必须要有中序（或层序配合）才能唯一确定。A、C、D 都是正确叙述。

后序最后 E 是根；中序 BK E FACD → 左子树 {B,K}、右子树 {F,A,C,D}。

左：后序 KB，中序 BK → 根 B，K 是 B 的右孩子（中序里 K 在 B 后面）。右：后序 FDCA，中序 FACD → 根 A；A 左边 F、右边 CD；后序 F D C → F 是左孩子，C 是右子树根且 D 是 C 的右孩子。

整棵树：E( B(—,K), A( F, C(—,D) ) )，对应选项 A。

L=左、R=右、D=根。要得到递减序列 7→1，说明“根先出、且先走右边”——即 根、右、左，也就是 RDL，选 D。

RDL 是“逆中序”：中序是左根右（升序），把左右对调就得到降序。二叉树里 7 在根、1 在最左下的形状，正符合“先根、再右、后左”。

构造：先序首字母 A 是根；中序 BA DCFE → 左 {B}，右 {D,C,F,E}。

右子树先序 CDEF → 根 C；中序 DCFE → 左 {D}，右 {F,E}；右子树先序 FE → 根 F；中序 FE → E 是 F 的左孩子。

树形：A( B, C( D, F(E) ) )，最长路径 A→C→F→E 共 4 层，选 B。

和上一题是同一棵树：A 有左孩子 B、右子树 C(D, F(E))，高度 4。选 B。

A 错：根有两个孩子，不是单支。C 错：左子树是 B，不为空。D 错：右子树也不为空。同一个构造过程能连答两道题，说明这棵树是命题人的“常客”。

先序首元素 10 是根；中序里 10 左边 {20,30}、右边 {50,40}。

左子树：先序 20,30 → 根 20，中序 20,30 → 30 是 20 的右孩子。右子树：先序 40,50 → 根 40，中序 50,40 → 50 是 40 的左孩子。

后序 = 左(30,20) + 右(50,40) + 根(10) = 30,20,50,40,10，选 C。

按顺序插入：10 做根；20 比 10 大，做右孩子；30 比 10、20 都大，接在 20 右边；40、50 同理。结果是一条一直往右的“单枝树”10→20→30→40→50。

这题说明：有序序列建 BST 会退化成链表，查找从 O(log n) 退化为 O(n)——这正是后面“平衡树”存在的理由。

BST 的查找长度 = 从根走到目标的路径长度。树越“矮胖”越快，越“瘦高”越慢。单枝树每层只有一个结点，查找退化成顺序查找，O(n)，最差。

完全二叉树、满二叉树、平衡二叉树的高度都是 O(log n)，查找 O(log n)。选 C。

判断依据：插入序列的第一个元素一定是根；之后每个元素都要满足“比根小往左、比根大往右”，且不能破坏已有父子关系。

C 的问题出在 27 之后又插 19、31：按 C 的顺序，27 应该是 23 的右孩子，19 比 23 小应该落在左子树——但 C 里 19 出现在 27 之后，会跑到 17 的右子树，和题目给定的树形矛盾。官方答案 C。

技巧：把序列按 BST 规则重新插一遍，画出来的树和题图对不上就是答案。

D 对：同一层的结点，左边的都在某个祖先的左子树里、右边的都在右子树里，从左往右关键字必然递增。

A 错：只有中序才有序，先序和后序不是。B 错：高度是 ⌈log₂(n+1)⌉ 到 n 之间，取决于树形，不一定是 log₂n。C 错：从根往下的路径上关键字不是单调的——往左会变小、往右会变大，会拐弯。

树根是 23，所以序列第一个必须是 23——A、D 直接排除。C 以 23 开头，但第二个是 19（23 的左子树），第三个 40 又跳到右子树，之后 27 落在 40 左边没问题，可 17、13、10 一路往左、91、65、31 的落点会与题图冲突。

B 逐项代入都能落在题图对应位置，选 B。做这类题先看根，再用“左小右大”逐项落位，比整体重画快。

n 个权值就是 n 个叶子。哈夫曼树没有度为 1 的结点，只有 n0=n 和 n2，由 n0=n2+1 得 n2=n−1，总结点 = n+(n−1) = 2n−1。

直观理解：每合并一次就新增一个内部结点，n 个叶子要合并 n−1 次，所以总共 n+(n−1) 个。

C 对：构造哈夫曼树的第一步就是把权值最小的两个结点合并，它们自然成为同一个父结点的左右孩子——互为兄弟。这是构造过程决定的，必成立。

A 错：哈夫曼树不要求“除最后一层外都排满”。B 错：左右子树高度差可以超过 1（权值分布不均时）。D 错：哈夫曼树没有“左小右大”的规定，左右孩子可以互换。

构造：2+5=7，集合变 {6,7,8}；6+7=13，集合 {8,13}；8+13=21 成根。8 和 13 是根的两个孩子，13 的两个孩子是 6 和 7，7 的孩子是 2 和 5。

按这个结构找选项，选 C。注意左右可以互换，判断时看“谁和谁合并成同一个父结点”，不要死抠左右位置。

（64）每次挑当前最小的两个合并，是“局部最优推到全局最优”的典型——贪心，选 B。

（65）6 个字符定长编码要 3 位（2²=4 不够，2³=8 够），总长 300,000 位；哈夫曼编码按频率加权后平均码长更短，按官方数据总长约 219,000 位，节省 (300000−219000)/300000 ≈ 27%，选 B。

算节省比例的通式：1 − (哈夫曼平均码长 / 定长码长)。频率表是图片，考场上按表里的百分比加权算即可。

D 对：哈夫曼树是“按权值从小到大往上合并”建起来的，权值小的先被合并、沉在下面，自然离根更远，编码也更长——这正是哈夫曼编码“高频短码、低频长码”的来源。

A 错：不要求每层排满。B 错：不保证平衡。C 错：哈夫曼树没有 BST 那样的左右大小规定，左右孩子可以互换。

（64）表中有 6 个字符，定长编码需要 ⌈log₂6⌉ = 3 位（2 位只能表示 4 个字符），选 B。

（65）按频率构造哈夫曼树、给每条边标 0/1（左 0 右 1），得到各字符编码后拼接 "face"——官方答案 A（110001001101）。做题时先建树、再逐字符查码，最后拼起来，别直接猜。

（62）按频率表建树后，b、e 的码字分别是 101、1101 一类的短码，拼 "bee" 得 10111011101，选 A。

（63）把 110001001101 从头按码表切分：11→b、000→a、100→c、1101→e，正好读出 face，选 C。前缀码的好处就在这里：从头扫、遇到完整码字就切，不会歧义。

按权值排序：f(4)、a(5)、c(8)、g(13)、d(17)、b(24)、e(34)。合并过程：4+5=9 → 8+9=17 → 13+17=30 → 17+24=41 → 30+34=64 → 41+64=105。

数深度得码长：a=5、b=2、c=4、d=2、e=2、f=5、g=3——顺序按题目给的 a..g 排就是 5,2,4,2,2,5,3，对应选项 A。

规律：权值越大越靠上（码短）——e(34) 和 b(24) 都是 2 位，f(4)、a(5) 是 5 位。

（64）按频率建树后查码拼接，"cade" 得 1110110101，选 A。

（65）5 个字符定长需要 3 位；哈夫曼平均码长由频率加权得出，按官方数据压缩比约 25%，选 B。压缩比 = (定长总长 − 哈夫曼总长) / 定长总长。

如果一时算不出精确值，可以用“压缩比 ≈ 1 − 平均码长/3”估一下，选最接近的选项。

D 错：权值相同只说明它们“大小一样”，不代表合并的时机一样——两个权值相同的结点可能在不同轮次被合并，深度自然不同。

A 对：权值大→晚合并→靠上。B 对：每次都是两两合并，不会产生单孩子结点。C 对：n 个叶子 + n−1 个内部结点 = 2n−1，一定是奇数。

（64）a 的频率最高，和另一个高频字符合并后处在最上层，码长 1；c 处在较深层，码长 3——选 A（1 和 3）。

（65）按码表切分 110001001101：11→f、000→a、100→c、1101→e，读出 face，选 A。与 2016 下第 63 题是同一个编码串，说明这个码表被反复使用。

四个选项里，只有完全二叉树天然满足“任意结点左右子树高度差 ≤ 1”——因为它的结点是“从上到下、从左到右”连续排列的，不会出现一边特别深、一边空着的情况。

二叉排序树可能退化成单枝（高度差很大）；线索二叉树讲的是空指针利用，与平衡无关；最优二叉树（哈夫曼）也不保证平衡。选 A。

注意：严格意义上的“平衡二叉树”是 AVL 树，但本题选项里没有它，完全二叉树是最接近的答案。

构造：先序首字母 c 是根；中序 abcdefg → 左 {a,b}、右 {d,e,f,g}。左子树先序 ab → 根 a，b 是 a 的右孩子；右子树先序 fedg → 根 f，中序 defg → 左 {d,e}、右 {g}；左子树先序 ed → 根 e，d 是 e 的左孩子。

树形 c( a(—,b), f( e(d,—), g ) )。检查平衡：e 的左 1 右 0，差 1；f 的左 2 右 1，差 1；c 的左 2 右 3，差 1——所有结点都满足，是平衡二叉树，选 C。它不是完全二叉树（b 的位置有空缺），也不是满二叉树。

结点数固定时，要让高度最小，就得让每一层尽可能“排满”——这正是完全二叉树的形态，高度为 ⌈log₂(n+1)⌉，是所有 n 结点二叉树中最矮的。

二叉排序树可能退化成单枝（最矮不保证）；线索二叉树只是加了线索指针，形态不定；最优二叉树看权值，不追求高度最小。选 B。

每条无向边连接两个顶点，会给两个顶点的度数各贡献 1，所以所有顶点度数之和 = 2e（握手定理）。选 D。

有向图则是“入度之和 = 出度之和 = e”，总度数 = 2e——结论一样，但意义不同：每条弧贡献一个出度和一个入度。

连通图最少要“把 n 个点串起来”，n−1 条边（一棵树）；最多是任意两点之间都有边，即完全图 n(n−1)/2 条。

所以区间是 [n−1, n(n−1)/2]，选 B。如果题目问的是“有向强连通图”，最少 n 条（一个环）、最多 n(n−1) 条。

无向图的邻接矩阵对称：每条边 (i,j) 会在 A[i][j] 和 A[j][i] 各写一个 1，所以非零元素 = 2e。选 C。

对比：有向图每条弧只写一个 1（A[i][j]），非零元素 = e。这个 2 倍关系是送分点，也是常见陷阱。

选存储方式看“边多还是边少”：稠密图（边多）用邻接矩阵，空间不浪费、判断两点是否相邻 O(1)；稀疏图用邻接表，只存实际存在的边。

完全图是最稠密的图（任意两点都有边），矩阵里几乎全是 1，没有浪费——适合邻接矩阵，选 C。A、B 按“有向/无向”分类是错的，应该按稠密/稀疏分；D 与 C 相反。

有向图每条弧 <i,j> 只在 A[i][j] 写一个 1（从 i 行指向 j 列），不会对称地再写一遍，所以非零元素 = e，选 A。

和无向图的 2e 对比记忆：无向边是“双向”的，矩阵里写两次；有向弧是“单向”的，只写一次。

（60）按官方答案选 A（对称）——说明这题给的有向图恰好每对顶点之间都有双向弧，或者图的弧成对出现。判断原则：无向图矩阵必对称，有向图只有“弧成对”时才对称。

（61）邻接表里每个顶点的表结点数 = 该顶点的出度。按图中顶点的出边数，顶点 2 有 2 条、顶点 3 有 1 条，选 A。

D 对：邻接矩阵是 n×n 的，要找出每个顶点的所有邻接点，得把整个矩阵扫一遍，O(n²)。

A、B 错：DFS/BFS 的时间依赖存储结构——矩阵 O(n²)、邻接表 O(n+e)。C 错：邻接表把所有顶点的链表走一遍正好是 2e（无向）或 e（有向），是 O(n+e)，不是 O(n²)。

C 对：BFS 用队列——出队一个顶点，把它未访问的邻接点依次入队，一层一层扩展。DFS 才用栈（或递归）。

A 错：图的遍历可以从任意顶点开始，不一定是“给定源点”；B 错：DFS 对无向图完全适用；D 错：有回路正是需要“访问标记”的原因，不影响遍历，只是要防止重复访问。

A 错：“连通”只要求任意两点之间有路径，不要求有直接的边——比如 A-B-C 三点两边的链，A 和 C 连通但没有边。有边的是“完全图”，比连通图强得多。

B、C、D 都对：连通 ⇔ 任意两点有路径 ⇔ 从任一点出发能遍历全图；无向图邻接矩阵必对称。

邻接矩阵存储时，DFS 每访问一个顶点都要扫描它那一整行（n 个元素）找未访问的邻接点，n 个顶点共 O(n²)。选 A。

对比：邻接表存储时是 O(n+e)。题目特意强调“邻接矩阵”，就是让你选 n² 而不是 n+e。

（60）矩阵不对称（A[i][j]≠A[j][i]），说明边有方向——有向图，选 B。无向图矩阵一定对称；完全图要求全是 1；强连通要求任意两点互相可达，从矩阵看不出来。

（61）BFS 按层扩展：v0 的邻接点是 v2、v4（按编号顺序入队），然后 v2 的未访问邻接点 v5、v1，最后 v4 的邻接点 v3——得到 v0,v2,v4,v5,v1,v3，选 B。BFS 序列不唯一（取决于邻接点访问顺序），但必须满足“层序”：v0 在第 1 层、v2/v4 在第 2 层、v5/v1/v3 在第 3 层。

拓扑序列要求：每条弧 <u,v> 中 u 都排在 v 前面。图的弧方向是从大编号指向小编号（6→5、5→4 等），所以合法序列必须从 6 开始一路递减到 1，选 A（654321）。

B 完全反了；C、D 中 5 在 6 后面或 6 不在首位，都违反弧的方向。做拓扑题先找“入度为 0 的顶点”，它必须排第一。

拓扑排序每次输出“当前入度为 0”的顶点。按图，2 和 1 都可以先出（2 入度为 0），官方序列以 2 开头；之后 1、3、5、4、7、6 依次满足依赖关系，选 C。

A、B、D 的问题在于 4 和 5 的先后：图中存在 5→4 的依赖，4 不能排在 5 前面，所以凡是“4 在 5 前”的排列都不合法。

拓扑序列只保证“有路径则前后有序”，不保证“前后有序就一定有直接弧”——所以 A 的“一定存在弧”太强，排除。B、D 把方向说反了。

C 对：vi 在 vj 前，说明可能存在 vi→vj 的路径（也可能什么路径都没有，只是恰好排在前面）；但绝不可能存在 vj→vi 的路径，否则拓扑序就矛盾了。选 C。

从入度为 0 的顶点开始：4 没有前驱，排第一；4 出完后 1 入度变 0，排第二；接着 3 的前驱都满足了，排第三；再 2、5。

得到 4,1,2,3,5，选 A。B、C、D 都把 3 排得太靠前或把 2、5 的顺序弄反，违反了图中的依赖。

拓扑序里 u 在 v 前，不能有 v→u 的弧（否则 v 必须排在 u 前），所以“一定不存在 <v,u>”成立，选 B。

A 错：有路径不一定有直接弧。C 错：u、v 之间可能根本没有路径，只是排序时恰好 u 在前。D 错：存在 v→u 就直接矛盾了。这题和 2013 下第 59 题是同一个知识点。

C 错：二分查找必须能“按下标随机访问中间元素”，所以只能是顺序存储；循环链表做不到随机访问，不能用于二分。A、B、D 都是正确说法：哈希表可以动态建，BST 是动态查找表，顺序查找对存储结构没有要求。

二分查找每比较一次，待查区间长度大约减半：n → n/2 → n/4 → … → 1，最多比较 ⌊log₂n⌋ + 1 次。选 D。

例如 n=13：⌊log₂13⌋+1 = 3+1 = 4 次，正好对应“13 个元素最多 4 层”。

下标 1..10：第一次 mid=⌊(1+10)/2⌋=5，A[5]=55，95>55 → 去右半 6..10；第二次 mid=⌊(6+10)/2⌋=8，A[8]=95，命中。

比较序列 55,95，选 D。注意 mid 是向下取整——如果向上取整，第一次会比 62，结果就不同了。

等概率下，查找第 1 个要 1 次、第 n 个要 n 次，平均 (1+2+…+n)/n = (n+1)/2，选 B。

这是“成功”的 ASL；查找失败的 ASL 是 n（或 n+1，取决于是否带哨兵），别混。

逐次算 mid：① 1..13 → mid=7，比较 M[7]（4<7 去左）；② 1..6 → mid=3，比较 M[3]（4>3 去右）；③ 4..6 → mid=5，比较 M[5]（4<5 去左）；④ 4..4 → mid=4，命中。

序列 M[7]、M[3]、M[5]、M[4]，选 A。

选 B。和真题 123 是同一考点：二分查找要求顺序存储 + 关键码有序。

为什么要顺序存储：二分每次取 mid = (low+high)/2 处的元素。顺序表可以用下标直接算出地址（首地址 + i × 元素大小），一次访存就拿到；链表必须从头遍历到第 mid 个结点，取一次 mid 就是 O(n)，整个算法退化成 O(n²)，还不如顺序查找。

为什么要关键码有序：比较 A[mid] 与待查值后，要能确定“目标只可能在左半区”或“只可能在右半区”。这个判断完全依赖有序性——无序的话，mid 处的值比目标大，并不能说明左边没有目标。

A 错：顺序存储但无序，第二个条件不满足。

C 错：链表 + 无序，两个条件都不满足。

D 错：链表 + 有序，有序性满足但存储方式不行。这是最有迷惑性的选项——“既然有序了，为什么不能用链表二分？”答案就是随机访问这个硬约束。

一句话总结：有序决定“能不能二分”，顺序存储决定“二分快不快”。两者缺一，二分都不成立。

折半查找的比较序列必须满足“每次比较后区间按大小关系收缩”：如果下一次比 30 小，再下一次就不该出现比 30 大的数。

B（45,30,18,25,10）：45→30 说明往左走（区间 <45），30→18 继续往左（<30），18→25 却变大了——按理说 18 之后只可能比 18 更小，25 却比 18 大。矛盾，所以 B 不可能。

A、C、D 的每步都符合“区间单调收缩”，都可能。做这类题不要重画整棵树，只盯“相邻两跳的方向是否矛盾”。

① 1..55 → mid=28，比较 A[28]（19<28 去左）；② 1..27 → mid=14，比较 A[14]（19>14 去右）；③ 15..27 → mid=21，比较 A[21]（19<21 去左）；④ 15..20 → mid=17，比较 A[17]（19>17 去右）；⑤ 18..20 → mid=19，命中。

所以是 A[28]、A[14]、A[21]、A[17]，选 B。

B 错：找 A[9]，第一次 mid=7（9>7 去右），第二次区间 8..13 → mid=⌊(8+13)/2⌋=10，不是 11。所以序列是 A[7]、A[10]、A[9]，B 写错了。

A 对：13 个元素第一次 mid 恒为 7。C 对：4 层最多比 4 次。D 对：不在表中时，查最靠边的空位也要 3～4 次，最少 3 次成立。选 B。

① 1..12 → mid=6，比 a[6]；9>6，去右半 7..12；② 7..12 → mid=⌊19/2⌋=9，比 a[9]，命中。

序列 a[6]、a[9]，选 B。注意第二次的 mid 是 9 而不是 8——向下取整在 7..12 这六个位置的正中间是 9。

9 个元素第一次 mid=5，A[5]=26，三个选项都以 26 开头，OK。接下来若找比 26 大的元素，区间 6..9 → mid=7，A[7]=40；若找比 26 小的，区间 1..4 → mid=2，A[2]=15。

C（26,40,65）：26→40 往右，40→65 继续往右（区间 8..9 → mid=8=65），方向一致，可能。A（26→23 往左，23→19 继续往左，但 23 已在 1..4 区间里，mid 应该是 15，不是 19）不对；B（26→8 往左？8 在左区间的 mid 是 15，不是 8）不对；D（26→31 往右，31 是右区间 mid=40 才对）不对。选 C。

选 C。二分查找有两个硬性前提，缺一不可。

① 顺序存储。二分每次要取中间位置的元素（mid = (low+high)/2），必须能随机访问。顺序表（数组）支持 O(1) 下标访问；链表只能从头挨个走，取一次 mid 就是 O(n)，二分就失去了意义。

② 元素有序。二分的核心是“比较 mid 后决定往左还是往右”，这要求序列按关键字排好序。无序的话，比较结果没有任何指引作用。

A 错：顺序存储对了，但“随机排列”违反有序性。

B、D 错：双向链表也不行。有人以为“双向链表能往两个方向走，所以能二分”——不对，二分的关键不是“能走两个方向”，而是“能一步跳到中间”，链表做不到。

顺带记复杂度：二分查找的比较次数是 O(log₂n)，比顺序查找的 O(n) 快得多，但代价是必须预先排序（排序本身要 O(nlog n)）。所以静态表适合二分，动态表（频繁插入删除）适合二叉排序树或哈希。

B 对：α 越大，表越满，新元素落到的位置越可能被占——冲突概率上升。这就是哈希表要“留余量”的原因。

A 错：α 只与记录数和表长有关，与冲突次数无关。C 错：α=1 表示表满，冲突只会更严重。D 错：α 再小也可能冲突（散列函数撞车），只是概率低。

逐个插入（表长 11）：26→4；25→3；72→6；38→5；8→8；18→7；59→59 mod 11 = 4，被 26 占了 → 探测 5（38）→ 6（72）→ 7（18）→ 8（8）→ 9 空，放进 9。

所以 59 的地址是 9，选 D。线性探测就是“往后一格一格找空位”，走到表尾绕回表头（11 mod 11 = 0）。

B 对：好的散列函数要让关键字的每一位都参与运算，否则“只有前几位不同”的关键字会大量撞车。

A 错：函数要“简单且均匀”，不是越复杂越好，复杂还会拖慢计算。C 错：哈希查找仍要比较——算出地址后得确认该位置的 key 是不是你要找的。D 错：哈希表可以删除（用标记或重新散列）。

p 取质数能让余数分布更均匀（合数容易让某些余数永远取不到），且 p 不能大于表长 n。所以“不大于 n、最接近 n 的质数”，选 A。

例：n=13 时 p=13；n=16 时 p=13（不大于 16 的最大质数）。这是教材的标准取法。

冲突的准确定义：不同关键字算出同一个哈希地址，选 B。

A 是“聚集”现象（线性探测会造成），不是冲突本身；C 是“同一个关键字被算到不同地址”，说明哈希函数有问题（哈希函数必须是确定性的）；D 是“溢出”，是地址越界，不是冲突。

逐个算地址并线性探测：23→1；40→7；91→3；17→6；19→8；10→10；31→9；65→65 mod 11 = 10 被占 → 11 mod 11 = 0；26→4。

最终表（下标 0..10）：0:65，1:23，2:空，3:91，4:26，5:空，6:17，7:40，8:19，9:31，10:10。选与这张表一致的选项。

这类题必须按插入顺序一步步来，不能先排好序再算——哈希表的形态依赖插入顺序。

线性探测时，e 被放在 H(e) 之后第一个空位；查找时从 H(e) 开始一路往后比，途中遇到的关键字可能是“同义词”（也映射到 H(e)），也可能是“非同义词”但恰好占了这段连续区域。

但第一个被比较的地址就是 H(e)，那里放的关键字不一定是 e 的同义词（它可能只是先占了这块位置）——所以 D 对。B、C 都太绝对；A 与“有序”无关。

小根堆要求每个结点 ≤ 它的两个孩子（数组下标 i 的孩子是 2i、2i+1）。D：16,40,25,53,39,55,45——看下标 2 的 40，它的孩子是 53、39，40 > 39，违反小根堆，选 D。

快速检查法：从最后一个非叶结点往前看，每个父结点都要比孩子小。A、B、C 都满足。

建堆从最后一个非叶结点（n/2=4）往前调整：1 与孩子 4 换；7 与 6 比不动；8 与 4 换；2 一路下沉到叶子。最终根是 8，第二层 4、7，第三层 2、3、5、6，最后 1——(8,4,7,2,3,5,6,1)，选 C。

D 是“从大到小排好序”，不是堆的形态；堆只保证父子关系，不保证整体有序。A、B 连根都不是最大值，直接排除。

C：73,65,25,21,15,53,33——下标 3 的 21，孩子是 15、53，21 < 53，对大根堆来说父结点必须 ≥ 孩子，这里 21 < 53，违反。小根堆呢？根 73 最大，显然不是小根堆。所以 C 既不是大根堆也不是小根堆，选 C。

A、B 是小根堆（根 15 最小）；D 是大根堆（根 73 最大）。判断时先看根，确定是大根堆还是小根堆，再逐层检查父子关系。

直接插入的比较次数取决于“逆序对”多少：序列越接近有序，比较越少。C（15,27,46,40,64,85）只有 46 和 40 一处逆序，其余都在正确位置，比较次数最少。

A、D 基本是递减的，每插入一个都要和前面所有元素比一遍，最费；B 中 16 要一路比到最前。选 C。

序列几乎有序（只有 5 需要往前挪），直接插入最省：1（0 次）、第二个 1（1 次）、2（1 次）、4（1 次）、7（1 次）、5（先比 7、再比 4，2 次），合计 1+1+1+1+2 = 6 次。

归并要 8 次左右、堆要建堆 + 调整、快排也要多次划分——都比 6 多。选 A、B。

（64）基本有序 → 插入排序退化最少，接近 O(n)，选 A。快速排序在基本有序时反而最差（每次划分极不均衡）。

（65）取值范围只有 0～9 十个值 → 计数排序最合适：数一遍每个值出现几次，再按序输出，O(n)，选 D。这就是“看数据特征选算法”的典型：范围小用计数/基数，基本有序用插入。

基本有序 → 直接插入排序每趟只需很少的比较和移动，最好情况 O(n)，选 A、A。

对比：快排基本有序时退化为 O(n²)；归并、堆都是 O(n log n)，稳定但“杀鸡用牛刀”。这题和第 136 题是同一知识点。

直接插入是稳定的：插入时遇到相等元素就停在它后面，不会越过。简单选择不稳定：选最小元素时会和第一个位置交换，这一换可能把相同的两个元素顺序颠倒。

例子：3, 3, 1——选择排序第一趟把 1 和第一个 3 交换，得到 1,3,3，两个 3 的相对位置变了。所以只有插入稳定，选 C。

要证明“不稳定”，只需举一个反例：序列里有两个相等的元素，排序后它们的先后顺序变了。

典型反例：2, 2, 1——第一趟选择最小元素 1，与第一个 2 交换，变成 1,2,2，原来第一个 2 跑到了第二个 2 后面。选项 A 就是这类反例。选 A。

（64）B 错：快排最坏是 O(n²)（基本有序、每次划分只分出一个元素），不是 O(n log n)。A、C、D 都是快排的正确性质。

（65）效率最高要求每次划分尽量“对半分”。以第一个元素为基准，A 的基准 45 正好是中位数，左右各 3 个元素——最均衡，选 A。C 完全有序，每次只分出一个，最差；B 逆序也差；D 的 45 也接近中间，但后面 85、67、52 的划分不如 A 均匀（官方答案 A）。

（62）基本有序 → 插入排序接近最好情况 O(n)，空间只用常数个临时变量 O(1)，选 A。

（63）基本有序 → 快排最坏，时间 O(n²)，递归栈深度 n，空间 O(n)，选 D。这组题把“同一个输入，不同算法的命运”考得很透：插入笑、快排哭。

（61）快排把序列划分成两半、分别递归——分治，选 A。

（62）最好情况每次对半分，递归 log n 层、每层 O(n) → O(n log n)；最坏情况每次只分出一个元素，递归 n 层、每层 O(n) → O(n²)。选 B。

（62）以 4 为基准，从两端向中间扫：左边找比 4 大的（8、7），右边找比 4 小的（1、3、2）……交换后最终 4 归位到下标 3，左边全是 <4 的 2,3,1，右边全是 >4 的 7,5,6,8——(2,3,1,4,7,5,6,8)，选 C。

注意左边三个数不要求有序（2,3,1），一趟划分只保证“比基准小的一堆、比基准大的一堆”。

（63）一趟划分要把 n 个元素扫一遍、交换若干次，O(n)，选 C。快排总时间 = 划分层数 × 每层 O(n)。

归并 = 把数组分成两半 → 分别递归排序 → 再把两个有序序列合并。典型的“分解—解决—合并”，分治法，选 B。

别和“归纳法”混：归纳法是从小到大递推；归并是分而治之再合并，递归树是自顶向下的。

插入排序逐个数逆序：3；1（比 3 → 1 次）；4（比 3 → 1 次）；1（比 4、3、1 → 3 次）；5（比 4 → 1 次）；9（比 5 → 1 次）；6（比 9、5 → 2 次）；5（比 6、5 → 2 次）。合计 11～12 次，取 12。

归并排序两两合并：数组合并的比较次数取决于谁先耗尽——官方答案 14。选 A（12,14）。

这类题的“标准答案”依赖具体的比较计数约定（是否把与哨兵的比较算进去），考场按选项中最接近的官方值选。

归并比较次数最多的情况是两个序列交替输出——每次比较后只取走一个元素，另一个序列的元素一直“卡”着不走。如果一方全部小于另一方，比较 n 次就能把一方搬完，最省。

C 项正是交错排列（a1,b1,a2,b2,…），每步都要比较，直到最后，比较次数最多。选 C。

（62）归并排序是分治，选 A。

（63）排序 O(n log n)，双指针扫描 O(n)，总复杂度取大头 O(n log n)，选 A。这里是“排序 + 线性扫描”的经典组合，比两两枚举 O(n²) 快一个量级。

比较次数最少 = 一方全部小于另一方：这样每次比较都取走 A 的元素，比完 m 次 A 就空了，剩下的 B 直接搬过去，不用再比。

所以条件是“A 的最大元素 < B 的最小元素”（或反之），对应选项 A。和第 146 题正好是“最多/最少”的两面。

（62）分成两半分别排序再合并——分治，选 A。

（63）归并排序无论数据怎么排，都要分 log n 层、每层合并 O(n)，所以最好最坏都是 O(n log n)，选 C。这也是它比快排“稳”的地方：快排最坏 O(n²)，归并不看数据脸色。

比较“最坏情况”：插入 O(n²)、冒泡 O(n²)、快速 O(n²)，只有归并稳定在 O(n log n)。选 C。

如果题目问“平均”或“最好”，快排和归并都是 O(n log n)；问“最坏”就是归并、堆的天下。

“一趟定一个元素的最终位置”——冒泡每趟把最大（或最小）元素送到最终位置；简单选择每趟选出最小元素放到前面；堆排序每趟取出堆顶放到末尾；快排每趟让基准元素归位。②③④⑤ 都满足，选 C。

①直接插入：第一趟只是把前两个元素排好，它们后面还可能被更小的元素挤动，不能定终位。⑥归并：第一趟只是把相邻两两合并，整体位置未定。

A 对：生成树就是“用 n−1 条边连通 n 个顶点”，顶点数比边数多 1，任何生成树都成立，与权值无关。

B 错：强连通最少只要 n 条边（一个环），不是 2n。C 错：估算工期用 AOE 网（边表示活动、带权），AOV 网（顶点表示活动）用于拓扑排序、判断先后关系。D 错：关键路径是最长路径，不是最短。

C 错：平衡化保证的是高度差不超过 1，不是结点数差不超过 1。左右子树高度相同，结点数可以差很多（一边满、一边稀疏）。

A 对（中序有序）；B 对（插入顺序不好会退化成单枝）；D 对（AVL 的定义就是高度差 ≤1）。这题专门考“高度”和“结点数”的字眼区别。

一步步取：L = ((x,y,z), a, (u,t,w))。
head(L) = (x,y,z)（第一个元素）；
tail((x,y,z)) = (y,z)；
head((y,z)) = y。

合起来就是 head(tail(head(L)))，选 C。记法：head 取第一个，tail 去掉第一个；要取嵌套里的元素，就从外往里层层剥。

串替换要求“替换后的串长度可以变”，而链式存储按结点分配，长度一变就要大量拆结点、并结点、搬字符，牵一发动全身——最不方便，选 D。

比较、求子串、连接相对好办：比较可以逐结点比，求子串可以定位后截取，连接只需把尾结点指针接上。替换因为“变长”最麻烦。

M 阶 B−树的关键约束：每个结点最多 M 个孩子、M−1 个关键字；除根外每个结点至少 ⌈M/2⌉ 个孩子。

看图里结点最多有几个孩子（几个分支）——图中结点最多 4 个孩子，所以 M=4，选 D。M 阶的“阶”指的就是“最多孩子数”。

顺序表：地址 = base + (i−1)×L，一步算出来，O(1)。单链表：从头结点走到第 i 个，走 i 步，O(n)。选 B。

这题是线性表那一节的“收尾题”，把顺序表与链表最本质的差异又考了一遍。

（64）两者都是“每步选当前权值最小的边/顶点”，局部最优推到全局——贪心，选 B。

（65）Prim 的复杂度 O(n²)，与边数无关，适合稠密图；Kruscal 的复杂度 O(e log e)，适合稀疏图。所以“网较稠密时 Prim 更好”，选 A。B 错：最小生成树可能不唯一（权值相同的边有多个选择时）。

（62）优先队列要“每次取最大/最小”，堆的堆顶正好是极值，插入删除 O(log n)——用堆实现，选 A。

（63）插入堆是“放到末尾再向上调整”，调整层数最多是树高 log n，所以 O(log n)，选 B。取堆顶是 O(1)，删除堆顶也是 O(log n)。

（64）选中位数做基准，每次划分最均衡，能把问题规模稳定减半，选 C。

（65）每次只递归处理“包含第 i 小元素的那一半”，总工作量 n + n/2 + n/4 + … ≈ 2n，所以最坏也是 O(n)，选 A。这就是“快速选择”算法（BFPRT 思想）。

注意：如果基准选得差（第一个/最后一个），最坏会退化成 O(n²)——所以题目问“最佳选择”时选中位数。