数据结构笔记3栈和队列
数据结构笔记3栈和队列
前言
做一下栈和队列的笔记。
思维框架
习题
选择题
\16. 若已知一个栈的入栈序列是1,2,3,…,n，其输出序列为p1,p2,p3，…，pN,若pN是n，则pi是( )。
A. i B. n-i C. n-i+1 D. 不确定
\17. 一个栈的输入序列为123…n，若输出序列的第一个元素是n，输出第i（1<=i<=n）个元素是（ ）。
A. 不确定 B. n-i+1 C. i D. n-i
\18. 有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列？（ ）
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
\19. 设栈的输入序列是1，2，3，4,则（ ）不可能是其出栈序列。
A. 1，2，4，3， B. 2，1，3，4， C. 1，4，3，2，
D. 4，3，1，2， E. 3，2，1，4
20.栈和队列的共同点是（ ）。
A. 都是先进先出 B. 都是先进后出
C. 只允许在端点处插入和删除元素 D. 没有共同点
\21. 假设以数组A[m]存放循环队列的元素,其头尾指针分别为front和rear，则当前队列中的元素个数为（ ）。
A．(rear-front+m)%m B．rear-front+1
C．(front-rear+m)%m D．(rear-front)%m
\22. 设循环队列存储空间的下标范围是0…n-1，当队列尾指针为rear（初始时rear=0），队列长度为len时，循环队列中队头元素所在位置为_________。
A. rear - len B. rear – len +1
C. (rear – len + 1 ) % n D. (rear – len + n ) % n
\23. 循环队列存储在数组A[0…m]中，则入队时的操作为（ ）。
A. rear=rear+1 B. rear=(rear+1) mod (m-1)
C. rear=(rear+1) mod m D. rear=(rear+1)mod(m+1)
\24. 最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是 （ ）。
A. (rear+1) MOD n=front B. rear=front
C．rear+1=front D. (rear-l) MOD n=front
\27. 若输入序列为1，2，3，4，借助于一个输入受限的双向队
列，不可能得到的输出序列为＿＿。
A）2，4，3，1 B）3，1，2，4
C）4，1，3，2 D）4，2，3，1
16.D 17.B 18.C 19.D 20.C
21.A 22.D 23.D 24.B 25.B 26.C 27.D
判断题
（ ）栈是实现过程和函数等子程序所必需的结构。
（ ）栈是一种插入与删除操作都限定在表的一端进行的线性表。
（ ）若输入序列为1,2,3,4,5,6,则通过一个栈可以输出序列3,2,5,6,4,1。
（ ）在顺序存储结构表示的栈中删除一个元素时可能会引起栈内数据元素的移动。
（ ）栈既可以采用顺序存储结构表示也可以采用链式存储结构表示。
（ ）队列是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。
（ ）无论队列采用顺序存储结构还是采用链式存储结构，入队列和出队列操作的时间复杂度均为O(1)。
（ ）循环队列就是用循环链表表示的队列。
（ ）队列和栈都是运算受限的线性表，只允许在表的两端进行运算。
19.√ 20.√
21.√ 22.X 23.√ 24.X 25.√ 26.X 27.X
简答题
队列问题：火车出站序列
栈元素逆置
循环链表队列实现队列初始化、入队列、出队列。
思绪
这一部分其实挺有意思，在生活中也很常见。
比如浏览器的退出和进入就是一个栈，后进先出。
比如手机限定五个后台应用，当你打开多个应用的时候，先进先出。是一个队列
此外编程中常用到的递归就是一个栈。
更新地址：GitHub