第三章 栈和队列：本章讲解两种特殊的线性表结构：栈和队列。要求重点理解栈的“先进后出”和队列的“先进先出”，并体会两种特殊的线性表结构的应用场景，在合适的场景中进行合理选择和应用。3.1栈和队列的特点:介绍栈、队列的操作特征和特殊性[单选题]设abcdef以所给次序进栈，若在进栈操作时允许退栈，则下列得不到的序列为（）
3.2顺序栈的基本操作:介绍顺序栈的存储实现方法，顺序栈中如何进行数据的插入、删除等操作。
3.3链栈的基本操作:介绍链栈的存储实现方法，链栈中如何进行数据的插入、删除等操作。
3.4栈的应用:通过具体案例，介绍栈在实际问题中的应用
3.5链队列的基本操作:介绍链队列的存储实现和数据插入、删除等基本操作的实现方法
3.6循环队列的基本操作:介绍循环队列的存储实现，理解循环队列的设计方法，介绍数据插入、删除等操作在循环队列中的实现
fedcba
bcafed
cabdef
dcefba
答案：cabdef
[单选题]若已知一个栈的进栈序列是1，2，3……n，其输出序列是p1，p2，p3，pn， 若p1=3，则p2为（）
一定是2
可能是2
一定是1
可能是1
[单选题]假定循环队列的队首和队尾指针分别为front和rear，则判断队满的条件为（ ）。
front = = 0
front= =rear
front+1 = = rear
(rear＋1) mod MAXSIZE = = front[判断题]队列和栈都是运算受限的线性表，只允许在表的两端进行运算。
错
对[单选题]循环队列A[0..m-1]存放其元素值，用front和rear分别表示队头和队尾，则当前队列中的元素数是( )。
rear-front+1
rear-front-1
(rear-front+m)%m
rear-front[判断题]不论栈是用数组实现，还是用链表实现，入栈和出栈的时间复杂度均为O(n)。
对
错[单选题]若栈采用顺序存储方式存储，两栈共享空间A[1..m]，top[i]代表第i个栈（i=1, 2）的栈顶，栈1的底在A[1]，栈 2的底在A[m]，则栈满的条件是（）。
|top[2]-top[1]|=0
top[1]=top[2]
top[1]+1=top[2]
top[1]+top[2]=m
[单选题]输入序列为ABC，若出栈的顺序为CBA时，经过的栈操作为（ ） 。
push,pop,push,push,pop,pop
push,pop,push,pop,push,pop
push,push,pop,pop,push,pop
push,push,push,pop,pop,pop[单选题]栈和队都是（ ）。
限制存取点的线性结构
链式存储的非线性结构
顺序存储的线性结构
限制存取点的非线性结构[单选题]链栈与顺序栈相比，有一个比较明显的优点是（ ）。
通常不会出现栈满的情况
会出现栈空的情况
删除操作更方便
插入操作更方便 [单选题]设计一个判别表达式中左，右括号是否配对出现的算法，采用（ ）数据结构最佳。
队列
线性表的链式存储结构
线性表的顺序存储结构
栈[单选题]某队列允许在其两端进行入队操作，但只允许在一端进行出队操作，若有元素a, b, c, d, e依次入队后再进行出队操作，则不可能得到的出队序列是（）。
b,a,c,d,e
d,b,c,a,e
d,b,a,c,e
e,c,b,a,d[单选题]有如下递归算法：int fact(int n){//n大于等于0 if(n<=0) return 1; else return n*fact(n-1);}则计算fact(n)需调用该函数的次数是（）。
n+2
n-1
n+1
n[单选题]栈在（）中有所应用。
函数调用
表达式求值
前三个选项都有
递归调用[单选题]设有一个递归算法如下 int fact(int n) { //n大于等于0 if(n<=0) return 1; else return n*fact(n-1); }则计算fact(n)需要调用该函数的次数为（ ）。
n
n+1
n+2
n-1
[单选题]（ ）的一个重要应用是在程序设计语言中实现递归。
栈
数组
队列
顺序表 [判断题]只有那种使用了局部变量的递归过程在转换成非递归过程时才必须使用栈。
对
错[判断题]栈是实现过程和函数等子程序所必需的结构。
错
对[判断题]通常使用队列来处理函数或过程的调用。
对
错[判断题]栈和队列的存储方式，既可以是顺序方式，又可以是链式方式
对
错
温馨提示支付 ￥1.00 元后可查看付费内容,请先翻页预览!
