数据结构习题(1,2,3章)

第三章 栈和队列

一．选择题

1．已知栈的最大容量为4。若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行,则可能出现的出栈序列为（ ）

A.5，4，3，2，1，6 B.2，3，5，6，1，4 C.3，2，5，4，1，6 D.1，4，6，5，2，3

2．在一个具有n个单元的顺序栈中，假定以地址低端（即0单元）作为栈底，以top作为栈顶指针，当做出栈处理时，top变化为（ ）

A．top不变 B．top=0 C．top-- D．top++ 3．在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队头指针和队尾指针，则判断队满的条件为（ ）

A．rear％n= = front B．（front+l）％n= = rear C．rear％n -1= = front D．(rear+l)％n= = front 4．在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队头指针和队尾指针，则判断队空的条件为（ ）

A．rear％n= = front B．front+l= rear

C．rear= = front D．(rear+l)％n= front 5．在一个链队列中，假定front和rear分别为队首和队尾指针，则删除一个结点的操作为（ ）

A．front=front->next B．rear=rear->next C．rear=front->next D．front=rear->next

6．某堆栈的输入序列为1，2，3，…，n，输出序列的第一个元素是n，则第i个输出元素为（ ）

A．i B．n-i C．n-i+1 D．哪个元素无所谓

7．用不带头结点的单链表存储队列时,其队头指针指向队头结点,其队尾指针指向队尾结点，则在进行删除操作时( )。

A．仅修改队头指针 B．仅修改队尾指针

C．队头、队尾指针都要修改 D．队头,队尾指针都可能要修改

8．最适合用做链队列的链表（链表有头结点，有队首指针则指向头结点，有队尾指针则指向终端结点）是（ ）。

A．只带队首指针的循环单链表。 B．只带队尾指针的循环单链表。 C．只带队首指针的非循环单链表。 D．只带队尾指针的非循环单链表。 9．最不适合用做队列的链表是（ ）。

A．只带队首指针的非循环双链表。 B．只带队首指针的循环双链表。 C．只带队尾指针的循环双链表。 D．只带队尾指针的循环单链表。

二．填空题

1．线性表、栈和队列都是 结构。线性表可以在 插入和删除元素；栈只能在 插入和删除元素；队列只能在 插入元素和 删除元素。

2．假设以S和X分别表示进栈和退栈运算，则对输入序列a,b,c,d,e进行一系列栈运算SSXSXSSXXX之后，得到的输出序列为 。

3．设栈S和队列Q的初始状态为空，元素a,b,c,d,e,f依次通过栈S，一个元素出栈后即进入队列Q。若这6个元素出队列的顺序是b,d,c,f,e,a，则栈S的容量至少应该是 。 三．解答题

1．一个双向栈S是在同一向量空间内实现的两个栈，它们的栈底分别设在向量空间的两端。 试为此双向栈设计初始化InitStack ( S ) 、入栈Push( S , i , x) 和出栈Pop( S , i )等算法， 其中i为0 或1， 用以表示栈号。

2．利用两个栈S1、S2模拟一个队列时，如何使用栈的运输实现队列的插入、删除运算。 3．简述下列算法的功能，并给出队列Q={12，34，25，4，8}在执行下列算法后的状态。

void unknows(SqQueue &Q) {

SqStack S; int k;

Initstack(S);

while(!queueempty(Q)) {

Dequeue(Q,k); Push(S,k); }

while(!stackempty(S)) {

Pop(S,k);

Enqueue(Q,k); } }

功能：

队列Q的值：