1．选择题
BBACA ACBAC DCCAB CBBC
2．填空题
（1）先栈顶指针，后存入元素
（2）先取出元素，后移动栈顶指针
（3）前一个位置
（4）先移动队首元素，后取出元素
（5）n-1
（6）10
（7）先进后出，先进先出
（8）顺序存储结构，链式存储结构
3．问答题
（1）栈与队列都属于有序数组，所以可使用数组的数据结构，并加以注释和索引来跟踪是否溢出或不足。当然也可以利用链表来表示。例子略。
（2）略。
（3）所有可能的出栈次序如下：
abcd abdc acbd acdb
adcb bacd badc bcad
bcda bdca cbad cbda
cdba dcba
（4）略。
（5）从队列中删除一个元素后front=3+1=4，再加入两个元素后rear=0+2=2。rear和front的值分别是2和4。
4．上机操作题
（1）设一个顺序栈S[max]，不考虑栈满问题，top为栈顶指针，top指向新元素应存放的位置。将num转换成r进制的每一位数字顺序进栈，再按退栈顺序输出。算法描述如下：
# define max 100
void conver(int num,int r)
{
int S[max],top=0;
while (num!=0)
{
S[top++]=num%r;
num=num/r;
}
while(top>0)
printf("%d",S[--top]);
}
（2）设front 指向实际队首，rear指向新元素应存放的位置。循环队列的类型为：
# define max 100
typedef struct
{
int data[max];
int front,rear;count;
}Squeue;
①顺序循环队列的入队算法：
int enqueue(Squeue*cq,int x)
{
if(cq->count==max)
return 0;
cq->data[cp->rear]=x;
cq->rear=(cq->rear+1)%max;
cq->count++;
return 1;
}
②顺序循环队列的出队算法：
int out quere(Squeue * cq,int *x)
{
if(cq->count==0)
returu 0;
*x=cq-.data[cq->front];
cq->front(cq->front+1)%max
cq->count--;
}
（3）在带表头节点的单循环链表中找队首节点为rear->next->next。
①置空队列算法：
Lnode *init queue()
{
Lnode *rear;
rear=(Lnode *)malloc(sizeof(Lnode));
rear->next=rear;
return rear;
}
②入队算法：
Lnode *enqueue(Lnode *rear,int x)
{
Lnode*p=(Lnode *)malloc(sizeof(Lnode));
p->data=x;p->next=rear->next;
return p;
}
③出队算法：
int outqueue(Lnode *rear,int *x)
{
Lnode *p;
if(rear->next==rear)
{
pintf("queue is empty");
return 0;
p=rear->next->next;
*x=p->data;
rear->next->next=p->next;
return 1;
}
}
（4）解本题的基本思路是：先将顺序队列q中所有元素出队，并依次进入顺序栈s中，然后出栈，再依次入队。设队列中的元素为data，出队并进栈的序列为front，出栈并入队的序列为rear，可见顺序队列q中所有元素已逆置。顺序队列的类型定义为：
# define MAX 100
typedef struct
{
int data[MAX];
int front,rear;
}Squeue;
算法描述如下：
void invert (Squeue *q)
{
int s[MAX],top=0;
while(q->front<q->rear)
s[top ++]q->data[++q->front];
q->front=-1;q->rear=o;
while(top>0)
q->data[q->rear++]=s[--top];
}