3.7 习题
3.7.1知识点：栈的基本概念
一、选择题
1①下列哪种数据结构常用于函数调用（A ）。
Ａ．栈Ｂ．队列Ｃ．链表Ｄ．数组
2①编译器中通常以哪种数据结构处理递归程序调用（C ）
Ａ．队列Ｂ．数组C．栈D．记录
3①下列哪些数据结构可用来实现栈（D ）。
（1）链表（2）数组（3）树（4）图
Ａ．（2），（3）Ｂ．（2），（4）C．（1），（4）D．（1），（2）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．栈
能发生栈的上溢，在进行出栈运算时，可能发生栈的下溢。
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，要求绘出堆栈的处理过程。
答:
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．top5①链表仿真堆栈时，栈满的条件是（C）。
A．top6②在用链表仿真堆栈时（假设stack为栈顶指针），将new指针指向的节点执行入栈操作应执行（B ）
Ａ．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 }
