近4年CSP-J初赛考察：

	题号	题型	分值
2020	第1、7题	单项选择	4分
2021	第5题		2分
2022	第2、4、5、10、11题		10分

难易度：中等

2024备考建议

最爱考的线性数据结构题型：

1.栈的先进后出，队列的先进先出特性。

2.出入栈合法性判断，举例：入栈序列为 xxx 非法的出栈序列是 ？

3.前缀和后缀表达式求值，举例：求前缀表达式 + 2 * 4 5 的值。

4.链表和数组的增删改查特性。

栈

栈是一种限定只能在表的​一端​（栈顶）进行插入和删除操作的线性表，是一种“​先进后出​”的结构，即最后添加的数据最先被取出。在计算机领域，通常用于临时存储数据。

栈的操作

入栈：在栈顶一端进行插入元素的操作，若栈中元素数量已达上限，执行入栈则会出现​上溢​；

出栈：在栈顶一端进行删除元素的操作，若栈中不含任何元素，执行出栈则会出现​下溢​。

int arr[SIZE];
int top = 0;
arr[++top] = 5;	//进栈，top指向栈顶，0表示栈底
top--;	//出栈

STL中的栈

STL 中的 stack 容器提供了一众成员函数以供调用，其中较为常用的有：

• 元素访问
  • st.top() 返回栈顶
• 修改
  • st.push() 插入传入的参数到栈顶
  • st.pop() 弹出栈顶
• 容量
  • st.empty() 返回是否为空，若为空则返回true，否则返回false
  • st.size() 返回元素数量

#include<stack>			//使用stack需要对应的头文件
stack<int> st1, st2;	//新建两个栈st1,st2
st1.push(1);	//st1入栈1
st2 = st1;				//stack可以进行整体赋值，将st1赋值给st2
st1.pop();				//st1出栈
cout << st1.size();		//输出st1的元素数量
cout << st2.top();		//输出st2的栈顶元素

单选题

1、元素R1、R2、R3、R4、R5入栈的顺序为R1、R2、R3、R4、R5。如果第1个出栈的是R3，那么第5个出栈的不可能是（ ）。

A. R1​

B. R2​

C. R4​

D. R5​

2、今有一空栈 S，对下列待进栈的数据元素序列 a，b，c，d，e，f 依次进行进栈，进栈，出栈，进栈， 进栈，出栈的操作，则此操作完成后，栈 S 的栈顶元素为()。

A. f

B. c

C. a

D. b

3、对于入栈顺序为 a,b,c,d,e,f,g的序列，下列（ ）不可能是合法的出栈序列。

A. a,b,c,d,e,f,g

B. a,d,c,b,e,g,f

C. a,d,b,c,g,f,e

D. g,f,e,d,c,b,a

4、如果一个栈初始时为空，且当前栈中的元素从栈底到栈顶依次为a,b,c，另有元素d已经出栈，则可能的入栈顺序是（ ）。

A. a,d,c,b

B. b,a,c,d

C. a,c,b,d

D. d,a,b,c

栈的应用：表达式求值

前缀表达式求值

假设前缀表达式为：+ * 2 3 4

首先从右往左扫描表达式，遇到4,3,2, 将它们入栈，此时栈顶元素为2，次顶元素为3。

扫描到 * 号，栈顶 2 和次顶 3 出栈做乘法，将结果 6 入栈。

接下来继续往左扫描表达式，遇到 2 入栈，最后遇到 + 号，将栈顶 6 和次顶 4 相加，结果 10 入栈。

因此，前缀表达式+ * 2 3 4的值为10。

后缀表达式求值

假设后缀表达式为：2 3 * 4 +

从左往右扫描表达式，遇到2和 3 , 将它们入栈，遇到 * 号， 将栈顶和次顶元素出栈，并计算得到 6， 入栈。

接下来继续往右扫描表达式，遇到 4 入栈，遇到 + 号，将栈顶和次顶元素出栈，计算得到10。

因此，后缀表达式2 3 * 4 +的值为10。

单选题

1、表达式a*(b+c)*d 的后缀表达式为（ ），其中“*”和“+”是运算符。

A.**a+bcd

B.abc+*d*

C.abc+d**

D.*a*+bcd

2、表达式 a+(b-c)*d 的前缀表达式为（ ），其中+、-、*是运算符。

• A *+a-bcd
• B +a*-bcd
• C abc-d*+
• D abc-+d