文档介绍：该【栈和队列练习题 】是由【书中金屋】上传分享，文档一共【5】页，该文档可以免费在线阅读，需要了解更多关于【栈和队列练习题 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。选择题:
1、设abcdef以所给的序次进栈,若在进栈操作时,同意退栈操作
,则下边得不
到的序列为(
D)。
2、若已知一个栈的入栈序列是
1,2,3,,n,其输出序列为
p1,p2,p3,,pN,若
pN是n,则pi
是(
D)。
-i
-i+1
3、设计一个鉴别表达式中左,右括号能否配对出现的算法,采纳(
D)数
据构造最正确。
4、用链接方式储存的行列,在进行删除运算时(
D
)。
、尾指针都要改正
、尾
指针可能都要改正
5、递归过程或函数调用时,办理参数及返回地点,要用一种称为(
C)的
数据构造。
表
6、假定以数组
A[m]寄存循环行列的元素,其头尾指针分别为front
和rear,则
目前行列中的元素个数为(
A
)。
A.(rear-front+m)%m
-front+1
C.(front-rear+m)%m
D.(rear-front)%m
7、若用一个大小为
6的数组来实现循环行列,且目前
rear和front的值分别
为0和3,当从行列中删除一个元素,再加入两个元素后,
rear和front的值
分别为多少(B)
8、最大容量为n的循环行列,队尾指针是
rear,队头是front,则队空的条件
是(A)。
A.(rear+1)MODn=front
=front
+1=front
D.(rear-l)MODn=front
9、栈和行列的共同点是(
C)。
10、设栈S和行列Q的初始状态为空,元素
e1,e2,e3,e4,e5和e6挨次通
过栈S,一个元素出栈后即进行列
Q,若
6个元素出队的序列是
e2,e4,
e3,e6,e5,e1则栈S的容量起码应当是(
C
)。
判断题:
栈和行列都是限制存取点的线性构造。
(
)
除去递归不必定需要使用栈,此说法(
)
任何一个递归过程都能够变换成非递归过程。
(
)
两个栈共享一片连续内存空间时,为提升内存利用率,减少溢出时机,应把两个
栈的栈底分别设在这片内存空间的两头。()
名词解说:
栈
行列
循环行列
1)什么是递归途序
2)递归途序的优、弊端是什么
3)递归途序在履行时,应借助于什么来达成
4)递归途序的进口语句、出口语句一般用什么语句实现
算法题:
1、已知数组a[],有n个元素,用递归实现以下算法:
乞降,求最大值,求均匀数。
判断能否为一个递加数组。
大则持续,不然返回false结束:
2、试将以下递归过程改写为非递归过程。
voidtest(int*sum)
{intx;
scanf(“%d”,&x);
if(x==0)*sum=0else{test(sum);*sum+=x;}
printf("%d",*sum);
}
3、请利用两个栈S1和S2来模拟一个行列。
已知栈的三个运算定义以下:PUSH(ST,x):元素x入ST栈;POP(ST,&x):
ST栈顶元素出栈,赋给变量x;Sempty(ST):判断ST栈能否为空。
那么怎样利用栈的运算来实现该行列的三个运算:enqueue:插入一个元素入行列;dequeue:删除一个元素出行列;queue_empty:判断行列为空。(请写明算法的思想及必需的说明,不需要代码实现)
[题目剖析]栈的特色是后进先出,行列的特色是先进先出。
所以,用两个栈s1和s2模拟一个行列时,s1作输入栈,逐一元素压栈,以此模拟行列元素的入队。当需要出队时,将栈s1退栈并逐一压入栈s2中,s1中最初入栈的元素,在s2中处于栈顶。s2退栈,相当于行列的出队,实现了先进先出。明显,只有栈s2为空且s1也为空,才算是行列空。
[算法议论]算法中假定栈s1和栈s2容量同样。
出队从栈s2出,当s2为空时,若s1不空,则将s1倒入s2再出栈。元素从栈s1倒入s2,一定在s2空的状况下才能进行,即在要求出队操作时,若s2空,则无论s1元素多少(只需不空),就要所有倒入s2中。
入队在s1,当s1满后,若s2空,则将s1倒入s2,以后再入队。所以行列的容量为两栈容量之和。
(1)intenqueue(stacks1,elemtpx)
//s1是容量为n的栈,栈中元素种类是elemtp。本算法将x入栈,若入栈成功返回1,不然返回0。
{if(top1==n&&!Sempty(s2))//top1是栈s1的栈顶指针,是全局变量。
{printf(“栈满”);return(0);}//s1满s2非空,这时s1不可以再入栈。
if(top1==n&&Sempty(s2))//若s2为空,先将s1退栈,元素再压栈到
s2。
{while(!Sempty(s1)){POP(s1,x);PUSH(s2,x);}
PUSH(s1,x);return(1);//x入栈,实现了行列元素的入队。
}
(2)voiddequeue(stacks2,s1)
//s2是输出栈,本算法将s2栈顶元素退栈,实现行列元素的出队。
{if(!Sempty(s2))//栈s2不空,则直接出队。
{POP(s2,x);printf(“出队元素为”,x);}
else//办理s2空栈。
if(Sempty(s1)){printf(“行列空”);exit(0);}//若输入栈也为空,则判断队空。
else//先将栈s1倒入s2中,再作出队操作。
{while(!Sempty(s1)){POP(s1,x);PUSH(s2,x);}
POP(s2,x);//s2退栈相当行列出队。
printf(“出队元素”,x);
}
}//结束算法dequue。
(3)intqueue_empty( )
本算法判用栈s1和s2模拟的行列能否为空。
{if(Sempty(s1)&&Sempty(s2))return(1);//行列空。
elsereturn(0);//行列不空。
}
DDDDC
ABACC
TTTT
1、栈是只准在一端进行插入和删除操作的线性表,同意插入和删除的一端叫栈
顶,另一端叫栈底。最后插入的元素最初删除,故栈也称后进先出(LIFO)表。
2、行列是同意在一端插入而在另一端删除的线性表,同意插入的一端叫队尾,
同意删除的一端叫队头。最初插入队的元素最初走开(删除),故行列也常称先进先出(FIFO)表。
3、用惯例意义下次序储存构造的一维数组表示行列,因为行列的性质(队尾插入和队头删除),简单造成“假溢出”现象,即队尾已抵达一维数组的高低标,不可以再插入,但是队中元素个数小于行列的长度(容量)。循环行列是解决“假溢出”的一种方法。往常把一维数组当作首尾相接。在循环行列下,往常采纳“牺牲一个储存单元”或“作标志”的方法解决“队满”和“队空”的判断问题。
(1)一个函数在结束本函数以前,直接或间接调用函数自己,称为递归。比如,函数f在履行中,又调用函数f自己,这称为直接递归;若函数f在履行中,调用函数g,而g在履行中,又调用函数f,这称为间接递归。在实质应用中,多为直接递归,也常简称为递归。
2)递归途序的长处是程序构造简单、清楚,易证明其正确性。弊端是履行中占内存空间许多,运转效率低。
3)递归途序履行中需借助栈这类数据构造来实现。
(4)递归途序的进口语句和出口语句一般用条件判断语句来实现。递归途序由
基本项和概括项构成。基本项是递归途序出口,即不再递归即可求出结果的部分;概括项是将本来问题化成简单的且与本来形式同样的问题,即向着“基本项”发展,最后“抵达”基本项。