最新数据结构练习题 第三章 栈、队列和数组 习题及答案

数据结构第三章栈和队列练习及答案⼀、选择题1、栈中存取数据的原则（）A、先进先出B、先进后出C、后进后出D、随意进出2、队列中存取数据的原则（）A、先进先出B、后进先出C、先进后出D、随意进出3、插⼊和删除只能在⼀端进⾏的线性表，称为（）A、队列B、循环队列C、栈D、循环栈4、在栈中，出栈操作的时间复杂度为（）A、O（1）B、O（log2n）C、O（n）D、O（n2）5、设长度为n的链队列⽤单循环链表表⽰，若只设头指针，则⼊队操作的时间复杂度为（）A、O（1）B、O（log2n）C、O（n）D、O（n2）6、设长度为n的链队列⽤单循环链表表⽰，若只设头指针，则出队操作的时间复杂度为（）A、O（1）B、O（log2n）C、O（n）D、O（n2）7、⼀个线性表的第⼀个元素的存储地址是100，每个元素的长度是2，则第5个元素的地址是（）A、110B、108C、100D、1208、⼀个栈的⼊栈序列是a,b,c,d,e，则栈的不可能的输出序列是（）A、edcbaB、decbaC、dceabD、abcde9、若已知⼀个栈的⼊栈序列是1，2，3，……，n，其输出序列是p1,p2,p3,……,pn，若p1=n，则pi为（）A、iB、n=iC、n-i+1D、不确定10、判断⼀个栈ST（最多元素m0）为空的条件是（）A、ST->top==0B、ST->top==-1C、ST->top!=m0D、ST->top==m011、判断⼀个栈ST（最多元素m0）为满的条件是（）A、ST->top!=0B、ST->top==0C、ST->top!=m0D、ST->top==m012、判断⼀个循环队列QU（最多元素为m0）为空的条件是（）A、QU.front==QU.rearB、QU.front!=QU.rearC、QU.front==(QU.rear+1)%m0D、QU.front!=(QU.rear+1)%m013、判断⼀个循环队列QU（最多元素为m0）为满的条件是（）A、QU.front==QU.rearB、QU.front!=QU.rearC、QU.front==(QU.rear+1)%m0D、QU.front!=(QU.rear+1)%m014、循环队列⽤数组存放其元素值A[0，m-1]，已知其头尾指针分别是rear和front，则当前队列的元素个数是（）A、(rear-front+m)%mB、rear-front+1C、rear-front-1D、rear-front15、栈和队列的共同特点是（）A、都是先进后出B、都是先进先出C、只允许在端点处插⼊和删除D、没有共同点⼆、填空题1、设长度为n的链队列⽤单循环链表表⽰，若只设头指针，则⼊队和出队操作的时间复杂度分别为（O(N)）和（O(1)）；若⼜设尾指针，则⼊队和出队操作的时间复杂度分别为（O(1)）和（O(1)）。

第三章栈、队列和数组一、名词解释：1.栈、栈顶、栈底、栈顶元素、空栈2.顺序栈3.链栈4.递归5.队列、队尾、队头6.顺序队7.循环队8.队满9.链队10.随机存储结构11.特殊矩阵12.稀疏矩阵13.对称方阵14.上（下）三角矩阵二、填空题：1.栈修改的原则是_________或称________，因此，栈又称为________线性表。

在栈顶进行插入运算，被称为________或________，在栈顶进行删除运算，被称为________或________。

2.栈的基本运算至少应包括________、________、________、________、________五种。

3.对于顺序栈，若栈顶下标值top=0,此时，如果作退栈运算，则产生“________”。

4.对于顺序栈而言，在栈满状态下，如果此时在作进栈运算，则会发生“________”。

5.一般地，栈和线性表类似有两种实现方法，即________实现和________实现。

6.top=0表示________，此时作退栈运算，则产生“________”；top=sqstack_maxsize-1表示________，此时作进栈运算，则产生“________”。

7.以下运算实现在顺序栈上的初始化，请在________处用适当的句子予以填充。

int InitStack(SqStackTp *sq){ ________;return(1);}8.以下运算实现在顺序栈上的进栈，请在________处用适当的语句予以填充。

