考研帮 > 数学 > 每日一练

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) 后缀表达式  

关于"最后阶段,真题的正确打开方式_备考经验_考研帮"15名研友在考研帮APP发表了观点

扫我下载考研帮

考研帮地方站更多

你可能会关心:

来考研帮提升效率

× 关闭