2024年王道考研数据结构——栈

3.1栈

(一)选择题：

本部分内容仅选本人觉得有点意思的题目。

1，栈和队列有相同的()

1,抽象数据类型 2,逻辑结构 3,存储结构 4,运算

抽象数据类型：抽象数据组织及与之相关的操作

逻辑结构：分为线性结构和非线性结构

存储结构：顺序存储，链式存储，索引存储，散列存储

2，栈是限制存取点的线性结构

3，表示入栈操作的是

a[top++] = x;相当于a[top] = x; top++;

a[++top] =x;相当于top++,a[top] =x;

a[top–] = x;相当于a[top] = x; top–;

a[–top] = x;相当于top–,a[top] =x;

4，设链表不带头结点且所有操作均在表头进行，则下列不适合做链栈的是：3

1，只有表头结点指针，没有表尾指针的双向循环链表//双向，所以操作很方便

2，只有表尾结点指针，没有表头指针的双向循环链表//双向，所以操作很方便

3，只有表头结点指针，没有表尾指针的单向循环链表//要找到尾结点操作头结点，需要遍历一遍。

4，只有表尾结点指针，没有表头指针的单向循环链表//有表尾的单向循环，直接操作的就是表头。

5，3个不同的元素依次进栈，能得到x种不同的出栈序列。

x = $\frac{1}{n+1}$ * (C2n,n) -->$\frac{1}{4}$ *C(6,3)

C(n,m) =$\frac{n!}{m!(n-m)!}$ -->C(6,3) = $\frac{6\ast 5\ast 4\ast 3\ast 2\ast 1}{3\ast 2\ast 1\ast (3\ast 2\ast 1)}$ = 20

x = $\frac{1}{4}$ * 20 = 5;

6，一个栈的输入序列是P1,P2,P3…Pn,输出序列是1,2,3…n,若P3 = 1 则P1的值是：B

A:可能是2 B:不可能是2 C:一定是2 D:不可能是3

因为输出的序列是1,2,3…n , 因为输出的序列第一个是1，而且P3是1，则第一个弹出的是P3则此时的P1,P2都还在栈里面，而后第二个输出的就是2，栈里面只有P2才会在下一个位置弹出，或者P4压入以后弹出P4，所以2只会使P2或者P4。P1百分之一万是不可能是2的，所以选 “不可能是2”。

7，若一个栈的入栈序列是1,2,3,4其出栈序列为P1,P2,P3,P4,则P2,P4不可能是:C

A: 2 ,4 | B: 2 , 1 | C: 4 , 3 | D: 3 , 4

假设P2是4 ，则P1会使1,2,3中任意一个

设P1是1，则P3一定是3 P4一定是2

设P1是2，则P3一定是3 P4一定是1

设P1是3，则P3一定是2 P4一定是1

P4必不可能是3所以选C

8，采用共享栈的好处是

节省存储空间，降低发生上溢的可能

9，一个栈的入栈序列为1,2,3…n，出栈序列是P1,P2,P3…Pn,若P2=3，则P3的可能取值的个数是：

∵P2 = 3

∴但是P1弹出过一次，可能是1也可能是2

∴栈里剩余的一个数有可能是1也可能是2

∴P3有可能是1||2

∵后续插入的数据也可以随时弹出

∴P3也可能是后续中的任意一个数

∴P3除了不可能是3以外任何一个数都是有可能的

∴答案是 n - 1;

10，下列关于栈的叙述中错误的是

①，采用非递归方式重写递归程序时必须使用栈//斐波那契数列的递归程序改写成非递归程序时只需要一个循环就行了，不用栈。

②，函数调用时，系统要用栈保存必要的信息

③，只要确定了入栈顺序就能确定出栈顺序//出栈只能出栈顶元素，但是出栈可以在任何时候出栈，所以出栈的顺序有很多可能。

④，栈是一种受限的线性表，允许在其两端进行操作//栈只能在一端上操作

