CSP 初赛 · 链表专题选择题（10 题）

1. 在单链表中，指针 p 指向某结点，要在 p 之后插入新结点 s，正确的操作是？

{{ select(1) }}

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

2. 单链表中，已知指针 p，删除 p 的后继结点，时间复杂度是？

{{ select(2) }}

• O(n)
• O(log n)
• O(1)
• O(n^2)

3. 相比数组（顺序表），链表最主要的缺点是？

{{ select(3) }}

• 不支持随机访问（无法按下标 O(1) 取第 k 个元素）
• 插入、删除更慢
• 不能存储整数
• 占用内存一定更少

4. 需要频繁在序列中间插入 / 删除元素，且很少按下标随机访问，最适合用？

{{ select(4) }}

• 顺序表（数组）
• 栈
• 链表
• 哈希表

5. 下列关于循环链表的说法，正确的是？

{{ select(5) }}

• 最后一个结点的指针域指向头结点，首尾相连
• 只能从头结点访问一趟就结束
• 无法用于约瑟夫（报数出圈）问题
• 必须是双向的

6. 双向链表的每个结点通常包含？

{{ select(6) }}

• 一个数据域和一个指针域
• 两个数据域
• 只有指针域，没有数据域
• 一个数据域和两个指针域（分别指向前驱和后继）

7. 用数组模拟链表（静态链表）时，nxt[i] 通常表示？

{{ select(7) }}

• 第 i 个结点的值
• 第 i 个结点的后继（下一个结点）的下标
• 第 i 个结点的前驱下标
• 链表的长度

8. 约瑟夫（n 人围圈报数、报到 m 的人出圈）问题，最贴切的数据结构是？

{{ select(8) }}

• 二叉树
• 栈
• 有序数组
• 循环链表

9. 用"头插法"依次插入 1, 2, 3, 4 建立单链表，从表头开始遍历输出的顺序是？

{{ select(9) }}

• 1 2 3 4
• 1 3 2 4
• 4 3 2 1
• 2 4 1 3

10. 关于顺序表与链表的"存储密度"（有效数据占总存储的比例），正确的是？

{{ select(10) }}

• 链表因需额外存储指针，存储密度通常低于顺序表
• 链表的存储密度更高
• 两者的存储密度总是相等
• 顺序表无法计算存储密度