数据结构之栈

选择题

01. 栈和队列具有相同的()。

A. 抽象数据类型
B. 逻辑结构
C. 存储结构
D. 运算

答案：B
解释：
栈和队列的逻辑结构相同，都是线性结构。它们的区别在于数据的运算方式不同，但逻辑上都属于线性表。

02. 栈是()。

A. 顺序存储的线性结构
B. 链式存储的非线性结构
C. 限制存取点的线性结构
D. 限制存储点的非线性结构

答案：C
解释：
栈是一种线性结构，具有“后进先出”（LIFO）的特点，它限制了只能在栈顶进行数据的插入和删除操作，属于“限制存取点的线性结构”。

03. ( ) 不是栈的基本操作。

A. 删除栈顶元素
B. 删除栈底元素
C. 判断栈是否为空
D. 将栈置为空栈

答案：B
解释：
栈的基本操作包括入栈（push）、出栈（pop）以及检查栈顶元素（top）等。删除栈底元素不是栈的基本操作，栈只允许操作栈顶元素。

04. 假定利用数组 a[n] 顺序存储一个栈，用 top 表示栈顶指针，用 top == -1 表示栈空并已知栈未满，当元素 x 进栈时所执行的操作为()。

A. a[--top] = x
B. a[top--] = x
C. a[++top] = x
D. a[top++] = x

答案：C
解释：
栈空时，top == -1，当元素进栈时，应先将栈顶指针 top 加 1，然后将元素存入栈顶位置。因此操作应为 a[++top] = x。

05. 设有一个空栈，栈顶指针为 1000H，每个元素需要一个存储单元，执行 Push、Push、Pop、Push、Pop、Push、Pop、Push 操作后，栈顶指针的值为()。

A. 1002H
B. 1003H
C. 1004H
D. 1005H

答案：A
解释：
每执行一次 Push 操作，栈顶指针 top 加 1；每执行一次 Pop 操作，栈顶指针 top 减 1。按照题目顺序操作后，指针的变化为：

初始指针：1000H
第一次 Push：1001H
第二次 Push：1002H
第一次 Pop：1001H
第三次 Push：1002H
第二次 Pop：1001H
第四次 Push：1002H

最终栈顶指针为 1002H。

06. 和顺序栈相比，链栈有一个比较明显的优势，即()。

A. 通常不会出现栈满的情况
B. 通常不会出现栈空的情况
C. 插入操作更容易实现
D. 删除操作更容易实现

答案：A
解释：
顺序栈采用数组存储，数组的大小是固定的，因此当栈满时无法继续插入元素。链栈采用链式存储，可以动态分配内存，不受栈大小的限制，因此通常不会出现栈满的情况。

07. 设链表不带头结点且所有操作均在表头进行，则下列最不适合作为链栈的是()。

A. 只有表头结点指针，没有表尾指针的双向循环链表
B. 只有表尾结点指针，没有表头指针的双向循环链表
C. 只有表头结点指针，没有表尾指针的单向循环链表
D. 只有表尾结点指针，没有表头指针的单向循环链表

答案：C
解释：
对于双向循环链表，不管是表头指针还是表尾指针，都可以很方便地找到表头结点，方便在表头做插入或删除操作。而单循环链表通过尾指针可以很方便地找到表头结点，但通过头指针找尾结点则需要遍历一次链表。对于C，插入和删除结点后，找尾结点需要花费0(n)的时间。

08. 向一个栈顶指针为 top 的链栈(不带头结点)中插入一个 x 结点，则执行()。

A. top->next = x
B. x->next = top->next; top->next = x
C. x->next = top; top = x
D. x->next = top; top = top->next

答案：C
解释：
链栈使用单链表表示时，进栈操作是在链表的首部插入一个结点。具体步骤为：新结点 x 的 next 指针指向当前栈顶元素（即 x->next = top），然后将 top 指针指向 x，即 top = x。

09. 链栈(不带头结点)执行 Pop 操作，并将出栈的元素存入 x 中，应该执行()。

A. x = top; top = top->next
B. x = top->data; top = top->next
C. top = top->next; x = top->data
D. x = top->data; top = top->next

