练习题及参考答案 个。
①～④：A.a B.b C.c D.d ⑤： A.1 B.2 C.3 D.0 答：①B ②D ③A ④B ⑤B
（14）设栈S和队列Q的初始状态为空，元素e1～e6依次通过栈S，一个元素出后即进队列Q，若6个元素出队的序列是e2、e4、e3、e6、e5、e1，则栈S的容量至少应该是（ ）。
A.5
答：C
B.4
C.3
D.2
2. 填空题
（1）栈是一种特殊的线性表，允许插入和删除运算的一端称为（ ① ）。不允许插入和删除运算的一端称为（ ② ）。
答：①栈顶 ②栈底
（2）一个栈的输入序列是12345，的输出序列为12345，其进栈出栈的操作为（ ）。 答：1进栈，1出栈，2进栈，2出栈，3进栈，3出栈，4进栈，4出栈，5进栈，5出栈。
（3）有5个元素，其进栈次序为A、B、C、D、E，在各种可能的出栈次序中，以元素C、D最先出栈（即C第一个且D第二个出栈）的次序有（ ）。
答：CDBAE、CDEBA、CDBEA。
（4）顺序栈用data[0..n-1]存储数据，栈顶指针为top，其初始值为0，则元素x进栈的操作是（ ）。
答：data[top]=x; top++;
（5）顺序栈用data[0..n-1]存储数据，栈顶指针为top，其初始值为0，则出栈元素x的操作是（ ）。
答：top--; x=data[top]; （6）（ ）是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。
答：队列
（7）设有数组A[0..m]作为循环队列的存储空间，front为队头指针（它指向队首元素的前一位置），rear为队尾指针（它指向队尾元素的位置），则元素x执行入队的操作是（ ）。
答：rear=(rear+1)%(m+1); A[rear]=x;
（8）设有数组A[0..m]作为循环队列的存储空间，front为队头指针（它指向队首元素的前一位置），rear为队尾指针（它指向队尾元素的位置），则元素出队并保存到x中的操作是（ ）。
答：front=(front+1)%(m+1); x=A[rear];
3. 简答题
（1）简要说明线性表、栈与队的异同点。
答：相同点：都属地线性结构，都可以用顺序存储或链表存储；栈和队列是两种特殊
17
数据结构简明教程
的线性表，即受限的线性表，只是对插入、删除运算加以限制。
不同点：①运算规则不同，线性表为随机存取，而栈是只允许在一端进行插入、删除运算，因而是后进先出表LIFO；队列是只允许在一端进行插入、另一端进行删除运算，因而是先进先出表FIFO。②用途不同，栈用于子程调用和保护现场等，队列用于多道作业处理、指令寄存及其他运算等等。
（2）顺序队的“假溢出”是怎样产生的？如何知道循环队列是空还是满？
答：一般的一维数组队列的尾指针已经到了数组的上界，不能再有进队操作，但其实数组中还有空位置，这就叫“假溢出”。
采用循环队列是解决假溢出的途径。另外，解决循环队列是空还是满的办法如下： ① 设置一个布尔变量以区别队满还是队空；
② 浪费一个元素的空间，用于区别队满还是队空。 ③ 使用一个计数器记录队列中元素个数（即队列长度）。
通常采用法②，让队头指针front指向队首元素的前一位置，队尾指针rear指向队尾元素的位置，这样判断循环队列队空标志是：front=rear，队满标志是：(rear+1)%MaxSize=front。
4. 算法设计题
（1）假设采用顺序栈存储结构，设计一个算法，利用栈的基本运算返回指定栈中栈底元素，要求仍保持栈中元素不变。这里只能使用栈st的基本运算来完成，不能直接用st.data[0]来得到栈底元素。
解：假定采用顺序栈结构。先退栈st中所有元素，利用一个临时栈tmpst存放从st栈中退栈的元素，最后的一个元素即为所求，然后将临时栈tmpst中的元素逐一出栈并进栈到st中，这样恢复st栈中原来的元素。对应算法如下：
int GetBottom(SqStack st,ElemType &x) { }
ElemType e; SqStack tmpst;
//定义临时栈 //初始化临时栈 //空栈返回0
//临时栈tmpst中包含st栈中逆转元素
InitStack(tmpst); if (StackEmpty(st)) { }
while (!StackEmpty(tmpst)) { }
return 1;
//返回1表示成功
Pop(tmpst,e); Push(st,e);
//恢复st栈中原来的内容
return 0; Pop(st,x); Push(tmpst,x);
while (!StackEmpty(st))
（2）设计一个算法，采用一个顺序栈逆向输出单链表L中所有元素。
解：本题并不需要改变单链表L的结构。设置一个顺序栈st，先遍历单链表并将所有
练习题及参考答案 元素进栈，然后栈不空循环并输出栈中所有元素。对应算法如下：
void ReverseDisp(SLink *L) { }
ElemType x; struct node {
ElemType data[MaxSize]; int top;
//定义一个顺序栈
} st;
st.top=-1;
SLink *p=L->next; while (p!=NULL) { }
while (st.top!=-1) { }
printf(\
x=st.data[st.top]; st.top--;
printf(\
//栈不空循环，输出栈中所有元素
st.top++;
st.data[st.top]=p->data; p=p->next;
//遍历单链表，将所有元素进栈
（3）设计一个循环队列，用front和rear分别作为队头和队尾指针，另外用一个标志
tag标识队列可能空（0）或可能满（1），这样加上front==rear可以作为队空或队满的条件。要求设计队列的相关基本运算算法。
解：设计的队列的类型如下：
typedef struct
{ ElemType data[MaxSize];
int front,rear; int tag;
//队头和队尾指针
//为0表示队空,为1时表示不空
} QueueType;
初始时tag=0，进行成功的插入操作后tag=1，进行成功的删除操作后tag=0；因为只有
在插入操作后队列才有可能满，只有在删除操作后队列才有可能空，因此，这样的队列的基本要素如下：
初始时：tag=0，front=rear
队空条件：qu.front==qu.rear && qu.tag==0 队满条件：qu.front==qu.rear && qu.tag==1 对应的算法如下：
//-----初始化队列算法----- void InitQueue1(QueueType &qu)
19
数据结构简明教程
{ }
//-----判队空算法-----
int QueueEmpty1(QueueType qu) { }
//-----判队满算法-----
int QueueFull1(QueueType qu) { }
//-----进队算法-----
int enQueue1(QueueType &qu,ElemType x) { }
//-----出队算法-----
int deQueue1(QueueType &qu,ElemType &x)//出队 { }
if (QueueEmpty1(qu)==1) //队空
return 0;
qu.front=(qu.front+1)%MaxSize; x=qu.data[qu.front]; qu.tag=0; return 1;
//出队一个元素,可能空
if (QueueFull1(qu)==1) //队满
return 0;
qu.rear=(qu.rear+1)%MaxSize; qu.data[qu.rear]=x; qu.tag=1; return 1;
//至少有一个元素,可能满
return(qu.tag==1 && qu.front==qu.rear); return(qu.front==qu.rear && qu.tag==0); qu.front=qu.rear=0; qu.tag=0;
//为0表示队空可能为空
（4）假设用一个循环单链表表示队列，并且只设一个指针rear指向队尾结点，但不设
头指针，设计出相应的队初始化、进队、出队和判队空的算法。
解：假设链队是不带头结点的循环单链表，其示意图如图3.1所示。队空条件：rear==NULL；进队操作：在*rear结点之后插入结点并让rear指向该结点；出队操作：删除*rear结点之后的一个结点。对应的算法如下：
队首 a1 a2 ? rear an 队尾 图3.1 不带头结点的循环单链表表示队列