A. N B. N+1 C. N-1 D. N-2
【解析：队列的头指针指向的是第一个元素的前一个结点，而不是指向第一个元素，一次队列的头指针要占用一个结点长度。】 22、队列的删除操作是在（ A ）。
A. 队首
B. 队尾
C. 队前
D. 队后
23、若让元素1，2，3依次进栈，则出栈次序不可能是（ C ）。
A. 3，2，1
B. 2，1，3
C. 3，1，2
D. 1，3，2
24、循环队列用数组A[0，m-1]存放其元素值，已知其头尾指针分别是front和rear，则当前队列中的元素个数是（ A ）。
A. (rear-front+m)%m C. rear-front-1
B. rear-front+1
D. rear-front
25、在解决计算机主机和打印机之间速度不匹配问题时，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则从该缓冲区中取走数据打印。该缓冲区应该是一个（ B ）结构。
A. 堆栈
B. 队列
C. 数组
D. 线性表
【解析：先进入缓冲区的文件先被打印，选择先进先出的结构，即队列。】 26、栈和队列都是（ C ）。
A. 链式存储的线性结构
B. 链式存储的非线性结构
D. 限制存取点的非线性结构
C. 限制存取点的线性结构
【解析：栈是只允许在栈顶进行插入和删除操作的线性表，队列是只允许在队头进行删除，在队尾进行删除操作的线性表】
27、在一个链队列中，假定front和rear分别为队头指针和队尾指针，删除一个结点的
26
操作是（ A ）。
A. front=front->next C. rear->next=front
B. rear= rear->next D. front->next=rear
28、队和栈的主要区别是（ D ）。
A. 逻辑结构不同
B. 存储结构不同
D. 限定插入和删除的位置不同
C. 所包含的运算个数不同
二、填空题
1、设栈S和队列Q的初始状态为空，元素e1,e2,e3,e4,e5,e6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出队的序列是e2,e4,e3,e6,e5,e1，则栈的容量至少应该是 。 答案：3
2、一个循环队列Q的存储空间大小为M,其队头和队尾指针分别为front和rear，则循环队列中元素的个数为 。 答案：(rear-front+M)%M
3、在具有n个元素的循环队列中，队满时具有 个元素。 答案：n-1
4、设循环队列的容量为70，现经过一系列的入队和出队操作后，front为20，rear为11，则队列中元素的个数为 。 答案：61
5、已知循环队列的存储空间大小为20，且当前队列的头指针和尾指针的值分别为8
27
和3，且该队列的当前的长度为 。 答案：15
三、判断题
1、栈和队列都是受限的线性结构。对
2、在单链表中，要访问某个结点，只要知道该结点的地址即可；因此，单链表是一种随机存取结构。错
3、以链表作为栈的存储结构，出栈操作必须判别栈空的情况。对
四、程序分析填空题
1、已知栈的基本操作函数：
int InitStack(SqStack *S); //构造空栈 int StackEmpty(SqStack *S);//判断栈空 int Push(SqStack *S,ElemType e);//入栈 int Pop(SqStack *S,ElemType *e);//出栈
函数conversion实现十进制数转换为八进制数，请将函数补充完整。
void conversion(){
InitStack(S); scanf(“%d”,&N); while(N){
（1） ;
28
}
N=N/8;
while( （2） ){ } }//conversion
答案：（1）Push(S,N%8) 2、写出算法的功能。
int function(SqQueue *Q,ElemType *e){ }
答案：循环队列出队操作 3、阅读算法f2,并回答下列问题：
（1）设队列Q=（1，3，5，2，4，6）。写出执行算法f2后的队列Q; （2）简述算法f2的功能。
void f2(Queue *Q){ DataType e; if(Q->front==Q->rear)
return ERROR;
（2）!StackEmpty(S)
Pop(S,&e); printf(“%d”,e);
*e=Q->base[Q->front];
Q->front=(Q->front+1)%MAXSIZE; return OK;
29
if (!QueueEmpty(Q)){ e=DeQueue(Q); f2(Q);
EnQueue(Q,e); } }
答案：（1）6,4,2,5,3,1
（2）将队列倒置
五、综合题
1、假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾结点，但不设头指针，请写出相应的入队列算法（用函数实现）。
rear
答案：void EnQueue(Lnode *rear, ElemType e)
{ Lnode *new;
New=(Lnode *)malloc(sizeof(Lnode));
If(!new) return ERROR;
new->data=e; new->next=rear->next; rear->next=new; rear =new; }
30