栈和队列的基本概念
标签: 数据结构
学习人数: 10837


全屏播放
赞赏支持

类似于一个盒子

特性

先进后出:要想取a1,则必须先取出a2

 

 

队列

类似于小朋友排队

特性

先进先出:先排队的小朋友先打到饭

 

 

栈、队列和线性表的关系

栈和队列是受限的线性表,具体表现为栈只能在头节点后进行插入和删除,队列是在头结点删除,尾节点插入。

登录查看完整内容


课后作业

课后习题

 

【2018年真题】若栈S1中保存整数,栈S2中保存运算符,函数F() 依次执行下述各步操作:
(1)从 S1 中依次弹出两个操作数    a和b;
(2)从 S2 中弹出一个运算符    op;
(3)执行相应的运算    b op a;
(4)将运算结果压人    S1 中。
假定 S1 中的操作数依次是    5, 8, 3, 2( 2 在栈顶),S2 中的运算符依次是*, - , + ( + 在栈顶)。调用 3 次 F() 后, S1 栈顶保存的值是()。
A . -15            B. 15            C. -20            D. 20

参考答案:B


【2017年真题】下列关于栈的叙述中,错误的是()
1.采用非递归方式重写递归程序时必须使用栈
2.函数调用时,系统要用栈保存必要的信息
3.只要确定了入栈次序,即可确定出栈次序
4.栈是一种受限的线性表,允许在其两端进行操作
A.仅1            B. 仅1、2、3        C. 仅1、3、4        D. 仅2、3、4

参考答案:C


【2015年真题】已知程序如下:

int S(int n)  
{     
    return (n<=0)?0:s(n-1)+n;  
}  
void main()  
{  
    cout << S(1);  
}  

程序运行时使用栈来保存调用过程的信息,自栈底到栈顶保存的信息依次对应的是()。
A.main()→S(1)→S(0)            B.S(0)→S(1)→main()
C.main()→S(0)→S(1)            D.S(1)→S(0)→main() 

参考答案:A


【2013年真题】一个栈的入栈序列为1,2,3,...,n,其出栈序列是p1,p2,p3,...,pn。若p2 = 3,则p3可能取值的个数是()
 A. n - 3             B. n - 2             C. n - 1             D. 无法确定

参考答案:C
答案解析:除了 3 本身以外,其他的值均可以取到,因此可能取值的个数为n - 1。 


【2011年真题】元素a,b,c,d,e依次进入初始为空的栈中,若元素进栈后可停留、可出栈,直到所有元素都出栈,则在所有可能的出栈序列中,以元素d开头的序列个数是()
A.3
B.4 
C.5
D.6 

参考答案:B
答案解析:出栈顺序必为d_c_b_a_,e的顺序不定,在任意一个“_”上都有可能。 


【2010年真题】若元素 a、b、c、d、e、f 依次进栈,允许进栈、退栈操作交替进行,但不允许连续三次进行退栈操作,则 不可能得到的出栈序列是()。 
A.d c e b f a         B.c b d a e f         C.b c a e f d         D.a f e d c b

参考答案:D
答案解析:考查限定条件的出栈序列。 
A 可由 in,in,in,in,out,out,in,out,out,in,out,out 得到; 
B 可由 in,in,in,out,out,in,out,out,in,out,in,out 得到; 
C 可由 in,in,out,in,out,out,in,in,out,in,out,out 得到; 
D 可由 in,out,in,in,in,in,in,out,out,out,out,out 得到,
但题意要求不允许连续三次退栈操作,故 D 错。 


登录后发布评论

暂无评论,来抢沙发