亚马逊意外错误报歉，由于程序执行时，遇到意外错误，您刚刚操作没有执行成功，请稍后重试。或将此错误报告给我们的客服中心：推荐您，确认您的操作无误后，再继续其他操作。您可以通过亚马逊，获得更多的帮助。与栈有关习题_C语言中文网
&&/&&&&/&&&&/&&
&、单项选择题
1.栈和队列具有相同的（&&& ）。
A.抽象数据类型 & & B.逻辑结构 & & C.存储结构 & & D.运算
2.栈是（）。
A.顺序存储的线性结构 & & B.链式存储的非线性结构
C.限制存取点的线性结构 & & D.限制存储点的非线性结构
3.（）不是栈的基本操作。
A.删除栈顶元素 & & B.删除栈底元素
C.判断栈是否为空 & & D.将栈置为空栈
4.假定利用数组 a[n] 顺序存储一个栈，用top表示栈顶指针，top==-1表示桟空，并已知栈未满，当元素x进栈时所执行的操作为（ ）。
A. a[--top]=x & & B. a[top--]=x & & C. a[++top]=x & & D. a[top++]=x
5.设有一个空栈，栈顶指针为1000H，每个元素需要1个存储单元，在执行Push、Push、 Pop、Push、Pop、Push、Pop、Push操作后，桟顶指针的值为（ ）。
A. 1002H&&& B. 1003H&&& C. 1004H&&& D. 1005H
6.和顺序栈相比，链栈有一个比较明显的优势是（&&& ）。
A.通常不会出现栈满的情况 & & B.通常不会出现栈空的情况
C.插入操作更容易实现 & & D.删除操作更容易实现
7.设链表不带头结点且所有操作均在表头进行，则下列最不适合作为链栈的是（&&& ）。
A.只有表头结点指针，没有表尾指针的双向循环链表
B.只有表尾结点指针，没有表头指针的双向循环链表
C.只有表头结点指针，没有表尾指针的单向循环链表
D.只有表尾结点指针，没有表头指针的单向循环链表
8.向一个栈顶指针为top的链栈中插入一个x结点，则执行（&&& ）。
A. top-&next=x & & &B. x-&next=top-& top-&next=x
C. x-&next= top=x & & &D. x-&next=top, top=top-&next
9.链栈执行Pop操作，并将出栈的元素存在x中应该执行（ ）。
A. x= top=top-&next & & &B.x=top-&data
C. top=top-& x=top-&data & & &D. x=top-& top=top-&next
10.经过以下栈的操作后，变量x的值为（&&& ）。
InitStack(st); Push(st, a); Push(st, b); Pop(st, x); Top(st,x);
A. a&&& B. b&&& C. NULL&&& D. FALSE
11.&&& 3个不同元素依次进栈，能得到（ ）种不同的出栈序列。
A. 4&&& B. 5&&& C. 6&&& D. 7
12.设a、b、c、d、e、f以所给的次序迸栈，若在进栈操作时，允许出栈操作，则下面得不到的序列为（ ）。
A. fedcba&&& B. bcafed&&& C. dcefba&&& D. cabdef
13.用S表示进栈操作，用X表示出栈操作，若元素的进栈顺序是1234，为了得到1342的出栈顺序，相应的S和X的操作序列为（ ）。
A. SXSXSSXX & & B. SSSXXSXX & & C. SXSSXXSX & & D. SXSSXSXX
14.【2010年计算机联考真题】
若元素a、b、c、d、e、f依次进栈，允许进栈、退栈操作交替进行，但不允许连续3次进行退栈工作，则不可能得到的出栈序列是（ ）。
A. dcebfa&&& B. cbdaef&&& C. bcaefd&&& D. afedcb
15.设找S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5和e6依次通过栈S，一个元素出栈后即进队列Q，若6个元素出栈的序列是e2、e4、e3、e6、e5、e1，则栈S的容量至少应该是（ ）。
A. 6&&& B. 4&&& C. 3&&& D. 2
16.【2009年计算机联考真题】
设栈S和队列Q的初始状态均为空，元素abcdefg依次进入栈S。若每个元素出栈后立即进入队列Q，且7个元素出队的顺序是bdefeag,则栈S的容量至少是（ ）。
A. 1&&& B. 2&&& C. 3&&& D. 4
17.若一个栈的输入序列是1, 2，3, &, n，输出序列的第一个元素是n，则第i个输出元素是（ ）。
A.不确定&&& B. n-i&&& C. n-i-1&&& D. n-i+1
18.一个栈的输入序列为1, 2, 3, &, n,输出序列的第一个元素是i，则第j个输出元素是（ ）。
A, i-j-1&&& B. i-j&&& C. j-i+1 & &D.不确定
19.某栈的输入序列为a、b、c、d，下面的4个序列中，不可能是它的输出序列的是（）。
A. a,b,c,d&&& B. c,b,d,a&&& C. d,c,a,b&&& D. a,c,b,d
20.若一个栈的输入序列是P1, P2, &, Pn，其输出序列是1, 2, 3, &, n，若P3=1，则p1的值（ ）。
A.可能是2 & & B. 一定是2 & & C.不可能是2 & & D.不可能是3
21.若已知一个栈的入栈序列是1、2、3、4。其出栈序列为P1、P2、P3、P4，则P2、P4不可能是（ ）。
A. 2、4&&& B. 2、1&&& C. 4、3&&& D. 3、4
22.设桟的初始状态为空，当字符序列&n 1 _&作为栈的输入时，输出长度为3，且可用做C语言标识符的序列有（ ）个。
A. 4&&& B. 5&&& C. 3&&& D. 6
23.【2011年计算机联考真题】
元素a、b、c、d、e依次进入初始为空的栈中，若元素进栈后可停留、可出栈，直到所有元素都出栈，则在所有可能的出栈序列中，以元素d开头的序列个数是（）。
A. 3&&& B. 4&&& C. 5&&& D. 6
24.釆用共享栈的好处是（&&& ）。
A.减少存取时间，降低发生上溢的可能
B.节省存储空间，降低发生上溢的可能
C.减少存取时间，降低发生下溢的可能
D.节省存储空间，降低发生下溢的可能
25.设有一个顺序共享栈Share[0: n-1]，其中第一个栈顶指针top1的初值为-1，第二个栈顶指针top2的初值为n，则判断共享栈满的条件是（ ）。
A. top2-top1==1 & & B. top1-top2==1 & & C. top1==top2 & & D.以上都不对
二、综合应用题
1.有5个元素，其入栈次序为A、B、C、D、E,在各种可能的出栈次序中，第一个出栈元素为C且第二个出栈元素为D的出栈序列有哪几个？
2.若元素的进栈序列为A、B、C、D、E,运用栈操作，能否得到出栈序列B、C、A、 E、D 和 D、B、A、C、E？为什么？
3.假设以I和O分别表示入栈和出栈操作。栈的初态和终态均为空，入栈和出栈的操作序列可表示为仅由I和O组成的序列，可以操作的序列称为合法序列，否则称为非法序列。
1) 下面所示的序列中哪些是合法的？
a. IOIIOIOO & & b. IOOIOIIO & & c. IIIOIOIO & & d. IIIOOIOO
2) 通过对1)的分析，写出一个算法，判定所给的操作序列是否合法。若合法，返回 true，否则返回false（假定被判定的操作序列已存入一维数组中）。
4.设单链表的表头指针为h，结点结构由data和next两个域构成，其中data域为字符型。试设计算法判断该链表的前n个字符是否中心对称。例如xyx、xyyx都是中心对称。
5.设有两个栈s1、s2都釆用顺序栈方式，并且共享一个存储区[0, &, maxsize-1]，为了尽量利用空间，减少溢出的可能，可釆用栈顶相向、迎面增长的存储方式。试设计s1、s2 有关入栈和出栈的操作算法。
答案与解析
一、单项选择题
线性表、栈和队列的逻辑结构都是相同的，都属于线性结构，只是它们对数据的运算不同，从而表现出不同的特点。
首先栈是一种线性表，所以B、D错。按存储结构的不同可分为顺序栈和链栈，但不可以把栈局限在某种存储结构上，所以A错。栈和队列都是限制存取点的线性结构。
基本操作是指该结构最核心、最基本的运算，其他较复杂的操作可以通过基本操作实现。删除栈底元素不属于栈的基本运算，但它可以通过调用栈的基本运算求得。
入栈指针top加1，初始时top为-1，则第1个元素入找后，top为0，即指向栈顶元素，故入栈时应先将指针top加1，再将元素入栈，只有C符合题意。
每个元素需要1个存储单元，所以每入栈一次top加1，出栈一次top减1。指针top的值依次为 1001H，1002H, 1001H, 1002H，1001H，1002H，1001H，1002H。
顺序栈釆用数组存储，数组的大小是固定的，不能动态地分配大小。和顺序栈相比，链栈的最大优势在于它可以动态地分配存储空间，所以答案为A。
通常栈的插入和删除在表头进行。对于选项C，插入和删除一个结点后，仍需将其变为循环单链表，因此需要找到其尾结点，时间复杂度为o(n)。
若不做题干中的限制，则栈顶可取表头（带头结点的链表）或第二个结点（不带头结点的链表)，找指针的位置取头结点（带头结点的链表）或表头（不带头结点的链表)。
链栈釆用不带头结点的单链表表示时，进栈橾作在首部插入一个结点x(即x-&next=top)，插入完后需将top指向该插入的结点X。请思考当链栈存在头结点时的情况。
这里假设栈顶指针指向的是栈顶元素，所以选D；而A中首先将top指针赋给了 x，错误；B中没有修改top指针的值；C为top指针指向栈顶元素的上一个元素时的答案。
执行前3句后，栈st内的值为a，b，其中b为栈顶元素，执行第4句后，x的值为b，执行最后一句后x的值为a。
对于n个不同元素进栈，出栈序列的个数为
上述的公式叫做卡特兰(Catalan)数，可釆用数学归纳法证明，有兴趣的读者可以参考组合数学的教材（知道该公式即可）。考题中给出的n值不会很大，可以根据栈的特点，若Xi已经出栈，则Xi前面的尚未出栈的元素一定逆置有序地出栈，因此可以釆取例举的方法。如a、b、c依次进栈的出栈序列有abc，acb, bac, bca, cba。
根据栈&先进后出&的特点，并且在进栈操作的同时允许出栈操作，显然，答案D中c 最先出栈，则此时栈内必定为a和b，但由于a先于b进栈，故要晚出栈。对于某个出栈的元素，在它之前进栈却晚出栈的元素必定是按逆序出栈的，其余答案均是可能出现的情况。
此题也可以釆用将各序列逐个代入，以确定是否有对应的进出栈序列（类似下题）。
釆用排除法，选项A、B、C得到的出栈序列分别为、1324。由1234得到 1342的进出栈序列为：1进，1出，2进，3进，3出，4进，4出，2出，故选D。
选项A可由a进，b进，c进，d进，d出，c出，e进，e出，b出，f进，f出，a出得到；
选项B可由a进，b进，c进，c出，b出，d进，d出，a出，e进，e出，f进，f出得到；
选项C可由a进，b进，b出，c进，c出，a出，d进，e进，e出，f进，f出，d出得到；
选项D可由a进，a出，b进，c进，d进，e进，f进，f出，e出，d出，c出，b出得到，但要求不允许连续3次退栈操作，故选D。
本题将队列和栈结合起来，由于队列&先进先出&的特性，所以出队的序列与进队的序列是相同的，从而可以得到出栈的次序为e2、e4、e3、e6、e5、e1；再由栈&先进后出&的特性，进栈的次序为e1、e2、e3、e4、e5、e6,可见，排在某个元素之后出栈却排在它之前进栈的元素个数，表示之前栈内的元素个数。因此，e4进栈后，e1和e3在栈中；而后e4 和e3出找；e6进找后，e5和e1也在找中。因此，找的最小容量为3。
时刻注意栈的特点是先进后出，下表是出入栈的详细过程。
找内的最大深度为3，故栈S的容量至少是3。
另解：由于元素的出队顺序和入队顺序是一样的，所以，元素的出栈顺序也就是b、d、 c、f、e、a、g,所以，元素的入栈出栈顺序为 Push(S, a)，Push(S, b)，Pop(S, b)，Push(S, c)，Push(S, d)，Pop(S, d)，Pop(S, c)，Push(S, e)。Push(S, f)，Pop(S, f)，Pop(S，e), Pop(S，a)，Push(S, g)，Pop(S, g)。假设初始所需容量为0，每做一次Push操作进行一次加1操作，每做一次Pop进行一次减1操作，记录容量的最大值为3，所以答案选C。
第n个元素先出栈，说明前n-1个元素都已经按顺序入栈，由&先进后出&的特点可知，此时的输出序列一定是输入序列的逆序，故答案选D。
当第i个元素第一个出栈时，则i之前的元素可以依次排在i之后出栈，但剩余的元素可以在此时进栈并且也会排在i之前的元素出栈，所以，第j个出栈的元素是不确定的。
对于A，可能的顺序是a入，a出，b入，b出，c入，c出，d入，d出。
对于B，可能的顺序是a入，b入，c入，c出，b出，d入，d出，a出。
对于D，可能的顺序是a入，a 出，b入，c入，c出，b出，d入，d出。
C没有对应的序列。
另解：若出栈序列的第一个元素为d，则出栈序列只能是dcba。该思想通常也适用了出栈序列的局部分析：如12345入栈，问出栈序列34152是否正确？如何分析？若第一个出栈元素是3,则此时12必停留在栈中，它们出栈的相对顺序只能是21，故34152错误。
入栈序列是P1，P2，&，Pn。由于P3=1，即P1、P2、P3连续入栈后，第一个出栈元素是 P3，说明P1、P2已经按序进栈，根据先进后出的特点可知，P2必定在P1之前出栈，而第二个出栈元素是2,而此时P1必定不是栈顶元素，因为P2尚未出栈。因此P1的值不可能是2。
对于A，可能的顺序是1入栈，1出栈，2入栈，2出栈，3入栈，3出栈，4入栈，4 出栈。
对于B，可能的顺序是1入栈，2入栈，3入栈，3出找，2出找，4入栈，4出桡，1 出栈。
对于D，可能的顺序是1入栈，1出栈，2入栈，3入栈，3出栈，2出桟，4入栈，4 出栈。
C则没有对应的序列。
标识符的第一个字符必须是大小写英文字母或者下画线，而不能是数字。按照上述规定&n 1 _&三个字符符合规定的标识符有n1_、n_1、_1n, _n1四种形式。第一种：n进栈再出栈， 1进栈再出栈，_进栈再出栈。第二种：n进栈再出栈，1进栈，_进栈，_出栈，1出栈。第三种：n进栈，1进栈_进栈，_出栈，1出栈，n出栈。而根据栈的操作特性，_n1这种情况不可能出现，故选C。
出栈顺序必为d_c_b_a，e的顺序不定，在任意一个&_&上都有可能。
另解：d首先出栈，则abc停留在栈中，此时钱的状态如下图所示。此时可以有如下4种操作：
①e进栈后出栈，则出栈序列为decba；
②c出栈，e进桟后出栈，出桟序列为dceba；
③cb出桟，e进栈后出栈，出栈序列为dcbea；
④cba出找，e进栈后出栈，出栈序列为dcbae。
存取栈中的元素都只需要0(1)的时间，所以,减少存取时间无从谈起。另外，栈的插入和删除操作都是在栈顶进行的，只可能发生上溢（栈顶指针超出了最大范围），不可能发生下溢（对于上溢、下溢，只需大概了解即可，不必深究），因此本题答案为B。
这种情况就是前面我们所描述的，详细内容请参见本节考点精析部分对共享栈的讲解。另外，读者可以思考若top1的初值为0，top2的初值为n-1时栈满的条件。
注意：栈顶、队头与队尾的指针的定义是不唯一的，读者务必要仔细审题。
二、综合应用题
CD出栈后的状态如下图所示。
此时有如下3种操作：
①E进栈后出栈，则出栈序列为CDEBA；
②B 出栈，E进栈后出栈，出栈序列为CDBEA；
③B出栈，A出栈，E进栈后出栈，出栈序列为CDBAE。
所以，以CD开头的出栈序列有：CDEBA、CDBEA、CDBAE三种。
能得到出栈序列BCAED。可由A进，B进，B出，C进，C出，A出，D进，E进，E出，D出得到。不能得到出栈序列DBACE。若出栈序列以D开头，说明在D之前的入栈元素是A、B和C，三个元素中C是栈顶元素，B和A不可能早于C出栈，故不可能得到出栈序列DBACE。
1) A、D合法，而B、C不合法。在B中，先入栈1次，再连续出栈2次，错误。在 C中，入栈和出栈次数不一致，会导致最终的栈不空。A、D均为合法序列，请自行模拟。注意：在操作过程中，入栈次数一定大于或等于出栈次数；结束时，栈一定为空。
2) 设被判定的操作序列已存入一维数组A中。算法的基本设计思想：依次逐一扫描入栈出栈序列（即由&I&和&O&组成的字符串），每扫描至任一位置均需检查出栈次数（即 &O&的个数）是否小于入栈次数（&I&的个数)，若大于则为非法序列。扫描结束后，再判断入栈和出栈次数是否相等，若不相等则不合题意，为非法序列。
int Judge(char A[]) {
//判断字符数组A中的输入输出序列是否是合法序列。如是，返回true,否则返回false
//i为下标，j和k分别为字母I和O的个数
while (A[i]!='\0') {
//未到字符数组尾
switch(A[i]){
case 'I' ; j++;
//入栈次数增 1
case 'O' : k++;
if (k&j ) { printf (&序列非法\n&) ; exit (0) ; }
//不论A[i]是&I&或&0&，指针i均后移
if (j!=k) {
printf (&序列非法\n& );
printf (&序列合法\n&);
另解：入栈后，栈内元素个数加1；出栈后，栈内元素个数减1，因此，可以将判定一组出入栈序列是否合法，转化为一组+1、-1组成的序列，它的任意前缀子序列的累加和不小于0 (每次出栈或入栈操作后判断)，则合法；否则，非法。
算法思想：使用栈来判断链表中的数据是否中心对称。将链表的前一半元素依次进栈。在处理链表的后一半元素时，当访问到链表的一个元素后，就从栈中弹出一个元素，两个元素比较，若相等，则将链表中下一个元素与栈中再弹出的元素比较，直至链表到尾。这时若栈是空栈，则得出链表中心对称的结论；否则，当链表中的一个元素与栈中弹出元素不等时，结论为链表非中心对称，结束算法的执行。
int dc(LinkList L, int n){
//h是带头结点的n个元素单链表，本算法判断链表是否是中心对称
char s[n/2];int i=1;
//i记结点个数，s字符栈
//p是链表的工作指针，指向待处理的当前元素
for{i=0;i&n/2;i++) {
//链表前一半元素进栈
//恢复最后的i值
if(n%2==1)
//若n是奇数，后移过中心结点
while(p!=NULL && s[i] ==p-&data) { //检测是否中心对称
//i充当找顶指针
if (i==-1)
//桟为空找
//链表中心对称
//链表不中心对称
算法先将&链表的前一半&元素（字符）进栈。当n为偶数时，前一半和后一半的个数相同；当n为奇数时，链表中心结点字符不必比较，移动链表指针到下一字符开始比较。比较过程中遇到不相等时，立即退出while循环，不再进行比较。
本题也可以先将单链表中的元素全部入栈，然后再次扫描单链表L并比较，直到比较到单链表L尾为止，但是算法需要两次扫描单链表L，效率不及上述算法高。
两个栈共享向量空间，将两个栈的栈底设在向量两端，初始时，s1栈顶指针为-1，s2 栈顶指针为maxsize。两个栈顶指针相邻时为栈满。两个栈顶相向、迎面增长，栈顶指针指向栈顶元素。
#define maxsize
// 两个栈共享顺序存储空间所能达到的最多元素数
#define elemtp int
//假设元素类型为整型
typedef struct{
elemtp stack[maxsize];
int top [2];
//top为两个栈顶指针
//s是如上定义的结构类型变量，为全局变量
本题的关键在于，两个桟入栈和退栈时的栈顶指针的计算。s1栈是通常意义下的栈；而 s2栈入栈操作时，其栈顶指针左移（减1），退栈时，栈顶指针右移（加1）。
此外，对于所有栈的操作，都要注意&入栈判满、出栈判空&的检查。
1) 入栈操作
int push(int i, int x){
//入栈操作。i为栈号，i=0表示左边的s1栈，i=1表示右边的s2栈，x是入栈元素
//入栈成功返回1，否则返回0
if(i&0 || i&1){
printf (&栈号输入不对&);
if(s.top[1]-s.top[0]==1){
printf (&栈已满\n&);
switch(i){
case 0: s.stack[++s.top[0]] = return 1;
case 1: s.stack[--s.top[1]] = return 1;
2) 退栈操作
elemtp pop(int i) {
//退栈算法。i代表栈号，i=0时为s1栈，i=l时为s2栈
//退栈成功返回退栈元素，否则返回-1
if(i&0||i&1){
printf (&栈号输入错误\1n&);
switch(i) {
if (s.top[0]==-1) {
printf (&栈空\n&);
return -1;
return s.stack[s.top[0]--];
if(s.top[1]==maxsize){
printf (&栈空\n&);
return -1;
return s.stack[s.top[1]++];
推荐文章 TOP10商品名称：
评价得分：
此评价对我
此评价对我
此评价对我
此评价对我
此评价对我
多品类齐全，轻松购物
快多仓直发，极速配送
好正品行货，精致服务
省天天低价，畅选无忧和数据结构与算法分析――C语言描述相关的内容