答案：D
解释：
在不带头结点的链栈中，栈顶指针 top 指向栈顶元素。出栈操作应首先将栈顶元素的数据存入变量 x 中 (x = top->data)，然后将 top 指针移动到下一个元素 (top = top->next)。

10. 经过以下栈的操作后，变量 x 的值为()

InitStack(st);
Push(st, a);
Push(st, b);
Pop(st, x);
Top(st, x);

A. a
B. b
C. NULL
D. FALSE

答案：A
解释：
执行 Push(st, a) 和 Push(st, b) 后，栈内的元素从底到顶依次为 a、b。执行 Pop(st, x) 后，栈顶元素 b 出栈，变量 x 的值变为 b，栈顶变为 a。然后执行 Top(st, x)，获取当前栈顶元素 a，x 的值变为 a。因此答案为 A。

11. 3 个不同元素依次进栈，能得到()种不同的出栈序列。

A. 4
B. 5
C. 6
D. 7

答案：B
解释：
3 个不同元素进栈后，可以有 5 种不同的出栈序列，具体为：abc、acb、bac、bca、cba。这可以通过排列组合和递归的方法枚举出栈的可能性。

这是一个卡特兰数：

卡特兰数有一个简单的封闭形式，可以直接计算。卡特兰数 $ C_n $ 的公式为：

$ C_n = $

12. 设 a, b, c, d, e, f 以所给的次序进栈，若在进栈操作时，允许出栈操作，则下面得不到的序列为()。

A. fedcba
B. bcafed
C. dcefba
D. cabdef

答案：D
解释：
根据栈“先进后出”的原则，若在进栈时允许出栈操作，c 如果最先出栈，则栈中只可能还剩下 a 和 b，但 a 是先于 b 进栈的，应该晚于 b 出栈。因此 cabdef 不符合栈的出栈规则，答案为 D。

13. 用 S 表示进栈操作，用 X 表示出栈操作，若元素的进栈顺序是 1, 2, 3, 4，为了得到 1342 的出栈顺序，相应的 S 和 X 的操作序列为()

A. SXSXSSXX
B. SSSXXSXX
C. SSSXSSXX
D. SXSSXSXX

答案：D
解释：
进栈顺序为 1, 2, 3, 4，出栈顺序为 1342。对应的进出栈操作为：1 进栈、1 出栈，2 进栈，3 进栈、3 出栈，4 进栈、4 出栈，最后 2 出栈。对应操作为 S X S S X S X S X X，即选项 D。

14. 若一个栈的输入序列是 1, 2, 3,…, n，输出序列的第一个元素是 n，则第 i 个输出元素是()

A. 不确定
B. n-i
C. n-i-1
D. n-i+1

答案：D
解释：
栈的“先进后出”特性决定了如果 n 是第一个出栈的元素，那么后续出栈的元素将依次为 n-1、n-2，依此类推。因此，第 i 个出栈的元素为 n-i+1，答案为 D。

15. 一个栈的输入序列为 1, 2, 3,…, n，输出序列的第一个元素是 i，则第 j 个输出元素是()

A. i-j-1
B. i-j
C. j-i+1
D. 不确定

答案：D
解释：
如果第一个出栈的元素是 i，那么 i 之前的元素可以依次排在 i 之后出栈，剩余的元素则可能在 i 出栈后再进栈，因此第 j 个出栈的元素是不确定的，答案为 D。

16. 某栈的输入序列为a, b, c, d，下面的4个序列中，不可能为其输出序列的是( )。

A. a, b, c, d
B. c, b, d, a
C. d, c, a, b
D. a, c, b, d

答案: C
解析: 如果d是第一个出栈的元素，那么在d出栈之前，a、b、c都必须已经入栈，这样的情况下，a和b不可能晚于c出栈。因此，C序列不符合栈的特性，其他序列都是可能的。

17. 若一个栈的输入序列是P, P, ..., P，输出序列是1, 2, 3, ..., n。若$P_3$=1, 则$P_1$的值( )。

A. 可能是2
B. 一定是2
C. 不可能是2
D. 不可能是3

答案: C
解析: 如果输入序列是P=1, 那么栈的顺序将按1, 2, 3, ...顺序出栈，符合栈的先进后出原则。P不能为2，因为这意味着出栈顺序不符合栈的特点，P不可能为2。

