CSP-J 近15年：栈、队列与链表真题专项（30题）

时间范围：2011～2025。

主要收录 NOIP 普及组初赛 / CSP-J 第一轮中与 栈、队列、链表 直接相关的真题。 第 30 题为 CSP-S 同知识点基础加餐题，已单独标注。

建议用时：35～45 分钟；满分 100 分。

1. 【2011 NOIP 普及组｜队列 / BFS】

进行广度优先搜索（BFS）时，通常需要借助哪一种数据结构？

{{ select(1) }}

• . 链表
• . 队列
• . 栈
• . 散列表

2. 【2011 NOIP 普及组｜链表 / 复杂度】

在一个含有 n 个元素的双向链表中查找给定关键字，最坏情况下的时间复杂度为（ ）。

{{ select(2) }}

• . O(1)
• . O(log n)
• . O(n)
• . O(n log n)

3. 【2012 NOIP 普及组｜队列概念】

下列哪一种线性表具有“先进先出”的访问特点？

{{ select(3) }}

• . 栈
• . 队列
• . 散列表
• . 二叉树

4. 【2012 NOIP 普及组｜栈 / 入栈顺序】

某时刻一个栈自底向上依次为 a、b、c，且元素 d 已经出栈。下列哪一个输入顺序可能产生这一状态？

{{ select(4) }}

• . a、d、c、b
• . b、a、c、d
• . a、c、b、d
• . d、a、b、c

5. 【2012 NOIP 普及组｜递归 / 栈】

递归函数调用层数过深时，最可能出现的情况是（ ）。

{{ select(5) }}

• . 系统分配的调用栈空间溢出
• . 系统分配的堆空间一定溢出
• . 队列空间一定溢出
• . 链表结点自动丢失

6. 【2013 NOIP 普及组｜栈概念】

【原题图示文字化】某数据结构只有一个开口，元素从同一端放入和取出；要取出底部元素，必须先移走其上方元素。该结构是（ ）。

{{ select(6) }}

• . 散列表
• . 栈
• . 队列
• . 二叉树

7. 【2014 NOIP 普及组｜链表特点】

下列哪一项不是链表通常具有的特点？

{{ select(7) }}

• . 不必事先固定整个线性表的存储空间
• . 可以像数组一样随机访问任一元素
• . 已知位置后插入、删除通常不需要整体移动元素
• . 所需结点空间随表长变化

8. 【2015 NOIP 普及组｜链表特点】

链表不具备下列哪一项能力？

{{ select(8) }}

• . 直接随机访问任意一个元素
• . 插入、删除时通常无需移动大量元素
• . 可以按需要动态申请结点
• . 存储空间随结点数量变化

9. 【2015 NOIP 普及组｜链式存储】

线性表采用链式存储结构时，各结点在内存中的地址关系可以是（ ）。

{{ select(9) }}

• . 必须全部连续
• . 只能部分连续
• . 必须全部不连续
• . 连续或不连续都可以

10. 【2015 NOIP 普及组｜栈 / 手动模拟】

有空栈 S，待处理数据依次为 a、b、c、d、e、f。依次执行“进栈、进栈、出栈、进栈、进栈、出栈”后，栈顶元素为（ ）。

{{ select(10) }}

• . f
• . c
• . a
• . b

11. 【2017 NOIP 普及组｜栈 / 后缀表达式】

表达式 a * (b + c) * d 的后缀形式是（ ）。

{{ select(11) }}

• . a b c d * + *
• . a b c + * d *
• . a * b c + * d
• . b + c * a * d

12. 【2017 NOIP 普及组｜链式栈 / 指针】

用链表实现栈，hs 指向当前栈顶结点，s 指向待插入的新结点。要把 s 压入栈顶，正确的关键操作是（ ）。

{{ select(12) }}

• . hs->next = s;
• . s->next = hs; hs = s;
• . s->next = hs->next; hs->next = s;
• . s->next = hs; hs = hs->next;

13. 【2017 NOIP 普及组｜栈 / 出栈序列】

元素按 a、b、c、d、e、f、g 的顺序入栈，下列哪一个序列不可能成为合法的出栈序列？

{{ select(13) }}

• . a、b、c、d、e、f、g
• . a、d、c、b、e、g、f
• . a、d、b、c、g、f、e
• . g、f、e、d、c、b、a

14. 【2018 NOIP 普及组｜栈概念】

【原题图示文字化】图中数据只能从同一个开口放入或取出，后放入的元素会挡住先放入的元素。该结构是（ ）。

{{ select(14) }}

• . 散列表
• . 栈
• . 队列
• . 二叉树

15. 【2018 NOIP 普及组｜双向链表完善程序①】

【真题母题拆分】在“右侧第一个更大值”的双向链表程序中，读入排列元素 x 时，需要记录值 x 出现的位置 i。空①应填（ ）。

{{ select(15) }}

• . a[x] = i
• . a[i] = x
• . L[x] = i
• . R[x] = i

16. 【2018 NOIP 普及组｜双向链表完善程序②】

【真题母题拆分】初始化双向链表时，若 L[i]=i-1，则右邻接数组 R[i] 应初始化为（ ）。

{{ select(16) }}

