习题
单项选择题
- 栈和队列具有相同的 _______ 。
- 栈是一种 _______ 。
- 下列选项中， _______ 不是栈的基本操作。
- 假定用数组 a[n] 存储一个栈，初始栈顶指针 top=-1，则元素 x 入栈的操作是 _______ 。
- 假定用数组 a[1…n] 存储一个栈，初始栈顶指针 top=1，则元素 x 入栈的操作是 _______ 。
- 假定用数组 a[1…n] 存储一个栈，初始栈顶指针 top=n+1，则元素 x 入栈的操作是 _______ 。
- 设有一个空栈，栈顶指针为 1000H，栈向高地址方向增长，每个元素占一个存储单元，执行 push、push、pop、push、pop、push、pop、push 操作后，栈顶指针为 _______ 。
- 和顺序栈相比，链栈有一个比较明显的优势，即 _______ 。
- 设链表不带头结点且所有操作均在表头进行，则下列最不适合作为链栈的是 _______ 。
- 向一个栈顶指针为 top 的链栈（不带头结点）中插入一个 x 结点，则执行 _______ 。
- 链栈（不带头结点）执行 pop 操作，并将出栈的元素存在 x 中，应该执行 _______ 。
- 经过以下栈的操作后，变量 x 的值为 _______ 。InitStack(st); Push(st, a); Push(st, b); Pop(st, x); GetTop(st, x);
- 3 个不同元素依次入栈，能得到 _______ 种不同的出栈序列。
- 设 (a, b, c, d, e, f) 以所给的次序入栈，若在入栈操作时，允许出栈操作，则下面不会出现的出栈序列为 _______ 。
- 4 个元素依次入栈的次序为 (a, b, c, d)，则以 (c, d) 开头的出栈序列的个数为 _______ 。
- 用 S 表示入栈操作，用 X 表示出栈操作，若元素的入栈顺序是 1234，为了得到 1342 的出栈顺序，相应的 S 和 X 的操作序列为 _______ 。
- 若栈的输入序列是 1, 2, 3, ⋯, n，输出序列的第一个元素是 (n)，则第 i 个输出元素是 _______ 。
- 若栈的输入序列是 1, 2, 3, ⋯, n，输出序列的第一个元素是 (i)，则第 j 个输出元素是 _______ 。
- 某栈的输入序列为 ( a, b, c, d )，下面的 4 个序列中，不可能为其输出序列的是 _______ 。
- 若栈的输入序列是 ( P_1, P_2, \cdots, P_n )，输出序列是 ( 1, 2, 3, \cdots, n )，若 ( P_3 = 1 )，则 ( P_1 ) 的值是 _______ 。
- 若栈的输入序列是 ( P_1, P_2, \cdots, P_n )，输出序列是 ( 1, 2, 3, \cdots, n )，若 ( P_3 = 3 )，则 ( P_1 ) 的值是 _______ 。
- 已知栈的入栈序列是 ( 1, 2, 3, 4 )，其出栈序列为 ( P_1, P_2, P_3, P_4 )，则 ( P_2, P_4 ) 不可能是 _______ 。
- 设栈的初始状态为空，当字符串列 “n1_” 作为栈的输入时，输出长度为 3，且可用作 C 语言标识符的序列有 _______ 个。
- 采用共享栈的好处是 _______ 。
- 设有一个顺序共享栈 Share[0:n-1]，其中第一个栈顶指针 top1 的初值为 -1，第二个栈顶指针 top2 的初值为 n，则判断共享栈满的条件是 _______ 。
- 【2009 统考真题】 设栈 S 和队列 Q 的初始状态均为空，元素 abcdefg 依次进入栈 S。若每个元素出栈后立即进入队列 Q，且 7 个元素出队的顺序是 bdefacg，则栈 S 的容量至少是 _______ 。
- 【2010 统考真题】 若元素 a, b, c, d, e, f 依次入栈，允许入栈、出栈操作交替进行，但不允许连续 3 次进行出栈操作，不可能得到的出栈序列是（）。
- 【2011 统考真题】 元素 a, b, c, d, e 依次进入初始为空的栈中，若元素入栈后可停留、可出栈，直到所有元素都出栈，则在所有可能的出栈序列中，以元素 d 开头的序列个数是（）。
- 【2013 统考真题】 一个栈的入栈序列为 1, 2, 3, ⋯, n，出栈序列是 ( P_1, P_2, P_3, ⋯, P_n )。若 ( P_2 = 3 )，则 ( P_3 ) 可能取值的个数是（）。
- 【2020 统考真题】 对空栈 S 进行 Push 和 Pop 操作，入栈序列为 a, b, c, d, e，经过 Push、Push、Pop、Push、Pop、Push、Push、Pop 操作后得到的出栈序列是（）。
- 【2022 统考真题】 给定有限符号集 S，in 和 out 均为 S 中所有元素的任意排列。对于初始为空的栈 ST，下列叙述中，正确的是（）。