🏷️ 知识点：串
为解决计算机与打印机之间速度不匹配的问题，通常设置一个打印数据缓冲区，主机将要输出的数据依 次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是()。
A. 栈
B. 队列
C. 树
D. 图
[tag_link]
正确答案：B
缓冲区 的概念出现在操作系统的设备管理中，其特点是先进先出。缓冲区的作用是解决主机与打印机之间速度不匹配的问题，而不应改变打印数据的顺序。若用栈，先进入缓冲区的数据则要排队到最后才能打印，显然不符题意，故选 B。
串"acaba"的 next 数组值为（ ）。
A. 01234 B. 01212 C. 01121 D. 01230
[tag_link]
正确答案：C
在 KMP 算法中，next 数组用于模式匹配失败时的跳转。 根据严蔚敏《数据结构》中的定义，对于模式串 `"acaba"`（下标从 1 开始），`next[1] = 0`。 对于 `j > 1`，`next[j]` 是满足条件 `1 < k < j` 且前 `k-1` 个字符与后 `k-1` 个��符相等的最大 `k` 值； 若不存在这样的 `k`，则 `next[j] = 1`。
具体计算过程如下：
- `j = 1` 时，`next[1] = 0`。 >
- `j = 2` 时，`k` 只能取 1，前 0 个字符与后 0 个字符相等，故 `next[2] = 1`。 >
- `j = 3` 时，`k = 2` 不成立（`'a' ≠ 'c'`），`k = 1` 成立，故 `next[3] = 1`。 >
- `j = 4` 时，`k = 3` 不成立（`"ac" ≠ "ca"`），`k = 2` 成立（`'a' = 'a'`），故 `next[4] = 2`。 >
- `j = 5` 时，`k = 4`、`3`、`2` 均不成立，`k = 1` 成立，故 `next[5] = 1`。 >
因此，next 数组值为 `[0, 1, 1, 2, 1]`，即 `01121`，对应选项 C。 >
（本题满分 10 分）栈的基本操作有出栈和入栈。将序列1,2,3,…,n依次入栈，回答下列问题：
(1) 当n=9时，可以得到出栈序列{2,3,1,6,4,7,5,8}吗？可以得到出栈序列{2,3,1,4,6,5,7,8}吗？（2 分）
(2) 假设1,2,…,n组成任意序列的出栈序列P1,P2,…,Pn，在序列中有Pi、Pj、Pk（i<j<k），若该出栈序列不能由栈得到，则Pi、Pj、Pk的大小关系是？（2 分）
(3) 若n=4，则以 2 开头的序列个数有多少个？（2 分）
(4) 若n=k−1时，出栈序列总共共有M个，如果n=k，那么以 1 开头的出栈序列个数有多少个？以 2 开头的出栈序列有多少个？总共的出栈序列有多少个？（4 分）
[tag_link]
【答案】
（1）当n=9时，出栈序列的可能性分析
序列{2,3,1,6,4,7,5,8}（假设包含9，即{2,3,1,6,4,7,5,8,9}）：存在下标i=4,j=5,k=7，满足Pj=4<Pk=5<Pi=6，即存在“312”模式，因此不能由栈得到。
序列{2,3,1,4,6,5,7,8}（假设包含9，即{2,3,1,4,6,5,7,8,9}）：不存在任何三个下标i<j<k满足Pj<Pk<Pi，因此可以由栈得到。
答案：第一个序列不能得到，第二个序列可以得到。（2）不能由栈得到的出栈序列中Pi,Pj,Pk的大小关系若出栈序列P1,P2,…,Pn不能由栈得到，则存在三个下标i<j<k，满足
Pj<Pk<Pi.即第二个出栈的数最小，第三个出栈的数居中，第一个出栈的数最大。答案：Pj<Pk<Pi.（3）n=4时以2开头的出栈序列个数枚举所有以2开头的出栈序列：{2,1,3,4},{2,1,4,3},{2,3,1,4},{2,3,4,1},{2,4,3,1}.共5个。答案：5个。（4）n=k时，以1开头、以2开头的序列个数及总个数已知当n=k−1时，栈可得到的出栈序列总数为Ck−1=M其中Cn为第n个卡特兰数。以 1 开头的出栈序列个数若第一个出栈元素为 1，则操作只能是：push(1) → pop(1)此后对2,3,…,k的出栈过程不再受限制，因此剩余元素的出栈序列个数就是规模为k−1时的总数，即Ck−1=M因此，以 1 开头的出栈序列个数为M。****以 2 开头的出栈序列个数若第一个出栈元素为 2，则操作前缀必为：push(1), push(2), pop(2)此时栈中剩余元素为 1，尚未入栈的元素为3,4,…,k。接下来的过程可以看作：在栈中已经保留元素 1 的基础上，继续对3,4,…,k进行正常的入栈、出栈操作。将元素3,4,…,k分别减去 1 后，与规模为k−1的序列1,2,…,k−1的合法出栈过程一一对应，因此合法出栈序列个数同样为Ck−1=M因此，以 2 开头的出栈序列个数也为M。****出栈序列总数卡特兰数满足递推关系：Ck=k+12(2k−1)Ck−1由Ck−1=M，得：Ck=k+12(2k−1)M所以：
- 以 1 开头的出栈序列个数：M
- 以 2 开头的出栈序列个数：M
- 出栈序列总数：k+12(2k−1)M