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章答案(已核)