Int Push(SqStackTp *sq,DataType x){ if(sp->top==sqstack_maxsize-1}{error(“栈满”);return(0);}else{________________:________________=x;return(1);}}9.以下运算实现在顺序栈上的退栈，请在________________用适当句子予以填充。

数据结构第3章栈与队列习题第3章栈与队列一、单项选择题1．元素A、Ｂ、C、D依次进顺序栈后，栈顶元素是，栈底元素是。

A．A B．B C．CD．D2．经过以下栈运算后，x的值是。

InitStack(s)；Push(s,a)；Push(s,b)；Pop(s,x)；GetTop(s,x); A．a C．1B．b D．03．已知一个栈的进栈序列是ABC，出栈序列为CBA，经过的栈操作是。

A．push,pop,push,pop,push,pop C．push,push,pop,pop,push,popB．push,push,push,pop,pop,pop D．push,pop,push,push,pop,pop4．设一个栈的输入序列为A、B、C、D，则借助一个栈所得到的序列是。

A．A,B,C,DB．D,C,B,AC．A,C,D,B D．D,A,B,C5．一个栈的进栈序列是a，b，c，d，e，则栈的不可能的输出序列是。

A．edcba C．dceabB．decba D．abcde6．已知一个栈的进栈序列是1，2，3，……,n，其输出序列的第一个元素是i，则第j个出栈元素是。

A．i C．j-i+1B．n-i D．不确定7．已知一个栈的进栈序列是1，2，3，……，n，其输出序列是p1,p2,…,Pn，若p1=n，则pi的值。

A．i C．n-i+1B．n-i D．不确定8．设n个元素进栈序列是1，2，3，……，n，其输出序列是p1,p2,…,pn，若p1=3,则p2的值。

A．一定是2B．一定是1C．不可能是1 D．以上都不对9．设n个元素进栈序列是p1,p2,…,pn，其输出序列是1，2，3，……，n，若p3=1,则p1的值。

A．可能是2 C．不可能是2B．一定是1 D．不可能是310．设n个元素进栈序列是p1,p2,…,pn，其输出序列是1，2，3，……，n，若p3=3,则p1的值。

A．可能是2 C．不可能是1B．一定是2 D．一定是111．设n个元素进栈序列是p1,p2,…,pn，其输出序列是1，2，3，……，n，若pn=1,则pi(1≤i≤n-1)的值。

第三章栈、队列和数组一、名词解释：1.栈、栈顶、栈底、栈顶元素、空栈2.顺序栈3.链栈4.递归5.队列、队尾、队头6.顺序队7.循环队8.队满9.链队10.随机存储结构11.特殊矩阵12.稀疏矩阵13.对称方阵14.上（下）三角矩阵二、填空题：1.栈修改的原则是_________或称________，因此，栈又称为________线性表。

在栈顶进行插入运算，被称为________或________，在栈顶进行删除运算，被称为________或________。

2.栈的基本运算至少应包括________、________、________、________、________五种。

3.对于顺序栈，若栈顶下标值top=0,此时，如果作退栈运算，则产生“________”。

4.对于顺序栈而言，在栈满状态下，如果此时在作进栈运算，则会发生“________”。

5.一般地，栈和线性表类似有两种实现方法，即________实现和________实现。

6.top=0表示________，此时作退栈运算，则产生“________”；top=sqstack_maxsize-1表示________，此时作进栈运算，则产生“________”。

7.以下运算实现在顺序栈上的初始化，请在________处用适当的句子予以填充。

int InitStack(SqStackTp *sq){ ________;return(1);}8.以下运算实现在顺序栈上的进栈，请在________处用适当的语句予以填充。

Int Push(SqStackTp *sq,DataType x){ if(sp->top==sqstack_maxsize-1}{error(“栈满”);return(0);}else{________________:________________=x;return(1);}}9.以下运算实现在顺序栈上的退栈，请在________________用适当句子予以填充。

第三章栈和队列(参考答案)// 从数据结构角度看，栈和队列是操作受限的线性结构，其顺序存储结构// 和链式存储结构的定义与线性表相同，请参考教材，这里不再重复。