18. 已知一个栈的入栈序列是 1, 2, 3, 4，其出栈序列为$P_1, P_2, P_3, P_4$，则$P_2,P_4$不可能是( )。

A. 2, 4
B. 2, 1
C. 4, 3
D. 3, 4

答案: C
解析: 若4是出栈的第一个元素，那么在4出栈时，1、2、3都已经进栈且无法打破先进后出的规则。因此，无法形成4, 3这样的出栈顺序，C序列不可能实现。

19. 设栈的初始状态为空，当字符序列“n1_”作为栈的输入时，输出长度为3，且可用作C语言标识符的序列有( )个。

A. 4
B. 5
C. 3
D. 6

答案: C
解析: 标识符只能以英文字母或下画线开头，而不能是数字开头。故由n、1、三个字符组合成的标识符有n1_ ,n_1，_1n 和 _n1四种。第一种:n进栈再出栈,1进栈再出栈，进栈再出栈。第二种:n进栈再出栈，1进栈，进栈，出栈，1出栈。第三种:n进栈，1进栈，进栈，出栈，1出栈，n出栈。而根据栈的操作特性， _n1这种情况不可能出现，故选C。

20. 采用共享栈的好处是()。

A. 减少存取时间，降低发生上溢的可能
B. 节省存储空间，降低发生上溢的可能
C. 减少存取时间，降低发生下溢的可能
D. 节省存储空间，降低发生下溢的可能

答案: B
解析: 共享栈是指两个栈共享一个连续的存储空间。当两个栈的栈顶从两端向中间移动时，能够有效节省存储空间，减少发生上溢的可能性。

21. 设有一个顺序共享栈 Share[0:n-1]，其中第一个栈顶指针 top1 的初值为 -1，第二个栈顶指针 top2 的初值为 n，则判断共享栈满的条件是 ( )。

A. top2 - top1 == 1
B. top1 - top2 == 1
C. top1 -= top2
D. 以上都不对

答案：A

解释：共享栈的两个栈顶指针分别从两端向中间移动。当 top1 + 1 == top2 时，表示两个栈相遇，栈已满。因此条件应为 top2 - top1 == 1。

22. 【2009 统考真题】设栈 S 和队列 Q 的初始状态均为空，元素 a, b, c, d, e, g 依次进入栈 S。若每个元素出栈后立即进入队列 Q，且 7 个元素出队的顺序是 b, d, c, f, e, a, g，则栈 S 的容量至少是 ( )。

A. 1
B. 2
C. 3
D. 4

答案：C

解释：通过分析入栈和出栈的顺序，栈的最大深度达到 3。对于每个元素的入栈出栈顺序，需要至少 3 个位置才能保证满足出队的顺序。因此栈的容量至少是 3。

23. 【2010 统考真题】若元素 a, b, c, d, e, f 依次进栈，允许进栈、退栈操作交替进行，但不允许连续 3 次进行退栈操作，不可能得到的出栈序列是 ( )。

A. d, c, e, b, f, a
B. c, b, d, a, e, f
C. b, c, a, e, f, d
D. a, f, e, d, c, b

答案：D

解释：对于选项 D，要求不允许连续 3 次进行退栈操作，但 a, f, e, d, c, b 这个序列中，最后连续 3 次出栈操作不符合要求。因此选项 D 不可能得到。

24. 【2011 统考真题】元素 a, b, c, d, e 依次进入初始为空的栈中，若元素进栈后可停留、可出栈，直到所有元素都出栈，则在所有可能的出栈序列中，以元素 d 开头的序列个数是 ( )。

A. 3
B. 4
C. 5
D. 6

答案：B

解释：d 作为第一个出栈的元素后，a、b、c 必须在 d 之后出栈，而 e 可以任意选择出栈位置。因此可以有以下 4 种出栈序列：d, e, c, b, a, d, c, e, b, a, d, c, b, e, a,d，c，b，a，e

25. 【2013 统考真题】一个栈的入栈序列为 1, 2, 3, ..., n，出栈序列是 `P_1, P_1, P_3, ..., P_n`。若 P_2=3，则 P_3 可能取值的个数是 ( )。

A. n-3
B. n-2
C. n-1
D. n

答案：C