• . i - 1
• . i + 1
• . a[i]
• . n + 1

17. 【2018 NOIP 普及组｜双向链表完善程序③】

【真题母题拆分】删除结点 a[i] 时，要把其右侧结点的前驱改成 L[a[i]]。语句 L[ ____ ] = L[a[i]] 中应填（ ）。

{{ select(17) }}

• . a[i]
• . L[a[i]]
• . R[a[i]]
• . R[i]

18. 【2018 NOIP 普及组｜双向链表完善程序④】

【真题母题拆分】删除结点 a[i] 时，要把其左侧结点的后继改成被删结点原来的右邻居。R[L[a[i]]] = R[ ____ ] 中应填（ ）。

{{ select(18) }}

• . i
• . a[i]
• . L[a[i]]
• . R[a[i]]

19. 【2018 NOIP 普及组｜双向链表完善程序⑤】

【真题母题拆分】程序最终要输出每个位置右侧第一个仍保留的更大值位置，对应应输出（ ）。

{{ select(19) }}

• . a[i]
• . L[i]
• . L[a[i]]
• . R[i]

20. 【2019 CSP-J 第一轮｜链表特点】

下列哪一项不是链表通常具有的特点？

{{ select(20) }}

• . 插入、删除时通常不必整体移动元素
• . 可以按需申请结点
• . 所需空间随表长变化
• . 可以像数组一样随机访问任意元素

21. 【2020 CSP-J 第一轮｜链表特点】

链表通常不具备下列哪一项特点？

{{ select(21) }}

• . 随机访问任意元素
• . 不必预先固定全部结点空间
• . 插入删除时通常不用整体搬移元素
• . 空间需求随表长变化

22. 【2020 CSP-J 第一轮｜栈概念】

【原题图示文字化】某结构只有一个可操作端，数据只能从该端进入和离开。它最符合（ ）。

{{ select(22) }}

• . 栈
• . 队列
• . 二叉树
• . 散列表

23. 【2022 CSP-J 第一轮｜栈 / 出栈序列】

6 个元素按 6、5、4、3、2、1 的顺序进入栈 S，下列哪一个出栈序列是不合法的？

{{ select(23) }}

• . 5 4 3 6 1 2
• . 4 5 3 1 2 6
• . 3 4 6 5 2 1
• . 2 3 4 1 5 6

24. 【2022 CSP-J 第一轮｜数组与链表】

关于数组和链表的区别，下列说法正确的是（ ）。

{{ select(24) }}

• . 数组不能排序而链表可以
• . 链表一定能保存比数组更多的信息
• . 数组容量通常在定义时确定，而链表可动态增减结点
• . 以上都正确

25. 【2022 CSP-J 第一轮｜栈与队列】

下列关于数据结构的表述中，不恰当的是（ ）。

{{ select(25) }}

• . 深度优先搜索常与栈有关
• . 栈后进先出，队列先进先出
• . 广度优先搜索常使用队列
• . 栈和队列本质不同，因此不可能用栈模拟队列

26. 【2022 CSP-J 第一轮｜双向循环链表】

在双向循环链表中，p 指向某结点，s 为新结点。把 s 插到 p 后面，哪组操作正确？

{{ select(26) }}

• . p->next=s; s->prev=p;
• . s->next=p; s->prev=p->prev;
• . s->next=p->next; p->next=s; s->prev=p;
• . s->next=p->next; p->next->prev=s; s->prev=p; p->next=s;

27. 【2022 CSP-J 第一轮｜栈 + 队列综合模拟】

栈 S 与队列 Q 初始为空。e1～e6 每个元素都按“入栈 S→出栈 S→入队 Q→出队 Q”经历四步，不同元素的步骤可交错。若 S 的入栈次序为 e1,e2,...,e6，而 Q 的出队次序为 e2,e4,e3,e6,e5,e1，则 S 的最小容量是（ ）。

{{ select(27) }}

• . 2
• . 3
• . 4
• . 6

28. 【2023 CSP-J 第一轮｜链表头插】

已定义 struct Node { int data; Node* next; };，head 指向链表首结点。要新建 data=42 的结点并插到链表最前面，正确操作是（ ）。

{{ select(28) }}

• . newNode->data=42; newNode->next=head; head=newNode;
• . head->data=42; newNode->next=head; head=newNode;
• . newNode->data=42; head->next=newNode;
• . newNode->data=42; newNode->next=head;

29. 【2025 CSP-J 第一轮｜栈 + 队列综合模拟】

栈 S 与队列 P 初始为空，依次处理 7、5、8、3、1、4、2：遇奇数压入 S；遇偶数且 S 非空，则弹出栈顶并加入 P 队尾。全部处理后，P 从队首到队尾为（ ）。

{{ select(29) }}

• . 5、1、3
• . 7、5、3
• . 3、1、5
• . 5、1、3、7

30. 【2024 CSP-S 第一轮（加餐）｜队列概念】

【加餐：同知识点提高组真题】下列哪一种数据结构最适合直接实现 FIFO（先进先出）功能？

{{ select(30) }}

• . 栈
• . 队列
• . 普通二叉搜索树
• . 只能使用数组，不能使用线性表