2.1 栈的概念、实现及应用

2.1 栈的概念、实现及应用

2.1 栈的概念、实现及应用

一、选择题

　　1．选择题题目部分
　　● 堆栈操作中， （1） 保持不变。
　　（1）A．堆栈的顶 B．堆栈中的数据 C．堆栈指针 D．堆栈的底
　　● 一个栈的入栈元素序列是1、2、3、4、5，若允许出栈操作可在任意可能的时刻进行，则下面的序列中，不可能出现的出栈序列是 （2） 。
　　（2）A．3、4、2、5、1 B．2、5、4、1、3
　　C．2、3、1、5、4 D．3、5、4、2、1
　　● 设一个栈的输入序列是 1、2、3、4、5，则下列序列中，是栈的合法输出序列的是 （3） 。
　　（3）A．5、1、2、3、4 B．4、5、1、3、2
　　C．4、3、1、2、5 D．3、2、1、5、4
　　● 若栈采用顺序存储方式存储，现两栈共享空间V[m]，top[i]代表第i个栈（i =1,2）栈顶，栈空时栈1的底在v[0]，top[1]=0，栈2的底在V[m-1]，top[2]=m-1，则栈满的条件是 （4） 。
　　（4）A．top[1] = top[2] B．top[1] + 1 = top[2]
　　C．top[1] + top[2] = m D．top[1]  1 = top[2]
　　● 判断一个表达式中左右括号是否匹配，采用 （5） 实现较为方便。
　　（5）A．线性表的顺序存储 B．队列 C．线性表的链式存储 D．栈
　　● 在做进栈运算时，应先判别栈是否 （6） ，在做退栈运算时，应先判别栈是否 （7） 。如果栈中元素为n个，做进栈运算时发生上溢，则说明该栈的最大容量为 （8） 。
　　为了增加内存空间的利用率和减少溢出的可能性，由两个栈共享一片连续的内存空间时，应将两栈的 （9） 分别设在这片内存空间的两端，这样，当 （10） 时，才产生上溢。
　　（6）A．空 B．满 C．上溢 D．下溢
　　（7）A．空 B．满 C．上溢 D．下溢
　　（8）A．n1 B．n C．n+1 D．n/2
　　（9）A．长度 B．深度 C．栈顶 D．栈底
　　（10）A．两个栈的栈顶同时到达栈空间的中心点
　　B．其中一个栈的栈顶到达栈空间的中心点
　　C．两个栈的栈顶在栈空间的某一位置相遇
　　D．两个栈均不空，且一个栈的栈顶到达另一个栈的栈底
　　● 若一个栈以向量V[1…n]存储，初始使栈指针top为n，则下面x入栈的正确操作是（11） 。设top指针指向栈顶元素。
　　（11）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；
　　● 一个递归算法必须包括 （12） 。
　　（12）A．递归部分 B．终止条件和递归部分 C．迭代部分 D．终止条件和迭代部分
　　● 执行完下列语句段后，i值为： （13） 。

　　

　　（13）A．2 B．4 C．8 D．无限递归
　　● 一个栈的输入序列是1,2,3,…,n，其输出序列为p1,p2,p3,…,pn；若p1=3，则p2为 （14） 。
　　（14）A．可能是2 B．一定不是2 C．可能是1 D．一定是1
　　● 表达式a×(b+c)-d 的后缀表达式是 （15） 。
　　（15）A．abcd×+-B．abc+×d- C．abc×+d-D．-+×abcd
　　2．选择题练习答案与分析
　　题号（1）答案 D
　　习题分析：
　　堆栈是另一种特殊的线性表，它限定只能够在一端进行插入和删除运算，这一端称为栈顶，而不能够进行插入和删除运算的那一端称为栈底。因此也称其为“后进先出（LIFO）”线性表。从而也不难得出在堆栈操作中，堆栈的底是保持不变的。
　　题号（2）答案 B
　　习题分析：
　　答此类题需要根据栈的先进后出特性进行判断，依照以下步骤可以很方便地找到答案：
　　（1）选择出栈序列的第一个元素A，入栈序列中在A之前的元素必须按照反序出现在出栈序列中，如果不按照反序出栈，则此出栈序列不合法，否则执行下一步。
　　（2）从入栈序列和出栈序列中将元素A删除，如果删除元素A后出栈序列为空，则说明此出栈序列合法，否则回到上一步继续执行。比如，在B选项中，第一个出栈元素为2，在2之前入栈元素的入栈次序为1，由于只有一个元素，故无论如何将会逆序出栈；在序列中剔除2，则入栈序列为“1、3、4、5”，出栈序列变为“5、4、1、3”；分析元素5，在新的入栈序列中，5之前的元素入栈序列为“1、3、4”，而出栈序列为“4、1、3”，不满足逆序出栈的条件，所以选项B错误。
　　题号（3）答案 D
　　习题分析：
　　分析情况如表2-1所示。

