《数据结构》期末复习题及参考答案

本文格式为Word版，下载可任意编辑——《数据结构》期末复习题及参考答案《数据结构》期末复习题及参考答案-第3章栈和队列

一、选择题

1、对于栈，操作数据的原则是（）。

A.先进先出B.后进先出C.后进后出D.不分顺序

2、要求数据遵循FIFO（先进先出）原则的数据结构是（）。A.线性表B.链表C.队列D.栈

3、若进栈的序列为1,2,3,4，则以下哪一个不可能是一个出栈序列。A.3,2,4,1B.3,2,1,4C.4,2,3,1D.1,3,2,44、有六个元素6，5，4，3，2，1的顺序进栈，问以下哪一个不是合法的出栈序列？（）A.543612B.453126C.346521D.234156

5、设栈的输入序列是1，2，3，4,则（）不可能是其出栈序列。

A.1，2，4，3，B.2，1，3，4，C.1，4，3，2，D.4，3，1，2，6、在一个链队列中，若f，r分别为队首、队尾指针，则插入s所指结点的操作为()(A)f->next=c；f=s(B)r->next=s；r=s(C)s->next=r；r=s(D)s->next=f；f=s

7、一个栈的输入序列为12345，则以下序列中不可能是栈的输出序列的是（）。A.23415B.54132C.23145D.154328、数字1、2依次入栈，则出栈的顺序可能有（）种状况；数字1、2依次进入队列，则出队列的顺序可能有（）种状况。A.1,2B.2,1C.2,2D.1,19、设一个栈的输入序列是1，2，3，4，5，则以下序列中，是栈的合法输出序列的是（）。A.51234B.45132C.43125D.3215410、某堆栈的输入序列为a,b，c，d,下面的四个序列中，不可能是它的输出序列的是（）。A.a，c，b，dB.b,c，d，aC.c,d，b,aD.d,c，a，b

11、顺序存储的栈和队列中已经各有N个结点，要删除一个结点分别需要移动数据（）

次和（）次。

A.N/2,NB.N,N/2C.0,ND.N,012、设有三个元素X，Y，Z顺序进栈（进的过程中允许出栈），以下得不到的出栈排列是()。A．XYZB.YZXC.ZXYD.ZYX13、一个递归算法必需包括（）。

A.递归部分B.终止条件和递归部分C.迭代部分D.终止条件和迭代部分

1

14、如下四个选项中，那个选项是能够正确判断循环队列是否排满元素的操作（其中

MAXQSIZE表示队列的容量）（）：A．if(Q.rear==Q.front)…

B．if(Q.rear==(Q.front+MAXQSIZE))C．if(Q.rear==(Q.front+1)%MAXQSIZE)D．if(Q.front==(Q.rear+1)%MAXQSIZE)15、假设以数组A[m]存放循环队列的元素，其头尾指针分别为front和rear，则当前队列中

的元素个数为（）。

A．(rear-front+m)%mB．rear-front+1C．(front-rear+m)%mD．(rear-front)%m

16、若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当

从队列中删除一个元素，再参与两个元素后，rear和front的值分别为多少？()A.1和5B.2和4C.4和2D.5和117、利用栈进行十进制数1348转换成八进制数，则入栈的数依次是（）。A.1,3,4,8B.8,4,3,1C.2,5,0,4D.4,0,5,218、最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是（）。A.(rear+1)MODn=frontB.rear=frontC．rear+1=frontD.(rear-l)MODn=front

19、栈和队列的共同点是（）。

A.都是先进先出B.都是先进后出C.只允许在端点处插入和删除元素D.没有共同点

二、填空题

1、栈是___操作受限（或限定仅在表尾进行插入和删除操作）的线性表，其运算遵循___后进先出____的原则。2、队列的插入操作在_队尾__进行，删除操作在队头___进行，其特点是__先进先出__。3、用S表示入栈操作，X表示出栈操作，若元素入栈的顺序为1234，为了得到1342出栈顺序，相应的S和X的操作串为___S×SS×S××__。4、表达式求值是___栈____应用的一个典型例子。5、栈和队列在本质上都是同一种基本数据结构的特例，这种基本的数据结构就是线性表。6、在作进栈运算时，应先判别栈是否.满，在作退栈运算时应先判别栈是否空。当栈中元素为n个，作进栈运算时发生上溢，则说明该栈的最大容量为n。