3.1 1 2 3 4 2 1 3 4 3 2 1 4 4 3 2 11 2 4 3 2 1 4 3 3 2 4 11 32 4 23 14 3 4 2 11 3 42 234 11 4 32 2 43 1设入栈序列元素数为n，则可能的出栈序列数为C2n n=(1/n+1)*(2n!/(n!)2)3.2 证明：由j<k和p j<p k说明p j在p k之前出栈，即在k未进栈之前p j已出栈，之后k进栈，然后p k出栈；由j<k和p j>p k说明p j在p k之后出栈，即p j被p k压在下面，后进先出。

由以上两条，不可能存在i<j<k使p j<p k<p i。

也就是说，若有1，2，3顺序入栈，不可能有3，1，2的出栈序列。

3.3 void sympthy(linklist *head, stack *s)//判断长为n的字符串是否中心对称{ int i=1; linklist *p=head->next;while (i<=n/2) // 前一半字符进栈{ push(s,p->data); p=p->next; }if (n % 2 !==0) p=p->next;// 奇数个结点时跳过中心结点while (p && p->data==pop(s)) p=p->next;if (p==null) printf(“链表中心对称”)；else printf(“链表不是中心对称”)；} // 算法结束3.4int match()//从键盘读入算术表达式，本算法判断圆括号是否正确配对（init s;//初始化栈sscanf(“%c”,&ch);while (ch!=’#’) //’#’是表达式输入结束符号switch (ch){ case ’(’: push(s,ch); break;case ’)’: if (empty(s)) {printf(“括号不配对”); exit(0);}pop(s);}if (!empty(s)) printf(“括号不配对”);else printf(“括号配对”);} // 算法结束3.5typedef struct // 两栈共享一向量空间{ ElemType v[m]; // 栈可用空间0—m-1int top[2] // 栈顶指针}twostack;int push(twostack *s,int i, ElemType x)// 两栈共享向量空间,i是0或1，表示两个栈，x是进栈元素，// 本算法是入栈操作{ if (abs(s->top[0] - s->top[1])==1) return(0);// 栈满else {switch (i){case 0: s->v[++(s->top)]=x; break;case 1: s->v[--(s->top)]=x; break;default: printf(“栈编号输入错误”); return(0);}return(1); // 入栈成功}} // 算法结束ElemType pop(twostack *s,int i)// 两栈共享向量空间,i是0或1，表示两个栈，本算法是退栈操作{ ElemType x;if (i!=0 && i!=1) return(0);// 栈编号错误else {switch (i){case 0: if(s->top[0]==-1) return(0);//栈空else x=s->v[s->top--];break;case 1: if(s->top[1]==m) return(0);//栈空else x=s->v[s->top++]; break;default: printf(“栈编号输入错误”);return(0);}return(x); // 退栈成功}} // 算法结束ElemType top (twostack *s,int i)// 两栈共享向量空间,i是0或1，表示两个栈，本算法是取栈顶元素操作{ ElemType x;switch (i){case 0: if(s->top[0]==-1) return(0);//栈空else x=s->v[s->top]; break;case 1: if(s->top[1]==m) return(0);//栈空else x=s->v[s->top]; break;default: printf(“栈编号输入错误”);return(0);}return(x); // 取栈顶元素成功} // 算法结束3．6void Ackerman(int m,int n)// Ackerman 函数的递归算法{ if (m==0) return(n+1);else if (m!=0 && n==0) return(Ackerman(m-1,1);else return(Ackerman(m-1,Ackerman(m,n-1))} // 算法结束3．7(1) linklist *init(linklist *q)// q是以带头结点的循环链表表示的队列的尾指针，本算法将队列置空{ q=(linklist *)malloc(sizeof(linklist));//申请空间，不判断空间溢出q->next=q;return (q);} // 算法结束(2) linklist *enqueue(linklist *q，ElemType x)// q是以带头结点的循环链表表示的队列的尾指针，本算法将元素x入队{ s=(linklist *)malloc(sizeof(linklist));//申请空间，不判断空间溢出s->next=q->next; // 将元素结点s入队列q->next=s;q=s; // 修改队尾指针return (q);} // 算法结束(3) linklist *delqueue(linklist *q)//q是以带头结点的循环链表表示的队列的尾指针，这是出队算法{ if (q==q->next) return (null); // 判断队列是否为空else {linklist *s=q->next->next; // s指向出队元素if (s==q) q=q->next; // 若队列中只一个元素，置空队列else q->next->next=s->next;// 修改队头元素指针free (s); // 释放出队结点}return (q);} // 算法结束。