解释：当 P=3 时，序列可以包含从 3 开始的连续元素，因为 3 需要在栈顶弹出。其他值在 3 弹出后可以继续进行出栈。因此，P 可能取值的个数为 $n-1$，即除了 3 之外，其他元素都可以出栈。

26. 【2017 统考真题】下列关于栈的叙述中，错误的是 ( )。

I. 采用非递归方式重写递归程序时必须使用栈
II. 函数调用时，系统要用栈保存必要的信息
III. 只要确定了入栈次序，即可确定出栈次序
IV. 栈是一种受限的线性表，允许在其两端进行操作

A. 仅 I
B. 仅 I、II、III
C. 仅 I、III、IV
D. 仅 II、III、IV

答案：C

解释：

I 是错误的，因为并非所有递归都需要用栈来重写，某些递归可以通过简单的循环来实现（如斐波那契数列的迭代实现）。
II 是正确的，函数调用时，系统会使用栈保存函数的返回地址、局部变量等信息。
III 是错误的，入栈顺序不唯一决定出栈顺序，可能有多个出栈序列。
IV 是错误的，栈只允许在一端（栈顶）进行操作。

27. 【2018 统考真题】若栈 S1 中保存整数，栈 S2 中保存运算符，函数 F() 依次执行下述各步操作：

从 S1 中依次弹出两个操作数 a 和 b。
从 S2 中弹出一个运算符 op。
执行相应的运算 b op a。
将运算结果压入 S1 中。

假定 S1 中的操作数依次是 5, 8, 3, 2 (2 在栈顶)，S2 中的运算符依次是 *、-、+ ( + 在栈顶)。调用 3 次 F() 后，S1 栈顶保存的值是 ( )。

A. -15
B. 15
C. -20
D. 20

答案：B

解释：

第一次调用 F()：弹出 2 和 3，运算符是 +，执行 $3 + 2 = 5$，结果 5 压入 S1。
第二次调用 F()：弹出 5 和 8，运算符是 -，执行 $8 - 5 = 3$，结果 3 压入 S1。
第三次调用 F()：弹出 3 和 5，运算符是 *，执行 $5 * 3 = 15$，结果 15 压入 S1。

最终 S1 栈顶保存的值为 15。

28. 【2020 统考真题】对空栈 S 进行 Push 和 Pop 操作，入栈序列为 a, b, c, d, e，经过 Push、Push、Pop、Push、Pop、Push、Push、Pop 操作后得到的出栈序列是 ( )。

A. b, a, c
B. b, a, e
C. b, c, a
D. b, c, e

答案：D

解析：

根据题目操作的顺序，按栈的“先进后出”原则分析如下：

Push a → 栈内：a
Push b → 栈内：a, b
Pop → 出栈：b，栈内剩下：a
Push c → 栈内：a, c
Pop → 出栈：c，栈内剩下：a
Push d → 栈内：a, d
Push e → 栈内：a, d, e
Pop → 出栈：e，栈内剩下：a, d

最终出栈顺序为：b, c, e。

因此，出栈序列为 D：b, c, e。

解答题

01. 有5个元素，其入栈次序为 A,B,C,D,E，在各种可能的出栈次序中，第一个出栈元素为 C 且第二个出栈元素为 D 的出栈序列有哪几个?

解答：

分析过程如下：

第一个出栈元素为 C，第二个出栈元素为 D，意味着 C 和 D 必须按顺序在 A 和 B 之前出栈。
在 C 和 D 出栈后，剩下的元素 A, B, E 可以按照不同的顺序出栈。

具体的出栈序列为：

CDEBA
CDBEA
CDBAE

因此，以 C, D 开头的出栈序列有 3 种：CDEBA, CDBEA, CDBAE。

02. 若元素的进栈序列为 A,B,C,D,E，运用栈操作，能否得到出栈序列 B,C,A,E,D 和 D,B,A,C,E？为什么？

解答：

出栈序列 B,C,A,E,D：
- 这个出栈序列是可能的。
- 操作过程可以如下：
  1. A 进栈。
  2. B 进栈，B 出栈。
  3. C 进栈，C 出栈。
  4. A 出栈。
  5. D 进栈，E 进栈，E 出栈。
  6. D 出栈。
