8 顺序栈
选择题
（1） 在一个具有n个单元的顺序栈中，假定以地址低端（即下标为0的单元）作为
栈底，以top作为栈顶指针，当出栈时，top的变化为（ ）。 A．不变 B．top=0 C．top-1 D．top=top+1
（2） 设数组S[n]作为两个栈S1和S2的存储空间，对任何一个栈只有当S[n]全满
时才不能进行进栈操作。为这两个栈分配空间的最佳方案是（ ）。 A．S1的栈底位置为0，S2的栈底位置为n-1 B．S1的栈底位置为0，S2的栈底位置为n/2 C．S1的栈底位置为0，S2的栈底位置为n D．S1的栈底位置为0，S2的栈底位置为1
（3） 为了增加内存空间的利用率和减少溢出的可能性，两个栈共享一片连续的内存
空间时，应将两栈的栈底分别设在这片内存空间的两端，这样，当（ ）时才产生上溢。
A．两个栈的栈顶同时到达栈空间的中心点 B．其中一个栈的栈顶到达栈空间的中心点 C．两个栈的栈顶在栈空间的某一位置相遇
D．两个栈均不空，且一个栈的栈顶到达另一个栈的栈底
（4） 两个栈共享一个数组空间的好处是（ ）。 A．减少存取时间，降低发生上溢的可能性 B．节省存储空间，降低发生上溢的可能性 C．减少存取时间，降低发生下溢的可能性 D．节省存储空间，降低发生下溢的可能性
算法设计题
（5） 假设以I和O分别表示入栈和出栈操作。栈的初态和终态均为空，入栈和出
栈的操作序列可表示为仅有I和O组成的序列，称可以操作的序列为合法序列，否则称为非合法序列。
①下面所示的序列中哪些是合法的？
②通过对①的分析，写出一个算法，判定所给的操作序列是否合法。若合法，返回true，否则返回false（假定被判定的操作序列已存入一维数组中）。
（6） 下面的算法将一个整数e压入到堆栈S，请在空格处填上适当的语句实现该操
作。
Typedef struct { int *base; int top; int stacksize; }SqStack;
21
int Push(SqStack S,int e) { if ( ① ) { S.base=(int *)realloc(S.base,(S.stacksize+1)*sizeof(int));
if ( ② ) { printf (“Not Enough Memory!\\n”); retuan 0; }
S.top= ③ ; S.stacksize= ④ ; }
⑤ ; retuan 1; } 22
9 链栈
选择题
（1） 向一个栈顶指针为h的带头结点的链栈中插入指针s所指的结点时，应执行
（ ）。 A．h->next=s; B．s->next=h; C．s->next=h; h->next=s; D．s->next=h->next; h->next=s;
（2） 从栈顶指针为top的链栈中删除一个结点，用x保存被删除结点的值，则执行
（ ）。
A．x=top; top=top->next; B．x=top->data; C．top=top->next; x=top->data; D．x=top->data; top=top->next;
23
10 队列的基本概念
选择题
（1） 队列的“先进先出”特性是指（ ）。 A．最后插入队列中的元素总是最后被删除
B．当同时进行插入、删除操作时，总是插入操作优先 C．每当有删除操作时，总要先做一次插入操作 D．每次从队列中删除的总是最早插入的元素
（2） 允许对队列进行的操作有（ ）。 A．对队列中的元素排序 B．取出最近入队的元素 C．在队头元素之前插入元素 D．删除队头元素
（3） 一个队列的入队顺序是1、2、3、4，则队列的输出顺序是（ ）。A．4321 B．1234 C．1432 D．3241
24
11 顺序队列
选择题
（1） 循环队列存储在数组A[0?m]中，则入队时的操作为（ ）。 A．rear=rear+1 B．rear=(rear+1) mod (m-1) C．rear=(rear+1) mod m D．rear=(rear+1) mod (m+1)
（2） 若用一个长度为6的数组来实现循环队列，且当前rear和front的值分别为0
和3，则从队列中删除一个元素，再增加两个元素后，rear和front的值分别为（ ）。 A．1和5 B．2和4 C．4和2 D．5和1
（3） 已知循环队列的存储空间为数组A[21]，front指向队头元素的前一个位置，rear
指向队尾元素，假设当前front和rear的值分别是8和3，则该队列的长度为（ ）。 A．5 B．6 C．16 D．17
（4） 如图所示为一个元素类型为字符型的环形队列，如果front指向队头元素的前
一个位置，rear指向队尾元素，则所表示的队列为（ ）。
0
1 2 3 4 5 6 7
f l
↑rear
8 9
10 11 12 13 14 15 16 17 18 19 20 21 22
I
s
b e a u T i
f
u
l
↑front
T h e o w e R A．The f
B．beautiful The f C．flower is D．eautiful The f
应用题
（5） 举例说明顺序队列的“假溢出”现象。
（6） 简述顺序队列假溢出的避免方法及队列满或空的判定条件。
（7） 在操作序列EnQueue(1)、EnQueue(3)、DeQueue、EnQueue(5)、EnQueue(7)、
DeQueue、EnQueue(9)之后，队头元素和队尾元素分别是什么？（EnQueue(k)表示整数k入队，DeQueue表示队头元素出队。）
算法设计题
（8） 在循环队列中设置一个标志flag，当front=rear且flag=0时为队空，当front=rear且flag=1时为队满。编写相应的入队和出队算法。
（9） 如果设置一个计数器count累计队列的长度，则当count=0时队列为空，当
count=QueueSize时队列为满。试设计相应的入队和出队算法。 （10）
25