第三章习题1.按图3.1(b)所示铁道（两侧铁道均为单向行驶道）进行车厢调度，回答：⑴如进站的车厢序列为123，则可能得到的出站车厢序列是什么？⑵如进站的车厢序列为123456，能否得到435612和135426的出站序列，并说明原因。

（即写出以“S”表示进栈、以“X”表示出栈的栈操作序列）。

2.设队列中有A、B、C、D、E这5个元素，其中队首元素为A。

如果对这个队列重复执行下列4步操作：（1）输出队首元素；（2）把队首元素值插入到队尾；（3）删除队首元素；（4）再次删除队首元素。

直到队列成为空队列为止，得到输出序列：（1）A、C、E、C、C（2）A、C、E（3）A、C、E、C、C、C（4）A、C、E、C3.给出栈的两种存储结构形式名称，在这两种栈的存储结构中如何判别栈空与栈满？4.按照四则运算加、减、乘、除和幂运算（↑）优先关系的惯例，画出对下列算术表达式求值时操作数栈和运算符栈的变化过程：A－B＊Ｃ／Ｄ＋Ｅ↑Ｆ5.试写一个算法，判断依次读入的一个以@为结束符的字母序列，是否为形如‘序列1&序列2’模式的字符序列。

其中序列1和序列2中都不含字符’&’，且序列2是序列1的逆序列。

例如，‘a+b&b+a’是属该模式的字符序列，而‘１+３&３－１’则不是。

6.假设表达式由单字母变量和双目四则运算算符构成。

试写一个算法，将一个通常书写形式且书写正确的表达式转换为逆波兰式。

7.假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点（注意不设头指针），试编写相应的队列初始化、入队列和出队列的算法。

8.要求循环队列不损失一个空间全部都能得到利用,设置一个标志域tag,以tag为0或1来区分头尾指针相同时的队列状态的空与满，请编写与此结构相应的入队与出队算法。

9.简述以下算法的功能（其中栈和队列的元素类型均为int）：（1）void proc_1(Stack S){ int i, n, A[255];n=0;while(!EmptyStack(S)){n++; Pop(&S, &A[n]);}for(i=1; i<=n; i++)Push(&S, A[i]);}（2）void proc_2(Stack S, int e){ Stack T; int d;InitStack(&T);while(!EmptyStack(S)){ Pop(&S, &d);if (d!=e) Push( &T, d);}while(!EmptyStack(T)){ Pop(&T, &d);Push( &S, d);}}（3）void proc_3(Queue *Q){ Stack S; int d;InitStack(&S);while(!EmptyQueue(*Q)){DeleteQueue(Q, &d);Push( &S, d);}while(!EmptyStack(S)){ Pop(&S, &d);EnterQueue(Q，d)}}实习题1．回文判断。

20XX年复习资料大学复习资料专业：班级：科目老师：日期：第3章作业参考答案1.1,4,3,5,2)能，IOIIIOOIOO；(1,4,2,3,5)不能，因为4先于3和2出栈，4出栈时，2和3都在栈中，且2压在3之下，故只能3先出栈才能2出栈。

*若借助栈由输入序列1,2, … , n得到输出序列为p1, p2, …, p n，则在输出序列中不可能出现这样的情形：存在着i<j<k使p j<p k<p i。

2. 借助栈T，删除栈S中元素值为k的元素。

4.//定义双向栈类template <class ElemType>//声明一个类模板class DSqStack{public: //双向栈类的各成员函数DSqStack(int m = 20XXXX0);~DSqStack();bool Empty(int i) const;ElemType & Top(int i) const;void Push(const ElemType &e,int i);void Pop(int i);private: //双向栈类的数据成员ElemType *base; //基地址指针int top[2]; //栈顶指针int size; //向量空间大小};//构造函数，分配m个结点的顺序空间，构造一个空的双向栈。

template <class ElemType>DSqStack <ElemType>::DSqStack(int m){top[0] = -1;top[1] = m;base = new ElemType[m];size = m;}//DSqStack//析构函数，将栈结构销毁。

template <class ElemType>DSqStack <ElemType>::~DSqStack(){if (base != NULL) delete[] base;}//~SqStack//判栈是否为空，若为空，则返回true，否则返回false。