(二)应用综合题

1，有5个元素，其次入栈的次序为A,B,C,D,E,在各种可能的出栈次序中，第一个出栈元素为C且第二个出栈为D的出栈序列有哪几个。

因为固定第一个是C第二个是D

此时栈里还有A和B

第三个可能是E也可能是B

所以有这些可能

CDEBA , CDBEA , CDBAE

总共三种

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

① B,C,A,E,D 是有可能的

因为A入B入B出 B

C入C出 BC

A出 BCA

D入E入E出 BCAE

D出 BCAED

②D,B,A,C,E是不可能的

A入B入C入D入D出 D

此时栈顶为C所以要出栈只能是C 或者E入E出但是不可能是B

所以这个序列是不可能的

3，假设以I和O分别表示入栈和出栈操作，栈的初态和终态均为空，入栈和出栈的操作序列可表示为仅由I和O组成的序列，可以操作的序列称为合法序列，否则称为非法序列。

(一)下面哪些操作是合法的？

A,IOIIOIOO B,IOOIOIIO C,IIIOIOIO D,IIIOOIOO

A 合法

B 不合法//因为出的时候为空，空栈出不了栈，所以不合法

C 不合法//因为入了五个出了三个，最后栈里面还剩有两个元素，所以栈的终态不是空栈，所以不合法

D 合法

(二)通过对(一)的分析，写出一个算法，判定所给的操作序列是否合法。若合法，返回true否则返回false

 bool solve(char s[],int len)
 {
 	int ans = 0;
 	for(int i=0;i<len;i++)
 	{
 		if(s[i]=='I')ans++;
 		else ans--;
 		if(ans<0)return false;
	 }
	 if(ans) return false;//判断终态是否为空
	 return true;
 }
1
2
3
4
5
6
7
8
9
10
11
12

4，一个字符单链表，设计算法，判断字符链表是否中心对称

思路，前一半先入栈，然后一边往后遍历一遍出栈判断是否相同。

bool solve(char s[],int len)
 {
	int midd = len/2 ;
	sqstack s1;
	init_stack(s1);
	int i =0;
	while(midd--)//先将前面的一般入栈，我这里用数组模拟单链表
	{
		push_s(s1,s[i]);
		i++;
	}
	if(len%2 == 1)i++;//如果是奇数个元素，则最中间的元素不用考虑、
	while(i<len)//一边出栈，一边和后面一半比较，不同就返回false。
	{
	int x ;
	pop_s(s1,x);	
	if(x == s[i])i++;
	else return false;
	} 
	return true;//判断完了还没返回说明是回文串，所以返回true;
 
 }
时间复杂度O(n)空间复杂度O(n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

5，写一个共享栈以及其入栈出栈的代码

typedef struct stack{
	int data[Maxsize]; 
	int top1,top2;//top1表示左端开始，top2表示右端开始
} sqstack;

void init_stack(sqstack &s)
{
	s.top= -1;
	s.top2 = Maxsize;//初始化两端
}

1
2
3
4
5
6
7
8
9
10
11

入栈操作

bool push_s(sqstack &s , int x,int id)
{
	if(id!=0&&id!=1)return false;//id = 0压左边 id = 1压右边
	if(s.top1 == s.top2-1) return false;//判断是不是已经满了
	if(id == 0)
	{
		s.data[++s.top1] = x;
	}
	else
		s.data[--s.top2] = x;
	return true;
}
1
2
3
4
5
6
7
8
9
10
11
12

出栈操作

bool pop_s(sqstack &s , int &x,int id)
{
	if(id!=0&&id!=1)return false;
	//这个判空需要跟开判定
	if(id == 0 )
	{
	if(s.top1 == -1)return false;
	x = s.data[s.top1--];	
	}
	else
	{
	if(s.top2 == Maxsize)return false;
	x = s.data[s.top2++];
	}
	return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16