NOIP2026初赛数据结构基础栈队列链表练习题

NOIP2026初赛数据结构基础（栈/队列/链表）练习题栈、队列与链表练习题（NOIP2026初赛模拟）第一部分：栈基础应用（共3题，每题10分）1.题目：括号匹配问题背景描述：在编程语言中，括号的正确匹配是语法正确性的重要保证。例如，在表达式`3+(2-[1(4/2)])`中，括号的嵌套和配对必须严格正确。设计一个栈结构，判断给定字符串中的括号（包括圆括号`()`,方括号`[]`,和花括号`{}`）是否匹配。输入描述：一个由括号、数字和运算符组成的字符串，长度不超过1000。仅包含字符`0-9`,`+`,`-`,``,`/`,`(`,`)`,`[`,`]`,`{`,`}`。输出描述：输出`YES`如果括号匹配正确，否则输出`NO`。示例输入：`3+(2-[1(4/2)])`示例输出：`YES`提示：-使用栈存储未匹配的左括号。-遇到右括号时，检查栈顶是否为对应的左括号，若匹配则弹出栈顶，否则不匹配。-字符串遍历结束后，栈应为空。2.题目：逆波兰表达式求值背景描述：逆波兰表达式（后缀表达式）是一种不需要括号的算术表达式，其中运算符位于其操作数之后。例如，表达式`34+`等同于`3+4`。使用栈结构计算给定逆波兰表达式的值。输入描述：一个逆波兰表达式，由数字和运算符`+`,`-`,``,`/`组成，每个元素间以空格分隔。数字为整数，范围在`-1000`到`1000`之间。输出描述：计算并输出表达式的值（结果为整数）。示例输入：`34+5`示例输出：`35`提示：-遍历表达式，遇到数字时压入栈中。-遇到运算符时，弹出栈顶两个数字进行计算，并将结果压回栈中。-最终栈顶元素为表达式的值。3.题目：浏览器历史记录模拟背景描述：浏览器的后退功能利用栈结构管理历史记录。用户每次访问新页面时，当前页面压入栈；点击后退按钮时，当前页面出栈。设计栈结构模拟此过程。输入描述：一个操作序列，由`VISIT`和`BACK`组成。`VISIT`后跟一个页面名称（字符串），`BACK`表示点击后退按钮。操作序列不超过200条。输出描述：按顺序输出每次操作后的当前页面名称。如果`BACK`操作时栈为空，输出`None`。示例输入：`VISITA\nBACK\nVISITB\nBACK\nBACK`示例输出：`A\nA\nB\nNone`提示：-使用栈存储当前访问的历史记录。-`VISIT`操作将页面压入栈。-`BACK`操作弹出栈顶页面，若栈为空则输出`None`。第二部分：队列基础应用（共3题，每题10分）4.题目：排队模拟背景描述：银行排队系统使用队列结构管理客户。客户按到达顺序进入队列，柜员按顺序服务客户。设计队列结构模拟此过程。输入描述：一个操作序列，由`ENQUEUE`和`DEQUEUE`组成。`ENQUEUE`后跟一个客户ID（正整数），`DEQUEUE`表示服务一个客户。操作序列不超过200条。输出描述：按顺序输出每次`DEQUEUE`操作服务的客户ID。如果`DEQUEUE`操作时队列为空，输出`None`。示例输入：`ENQUEUE1\nDEQUEUE\nENQUEUE2\nDEQUEUE\nDEQUEUE`示例输出：`1\n2\nNone`提示：-使用队列存储客户ID。-`ENQUEUE`操作将ID加入队尾。-`DEQUEUE`操作移除队首ID，若队列为空则输出`None`。5.题目：循环队列实现背景描述：循环队列是队列的一种高效实现，利用固定长度的数组，通过头尾指针模运算实现队列的循环。设计循环队列解决以下问题。输入描述：一个操作序列，包含`ENQUEUE`,`DEQUEUE`,`FRONT`,`REAR`。`ENQUEUE`后跟一个元素，`DEQUEUE`移除队首，`FRONT`查看队首元素，`REAR`查看队尾元素。操作序列不超过200条。输出描述：按顺序输出每次`FRONT`,`REAR`操作的结果。如果队列为空且`FRONT`操作，输出`None`。示例输入：`ENQUEUE1\nENQUEUE2\nFRONT\nDEQUEUE\nREAR`示例输出：`1\n2`提示：-使用固定长度的数组（如长度为10）实现循环队列。-维护头尾指针`front`和`rear`，计算模长时考虑队空或队满情况。-队列为空时，`front==rear`；队满时，`(rear+1)%size==front`。6.题目：任务调度队列背景描述：操作系统使用队列调度任务。假设有多个任务按到达顺序进入队列，每次调度器选择队首任务执行。设计队列结构模拟任务调度。输入描述：一个操作序列，由`ARRIVE`和`SCHEDULE`组成。`ARRIVE`后跟任务ID（正整数），`SCHEDULE`表示调度一个任务。操作序列不超过200条。输出描述：按顺序输出每次`SCHEDULE`调度的任务ID。如果`SCHEDULE`操作时队列为空，输出`None`。示例输入：`ARRIVE1\nARRIVE2\nSCHEDULE\nSCHEDULE\nSCHEDULE`示例输出：`1\n2\nNone`提示：-使用队列存储任务ID。-`ARRIVE`操作将ID加入队尾。-`SCHEDULE`操作移除队首ID，若队列为空则输出`None`。第三部分：链表基础应用（共3题，每题10分）7.题目：单链表反转背景描述：单链表反转是链表操作的基本问题。给定一个单链表，设计算法将其反转。输入描述：一个由正整数组成的链表，用空格分隔。例如：`12345`。输出描述：输出反转后的链表，用空格分隔。例如：`54321`。示例输入：`12345`示例输出：`54321`提示：-使用三个指针`prev`,`current`,`next`实现反转。-初始时`prev=null`,`current=head`。-逐个节点反转指针方向，并移动指针。8.题目：链表合并背景描述：合并两个有序的单链表，使其依然有序。例如，合并`1->2->4`和`1->3->4`得到`1->1->2->3->4->4`。输入描述：两个由正整数组成的有序链表，用空格分隔。例如：-第一个链表：`124`-第二个链表：`134`输出描述：输出合并后的有序链表，用空格分隔。例如：`112344`示例输入：`124\n134`示例输出：`112344`提示：-使用两个指针分别遍历两个链表。-比较当前节点的值，将较小的节点加入新链表，并移动对应指针。-处理剩余节点。9.题目：链表删除重复节点背景描述：给定一个链表，删除所有重复的节点，保留唯一节点。例如，`1->2->3->3->2->1`删除后为`1->2->3`。输入描述：一个由正整数组成的链表，用空格分隔。例如：`123321`。输出描述：输出删除重复节点后的链表，用空格分隔。例如：`123`示例输入：`123321`示例输出：`123`提示：-使用哈希集合记录已出现的节点值。-遍历链表，若当前节点值在集合中，则删除该节点；否则加入集合。答案与解析第一部分：栈基础应用1.括号匹配问题-答案：使用栈存储未匹配的左括号。遍历字符串：-遇到`(`,`[`,`{`时压入栈。-遇到`)`,`]`,`}`时，检查栈是否为空：-若为空，不匹配。-否则，弹出栈顶并检查是否与当前右括号匹配。-字符串遍历结束后，栈应为空。-示例输入`3+(2-[1(4/2)])`匹配，输出`YES`。2.逆波兰表达式求值-答案：使用栈存储数字。遍历表达式：-遇到数字时压入栈。-遇到运算符时，弹出栈顶两个数字`a`和`b`（`b`在前），计算`aopb`，将结果压回栈。-最终栈顶为表达式值。-示例输入`34+5`计算过程：`34+=7`,`75=35`，输出`35`。3.浏览器历史记录模拟-答案：使用栈存储历史记录。遍历操作：-`VISIT`：将页面压入栈。-`BACK`：若栈非空，弹出栈顶；否则输出`None`。-示例输入`VISITA\nBACK\nVISITB\nBACK\nBACK`：-`VISITA`：栈`[A]`-`BACK`：弹出`A`，当前`A`-`VISITB`：栈`[A,B]`-`BACK`：弹出`B`，当前`A`-`BACK`：栈为空，输出`None`。第二部分：队列基础应用4.排队模拟-答案：使用队列存储客户ID。遍历操作：-`ENQUEUE`：将ID加入队尾。-`DEQUEUE`：若队列非空，移除队首；否则输出`None`。-示例输入`ENQUEUE1\nDEQUEUE\nENQUEUE2\nDEQUEUE\nDEQUEUE`：-`ENQUEUE1`：队列`[1]`-`DEQUEUE`：移除`1`，当前`[]`-`ENQUEUE2`：队列`[2]`-`DEQUEUE`：移除`2`，当前`[]`-`DEQUEUE`：输出`None`。5.循环队列实现-答案：使用数组`queue[0..9]`，头指针`front=0`，尾指针`rear=0`，长度`size=10`。操作：-`ENQUEUEx`：`queue[rear]=x`,`rear=(rear+1)%size`-`DEQUEUE`：`front=(front+1)%size`-`FRONT`：`queue[front]`（若`front==rear`则为空）-`REAR`：`queue[(rear-1+size)%size]`-示例输入`ENQUEUE1\nENQUEUE2\nFRONT\nDEQUEUE\nREAR`：-`ENQUEUE1`：`rear=1`,`queue=[0,1,0,0,0,0,0,0,0,0]`-`ENQUEUE2`：`rear=2`,`queue=[0,1,2,0,0,0,0,0,0,0]`-`FRONT`：`queue[0]=1`-`DEQUEUE`：`front=1`,`queue=[0,0,2,0,0,0,0,0,0,0]`-`REAR`：`queue[1]=2`6.任务调度队列-答案：与第4题类似，使用队列存储任务ID。遍历操作：-`ARRIVEx`：将`x`加入队尾。-`SCHEDULE`：若队列非空，移除队首；否则输出`None`。-示例输入`ARRIVE1\nARRIVE2\nSCHEDULE\nSCHEDULE\nSCHEDULE`：-`ARRIVE1`：队列`[1]`-`SCHEDULE`：移除`1`，当前`[]`-`ARRIVE2`：队列`[2]`-`SCHEDULE`：移除`2`，当前`[]`-`SCHEDULE`：输出`None`。第三部分：链表基础应用7.单链表反转-答案：使用三个指针`prev=null`,`current=head`,`next=null`。操作：-`next=current.next`,`current.next=prev`,`prev=current`,`current=next`-重复直到`current=null`。-示例输入`12345`：-反转后为`54321`。8.链表合并-答案：使用两个指针`p`和`q`分别遍历两个链表。操作：