第三章 栈与队列：栈和队列是两种重要的数据结构，它们的逻辑结构和线性表相同。其特点在于运算受到了限制，栈按照“后进先出”的规则进行操作，队列按“先进先出”的规则进行操作，因此它们也被称为受限的线性表。3.1栈的定义与顺序栈:栈是限制在表的一端进行插入和删除的线性表。允许插入和删除的一端为栈顶，另一端为栈底，当表中没有元素时称为空栈。栈的基本操作是插入和删除，一般称为入栈和出栈。栈按照存储结构可分为顺序栈和链栈两类，顺序栈一般用数组来实现，链栈用链指针连接数据元素节点来实现。[判断题]在顺序栈空的情况下不能进行出栈操作，否则将产生“下溢”。
3.2链栈与栈的应用:链栈是栈的一种实现形式，通过链指针连接数据元素来实现。栈的应用包括表达式求值，括号匹配。
3.3队列的定义及顺序队列:队列是限制在表的一段进行插入，另一端进行删除的的线性表，分别对应于入队和出队操作。队列按照存储结构可分为顺序队列和链队列两类，顺序队列一般用数组实现，链队列用链指针连接数据元素节点来实现。
3.4链队列与队列的应用:链队列是队列的一种实现形式，通过链指针连接数据元素来实现。
3.5栈在消除递归中的应用举例:递归是一种常用的算法设计思想。递归算法通常描述简洁、思路清晰、程序可读性和可维护性好，但递归程序的执行因其时间和空间开销的增大而效率很低。如何将递归过程变为非递归执行过程？结合函数调用特征以及栈的工作特征，因此在消除递归函数时通常使用栈这种数据结构。本节主要通过一个实例介绍栈在消除递归过程中的应用。
3.6栈与队列的综合应用:栈与队列的综合应用
错
对
答案：对
[判断题]栈和队列都是限制存取位置的线性表。
错
对[判断题]若元素a,b,c,d,e,f依次进栈，允许进栈、退栈操作交替进行，则不可能得到出栈序列：a,f,e,d,c,b。
对
错[判断题]入栈操作和入队列操作在链式存储结构上实现时一般不需要考虑栈溢出的情况。
对
错[判断题]同一个栈内的各个数据元素类型可以不一致。
错
对[多选题]以下说法中正确的是（ ）
队列被称为“先进后出”表。
栈是一种操作不受限制的线性表。
栈是一种只允许在一端进行插入和删除的线性表。
当队列中无数据元素时，称空队列。 [多选题]以下说法中错误的是( ) 。
top=-1时为空栈，元素进栈时指针top不断减1。
栈不能对输入序列部分或全局求逆。
当top等于数组最大下标时则栈满。
利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，这种形式的栈称为顺序栈。[多选题]已知一个栈的进栈序列是a1,a2,a3....an.其输出序列为1,2,3...n,若a3=1则a1为（ ）
不可能是3
一定是2
可能是3
可能是2
不可能是2[单选题]栈的特点是（ ）
进优于出
出优于进
先进后出
先进先出[单选题]设循环队列的容量为20，序号从0到19，经过一系列的入队和出队后，front=5,rear=10,问队列中有多少个元素（采用节省一个队列存储空间的方式）。
4
5
7
6[单选题]一个队列的入队序列是1，2，3，4，则队列的出队序列是（ ）
3，2，4，1
1，2，3，4
1，4，3，2
4，3，2，1[单选题]一般情况下，将递归算法转换成等价的非递归算法应该设置（ ）
数组
栈
队列
栈或队列[单选题]设用链表作为栈的存储结构则退栈操作（ ）
必须判别栈是否为满
对栈不作任何判别
必须判别栈是否为空
判别栈元素的类型
温馨提示支付 ￥1.00 元后可查看付费内容,请先翻页预览!