该出栈序列满足栈的操作规则，因此可以得到。
出栈序列 D,B,A,C,E：
- 这个出栈序列是不可能的。
- 原因：若出栈序列以 D 开头，意味着 A, B, C 必须已经入栈，但栈的特点是“先进后出”，所以 D 不可能早于 A, B, C 出栈。由于 C 必须在 A 和 B 之后出栈，B 和 A 不可能在 C 出栈前被弹出。因此，不可能得到这个出栈序列。

03. 假设以 "I" 和 "O" 分别表示入栈和出栈操作，栈的初态和终态均为空，入栈和出栈的操作序列可表示为仅由 "I" 和 "O" 组成的序列，可以操作的序列称为合法序列，否则称为非法序列。

1) 下面所示的序列中哪些是合法的？

A. IOIIOIOO
B. IOOIOIIO
C. IIIOIOIO
D. IOOIOC

解答：

A. IOIIOIOO → 合法序列
- 分析：每次出栈时，栈中总有元素，且最终栈为空。
B. IOOIOIIO → 非法序列
- 分析：前两个操作为 IOO，即连续两次出栈操作，但此时只有一个元素入栈，导致出栈操作非法。
C. IIIOIOIO → 非法序列
- 分析：虽然入栈和出栈次数匹配，但操作顺序不允许因为在操作过程中过早进行了出栈。
D. IOOIOC → 合法序列
- 分析：该序列满足栈操作规则，最终栈也为空。

2) 通过对 1) 的分析，写出一个算法，判定所给的操作序列是否合法。若合法，返回 true，否则返回 false（假定被判定的操作序列已存入一维数组中）。

解答：

算法思路：

遍历操作序列，使用两个计数器 i 和 k 分别记录入栈（I）的次数和出栈（O）的次数。
在任何时刻，如果 k（出栈次数）大于 i（入栈次数），则该序列为非法，因为不能在没有入栈的情况下出栈。
最终，如果入栈次数和出栈次数不相等，栈未能清空，也是非法序列。

int Judge(char A[]) { // 判断字符数组 A 中的操作序列是否合法
    int i = 0, j = 0, k = 0;  // i 为下标，j 和 k 分别为 I 和 O 的个数

    // 遍历字符串，直到字符串结束
    while (A[i] != '\0') {
        switch (A[i]) {
            case 'I':  // 入栈操作，入栈次数增 1
                j++;
                break;
            case 'O':  // 出栈操作，出栈次数增 1
                k++;
                // 若出栈次数大于入栈次数，非法
                if (k > j) {
                    printf("序列非法\n");
                    return false;
                }
                break;
        }
        i++;  // 继续遍历下一个操作符
    }

    // 最后判断入栈和出栈次数是否相等
    if (j != k) {
        printf("序列非法\n");
        return false;
    } else {
        printf("序列合法\n");
        return true;
    }
}

这个算法能够根据入栈和出栈操作判定序列是否合法，复杂度为 $O(n)$，其中 $n$ 是操作序列的长度。

04. 单链表中心对称判定算法

问题描述：
设单链表的表头指针为 L，结点结构由 data 和 next 两个域构成，data 域为字符型。设计一个算法来判断该链表的全部 $ n $ 个字符是否为中心对称。例如，字符串 xyx 和 xyyx 都是中心对称。

算法思想：

将链表的前一半元素（字符）依次压入栈中。
如果链表长度为奇数，跳过中间元素。
比较链表的后一半元素和栈中弹出的元素，若全部相等则表明链表中心对称，否则不对称。
如果遇到不相等的情况，立即返回不对称。

代码实现：

int checkSymmetry(LinkList *L, int n) {
    int i;
    char s[n / 2];  // 用栈保存前半部分字符
    LinkList *p = L->next;

    // 将前一半的字符压入栈
    for (i = 0; i < n / 2; i++) {
        s[i] = p->data;
        p = p->next;
    }

    // 如果 n 是奇数，跳过中间的字符
    if (n % 2 == 1) {
        p = p->next;
    }

    // 检测是否中心对称
    while (p != NULL && s[--i] == p->data) {
        p = p->next;
    }

    // 如果栈已经空了，说明对称
    if (i == -1) {
        return 1;  // 中心对称
    } else {
        return 0;  // 非中心对称
    }
}

