3.5习题
一、名词解释
（1）栈
栈是限制在表的一端进行插入和删除操作的线性表。
允许插入、删除的这一端称为栈顶，另一个固定端称为栈底。 栈的顺序结构：利用顺序存储方式实现的栈 称为 顺序栈。 栈的链式结构：用链式存储结构实现的栈 称为 链栈。 （2）队
队是一种“先进先出” (FIFO---First In First Out)的数据结构，即插入操作在表一端进行，而删除操作在表的另一端进行，这种数据结构称为 队列。 把允许插入的一端称为队尾(rear) ，把允许删除的一端称为队头(front)。 队的顺序结构：顺序存储的队称为 顺序队。 队的链式结构：采用链式存储结构的队称为 链队。
二、判断题
（1）栈和队列都是特殊的线性表。 ( √ )
（2）栈和队列都将插入和删除操作限制在表的端点处进行。 (√ ) （3）只允许在表的一端进行插入和删除操作的线性表称为栈。(√) （4）没有元素的栈称为空栈，空栈用不着栈顶指针。( × ) （5）只要栈不空，就能任意删除栈的元素。 (× )
（6）栈允许删除的一端称为栈顶，而栈底元素是不能删除的。 (× ) （7）对采用链式存储结构的栈进行操作不必判断溢出。 (√ ) （8）元素进出队列一定满足“先进先出”的规律。 (√ ) （9）链队列 不存在溢出问题。 (√ )
（10）在链队列中删除一个元素是在链表的最前端进行的。 (√ ) 三、单项选择题
（1）栈和队列的共同之处在于它们具有相同的( A )。 A．逻辑特性 B．物理特性 C．运算方法 D．元素类型
（2）栈和队列都是特殊的线性表，其特殊性在于( C )。 A．它们具有一般线性表所没有的逻辑特性 B．它们的存储结构比较特殊 C．对它们的使用方法做了限制 D．它们比一般线性表更简单
（3）若5个元素的出栈序列为1，2，3，4，5，则进栈序列可能是( )。 A．2，4，3，1，5 B．2，3，1，5，4
C．3，1，4，2，5 D．3，1，2，5，4
（4）某队列初始为空，若它的输入序列为a，b，c，d，它的输出序列应为( )。
A．a，b，c，d B．d，c，b，a C．a，c，b，d D．d，a，c，b
（5）当3个元素的进栈序列给定以后，由这3个元素组成的可能的出栈序列应该有( )。
A．5种 B．6种 C．4种 D．3种
（6）若栈采用顺序存储结构，正常情况下，往堆栈中插入一个元素，栈顶指针top的变化是( )。
A．不变 B．top=0 C．--top D．top++
（7）若栈采用顺序存储结构，正常情况下，删除 栈 中一个元素，栈顶指针top的变化是( )。
A．不变 B．top=0 C．top-- D．top++ （8）若队列采用顺序存储结构，元素的排列顺序( B )。 A．与元素的值的大小有关
B．由元素进入队列的先后顺序决定 C．与队头指针和队尾指针的取值有关 n与作为顺序存储结构的数组的大小有关
（9）若非空栈采用含头结点的链式存储结构，栈顶指针为top，删除堆栈的一个元素的过程是依次执行：p=top，( B )，free(p)。
A．top=p->next B．top->next =p->next
C．p=top D．p=p-> next
（10）若队列采用链式存储结构，队头元素指针与队尾元素指针分别为front和rear，向队列中插入一个由p所指的新结点的过程是依次执行：( )，rear=p。
A．rear=p B．front=p
C．rear->next=p D．front->next=p
（11）若非空队列采用链式存储结构，队头元素指针与队尾元素指针分别为front和rear，删除队列的一个元素的过程是依次执行：p=front，( )，free(p)。
A．rear=p B．rear=p->next C．rear=p->next D．front=p->next
（12）在循环队列中，若front与rear分别表示队头元素和队尾元素的位置，则判断循环队列 队空 的条件是( C )。
A．front=rear+1 B．rear=front+1
C．front==rear D．rear=front-1
四、填空题
（1）栈和队列的逻辑结构都是__线性__结构。
（2）栈的插入和删除操作都是在_栈顶_进行，而队列的插入操作在_队尾___进行，删除操作在__队头__进行。
（3）对某栈执行删除操作时，只有在_栈中只有一个元素的___情况下，才会将栈底元素删除。
（4）在具体的程序设计过程中，栈的顺序存储结构一般是利用一个_数组___描述的，同时还要定义一个整型变量来_给出栈顶元素的位置___。
（5）若 栈 采用顺序存储结构，在不产生溢出的情况下 往 栈 中插人一个新元素，首先_将栈顶指针后移一个位置___，然后__将被插入元素放在修改后的栈顶指针所指出的位置_。
（6）若队列采用顺序存储结构，未溢出时插入一个元素首先__将队尾指针后移一个位置__，然后再__将被插入元素放在修改后的队尾指针所指出的位置__。
（7）当栈的最大长度难以估计时，最好采用_链式___存储结构。
数据结构 第3章答案(已核)
