数据结构期末复习:第三章 栈和队列（选择题25道+判断题18道+程序题6道）进栈/出栈/循环队列/链队/递归
数据结构期末复习 第三章 数组和广义表
一、选择题
1．若让元素1，2，3依次进栈，则出栈顺序不可能为（C）。
A．3，2，1 B．2，1，3
C．3，1，2 D．1，3，2
2．一个队列的入队序列是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
3. 一个栈的进栈序列是10，20，30，40，50，则栈的不可能输出序列是（B）（进栈出栈可以交替进行）。
A．10,20,30,40,50 B．40,30,50,10,20
C．40,50,30,20,10 D．50,40,30,20,10
4. 元素4，6，8，10按顺序依次进栈，按该栈的可能输出序列依次入队列，该队列的可能输出序列是（D）（进栈出栈可以交替进行）。
A．10，8，4，6 B．10，6，4，8
C．8，4，6，10 D．10，8，6，4
5．向顺序栈中压入新元素时，应当（A）。
A．先移动栈顶指针，再存入元素
B．先存入元素，再移动栈顶指针
C．先后次序无关紧要
D．同时进行
6．在一个栈顶指针为top的链栈中，将一个p指针所指的结点入栈，应执行（C）。
A．top->next=p;
B．p->next=top->next; top->next=p;
C．p->next=top; top=p;
D．p->next=top->next; top=top->next;
7．在一个栈顶指针为top的链栈中删除一个结点时，用 x保存被删结点的值，则执行（D）。
A．x=top;top=top->next;
B．x=top->data;
C．top=top->next; x=top->data;
D．x=top->data; top=top->next;
8．一般情况下，将递归算法转换成等价的非递归算法应该设置（A）。
A．栈 B．队列
C．堆栈或队列 D．数组
9．表达式a*(b+c)-d的后缀表达式是（B）。
A．abcd*+- B．abc+*d- C．abc*++d- D．-+*abcd
10．判断一个顺序队列sq（最多元素为m）为空的条件是（C）。
A．sq->rear-sq->front== m B．sq->rear-sq->front-1= = m
C．sq->front==sq->rear D．sq->front==sq->rear+1
11．判断一个循环队列Q（最多元素为m）为满的条件是（C）。
A．Q->front==Q->rear B．Q->front!=Q->rear
C．Q->front==(Q->rear+1)% m D．Q->front!= (Q->rear+1)% m
12．判断栈s满（元素个数最多n个）的条件是（C）。
A．s->top==0 B．s->top!=0
C．s->top==n-1 D．s->top!=n-1
13．一个队列的入队顺序是a,b,c,d，则离队的顺序是（B）。
A．a,d,cb B．a,b,c,d C．d,c,b,a D．c,b,d,a
14．如果以链表作为栈的存储结构，则退栈操作时（C）。
A．必须判断栈是否满 B．判断栈元素类型
C．必须判断栈是否空 D．对栈不作任何判断
解析：以链表作为栈的存储结构（链栈）时，退栈（出栈）操作需要删除栈顶结点。
如果栈为空（即栈顶指针为NULL），则无法执行退栈操作，否则会发生错误。因此，退栈前必须判断栈是否空。
15．在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印数据缓冲区，主机将要输出的数据依次写入缓冲区中，而打印机则从缓冲区中取出数据打印，该缓冲区应该是一个（B）结构。
A．堆栈 B．队列 C．数组 D．先性表
16．一个递归算法必须包括（B）。
A．递归部分 B．终止条件和递归部分
C．迭代部分 D．终止条件和迭代部分
17．从一个栈顶指针为top的链栈中删除一个结点时，用变量x保存被删结点的值，则执行（A）。
A．x=top->data; top=top->next; B．x=top->data;
C．top=top->next; x=top->data; D．top=top->next; x=data;
18．在一个链队中，假设f和r分别为队头和队尾指针，则删除一个结点的运算为（C）。
A．r=f->next; B．r=r->next; C．f=f->next; D．f=r->next;
19．在一个链队中，假设f和r分别为队头和队尾指针，则插入s所指结点的运算为（B）。
A．f->next=s; f=s; B．r->next=s;r=s;
C．s->next=r;r=s; D．s->next=f;f=s;
20．在一个不带头结点的链队中，假设f和r分别为队头和队尾指针，则从该对列中删除一个结点并把结点的值保存在变量x中的运算为（C）。
A．x=r->data；r=r->next; B．r=r->next; x=r->data
C．x=f->data；f=f->next; D．f=f->next; x=f->data
21．栈和队列的共同特点是（C）。
A．都是先进后出 B．元素都可以随机进出
C．只容许在端点处插入和删除元素 D．都是先进先出
22．栈的插入和删除操作在（A）进行。
A．栈顶 B．栈底
C．任意位置 D．指定位置
23．在一个顺序队列中，队首指针指向队首元素的（C）位置。
A．前一个 B．后一个
C．当前 D．后面
24．当利用大小为n的数组顺序存储一个队列时，该队列的最大长度为( B )。
A. n-2 B. n-1 C. n D. n+1
25．从一个顺序存储的循环队列中删除一个元素时，首先需要( C )。
A. 队头指针加一 B. 队头指针减一
C. 取出队头指针所指的元素 D. 取出队尾指针所指的元素
二、判断题
1. 链式栈与顺序栈相比, 一个明显的优点是通常不会出现栈满的情况。（√）
2. 在一个顺序存储的循环队列中, 队头指针指向队头元素的后一个位置。（×）
3. 栈和队列都是顺序存取的线性表, 但它们对存取位置的限制不同。（√）
解析：顺序存取：指存取元素时，只能按照某种特定的顺序进行（不能像数组一样随机访问）。
如果表述为“栈和队列都是顺序存储的线性表,但它们对存取位置的限制不同。“就是错误的
4. 若让元素1,2,3依次进栈，则出栈次序1,3,2是不可能出现的情况。（×）
5. 在用单链表表示的链式队列Q中，队头指针为Q->front，队尾指针为Q->rear，则队空条件为Q->front == Q->rear。（√）
6. 递归定义的数据结构通常用递归算法来实现对它的操作。（√）
7. 递归的算法简单、易懂、容易编写，而且执行效率也高。（×）
8. 递归调用算法与相同功能的非递归算法相比，主要问题在于重复计算太多，而且调用本身需要分配额外的空间和传递数据和控制，所以时间与空间开销通常都比较大。（√）
9. 用非递归方法实现递归算法时一定要使用递归工作栈。（×）
10. 栈是限定在表的一端进行插入和删除操作的线性表，又称为先进后出表。（√）
11. 队列的特性是先进后出。（×）
12. 往栈中插入元素的操作方式是：先写入元素，后移动栈顶指针。（×）
13.循环队列队头指针在队尾指针前一个位置，队列是“满”状态。（√）
解析：表述为“队头指针在队尾指针下一个位置”更没有歧义
14. 在队列的顺序存储结构中，当插入一个新的队列元素时，尾指针后移，当删除一个元素队列时，头指针后移。（√）
15. 向一个栈顶指针为h的链栈(结点的指针域为next)中插入一个s所指结点时，先执行s->next=h，再执行h=s操作。（√）
16. 一个递归算法不必包括递归终止条件。（×）
17. 在一个链式队列中，若队头指针与队尾指针的值相同，则表示该队列至多有1个结点。（×）
18. 在用循环单链表表示的链式队列中，可以不设队头指针，仅在链尾设置队尾指针。（√）
解析：在循环单链表中，如果只设置队尾指针rear，不设队头指针front：
队尾指针rear指向最后一个结点
第一个结点（队头）是rear->next（因为是循环链表）
因此，通过队尾指针可以访问到队头结点，不需要单独设队头指针。
三、程序选择题
1．在下面空格处填写一条语句，以使下面的链式队列全部元素出队的算法完整。
int write(LinkQueue *q)
{QueueNode *p;
if (q->front==q->rear) /*队空*/
{printf(“队空！无元素可取”);
exit(0);
}
while (q->front->next != NULL)
{p=q->front->next;
q->front->next=p->next;/*出队*/
printf(“%4d”,p->data);
free(p); /*释放已出队结点*/
}
_______C________ /*队空时，头尾指针指向头结点*/
}
A. q->front=q->rear;
B. q=q->next;
C. q->rear=q->front;
D. p=p->next;
解析：多次执行q->front->next=p->next;后，q->front并不会被改变，改变的是
next的值，实际上front始终指向头结点。
2. 在下面空格处填写适当的语句，以使下面的循环队列的入队和出队算法完整。
define MAXSIZE 100;
typedef char Elemtype;
typedef struct
{
Elemtype queue [MAXSIZE];
int front,rear;
}sequeuetype;
Sequeuetype Q;
int encqueue(sequeuetype*Q,elemtype x)
{
if ((Q->rear+1)%MAXSIZE==Q->front)
{
printf(“队列已满!\n”);
return 1;
}
else
{
Q->rear=(Q->rear+1)%MAXSIZE;
(1)
return 0;
}
} /*入队算法*/
Elemtype del_cqueue(sequeuetype *Q)
{
if ( (2) )
{
printf(“队列为空!\n”);
return 1;
}
else
{
Q->front=(Q->front+1)%MAXSIZE;
return(Q->queue[Q->front]);
}
} /*出队算法*/
A. (1) (Q->rear+1)%MAXSIZE==Q->front (2) Q->front=(Q->front+1)%MAXSIZE;
B. (1) (Q->front+1)%MAXSIZE==Q->rear (2) Q->rear=(Q->rear+1)%MAXSIZE;
C. (1) Q->front==Q->rear (2) Q->queue[Q->rear]=x;
D. (1) Q->queue[Q->rear]=x; (2) Q->front==Q->rear
【答案】D
3. 写出下列程序执行后的结果
SeqQueue Q;
InitQueue(Q);
int a[4]={5,8,12,15};
for(int i=0;i<4;i++) InQueue(Q,a[i]);
InQueue(Q,OutQueue(Q));
InQueue(Q,30);
InQueue(Q,OutQueue(Q)+10);
while(!QueueEmpty(Q)) printf(“%d ”,OutQueue(Q));
执行后的输出结果为：_______B___________。
A. 5 8 12 15 30
B. 12 15 5 30 18
C. 8 12 15 30 18
D. 12 15 5 18 30
4. 写出下列程序执行后的结果
SeqStack S;
InitStack(S);
Push(S,3);
Push(S,4);
Push(S,5);
int x=Pop(S)+2*Pop(S);
Push(S,x);
int i,a[4]={5,8,12,15};
for (i=0;i<4;i++) Push(S,a[i]);
while(!StackEmpty(S)) Printf(“%d “,Pop(S));
执行后的输出结果为：________A__________。
A. 15 12 8 5 13 3
B. 3 5 8 12 13 15
C. 15 13 12 8 5 3
D. 15 12 13 3 8 5
5.在下面空格处填写一条语句，以使下面的进栈算法完整。
void Push(struct SeqStack*s,ElemType x)
{
If (s->top==MaxSize-1){
printf(“栈满溢出错误！\n”);
exit(1);
}
____C____
s->data[s->top]=x;
}
A. s->top=s->data;
B. s->data++;
C. s->top++;
D. s->data=s->top;
6. 在下面空格处填写一条语句，以使下面的出栈算法完整。
ElemTypePop(struct SeqStack*s,ElemType x)
{
If (StackEmpty(s)){
printf(“栈下溢出错误！\n”);
exit(1);
}
x=s->data[s->top];
____A_____
return x;
}
A. s->top--;
B. s->data--;
C. s->top=s->data;
D. s->data=s->top;