解释：

使用一个数组 s[] 作为栈保存链表的前一半字符。
对于奇数个元素，跳过中间的字符。
后一半的字符依次和栈中的字符进行比较，若全部相等则说明链表中心对称。
如果比较过程中有不匹配的字符，立即返回不对称。

05. 两栈共享空间的入栈和出栈操作

问题描述：
两个栈 s1 和 s2 共享同一块存储区 [0, maxsize-1]，为了最大限度利用空间，采用栈顶相向、迎面增长的存储方式。设计 s1 和 s2 的入栈和出栈操作算法。

存储方式：

栈 s1 的栈底在存储区的左端，栈顶向右增长。
栈 s2 的栈底在存储区的右端，栈顶向左增长。
当 s1 和 s2 的栈顶指针相遇时，表示栈满。

栈的结构：

#define MAXSIZE 100  // 栈的最大容量
typedef int elemtp;  // 元素类型为整型

typedef struct {
    elemtp stack[MAXSIZE];  // 栈的共享空间
    int top[2];  // top[0] 为 s1 的栈顶指针，top[1] 为 s2 的栈顶指针
} Stack;

初始化：

top[0] = -1：s1 栈为空，栈顶指针为 -1。
top[1] = MAXSIZE：s2 栈为空，栈顶指针为 MAXSIZE。

入栈操作

int push(int i, elemtp x, Stack *S) {
    if (i < 0 || i > 1) {
        printf("栈号输入不对\n");
        return 0;
    }
    // 判断是否栈满
    if (S->top[1] - S->top[0] == 1) {
        printf("栈已满\n");
        return 0;
    }
    // 入栈
    if (i == 0) {
        S->stack[++S->top[0]] = x;  // s1 入栈
    } else {
        S->stack[--S->top[1]] = x;  // s2 入栈
    }
    return 1;
}

出栈操作

elemtp pop(int i, Stack *S) {
    if (i < 0 || i > 1) {
        printf("栈号输入不对\n");
        return -1;
    }
    if (i == 0) {
        // 判断 s1 是否为空
        if (S->top[0] == -1) {
            printf("s1 栈空\n");
            return -1;
        }
        return S->stack[S->top[0]--];  // s1 出栈
    } else {
        // 判断 s2 是否为空
        if (S->top[1] == MAXSIZE) {
            printf("s2 栈空\n");
            return -1;
        }
        return S->stack[S->top[1]++];  // s2 出栈
    }
}

解释：

push 函数用于入栈操作。根据栈号 i，选择对 s1 或 s2 进行入栈。如果栈满（两个栈顶指针相邻），则返回入栈失败。
pop 函数用于出栈操作。根据栈号 i，对 s1 或 s2 进行出栈操作。如果栈空，则返回出栈失败。

数据结构之栈

数据结构之栈

选择题

01. 栈和队列具有相同的()。

02. 栈是()。

03. ( ) 不是栈的基本操作。

04. 假定利用数组 a[n] 顺序存储一个栈，用 top 表示栈顶指针，用 top == -1 表示栈空并已知栈未满，当元素 x 进栈时所执行的操作为()。

05. 设有一个空栈，栈顶指针为 1000H，每个元素需要一个存储单元，执行 Push、Push、Pop、Push、Pop、Push、Pop、Push 操作后，栈顶指针的值为()。

06. 和顺序栈相比，链栈有一个比较明显的优势，即()。

07. 设链表不带头结点且所有操作均在表头进行，则下列最不适合作为链栈的是()。

08. 向一个栈顶指针为 top 的链栈(不带头结点)中插入一个 x 结点，则执行()。

09. 链栈(不带头结点)执行 Pop 操作，并将出栈的元素存入 x 中，应该执行()。

10. 经过以下栈的操作后，变量 x 的值为()

11. 3 个不同元素依次进栈，能得到()种不同的出栈序列。

12. 设 a, b, c, d, e, f 以所给的次序进栈，若在进栈操作时，允许出栈操作，则下面得不到的序列为()。

13. 用 S 表示进栈操作，用 X 表示出栈操作，若元素的进栈顺序是 1, 2, 3, 4，为了得到 1342 的出栈顺序，相应的 S 和 X 的操作序列为()

