元素 a、b、c、d、e 依次进入初始为空的栈中，若元素进栈后可停留、可出栈，直到所有元素都出栈，则在所有可能的出栈序列中，以元素 d 开头的序列个数是（ ）。
目标与前置知识
- 根据输出约束给出可行操作过程，或指出无法越过的阻挡关系。
- 追踪运算符栈、操作数栈和调用栈，区分顺序、深度与累计操作数。
- 从指针含义推导共享空间不变量，并论证链队列的空间复用与常数时间操作。
- 用必要性、充分性和不重不漏的分类完成序列证明与计数。
前置阅读：2.1 栈、2.2 队列、2.3 栈与队列的应用。建议先完成本章两组基础自测。
试卷与评分
| 部分 | 题量 | 分值 | 建议用时 |
|---|---|---|---|
| 单项选择 | 20 题，每题 2 分 | 40 分 | 35～45 分钟 |
| 理论大题 | 5 题，每题 12 分 | 60 分 | 65～85 分钟 |
| 合计 | 25 题 | 100 分 | 100～130 分钟 |
选择题得分为答对题数 × 2（满分 40）；大题依据各题评分要点人工自评，另记 60 分。
环境为现代浏览器和纸笔，无需编译器。输入是下列题面；提交产物是一份选择题作答记录和五份包含推导、结构图或伪代码的书面答案。结构图允许用结点编号及箭头表示。
题目中的栈底/栈顶、队头/队尾按各题约定。一般假设单个结点分配成功且分配、释放计为常数时间；这不等同于操作系统分配器具有硬实时保证。证明须覆盖空结构、单元素、容量边界和非法操作，不能只给正常例子。
选择题
答题进度已答 0/20正确 0
设栈 S 和队列 Q 的初始状态均为空，元素 a、b、c、d、e、f、g 依次进入栈 S。若每个元素出栈后立即进入队列 Q，且 7 个元素出队的顺序是 b、d、c、f、e、a、g，则栈 S 的容量至少是（ ）。
若元素 a、b、c、d、e、f 依次进栈，允许进栈、退栈操作交替进行，但不允许连续三次进行退栈操作，则不可能得到的出栈序列是（ ）。
已知操作符包括 +、-、*、/、( 和 )。将中缀表达式 a+b-a*((c+d)/e-f)+g 转换为等价的后缀表达式 ab+acd+e/f-*-g+ 时，用栈存放暂时还不能确定运算次序的操作符。若栈初始为空，则转换过程中同时保存在栈中的操作符的最大个数是（ ）。
一个栈的入栈序列为
假设栈初始为空，将中缀表达式 a/b+(c*d-e*f)/g 转换为等价的后缀表达式的过程中，当扫描到 f 时，栈中的元素从栈底到栈顶依次是（ ）。
已知程序片段如下（沿用试题的主函数写法）：
int S(int n) {
return (n <= 0) ? 0 : S(n - 1) + n;
}
void main() {
cout << S(1);
}
程序运行时使用栈来保存调用过程的信息。在调用达到最深层、尚未返回时，自栈底到栈顶保存的信息依次对应的是（ ）。
下列关于栈的叙述中，错误的是（ ）。
I. 采用非递归方式重写递归程序时必须使用栈。
II. 函数调用时，系统要用栈保存必要信息。
III. 只要确定了入栈次序，即可确定出栈次序。
IV. 栈是一种受限的线性表，允许在其两端进行操作。
栈 S1 保存整数，栈 S2 保存运算符。函数 F() 依次从 S1 弹出操作数 a、b，从 S2 弹出运算符 op，计算 b op a，再把结果压入 S1。
S1 中的操作数从栈底到栈顶依次为 5、8、3、2，S2 中的运算符从栈底到栈顶依次为 *、-、+。调用 3 次 F() 后，S1 栈顶的值是（ ）。
表达式 x+y*(z-u)/v 的等价后缀是（ ）。按通常中缀转后缀规则保留原式的优先级和结合顺序，不进行代数变形。
对于括号匹配问题，符号栈初始为空，容量为 3，下列表达式的括号匹配不能在该容量内实现的是（ ）。只考查括号，不检查其他字符构成的算术语法。
已知循环队列存储在一维数组 A[0..n-1] 中，且队列非空时 front 和 rear 分别指向队头元素和队尾元素。若初始时队列空，且要求第一个进入队列的元素存储在 A[0] 处，则初始时 front 和 rear 的值分别是（ ）。入队按 rear 先循环后移、再写入的常规规则执行。
设有图示火车车轨，入口到出口之间有 n 条轨道。列车全程从左向右行进，可驶入任意一条轨道；每条轨道内不可调头、不可超车，相当于 FIFO 队列。
编号为 1 至 9 的列车按 8、4、2、5、3、9、1、6、7 的次序驶入，若要求按 1 至 9 的次序驶出，则 n 至少是（ ）。
某队列允许在其两端进行入队操作，但仅允许在一端进行出队操作。若元素 a、b、c、d、e 依次入此队列后再进行出队操作，则不可能得到的出队序列是（ ）。
已知初始为空的队列 Q 的一端仅能进行入队操作，另外一端既能进行入队操作又能进行出队操作。若 Q 的入队序列是 1、2、3、4、5，则不能得到的出队序列是（ ）。入队与出队允许交替。
下列描述的几种链表中，最不适合用作链式队列的是（ ）。
用栈求中缀算术表达式的值，运算符栈与运算数栈分开。若运算数栈 OPEN 只有 2 个存储单元，则下列表达式中不会使 OPEN 溢出的是（ ）。A、B、C、D 均为单个运算数，按通常优先级和左结合规则及时求值，不重排运算。
若以 1、2、3、4 作为双端队列的输入序列，入队与出队允许交替，则既不能由输入受限的双端队列得到、又不能由输出受限的双端队列得到的输出序列是（ ）。输入受限指仅一端可入队、两端可出队；输出受限指两端可入队、仅一端可出队。
用不带头结点的单链表作为链式栈，结点结构为 (data, link)，其中 data 是数据域，link 是指针域，top 指向栈顶结点。假设栈非空，要摘除栈顶结点并将其值保存到 x，应执行的关键操作是（ ）。本题只比较取值与摘链步骤，结点释放另行处理。
与顺序队列相比，链式队列的（ ）。
答案总览（建议完成全部题目后查看）
- 第 1 题：B
- 第 2 题：C
- 第 3 题：D
- 第 4 题：A
- 第 5 题：C
- 第 6 题：B
- 第 7 题：A
- 第 8 题：C
- 第 9 题：B
- 第 10 题：A
- 第 11 题：D
- 第 12 题：B
- 第 13 题：C
- 第 14 题：C
- 第 15 题：D
- 第 16 题：C
- 第 17 题：B
- 第 18 题：C
- 第 19 题：A
- 第 20 题：D
理论大题
综合题 1：出栈序列的禁形与条件计数
来源：2026 年 408 真题第 42 题（ds-2026-42，题面整理）；本 Lab 评分细分为 12 分。
入栈序列为
- 当
时，分别判断序列 2,3,1,6,4,7,5,9,8和2,3,1,5,6,7,4,9,8能否得到，并给出阻挡证据或可行过程。（3 分） - 对输出序列中的
，其中 ，哪一种大小关系能证明序列不可能得到？说明原因。（3 分） - 当
时，列举所有以 2 开头的合法出栈序列，给出总数。（2 分） - 已知
时全部合法出栈序列共 个， 。当 时，以 1 开头、以 2 开头以及所有合法出栈序列分别有多少个？给出推导。（4 分）
综合题 1 参考答案与评分要点
（1）第一条不合法，第二条合法。
第一条先输出 2,3,1 后栈空。为输出 6，必须依次压入 4、5、6。弹出 6 后，5 压在 4 上方，无法立即输出 4。
第二条可按下表完成。+x 为入栈，-x 为出栈，栈状态均从底到顶列出。
| 阶段 | 操作 | 阶段后栈状态 | 新输出 |
|---|---|---|---|
| 1 | +1 +2 -2 +3 -3 -1 | 空 | 2,3,1 |
| 2 | +4 +5 -5 +6 -6 +7 -7 -4 | 空 | 5,6,7,4 |
| 3 | +8 +9 -9 -8 | 空 | 9,8 |
（2）禁止出现
因为 6,4,5 就是这样的三元组。
（3）共有 5 个。
text
2,1,3,4
2,1,4,3
2,3,1,4
2,3,4,1
2,4,3,1先压 1、2 并弹出 2，剩余输入是 3、4，而 1 已在栈底。后续情形与三个有序元素 1、3、4 的合法栈输出一一对应，因此枚举没有漏项。
（4）依次为
以 1 开头时，必须先压入并立即弹出 1，剩下的
以 2 开头时，先压 1、2 并弹 2，剩下 1 已在栈中、3 至 k 尚未进入。对有序输入 1、3、…、k 的任意合法操作，其第一步本就必须压 1；省略这一步便与当前状态的后续操作一一对应，仍为
设全部合法序列数为
也可把入栈/出栈看作上升/下降步：长度
这里
评分要点（12 分）：第一条阻挡证据 1 分、第二条可行过程 2 分；禁形大小关系 1 分、压栈先后与矛盾证明 2 分；五条无重无漏的枚举 2 分；两个条件计数及一一对应理由各 1 分，总数关系及推导 2 分。只写数值而无依据的子问至多得该子问一半分。
综合题 2：空间只增不减的队列设计
来源：2019 年 408 真题第 42 题（ds-2019-42）；保留四项要求，并增加边界核验，按 12 分计。
设计一个队列，满足：初始为空；入队时允许增加占用空间；出队结点的空间可重复使用，队列所占空间只增不减；每次入队、出队都保持
- 选择顺序或链式存储并说明理由。（2 分）
- 画出初始状态，明确 front、rear 的含义以及判空、判定当前空间无可用槽位的条件。（3 分）
- 画出第一个元素 x 入队后的状态。（1 分）
- 给出入队、出队的伪代码；说明空队出队失败，以及“入队 x、入队 y、出队两次、再入队 z”时的结点复用情况。（6 分）
综合题 2 参考答案与评分要点
（1）选择保留所有已分配结点的循环单链表。
需要扩容搬移全部元素的普通连续数组，其扩容那次操作为
（2）使用一个随出队移动的空位标记，而非永久固定的头结点。
- front 指向逻辑队头的前一个结点；rear 指向逻辑队尾。
- 非空时，从
front->next沿 next 到 rear 的闭区间是有效数据区，front 本身不属于有效数据；front == rear时有效数据区为空。 - rear 之后、front 之前是可供下次入队复用的空闲结点；永远保留 front 这个空位。
- 队空：
front == rear。现有环没有可复用槽位：rear->next == front，此时入队需要增配一个结点。
初始只分配结点 u，自环：
text
front, rear -> u
u.next = u初始状态同时“逻辑为空”和“现有空间无可用数据槽”。两者不矛盾：当前环只有用于区分状态的一个空位，首次入队允许扩充。
（3）第一次入队 x 后：
text
front -> u -> v(x) <- rear
^ |
+-----+新增 v，u.next=v、v.next=u；front 仍为 u，rear 为 v。
（4）伪代码如下，失败不修改队列。
text
EnQueue(x):
if rear.next == front:
p = allocateNode()
if allocation failed: return false
p.next = rear.next
rear.next = p
rear = rear.next
rear.data = x
return true
DeQueue(out):
if front == rear: return false
front = front.next
out = front.data
return true出队把 front 移到原队头并取走值；这个结点从此成为新的空位标记，其残留 data 不再属于队列。整个环不删结点，也不释放空间。这样 front 所指结点会变化，不能把最初的 u 当作永远固定的哨兵。
复用轨迹如下，u、v、w 为物理结点编号：
| 操作后 | 物理环 | front | rear | 逻辑队列 | 已分配结点数 |
|---|---|---|---|---|---|
| 初始化 | u → u | u | u | 空 | 1 |
| 入 x | u → v → u | u | v | x | 2 |
| 入 y | u → v → w → u | u | w | x,y | 3 |
| 出 x | u → v → w → u | v | w | y | 3 |
| 出 y | u → v → w → u | w | w | 空 | 3 |
| 入 z | u → v → w → u | w | u | z | 3 |
最后一次入队时 rear.next=u，而 front=w，有空闲槽位，直接复用 u，不发生分配。每次操作只做常数次访问与指针修改。若历史最大逻辑长度为 H，最小初始方案总计保留 H+1 个结点，空间为
评分要点（12 分）：选型及单次复杂度理由 2 分；指针含义、数据/空闲区和两个判定 3 分；首次入队图 1 分；入队按需扩展且失败不破坏环 2 分；出队不释放且空队不修改 2 分；复用轨迹与复杂度 2 分。其他自洽的循环链结构亦可，不能混用两套 front/rear 约定。
综合题 3：共享栈的空间不变量与固定分区比较
来源：基于笔记“栈的应用”共享栈题（ds-drill-stack-application-012、016）整理的综合训练，非原考试大题。分值：12 分。
数组 A[0..m-1] 同时存放两个栈 L、R。L 从左端向右增长，R 从右端向左增长。topL、topR 指向实际栈顶，空栈初值分别为 -1、m，
- 写出两栈的元素数、空闲槽位数及允许状态的不变量，并推导判空、判满条件。（3 分）
- 当
、 topL=2、topR=7时，依次向 L 压入两项、向 R 压入两项；再尝试向 L 压入一项。列出每一步的指针值，说明最后一步的结果。（3 分） - 写出左右两栈的 Push/Pop 关键伪代码，要求先检查边界再修改指针，失败保持状态不变。（3 分）
- 若改成 L 永久分配 a 个槽、R 分配 m-a 个槽，证明不存在一个固定 a 能同时支持占用峰值分别为
(m,0)和(0,m)的两类工作负载；共享方案为何能够支持？说明它仍不能解决什么溢出。（3 分）
综合题 3 参考答案与评分要点
（1）不变量由实际占用区间得到。
合法指针满足 topL==-1，R 空当且仅当 topR==m。共享空间满当且仅当 topL+1==topR，此时空闲槽为 0。不存在“L 分到的一半满了”的单独容量限制。
（2）轨迹如下。
| 操作 | topL | topR | 空闲槽 | 结果 |
|---|---|---|---|---|
| 初始 | 2 | 7 | 4 | L、R 各 3 项 |
| PushL | 3 | 7 | 3 | 成功 |
| PushL | 4 | 7 | 2 | 成功 |
| PushR | 4 | 6 | 1 | 成功 |
| PushR | 4 | 5 | 0 | 成功，空间刚满 |
| PushL | 4 | 5 | 0 | 失败，指针和数据均不变 |
（3）先判断再修改。
text
PushL(x):
if topL + 1 == topR: return false
topL = topL + 1
A[topL] = x
return true
PushR(x):
if topL + 1 == topR: return false
topR = topR - 1
A[topR] = x
return true
PopL(out):
if topL == -1: return false
out = A[topL]
topL = topL - 1
return true
PopR(out):
if topR == m: return false
out = A[topR]
topR = topR + 1
return true四种操作都只访问本栈栈顶，时间为
（4）固定分区无法适配两种相反峰值。
支持 (m,0) 要求 (0,m) 要求
共享栈仅要求两栈当前元素总数不超过 m，能把全部槽位临时让给任一栈，因此支持这两类工作负载。它解决的是固定分区下的闲置空间问题，不能在两栈同时总需求超过 m 时避免真实溢出。
评分要点（12 分）：三项计数、不变量、空满判定 3 分；完整轨迹与失败不变 3 分；四个操作及边界检查 3 分；固定分区矛盾、共享优势和真实容量限制各 1 分。
综合题 4：仅用尾指针拼接与旋转循环链队列
来源：基于笔记“队列”尾指针循环链结构（ds-drill-queue-016）延伸的综合训练，非原考试大题。分值：12 分。
两个队列 A、B 分别采用不带头结点的循环单链表，仅长期保存队尾指针 rearA、rearB；空队列尾指针为空，非空队列的队头为 rear->next。两个队列对象不同，结点互不共享。允许使用常数个临时指针。
- 设计
Append(A,B)：将 B 的全部元素接到 A 后面，保持两个原队列内部次序，之后 B 变为空队列。不得逐个搬移数据、分配或释放结点，要求最坏。（5 分） - 非空队列
a,b,c,d执行一次“队头转到队尾”，只修改哪个指针即可？写出结果，并说明空队列、单元素队列如何处理。（3 分） - 对 A=
a,b,c、B=d,e，画出拼接前后所有改变的 next 链接。证明算法仍形成一个完整环，并说明为什么“复制 rearB 给 rearA 后保留 B 非空”不满足要求。（4 分）
综合题 4 参考答案与评分要点
（1）非空情况下交换两条跨边即可。
text
Append(A, B):
if B.rear == null: return
if A.rear == null:
A.rear = B.rear
B.rear = null
return
headA = A.rear.next
headB = B.rear.next
A.rear.next = headB
B.rear.next = headA
A.rear = B.rear
B.rear = null当 B 空时 A 不变；当 A 空且 B 非空时，只转移尾指针的所有权。两者都非空时，必须先保存原队头，防止第一次改链接后失去原环的入口。整个操作只改常数条链接，最坏时间和额外空间均为
（2）非空时执行 rear=rear->next。
物理 next 链接不变；新的 rear 是原队头，新队头是原队头的后继，因此 a,b,c,d 变为 b,c,d,a。空队列保持空并返回失败或约定的无操作结果，不能解引用空指针；单元素自环执行后还是自身，队列次序不变。
（3）只改变 c 与 e 的 next。
text
拼接前：a -> b -> c -> a d -> e -> d
rearA rearB
改动： c.next: a -> d
e.next: d -> a
拼接后：a -> b -> c -> d -> e -> a
rearA = e, rearB = null从 headA 出发，先经过 A 的全部原结点，再通过 c.next=d 进入 B，经过 B 的全部原结点，最后通过 e.next=a 回到起点。因原来两个环各自完整且不共享结点，新环恰好经过全部结点一次，内部次序保持不变。
若仅 rearA=rearB 而不连接两个环，会丢失 A 的原队列。即使已正确拼接，仍让 B 的 rear 非空也会使两个队列对象共同引用同一个环；后续出队、销毁可能影响另一队列或重复释放，不满足“B 变空、结点归 A 所有”的后置条件。题设排除 Append(A,A)，不能忽略这一前提。
评分要点（12 分）：两个空队分支 2 分、非空拼接与清空 B 2 分、常数复杂度 1 分；旋转指针和结果 2 分、空/单元素边界 1 分；两条改边 2 分、环与次序证明 1 分、所有权说明 1 分。
综合题 5：受限双端队列的可达序列与计数
来源：基于笔记“双端队列”和“队列”受限出队题整理的综合证明训练（ds-2010-02、ds-drill-queue-014），非原考试大题。分值：12 分。
输入为互异元素
- 对输出受限双端队列，允许左右两端入队，只允许左端出队。证明可达输出序列恰好由“严格递减的一段、元素 1、严格递增的一段”构成，两段均可为空；据此求不同输出序列总数。（5 分）
- 对输入受限双端队列，只允许右端入队，允许两端出队。给出判断某个排列可达的必要充分条件，并求不同输出序列总数。（4 分）
- 当
时，分别给出一个只由第 1 种结构可达的排列和一个只由第 2 种结构可达的排列，说明可行过程及另一结构不可行的原因。（3 分）
综合题 5 参考答案与评分要点
（1）输出受限：每个大于 1 的元素只需决定放在哪一侧。
必要性：1 最先进入。之后左插的元素位于 1 前，按入队次序的反序出现，所以严格递减；右插的元素位于 1 后，按原入队次序出现，所以严格递增。
充分性：给定这样的目标排列，把 1 前的元素依其原输入次序从左端插入，把 1 后的元素从右端插入，就能构造出目标排列。故该形状既必要又充分。
对每个 (1)，公式仍得 1。
（2）输入受限：每次输出必须是剩余区间的一个端点。
全部右插结束后，物理队列为 1,2,...,n。令
text
if x == l: l = l + 1
else if x == r: r = r - 1
else: reject如果每一步都通过检查，则相应从左或右端删除即可，充分性成立；若某步 x 不是端点，它被剩余元素夹在内部，不能直接取出，必要性成立。判断的时间为
前
（3）数量相同不表示集合相同。
| 排列 | 可达结构与过程 | 另一种结构为何不可达 |
|---|---|---|
| 3,1,2,4 | 输出受限：依次入 1、右插 2、左插 3、右插 4，再从左端取完 | 输入受限全入后的端点只有 1、4，无法首先输出 3 |
| 1,4,2,3 | 输入受限：全入后依次从左、右、左、左取出 | 输出受限中 1 后必须严格递增，而 4 在 2 前不满足 |
这里的全部入队后再出队是证明的一部分。放宽为任意交替操作后，不能直接沿用本题的计数公式。
评分要点（12 分）：输出受限的必要性 2 分、充分性 1 分、计数及无重性 2 分；输入受限的端点条件与双向论证 2 分、计数和最后一步处理 2 分；两组正确反例与可达/不可达理由 3 分。
完成清单与复盘
复盘时将错误归到“忽略额外操作限制”“混用指针约定”“只给结论未证明”或“计数重漏”之一，并重写对应的一步推理。