3.7 习题
3.7.1知识点：栈的基本概念
一、选择题
1① 下列哪种数据结构常用于函数调用（ A ）。
Ａ．栈 Ｂ．队列 Ｃ．链表 Ｄ．数组 2① 编译器中通常以哪种数据结构处理递归程序调用（ C ） Ａ．队列
Ｂ．数组
C．栈 D．记录
3① 下列哪些数据结构可用来实现栈（ D ）。 （1）链表
（2）数组
（3）树 （4）图
D．（1），（2）
Ａ．（2），（3） Ｂ．（2），（4） C．（1），（4）
4② 元素的入栈序列是a,b,c,d，则栈的不可能的输出序列是（ C ）。 A．dcba B．abcd C．dcab D．cbad
5② 已知栈的最大容量为4。若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行,则可能出现的出栈序列为（ C ）。
A．5，4，3，2，1，6 B．2，3，5，6，1，4 C．3，2，5，4，1，6 D．1，4，6，5，2，3
6② 若以S和X分别表示进栈和退栈操作，则对初始状态为空的栈可以进行的栈操作系列是（ D ）。
A．SXSSXXXX B．SXXSXSSX C．SXSXXSSX D．SSSXXSXX 7① 对于栈操作数据的原则是（ B ）。【青岛大学 2001】
A． 先进先出 B．后进先出 C．后进后出 D．不分顺序 8① 栈在（ D ）中应用。【中山大学 1998】
A．递归调用 B．子程序调用 C．表达式求值 D．A，Ｂ，Ｃ 9② 一个栈的输入序列为123…n，若输出序列的第一个元素是n，输出第i（1<=i<=n）个元素是（B ）。【中山大学 1999】
A．不确定 B．n-i+1 C．i D．n-i
10② 若一个栈的输入序列为1,2,3,…,n，输出序列的第一个元素是i，则第j 个输出元素是（D ）。【武汉大学 2000】
A．i-j-1 B．i-j C．j-i+1 D．不确定的 11② 有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列？（ C ）【北方交通大学 2001】
A．5 4 3 6 1 2 B．4 5 3 1 2 6 C．3 4 6 5 2 1 D．2 3 4 1 5 6
12② 输入序列为ABC，可以变为CBA 时，经过的栈操作为（B ）【中山大学 1999】 A．push,pop,push,pop,push,pop B．push,push,push,pop,pop,pop
C．push,push,pop,pop,push,pop D．push,pop,push,push,pop,pop
13② 设计一个判别表达式中左，右括号是否配对出现的算法，采用（ D ）数据结构最佳。【西安电子科技大学 1996】
A．线性表的顺序存储结构 B．队列 C．线性表的链式存储结构 D．栈 二、填空题 1① 栈是一种特殊的线性表，允许插入和删除运算的一端称为 栈顶 ，不允许插入和删除运算的一端称为 栈底 。 2① 对于顺序存储的栈，因为栈的空间是有限的，在进行 入栈 运算时，可能发生栈的上溢，在进行 出栈 运算时，可能发生栈的下溢。
3① 表达式求值是 栈 应用的一个典型例子。
4① 栈是__一种特殊_____的线性表，其运算遵循____先进后出_____________的原则。【北京科技大学 1997】
5② 设有一个空栈， 栈顶指针为1000H（ 十六进制） ， 现有输入序列为1 ， 2 ， 3 ， 4 ， 5 ， 经过PUSH,PUSH,POP,PUSH,POP,PUSH,PUSH 之后，输出序列是 2,3，_______，而栈顶指针值是_1000C_____H。设栈为顺序栈，每个元素占4 个字节。【西安电子科技大学 1998】
6② 用S 表示入栈操作，X 表示出栈操作，若元素入栈的顺序为1234，为了得到1342 出栈顺序，相应的S和X 的操作串为_________sxssxsxx__________。【西南交通大学 2000】 三、判断题
（ F ）1① 栈具有先进先出的特性。 （ T ）2① 栈用于实现子程序调用。 （ F ）3① 栈和链表是两种不同的数据结构。 （ T ）4① 栈顶的位置是随着操作而变化的。 （ T ）5① 栈和队列逻辑上都是线性表。
（ T ）6① 栈是实现过程和函数等子程序所必需的结构。【合肥工业大学 2000】 （ F ）7② 即使对不含相同元素的同一输入序列进行两组不同的合法的入栈和出栈组合操作，所得的输出序列也一定相同。【北京邮电大学 1999】
（ T ）8② 若输入序列为1,2,3,4,5,6,则通过一个栈可以输出序列3,2,5,6,4,1。【上海海运学院1995】
（ F ）9② 若输入序列为1，2，3，4，5，6，则通过一个栈可以输出序列1，5，4，6，2，3。【上海海运学院 1999】 四、简答题
1① 什么是栈？试举两个应用实例。 2① 简述栈和线性表的差别。
3③ 计算表达式 6*3/2-5*1，要求绘出堆栈的处理过程。
答:
操作数栈 第一次 6 第二次 6 第三次 3 6 18 第五次 18 第六次 2 18 第七次 9 第八次 9 第九次 5 9 第十次 5 9 第十一次 1 5 9 第十二次 5 9 第十三次 4
运算符栈 空 * 空 * 空 / 空 / 空 - 空 - * - 空 * - 空 - 空 5② 有5 个元素，其入栈次序为：A，B，C，D，E，在各种可能的出栈次序中，以元素C，D 最先出栈（即C 第一个且D 第二个出栈）的次序有哪几个？【西南交通大学 2000】
3.7.2知识点：栈的存储
一、选择题
1① 如果以链表作为栈的存储结构，则入栈操作时（ B ）。
A．必须判别栈是否满 B．对栈不作任何判别 C．必须判别栈是否空 D．判别栈元素的类型
2① 上溢现象通常出现在（ A ）。
A．顺序栈的入栈操作过程中 B．顺序栈的出栈操作过程中 C．链栈的入栈操作过程中 D．链栈的出栈操作过程中 3① 判定一个栈ST（最多元素为m0）为空的条件是（ B ）
Ａ．ST->top！=0 Ｂ．ST->top= =0 Ｃ．ST->top！=m0 Ｄ．ST->top= =m0 4① 链表仿真堆栈时，栈空的条件是（B ）。
A．top A．top Ａ．new->next=stack->next； stack=new； Ｂ．new->next=stack； stack=new； Ｃ．new->next=stack；stack=new->next； Ｄ．stack=new；stack->next=new->next； 7② 若一个栈以向量V[1．．n]存储，初始栈顶指针top 为n+1，则下面x 进栈的正确操作是（ B ）。【南京理工大学 1998】 A．top=top+1; V [top]=x B．V [top] =x; top=top+1 C．top=top-1; V [top]=x D．V [top]=x; top=top-1 8② 执行完下列语句段后，i 值为：（ B）。【浙江大学 2000】 int f（int x） { return （（x>0） ? x* f（x-1）:2）;} int i ; i =f（f（1））; A． 2 B． 4 C． 8 D． 无限递归 二、填空题 1② 以下语句是堆栈的入栈操作，用全局数组stack仿真堆栈，数组类型是int，大小是MaxSize，栈顶指针是top，初始化等于－1。 01 void push（int value） 02 { 03 if（top>MaxSize-1） 04 return –1; 05 else 06 { 07 top++; 08 stack[top]=value; 09 } 10 }