14. 若一个栈的输入序列是 1, 2, 3,…, n，输出序列的第一个元素是 n，则第 i 个输出元素是()

15. 一个栈的输入序列为 1, 2, 3,…, n，输出序列的第一个元素是 i，则第 j 个输出元素是()

16. 某栈的输入序列为a, b, c, d，下面的4个序列中，不可能为其输出序列的是( )。

17. 若一个栈的输入序列是P, P, ..., P，输出序列是1, 2, 3, ..., n。若\(P_3\)=1, 则\(P_1\)的值( )。

18. 已知一个栈的入栈序列是 1, 2, 3, 4，其出栈序列为\(P_1, P_2, P_3, P_4\)，则\(P_2,P_4\)不可能是( )。

19. 设栈的初始状态为空，当字符序列“n1_”作为栈的输入时，输出长度为3，且可用作C语言标识符的序列有( )个。

20. 采用共享栈的好处是()。

21. 设有一个顺序共享栈 Share[0:n-1]，其中第一个栈顶指针 top1 的初值为 -1，第二个栈顶指针 top2 的初值为 n，则判断共享栈满的条件是 ( )。

22. 【2009 统考真题】设栈 S 和队列 Q 的初始状态均为空，元素 a, b, c, d, e, g 依次进入栈 S。若每个元素出栈后立即进入队列 Q，且 7 个元素出队的顺序是 b, d, c, f, e, a, g，则栈 S 的容量至少是 ( )。

23. 【2010 统考真题】若元素 a, b, c, d, e, f 依次进栈，允许进栈、退栈操作交替进行，但不允许连续 3 次进行退栈操作，不可能得到的出栈序列是 ( )。

24. 【2011 统考真题】元素 a, b, c, d, e 依次进入初始为空的栈中，若元素进栈后可停留、可出栈，直到所有元素都出栈，则在所有可能的出栈序列中，以元素 d 开头的序列个数是 ( )。

25. 【2013 统考真题】一个栈的入栈序列为 1, 2, 3, ..., n，出栈序列是 `P_1, P_1, P_3, ..., P_n`。若 P_2=3，则 P_3 可能取值的个数是 ( )。

26. 【2017 统考真题】下列关于栈的叙述中，错误的是 ( )。

27. 【2018 统考真题】若栈 S1 中保存整数，栈 S2 中保存运算符，函数 F() 依次执行下述各步操作：

28. 【2020 统考真题】对空栈 S 进行 Push 和 Pop 操作，入栈序列为 a, b, c, d, e，经过 Push、Push、Pop、Push、Pop、Push、Push、Pop 操作后得到的出栈序列是 ( )。

解析：

解答题

01. 有5个元素，其入栈次序为 A,B,C,D,E，在各种可能的出栈次序中，第一个出栈元素为 C 且第二个出栈元素为 D 的出栈序列有哪几个?

02. 若元素的进栈序列为 A,B,C,D,E，运用栈操作，能否得到出栈序列 B,C,A,E,D 和 D,B,A,C,E？为什么？

03. 假设以 "I" 和 "O" 分别表示入栈和出栈操作，栈的初态和终态均为空，入栈和出栈的操作序列可表示为仅由 "I" 和 "O" 组成的序列，可以操作的序列称为合法序列，否则称为非法序列。

04. 单链表中心对称判定算法

05. 两栈共享空间的入栈和出栈操作

入栈操作

出栈操作

数据结构之栈

选择题

01. 栈和队列具有相同的()。

02. 栈是()。

03. ( ) 不是栈的基本操作。

04. 假定利用数组 a[n] 顺序存储一个栈，用 top 表示栈顶指针，用 top == -1 表示栈空并已知栈未满，当元素 x 进栈时所执行的操作为()。

05. 设有一个空栈，栈顶指针为 1000H，每个元素需要一个存储单元，执行 Push、Push、Pop、Push、Pop、Push、Pop、Push 操作后，栈顶指针的值为()。

06. 和顺序栈相比，链栈有一个比较明显的优势，即()。

07. 设链表不带头结点且所有操作均在表头进行，则下列最不适合作为链栈的是()。

08. 向一个栈顶指针为 top 的链栈(不带头结点)中插入一个 x 结点，则执行()。