表2-1 选择题第3题分析表

　　

选    项	A	B	C
第一个出栈素	5	4	4
入栈序列	1、2、3、4	1、2、3	1、2、3
实际出栈序列	1、2、3、4	1、3、2	3、1、2
判断	未逆序，不合法	未逆序，不合法	未逆序，不合法

　　题号（4）答案 D
　　习题分析：
　　本题属于栈的应用，两栈合用一个数组空间，通过栈空时top的值可知：top指向了下一个元素入栈的数组下标位置，因此如果“top[1]=top[2]”可知当前还有一个元素空间未用，此后再有一个元素入栈则栈满。
　　（1）如果栈1执行入栈操作，则top[1]++；
　　（2）如果栈2执行入栈操作，则top[2]--。
　　因此，无论是情况（1）还是情况（2），最终的结果都将是“top[1]-1=top[2]”。
　　题号（5）答案 D
　　习题分析：
　　要判断表达式中左右括号是否匹配，最简单的方法是采用栈来实现，从左到右分析，遇到左括号压栈，遇到右括号弹栈，最后看栈是否为空，就知道是否匹配。

题号	（6）	（7）	（8）	（9）	（10）
答案	B	A	B	D	C

　　习题分析：
　　根据栈的定义，在进行入栈操作时，要检查栈是否已满；而出栈操作时，则要检查栈是否为空。因此，（6）、（7）的答案分别为B、A。
　　如果栈中元素为n个，作进栈运算时发生上溢，则说明该栈的最大容量为n。
　　（9）、（10）两空考查的是对栈基本概念的应用。当两个栈共用一片连续的存储空间时，应该将两个栈的栈底分别设在内存空间的两端，进行入栈操作时，两个栈分别向相反的方向添加元素，这样可以确保两个栈在栈空间的某一位置相遇，从而发生上溢。
　　题号（11）答案 C
　　习题分析：
　　这道题目的独特之处在于：题中已经说明向量的大小为n，而栈顶指针此时已指向n，一般情况下，这说明已经栈满，从而不能再进行入栈的操作。也就是说无答案可选，这正是此题的巧妙之处。
　　一般情况下，都是使用一维数组中的小下标作为栈底，下标大的位置存储栈顶元素。但并不是说这是唯一的选择，根据程序员的喜好，也可以使用下标大的位置存储栈底，而用下标小的位置存储栈顶元素；此题正好是这种情况。
　　正常情况下，元素入栈时，栈顶指针加1，这里刚好相反，栈顶指针应该减1。因此答案为C。
　　题号（12）答案 B
　　习题分析：
　　一个递归算法必须包括递归部分及递归出口（终止条件）。
　　题号（13）答案 B
　　习题分析：
　　本题考查对于递归函数的理解。任何一个递归函数都有一个递归出口。而其递归部分可以理解成一种递推关系。在本题中，其递归出口为x=0。当x=0时，f(0)=2。根据递推关系，可以得出：

f(1)=1×f(0)=2；
f(f(1))=f(2)=2×f(1))=2×2=4。

　　题号（14）答案 A
　　习题分析：
　　p1=3代表3最先出栈，那么此时栈内的元素必然为2、1。如果此时进行出栈操作，那么p2=2；若此时进行入栈操作，比如4入栈，或者经过多次入栈操作之后再进行出栈操作，那么p2=4或等于其他值。在这种情况下，p2的值就不确定了。因此，只能说p2可能为2。
　　题号（15）答案 B
　　习题分析：
　　这道题目主要考查对中缀表达式与后缀表达式相互转换的理解。根据其转换算法可知，正确答案为B。
　　3．训练自测表（如表2-2所示）

表2-2 选择题练习自测表

题    号	考  查  点	得    分
（1）	栈定义的理解
（2）	栈可能的输出序列
（3）	栈的合法输出序列
（4）	栈满的条件
（5）	栈的应用
（6）～（10）	栈的定义和应用
（11）	入栈操作
（12）	递归的定义

续表

题    号	考  查  点	得    分
（13）	递归的理解
（14）	栈输出序列的应用
（15）	后缀表达式

2.1 栈的概念、实现及应用