第3章 栈和队列
一、选择题
1.栈结构通常采用的两种存储结构是（A   ）。
A、顺序存储结构和链表存储结构             B、散列和索引方式
C、链表存储结构和数组                     D、线性链表结构和非线性存储结构
2.设栈ST 用顺序存储结构表示，则栈ST 为空的条件是（ B ）
A、ST.top-ST.base<>0                     B、ST.top-ST.base==0
C、ST.top-ST.base<>n                     D、ST.top-ST.base==n
3.向一个栈顶指针为HS 的链栈中插入一个s 结点时，则执行（ C ）
A、HS->next=s;                             B、s->next=HS->next；HS->next=s;
C、s->next=HS；HS=s;                     D、s->next=HS；HS=HS->next;
4.从一个栈顶指针为HS 的链栈中删除一个结点，用x 保存被删除结点的值，则执行（ C）
A 、x=HS；HS=HS->next;                 B 、HS=HS->next；x=HS->data;
C 、x=HS->data；HS=HS->next;             D 、s->next=Hs；Hs=HS->next;
5.表达式a*(b+c)-d 的后缀表达式为（ B  ）
A、abcdd+-             B、abc+*d-             C、abc*+d-             D、-+*abcd
6.中缀表达式A-（B+C/D）*E 的后缀形式是（ D ）
A、AB-C+D/E*         B、ABC+D/E*         C、ABCD/E*+-         D、ABCD/+E*-
7.一个队列的入列序列是1，2，3，4， 则队列的输出序列是（ B  ）
A、4，3，2，1         B、1，2，3，4         C、1，4，3，2         D、3，2，4，1
8.循环队列SQ 采用数组空间SQ.base[0,n-1]存放其元素值，已知其头尾指针分别是front 和rear，则判定此循环队列为空的条件是（  ）
A、Q.rear-Q.front==n                         B、Q.rear-Q.front-1==n
C、Q.front==Q.rear                         D、Q.front==Q.rear+1
9.循环队列SQ 采用数组空间SQ.base[0,n-1]存放其元素值，已知其头尾指针分别是front 和rear，则判定此循环队列为满的条件是（   ）
A、Q.front==Q.rear                         B、Q.front!=Q.rear
C、Q.front==(Q.rear+1)%n                     D、Q.front!=(Q.rear+1)%n
10.若在一个大小为6 的数组上实现循环队列，且当前rear 和front 的值分别为0 和3，当从队列中删除一个元素，再加入两个元素后，rear 和front 的值分别为（  ）
A、1，5             B、2, 4                 C、4，2             D、5，1
11.用单链表表示的链式队列的队头在链表的（  ）位置
A、链头             B、链尾             C、链中
12.判定一个链队列Q（最多元素为n 个）为空的条件是（   ）
A、Q.front==Q.rear                         B、Q.front!=Q.rear    
C、Q.front==(Q.rear+1)%n                     D、Q.front!=(Q.rear+1)%n
13.在链队列Q 中，插入s 所指结点需顺序执行的指令是（  ）
A 、Q.front->next=s；f=s;                     B 、Q.rear->next=s；Q.rear=s;
C 、s->ar；Q.rear=s;                 D 、s->next=Q.front；Q.front=s;
14.在一个链队列Q 中，删除一个结点需要执行的指令是（   ）
A、Q.rear=Q.front->next;                     B、Q.rear->ar->next->next;
C、Q.front->next=Q.front->next->next;         D、Q.ar->next;
数组和链表
15.用不带头结点的单链表存储队列，其队头指针指向队头结点，队尾指针指向队尾结点，则在进行出队操作时（ ）
A、仅修改队头指针                         B、仅修改队尾指针
C、队头尾指针都要修改                     D、队头尾指针都可能要修改。
16.栈和队列的共同点是（   ）
A、都是先进后出                         B、都是先进先出
C、只允许在端点处插入和删除元素         D、没有共同点
17.消除递归（   ）需要使用栈。
A、一定                                 B、不一定
18.设有一顺序栈S，元素s1，s2，s3，s4，s5，s6 依次进栈，如果6 个元素出栈的顺序是s2，s3，s4，s6，s5，s1，则栈的容量至少应该是（   ）
A、2                 B、3                 C、 5                 D、 6
19.若一个栈的输入序列是a，b，c，则通过入、出栈操作可能得到a,b,c 的不同排列个数为
（   ）
A、 4                 B、 5                 C、 6                 D、 7
20.设有一顺序栈已经含有3 个元素，如图3.1 所示元素a4 正等待进栈。下列不可能出现的出栈序列是（  ）
A、a3,a1,a4,a2         B、 a3,a2,a4,a1         C、 a3,a4,a2,a1         D、 a4,a3,a2,a1
图3.1
21.链栈和顺序栈相比，有一个比较明显的优势是（  ）
A、通常不会出现栈满的情况                 B、通常不会出现栈空的情况
C、插入操作更容易实现                     D、删除操作更加容易实现
22.若一个栈的输入序列是1，2，3，4，…，n，输出序列的第一个元素是n，则第i 个输出元素是（ C ）
A、不确定             B、 n-i                 C、 n-i+1             D、n-i-1
23.以下说法正确的是(   )
A、因链栈本身没有容量限制,故在用户内存空间的范围内不会出现栈满情况
B、因顺序栈本身没有容量限制,故在用户内存空间的范围内不会出现栈满情况
C、对于链栈而言,在栈满状态下,如果此时再作进栈运算，则会发生“上溢”
D、对于顺序栈而言在栈满状态下如果此时再作进栈运算，则会发生“下溢”。
二、判断题
1.在顺序栈栈满情况下，不能做进栈运算，否则会产生“上溢”。
2.链栈与顺序栈相比的一个优点是链栈插入和删除操作更加方便。
3.若一个栈的输入序列为 1，2，3，…，n，其输出序列的第一个元素为n，则其输出序列的每个元素一定满足ai=i+1(i=1,2, …,n)。
4.在链队列中，即使不设置尾指针也能进行入队操作。
5.在对链队列（带头指针）做出队操作时，不会改变 front 指针的值。
6.循环队列中元素个数为 rear-front。
7.一个栈的输入序列是 1,2,3,4，则在栈的输出序列中可以得到4,3,1,2。
8.一个栈的输入序列是 1,2,3,4，则在栈的输出序列中可以得到1,2,3,4。
9.若以链表作为栈的存储结构，则进栈需要判断栈是否满。
10.若以链表作为栈的存储结构，则出栈需要判断栈是否空。
三、填空题
1.栈的特点是（先进后出  ），队列的特点是（ 先进先出  ）。
2.线性表、栈、队列都是（  ）结构，可以在线性表的（  ）位置插入和删除元素；对于栈只能在（  ）插入和删除元素；对于队列只能在（  ）插入元素和在（  ）位置删除元素。
3.有程序如下，则此程序的输出结果（栈的元素类型是SelemType 为char）是（  ）。
void main(){
stack  s;
char  x,y;
initstack (s);
x=’c’;
y=’k’;
push(s,x);
push(s,’a’);
push(s,y);
pop(s,x);
push(s,’t’);
push(s,x);
pop(s,x);
push(s,’s’);
while(!stackempty(s)){
pop(s,y);
printf(y);
}
printf(x);
}
4.在栈顶指针为HS 的链栈中，判定栈空的条件是（  ）。
5.向栈中压入元素的操作是先（  ）后（  ）。
6.对栈进行退栈操作是先（  ）后（  ）。
7.用循环链表表示的队列长度为n，若只设头指针，则出队和入队的时间复杂度分别是（  ）和（  ）；若只设尾指针，则出队和入队的时间复杂度分别是（  ）和（  ）。
8.从循环队列中删除一个元素时，其操作是（  ）。
9.在一个循环队列中，队首指针指向队首元素的（  ）。
10.在具有n 个单元的循环队列中，队满时共有（  ）个元素。
11.在HQ 的链队列中，判断只有一个结点的条件是（  ）。
12.设栈S 和队列Q 的初始状态为空，元素a、b、c、d、e、f 依次通过栈S，一个元素出栈后
即进入队列Q。若这6个元素出队列的顺序是b、d、c、f、e、a 则栈S 的容量至少应该是（  ）。
13.有程序如下，则此程序的输出结果（队列的元素类型是QSelemType 为char）是（  ）。
void main(){
char x=’e’,y=’c’;
enqueue(q,’h’);enqueue(q,’r’);enqueue(q,y);dequeue(q,x);enqueue(q,x);degueue(q,x);
enqueue(q,’a’);
while(!queueempty(q)){
dequeue(q,y);printf(y);
}
printf(x);
}
14.有如下递归函数：
int dunno(int m){
int value;
if(m==0)
value=3;
else
value=dunno(m-1)+5;
return(value);
}
执行语句printf(“%d\n”,dunno(3));的结果是（  ）。
四、简答题
1.对于堆栈，给出三个输入项A，B，C，如果输入项序列为ABC，试给出全部可能的输出序列，并写
出每种序列对应的操作。例如：A 进B 进C 进C 出B 出A 出，产生的序列为CBA。
2.简述以下算法的功能（栈的元素类型是 SelemType 为int）。
（1）
status  algo1(stack s){
int I,n,a[255];
n=0;
while(!stackempty(s)){
n++;
pop(s,a[n]);
}
for(I=1;I<=n;I++)
push(s,a[I]);
}
(2)
status  algo2(stack s,int e){
stack t;int d;
initstack(t);
while(!stackempty(s)){
pop(s,d);
if(d!=e)
push(t,d);

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。