09. 链栈(不带头结点)执行 Pop 操作，并将出栈的元素存入 x 中，应该执行()。

10. 经过以下栈的操作后，变量 x 的值为()

11. 3 个不同元素依次进栈，能得到()种不同的出栈序列。

12. 设 a, b, c, d, e, f 以所给的次序进栈，若在进栈操作时，允许出栈操作，则下面得不到的序列为()。

13. 用 S 表示进栈操作，用 X 表示出栈操作，若元素的进栈顺序是 1, 2, 3, 4，为了得到 1342 的出栈顺序，相应的 S 和 X 的操作序列为()

14. 若一个栈的输入序列是 1, 2, 3,…, n，输出序列的第一个元素是 n，则第 i 个输出元素是()

15. 一个栈的输入序列为 1, 2, 3,…, n，输出序列的第一个元素是 i，则第 j 个输出元素是()

16. 某栈的输入序列为a, b, c, d，下面的4个序列中，不可能为其输出序列的是( )。

17. 若一个栈的输入序列是P, P, ..., P，输出序列是1, 2, 3, ..., n。若\(P_3\)=1, 则\(P_1\)的值( )。

18. 已知一个栈的入栈序列是 1, 2, 3, 4，其出栈序列为\(P_1, P_2, P_3, P_4\)，则\(P_2,P_4\)不可能是( )。

19. 设栈的初始状态为空，当字符序列“n1_”作为栈的输入时，输出长度为3，且可用作C语言标识符的序列有( )个。

20. 采用共享栈的好处是()。

21. 设有一个顺序共享栈 Share[0:n-1]，其中第一个栈顶指针 top1 的初值为 -1，第二个栈顶指针 top2 的初值为 n，则判断共享栈满的条件是 ( )。

22. 【2009 统考真题】设栈 S 和队列 Q 的初始状态均为空，元素 a, b, c, d, e, g 依次进入栈 S。若每个元素出栈后立即进入队列 Q，且 7 个元素出队的顺序是 b, d, c, f, e, a, g，则栈 S 的容量至少是 ( )。

23. 【2010 统考真题】若元素 a, b, c, d, e, f 依次进栈，允许进栈、退栈操作交替进行，但不允许连续 3 次进行退栈操作，不可能得到的出栈序列是 ( )。

24. 【2011 统考真题】元素 a, b, c, d, e 依次进入初始为空的栈中，若元素进栈后可停留、可出栈，直到所有元素都出栈，则在所有可能的出栈序列中，以元素 d 开头的序列个数是 ( )。

25. 【2013 统考真题】一个栈的入栈序列为 1, 2, 3, ..., n，出栈序列是 P_1, P_1, P_3, ..., P_n。若 P_2=3，则 P_3 可能取值的个数是 ( )。

26. 【2017 统考真题】下列关于栈的叙述中，错误的是 ( )。

27. 【2018 统考真题】若栈 S1 中保存整数，栈 S2 中保存运算符，函数 F() 依次执行下述各步操作：

28. 【2020 统考真题】对空栈 S 进行 Push 和 Pop 操作，入栈序列为 a, b, c, d, e，经过 Push、Push、Pop、Push、Pop、Push、Push、Pop 操作后得到的出栈序列是 ( )。

解析：

解答题

01. 有5个元素，其入栈次序为 A,B,C,D,E，在各种可能的出栈次序中，第一个出栈元素为 C 且第二个出栈元素为 D 的出栈序列有哪几个?

02. 若元素的进栈序列为 A,B,C,D,E，运用栈操作，能否得到出栈序列 B,C,A,E,D 和 D,B,A,C,E？为什么？

03. 假设以 "I" 和 "O" 分别表示入栈和出栈操作，栈的初态和终态均为空，入栈和出栈的操作序列可表示为仅由 "I" 和 "O" 组成的序列，可以操作的序列称为合法序列，否则称为非法序列。

04. 单链表中心对称判定算法

05. 两栈共享空间的入栈和出栈操作

入栈操作

出栈操作

25. 【2013 统考真题】一个栈的入栈序列为 1, 2, 3, ..., n，出栈序列是 `P_1, P_1, P_3, ..., P_n`。若 P_2=3，则 P_3 可能取值的个数是 ( )。