2

三、简答题

1、简要表达循环队列的数据结构，分析循环队列的队头指针和队尾指针与循环队列元素之间的关系，写出InitQueue()、QueueLength()、EnQueue()、DeQueue()等循环队列的基本操作算法，并举例说明循环队列的操作函数的应用。参考答案：

（1）队列：是一种先进先出(firstinfirstout，简称FIFO表)的线性表。它只允许在表的一端进行插入，而在另一端进行删除元素。在队列中，允许插入的一端叫做队尾(rear)，允许删除的一端称为队头(front)。假设队列为q=（a1,a2,?an），则a1为队头元素，an为队尾元素。

队列的顺序存储结构称为顺序队列。顺序队列用一组地址连续的存储单元依次存放从队列头到队列尾的元素。

由于队列的队头和队尾的位置是变化的，因而需要附设两个指针front和rear以指示队头和队尾元素在队列中的位置。

在C语言中为了便利描述，约定：初始化创立空队列时，令front=rear=0(头尾指针相等)。每当插入新的队尾元素时，rear指针增1。每当删除队头元素时，front指针增1。因此，在非空队列中，头指针front始终指向队头元素，而尾指针rear始终指向队尾元素的下一位置。循环队列：用顺序存储结构的一维数组表示队列，由于队列的性质（队尾插入和队头删除），简单造成“假溢出〞现象，即队尾已到达一维数组的高下标，不能再插入，然而队中元素个数小于队列的长度（容量）。

循环队列为了解决上述“假溢出〞现象，可采用牺牲一个存储单元（即少用了队列的一个元素空间）的方法解决“队满〞和“队空〞的判定问题，并规定:队空时：front==rear；队满时：(rear+1)%MAXQSIZE==front。

循环队列的数据结构

#defineMAXQSIZE100//最大队列长度typedefstruct{

QElemType*base;//指向初始化的动态分派存储空间

intfront;//头指针,若队列不空，指向队列头元素

intrear;//尾指针,若队列不空，指向队列尾元素的下一个位置}Sueue;

（2）循环队列的队头指针和队尾指针与循环队列元素之间的关系见如下示意图：

3

循环队列为了战胜“假溢出〞现象，少用了队列的一个元素空间。在循环队列中，指针和队列元素之间的关系不变。每当插入新的队尾元素时，rear指针增1。每当删除队头元素时，front指针增1。并规定:

队空时：front==rear；队满时：(rear+1)%MAXQSIZE==front。

（3）基本操作的算法描述

StatusInitQueue(Sueueif(!Q.base)exit(OVERFLOW);//存储分派失败Q.front=Q.rear=0;returnOK;}

intQueueLength(SueueQ)

{//返回队列Q的元素个数，即队列的长度

return(Q.rear-Q.front+MAXQSIZE)%MAXQSIZE;}

StatusEnQueue(Sueue//队列满Q.base[Q.rear]=e;

Q.rear=(Q.rear+1)%MAXQSIZE;

4

returnOK;}

StatusDeQueue(Sueue否则返回ERRORif(Q.front==Q.rear)returnERROR;e=Q.base[Q.front];

Q.front=(Q.front+1)%MAXQSIZE;returnOK;}

注意:上述函数代码要很好把握！

（4）循环队列的操作函数的应用举例（略）

注意:上述操作要很好理解和把握,能灵活应用！

2、若元素的进栈序列为：A、B、C、D、E，运用栈操作，能否得到出栈序列B、C、A、E、D和D、B、A、C、E？为什么？答案：

能得到出栈序列B、C、A、E、D，不能得到出栈序列D、B、A、C、E。其理由为：

若出栈序列以D开头，说明在D之前的入栈元素是A、B和C，三个元素中C是栈顶元素，B和A不可能早于C出栈，故不可能得到D、B、A、C、E出栈序列。

3、有字符串次序为3*-y-a/y^2,利用栈，给出将次序改为3y-*ay2^/-的操作步骤。（可用X代表扫描该字符串过程中顺序取一个字符进栈的操作，用S代表从栈中取出一个字符参与到新字符串尾的出栈操作。例如，